[NALOGA] največji skupni delitelj dveh celih števil

Napiši podprogram, ki poišče in vrne največji skupni delitelj dveh celih števil..
Potreboval bi pomoč

Zelo enostavn pristop:

1. kandidat za rešitev je manjše od obeh števil
2. preveri če trenuten kandidat deli večje število, če ga deli si našel NSD in končaj
3. kandidat := kandidat -1, izvedi 2. korak

koraka 2 in 3 izvajaj dokler je kandat večji od 1, če prideš do 1 brez da katerokoli od preizkušenih števil deli večje število končaš. Števili sta si tuji.

Kaj je to, tekmovanje za najbolj okorno rešitev?

 def gcd(a,b):
        while b:
            a,b = b, a % b
        return a

Enostavna razumljivost, nič ne rečem (čeprav se meni moja rešitev -- Evklidov algoritem -- ne zdi ravno kriptična), ampak ali sistematičnemo preiskovanje prostora rešitev (ki ima v "splošnem" vsaj par desettisoč elementov) res lahko okličemo za elegantno?

Preberi naslednje, http://en.wikipedia.org/wiki/Euclidean_algorithm, in mora biti vse kristalno jasno.

bravo MS; razkuri se, pa povej svoje

itaq da nihče "leet"a ne zastopi, ker je "unikatno" bitje v tej galaksiji

zaradi danih problemov, kreiramo rešitve, katere zahtevalo vedno več in več procesorske moči; zaradi tega smo včasih bitje "srca" šteli v mega, danes v giga, jutri verjetno v tera...

aja, turbo--, da ne bom zašel iz teme (pa ne mislim prostora brez luči), lahko ti napišem rešitev v jeziku, katerega ne razumeš; je pa v igri while in if; tako kot v tem velikonočnem času zajček in pisano jajce

Dragi Micro$oft. Lepo bi bilo, če bi se malce izobrazil na področju programskih jezikov.
BTW. Tisto je Python. Ne pa da povsod vlačiš "smrdljivi" C#

Microsoft
Kodo naslednjič opremi s st.koda tagi, kjer lahko uporabljaš tudi znak manjše.

Sam par pripomb:

Govoriti o učinkoviti rešitvi in delati rekurziven algoritem je protislovje.

Evklidov algoritem je najstarejši znan algoritem sploh. Programiranje pa ni le uporaba znanih receptov ampak tut razumevanje problema. Ko prvič vidiš evklida ti ni jasno nič.

Algoritmi se podajajo v psevdokodi. Zato, da se človek ne ubada z tehnikalijami jezika ampak da razmišlja o algoritmu samemu.

Če je owc-in program tipičen program v pythonu, pol lahk rečem le, da se programerska industrija iz napak c-ja ni naučila čisto nič. Njegov program je za neposvečenega TOTALNO nerazumljiv. Re-usanje iste variable za kontrolo zanke in samo naračunavanje je zelo leet, je pa zelo mim, kar se tiče dobrega programiranja.

Poleg tega pa, človek verjetno ne študira boljše rešitve znanih problemov, ampak se uči programirat. Tle je pa glavno analitično razmišljanje. Kjer največ pomaga psevdokoda.

Še enkrat:

Če človek ne zna napisat programa za gcd, je očitno še precej na začetku. Placa za izbolšave mu itak ne bo nikol zmanjkal. Naj pa najprej nardi neki kar bo delalo in bo tut razumel zakaj in kako dela. Pol se pa nej matra in stvar izboljšuje. Tut preko evklida, rekurcije, etc.

Maturitetni katalog za matematiko, 2001, stran 9 - Evklidov algoritem se zahteva za višji nivo iskanje največjega skupnega deljitelja pa tudi za osnovni nivo. Evklida pa smo učili pri pouku iz matematike učili vsi - gimnazija Velenje.

Pa OwcA ni podal rekurzivne rešitve.

Povejte, ko ste prvic dobili nalogo, da zracunate takole nalog, ste sigurno zaceli vsim tezit z nekim algoritmom, optimizacijo, rekurzijo, ...

Pravzaprav ja. To je prednost, če nisi čisto v vsem samouk. Tako kaj kmalu ugotovoiš, da za večino problemov že obstjajo razmeroma elegantni algoritmi in se k naivni rešitvi zatčeš šele, če ne najdeš nič boljšega, ne obratno.

Skratka, ne gre tako. Stvari gredo po vrsti. In ce prvo ne naredis z for zanko (ali cem podobnim), potem nikoli ne bos znal nic drugega, kot kopirat algiritme.

Odvisno od tega, kaj se učiš. Če govorimo o obrtniškem izdelovanju aplikacij, potem imaš verjetno prav. Imamo kladivo in vsak problem zbijemo na obliko žeblja.
Ampak to ni programiranje. Katero orodje (jezikovni konstrukt) uporabiš je zadnja skrb (čisti funkcijski jeziki niti nimajo zank), rešitev problema se nikoli ne skriva v vprašanju "a je to za for al za if?" ampak v razumevanju problema.

In taksnega algoritma nismo imeli v srednji soli. Se zdalec ne! Pa rekurzijo. V prvem letniku?! Lepo vas prosm. Neumnosti na celi crti. (govorim za 5~10 let nazaj).

Mi (gimnazija Vič) smo 7 let nazaj imeli oboje, Evklidov algoritem in rekurzijo, v 1. letniku.

Microsoft, Evklidov algoritem JE elegantna in enostavna rešitev, ki se jo učimo tudi v šoli. Mislim, računanje ostanka pri deljenju pa res ni zahtevno, niti za začetnike v programiranju. Na Wikipedi piše : "Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity."

Morda temu v šoli niste rekli Evklidov algoritem, kar pa niti ni tako pomembno.

Največji skupni deljitelj na googlu - rešitev, če človek ne ve kaj je največji skupni deljitelj.

Če pa je problem pri programiranju tega, pa moramo vedeti za programski jezik gre - verjetno kateri od tistih katerih rešitve so zgoraj navedene, ni pa nujno.