| Autor | Zpráva | ||
|---|---|---|---|
| standik Profil * |
#1 · Zasláno: 5. 3. 2010, 14:17:17
Dobrý den,
mám úkol vytvořit funkci na ověření čísla zda je prvočislo či ne. V hodině jsem chyběl a tak nevím co s tím. Nevím kde mám chybu.
<?php
function je_prvocislo($x) {
$pocet = 0;
for ($y = 1; $y < $x; $y++) {
$podil = $x % $y;
if ($podil == 0) {
$pocet = $pocet + 1;} }
if ($pocet > 2) {
return false;
} else {
return true; }
}
echo je_prvocislo(4)
?>Byl bych moc rád kdyby jste mi opravili moje řešení a nepsali mi tu kody sice asi programátorsky víc na úrovni, ale zcela nepochopitelně pro mě :-) děkuju |
||
| Alphard Profil |
#2 · Zasláno: 5. 3. 2010, 14:29:43
standik:
Na první pohled by tam mělo být if ($pocet >= 2) Přesto sem dám jiný script a pokuste se ho pochopit, ten váš je zbytečně složitý. Ptejte se, co vás zajímá. function jePrvocislo($cislo)
{
$limit = ceil(sqrt((int)$cislo));
for($delitel = 2; $delitel <= $limit; $delitel++)
{
if(($cislo % $delitel) === 0)
{
return false;
}
}
return true;
}Jen rovnou vysvětlím, že stačí testovat do odmocniny daného čísla, větší dělitel už být nemůže. To u velkých čísel ušetří hodně prostředků. |
||
| standik Profil * |
#3 · Zasláno: 5. 3. 2010, 14:41:07
Dobrý den,
chápu to do řádku č.2 :-) Teď vážně ... řádek č.3 mi to zkracuje abych neinkrementoval az k hodnote toho cisla ale pouze k jeho odmocnině... protože pokud bych měl velké číslo muselo by PHPčko počítat jako šílený :-) a to "===" je co? vím že jedno = je "přiřaď", dvě == jsou "rovná se", ale co jsou tři jsme se neučili :-) Ale v podstatě jsem to neměl až tak špatně, ne? |
||
| _es Profil |
#4 · Zasláno: 5. 3. 2010, 14:41:12
Alphard:
Stačí overovať ešte o zväčša jedno číslo menej v treťom riadku: $limit = floor(sqrt((int)$cislo)); |
||
| Alphard Profil |
#5 · Zasláno: 5. 3. 2010, 14:51:10
standik:
„a to "===" je co?“ Porovnání identity, zatímco == porovnává jen hodnoty, === porovnává i datový typ. Tzn. že platí 0 == false, ale neplatí 0 === false. Tady to ale není nezbytné. „Ale v podstatě jsem to neměl až tak špatně, ne?“ Ne, hlavní zbytečnost vidím v tom, že začínáte s $y = 1 a pak se musíte zabývat počtem shod. Když dáte $y = 2, tak při prvním nálezu zbytku 0 můžete vrátit false. _es: „Stačí overovať ešte o zväčša jedno číslo menej v treťom riadku:“ Po krátkém matematickém zamyšlení, ano, stačí. Ale tím už se moc neušetří. |
||
| Joker Profil |
#6 · Zasláno: 5. 3. 2010, 14:52:02
standik:
„a to "===" je co?“ Když vidíte neznámý operátor, máme tu manuál. === je operátor identity (něco jako "striktní ==", platí když oba parametry mají přesně stejnou hodnotu stejného typu- tj. například 0=="" platí, ale 0==="" neplatí) „Ale v podstatě jsem to neměl až tak špatně, ne?“ Mno, až na jednu chybu správně, ovšem použitý algoritmus nebyl moc efektivní. Minimálně jedna věc, že jedničkou je přece dělitelné jakékoliv číslo, takže to se nemusí testovat. A potom se to celé zjednoduší tím, že první nalezený dělitel znamená, že to není prvočíslo a může se rovnou skončit (nemusím už zkoušet další čísla). |
||
| standik Profil * |
#7 · Zasláno: 5. 3. 2010, 15:06:39
Dobrý den,
moc si vážím vaši pomoci a vysvětlení... Mnohokrát vám děkuji |
||
| Keeehi Profil |
#8 · Zasláno: 5. 3. 2010, 15:56:42 · Upravil/a: Keeehi
Já bych tu funkci ještě trochu upravil. Je pravda, že kód je o trochu delší, avšak při velkých číslech by měla být ještě rychlejší.
function jePrvocislo($cislo)
{
if($cislo == 1)
return false;
if($cislo == 2 or $cislo == 3)
return true;
if(($cislo % 2) == 0)
return false;
$limit = ceil(sqrt((int)$cislo));
for($delitel = 3; $delitel <= $limit; $delitel+=2)
{
if(($cislo % $delitel) == 0)
{
return false;
}
}
return true;
} |
||
| Timy Profil |
#9 · Zasláno: 5. 3. 2010, 16:08:23 · Upravil/a: Timy
Všichni špatně, jednička není prvočíslo a dvojka je prvočíslo ;-). Na té wiki je pak dole funkce v Céčku, která bude asi správná a celkem efektivní.
|
||
| _es Profil |
#10 · Zasláno: 5. 3. 2010, 16:16:22
Timy:
No tak chýba kontrola vstupu, Alphardova funkcia funguje na všetky celé kladné čísla väčšie alebo rovné 2, no až keď opraví ten jeden riadok. Keeehi to s tým vylepšením algoritmu trochu prehnal. |
||
| Keeehi Profil |
#11 · Zasláno: 5. 3. 2010, 16:34:30
_es:
Můžu se zeptat, jak jsem to přehnal? Je možné, že tam byla chyba, netestoval jsem to. Ale to co jsem měl na mysli bylo snad jasné stačí zkusit dělitelnost dvojkou a pak už jen lichým čísly. (Ve skutečnosti stačí zkoušet dělitelnost jen prvočísly) |
||
| Timy Profil |
#12 · Zasláno: 5. 3. 2010, 16:44:51
_es:
Cože to? Jaká kontrola vstupu? Jednička a dvojka je regulérní vstup do této funkce, nic mimo definiční obor funkce, funkce pouze tento vstup špatně vyhodnotí. A pro dvojku to taky nefunguje správně, když mi vrací false. A Keeehiho vylepšení je naprosto správné, není potřeba projíždět všechna sudá čísla, když žádné další sudé číslo krom dvojky už nemůže být prvočíslo, takže inkrementace o dva přes všechna lichá dává smysl. |
||
| _es Profil |
#13 · Zasláno: 5. 3. 2010, 17:31:05 · Upravil/a: _es
Timy:
„Jaká kontrola vstupu? Jednička a dvojka je regulérní vstup do této funkce, nic mimo definiční obor funkce,“ Na dvojku dá Alphardova funkcia správny výstup, ak sa opraví ten jeden riadok, ktorý ešte navyše väčšinou funkciu skráti o jeden výpočet. Aký je definičný obor tej funkcie? Ak sa zadefinuje definičný obor tejto funkcie ako celé kladné čísla väčšie alebo rovné dvom, tak pre tento definičný obor dá tá funkcia správne výsledky. Inak by tá funkcia musela overovať: či je to číslo, či je to celé číslo, či je to kladné číslo... Keeehi:„Můžu se zeptat, jak jsem to přehnal?“ Timy:„A Keeehiho vylepšení je naprosto správné,“ Bolo to prehnané tým, že tým vylepšením vznikli nové chyby, ktoré si musel následne zložito ošetrovať, takže pre menšie čísla je vlastne neefektívna. Prečo je úplne každé číslo vždy overované na rovnosť jednej? Ten algoritmus sa dá vylepšiť trochu priamočiarejšie, bez nejakých výnimiek pre dvojku, trojku a pod. Napríklad po otestovaní 2, 3, 5, 7 stačí postupne skúšať čísla s inkrementom 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, ... (čísla 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, ...) Podobne by to šlo pre vylúčenia čísel deliteľných 2, 3, 5, 7. A funkcia by bola kompaktná, bez nejakých ťažšie zrozumiteľných výnimiek. |
||
| Timy Profil |
#14 · Zasláno: 5. 3. 2010, 17:43:07 · Upravil/a: Timy
_es:
„Aký je definičný obor tej funkcie?“ Prvočíslo je přirozené číslo, které je beze zbytku dělitelné právě dvěma různými přirozenými čísly, a to číslem jedna a sebou samým (tedy 1 není prvočíslo). ~ Wikipedie Definičním oborem budiž Přirozená čísla a jednička a dvojka je přirozené číslo. Pro tento obor to musí rozhodně fungovat správně, co by to mělo vyhodit na třeba záporných číslech je otázka, ale málokdo asi očekává, že když do funkce pro ověření prvočíselnosti hodíš jedničku nebo dvojku, že ti vrátí špatný výsledek... „Ak sa zadefinuje definičný obor tejto funkcie ako celé kladné čísla väčšie alebo rovné dvom, tak pre tento definičný obor dá tá funkcia správne výsledky.“ Jo a když se zadefinuje definiční obor jako všechna prvočísla, tak pak můžeme tu funkci mít jen takhle: function jePrvocislo($cislo){
return true;
} |
||
| _es Profil |
#15 · Zasláno: 5. 3. 2010, 17:52:43 · Upravil/a: _es
Timy:
„Prvočíslo je přirozené číslo“ Prvočislo je aj celé číslo, racionálne číslo, reálne číslo, komplexné číslo. Z toho predsa nijako nevyplýva, že je nutné, aby tá funkcia mala definičný obor práve a len prirodzené čísla. Problematická je ešte nula, v nejakej literatúre je nula považovaná za prirodzené číslo, v inej tam zase nepatrí. Keď si dal ten odkaz na wikipédiu, tak tam je dobrá jednoduchá funkcia v C++ a stačí ju len prepísať do syntaxe PHP. |
||
| Timy Profil |
#16 · Zasláno: 5. 3. 2010, 18:11:21
_es:
„Z toho predsa nijako nevyplýva, že je nutné, aby tá funkcia mala definičný obor práve a len prirodzené čísla.“ Klidně můžeme mít definiční obor komplexní čísla. Pak ta funkce nebude fungovat o to víc :-)). Přirozená čísla se mi jeví jako nejlogičtější DO, už třeba jen z toho principu, že dělitelnost není na komplexních číslech definována... Zkrátka a jednoduše, pro jedničku a dvojku musí ta funkce normálně fungovat. Na -54, 5,58, 45+8i nebo řetězec "Eratosthenovo síto" ať si to klidně vyhazuje výjimku, že je to neplatný vstup nebo ať to zpracuje nějak jinak, ale 1 a 2 je naprosto validní vstup. „Keď si dal ten odkaz na wikipédiu, tak tam je dobrá jednoduchá funkcia v C++ a stačí ju len prepísať do syntaxe PHP.“ Ano, to jsem zmiňoval výše. Je prakticky stejná, jako ta Keeehiho funkce. |
||
| _es Profil |
#17 · Zasláno: 5. 3. 2010, 18:22:22
Timy:
„Je prakticky stejná, jako ta Keeehiho funkce.“ Nie, K.ho je horšia, je očividne neefektívna, napríklad každé číslo vždy overuje na rovnosť jednej a tipujem, že na záporné čísla nebude správne fungovať, na rozdiel od tej z wikipédie. „Přirozená čísla se mi jeví jako nejlogičtější DO, už třeba jen z toho principu, že dělitelnost není na komplexních číslech definována...“ V tej definícii prvočísla sa formulácia "prirodzené číslo" môže zmeniť na "celé číslo väčšie ako 1" a výsledok bude rovnaký. Deliteľnosť komplexných čísel nie je definovaná, no je definovaná podmnožina komplexných čísel "prirodzené čísla" a v nej je definovaná podmnožina "prvočísla". |
||
| Timy Profil |
#18 · Zasláno: 5. 3. 2010, 18:32:45
_es:
Dobře, polopatě a jednoduše: myslíš si, že je v pořádku, když funkce ověřující prvočíselnost vrátí TRUE na jedničku? |
||
| Alphard Profil |
#19 · Zasláno: 5. 3. 2010, 18:47:54 · Upravil/a: Alphard
A sakra, jdu se zahrabat :-) Na co jsem tehdá myslel...
Opravená verze: function jePrvocislo($cislo)
{
if(!is_int($cislo) || $cislo < 2) return false;
$limit = floor(sqrt((int)$cislo));
for($delitel = 2; $delitel <= $limit; $delitel++)
{
if(($cislo % $delitel) === 0)
{
return false;
}
}
return true;
}Vidí zde ještě někdo chybu? Mírně upraveno dle _es. |
||
| standik Profil * |
#20 · Zasláno: 5. 3. 2010, 19:54:42
Dobrý den,
mohl byste mi prosím vysvětlit co znamená řádek č.3 Predevším !is_int a || Děkuji |
||
| standik Profil * |
#21 · Zasláno: 5. 3. 2010, 19:57:30
Aha, už nemusíte. Díval jsem se do manuálu a pokud jsem to dobře přeložil, tak už asi vím :-)
|
||
| Keeehi Profil |
#22 · Zasláno: 5. 3. 2010, 20:32:16
_es:
Prvočíslo je číslo přirozené (kladné celé číslo wiki) které je beze zbytku dělitelné právě dvěma různými přirozenými čísly. wiki Takže jak to tedy s prvočísly vypadá? záporná celá čísla: False (nesplňují podmínku přirozených čísel) 0: False (nesplňuje podmínku přirozených čísel) 1: False (nesplňují podmínku, že je dělitelné dvěma růzými přirozenými čísly) 2: True 3: True 4: False (je dělitelné 2) 5: True a tak dále, tam už snad problémy nemáme, co je a co není prvočíslo desetinné číslo,imaginární číslo, a podobná verbež: False (nesplňují podmínku přirozených čísel) Teď už zbývá napsat funkci takovou, aby vracela tyto hodnoty. function jePrvocislo($cislo)
{
if($cislo != floor($cislo))
return false;
// tímto se vyloučila desetinná čísla
if($cislo < 2)
return false;
// tímto se vyloučila záporná čísla, 0 a 1
if($cislo <= 3)
return true;
// tuto podmínku splňují už jen pouze 2 a 3
if(($cislo % 2) == 0)
return false;
// vyloučíme sudá čísla (2 už byla zkontrolována dříve)
// už zbývají jenom čísla jako 5,7,9,11,13,15,17,19,...
$limit = floor(sqrt((int)$cislo));
for($delitel = 3; $delitel <= $limit; $delitel+=2)
{
if(($cislo % $delitel) == 0)
{
return false;
}
}
return true;
} |
||
| _es Profil |
#23 · Zasláno: 5. 3. 2010, 22:41:20
Alphard:
„Vidí zde ještě někdo chybu?“ Stále, bez dôvodu, zaokrúhľuješ tú druhú odmocninu nahor. Ak by si ju zaokrúhľoval nadol, nedávala by tá tvoja prvá funkcia zlý výsledok pre číslo 2. |
||
| Alphard Profil |
#24 · Zasláno: 5. 3. 2010, 23:08:13 · Upravil/a: Alphard
_es:
Dík, přiznám se, že jsem předtím jen kouknul na odkazovanou wiki a o jedné iteraci navíc jsem moc nepřemýšlel. V tomto kontextu (odstranění jedné podmínky) to už ale má význam a ruší to tak trochu nesystémový krok. Upravil jsem původní funkci [#19], ať to tady není kilometr dlouhé. Současný stav se mi docela líbí, ošetření vstupních podmínek a jednoduchý cyklus. „A Keeehiho vylepšení je naprosto správné, není potřeba projíždět všechna sudá čísla, když žádné další sudé číslo krom dvojky už nemůže být prvočíslo, takže inkrementace o dva přes všechna lichá dává smysl.“ To je otázka jednoduchosti a efektivnosti. Má verze bude pro začátečníka na první pohled asi přehlednější. |
||
| Timy Profil |
#25 · Zasláno: 5. 3. 2010, 23:33:04
Alphard:
„To je otázka jednoduchosti a efektivnosti. Má verze bude pro začátečníka na první asi přehlednější.“ Souhlasím :-). |
||
|
Časová prodleva: 14 let
|
|||
0