Hogyan oldanátok meg az alábbi feladatot?

Le van irva huszmillio helyen, hogy kell ket szam legkisebb kozos tobbszoroset kiszamolni, tele van a net kesz algoritmussal ra. Tessek: [link]

N db szam legkisebb kozos tobbszorosehez meg csak vegig kell iteralnod a szamokon.

Jah, senki nem tudja megoldani a vilagon.

[link]

Ha megvannak a prímtényezők, akkor 2 szám lkkt-hez összeszorzod azokat, ami valamelyik szám prímtényezője (halmazok uniója)

a,b,c szám lkkt-je pedig úgy kapod, hogy a és b lkkt-t kiszámolod, majd az így kapsz egy x számt, és kiszámolod lkkt(x,c)-t

vagyis lkkt(a,b,c) = lkkt(c, lkkt(a,b))

És ezt lehet tetszőleges n számig

Pythonban van egy megoldásom. Nem teszteltem agyon, de működni látszik.

Látom, hogy a kulcsszavak alapján Pascalban kellene, ezért meg merem osztani. :)

[link]

Tegyük fel, hogy KÉT szám legkisebb közös többszörösét ki tudjuk számolni. (Jelüljük most itt a, b legkisebb közös többszörösét [a, b]-vel.

A feladat persze akárhány számra vonatkozik.

[x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈] = ?

Három tételt használjunk föl ahhoz, hogy az akárhány számra vonatkozó legkisebb közös többszöröst visszavezessük a két számra vonatkozó legkisebb közös többszörösre.

[x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈] = [[[[[[[x₁, x₂], x₃], x₄], x₅], x₆], x₇], x₈]

az elfajuló esetek miatt pedig még két tételt vegyünk hozzá:

[] = 1

[x] = x

vagyis a nulla darab számra vonatozóan formálisan az 1, eredményt tekintsük, mint elfajuló esetet, egyetlen számra vonatkzóan pedig magát a számot.

Úgy is mondhatnám, hogy a legkissebb közös többszörös mint művelet egységelemes félcsoportképző művelet lehetne, az asszociativ tulajdonsággal, és az 1-gyel mint neutrális elemmel.

A gyakorlat terén ez azt jelenti, hogy már ciklussal meg lehet oldani.

legyen egy cikluson kívüli változó a lkktN. Ennek adjuk az 1 kezdőértéket. Ezután egy cikluson pörgessünk végig az N darab számon, és mindegyikkel ,,műveletezzük össze'' a külső változót:

Ciklus k := 1-től N-ig, a ciklusmagban pedig lkktN := [lkktN, xₖ]

Tehát a megoldás:

Függvény [x₁, x₂, x₃,... xₙ] kiszámolására:

lkktN := 1

Ciklus k := 1-től N-ig, a ciklusmagban lkktN := [lkktN, xₖ]

Visszaadott érték: lkktN

Most már csak a párban, a számpárra működő [a, b] legisebb közös többszörös képző függvyényt kell megírni.

Ez pedig pl. mehet az euklideszi algoritmussal,

Ehhez először egy pillanatra fogalkozzunk egy másik fogalommal, egy ,,társfogalommal'', a legnagyobb közös osztóval.

jelölje az a, b szám legnagyobb közös osztóját (a, b)

a leglényegesebb összefüggés, amit kihasználhatunk, az alábbi képlet:

(a, b) * [a, b] = a * b

vagyis ez alapján

[a, b] = a * b / (a, b)

Tehát most már a programunk egy további függvénnyel bővülhet. Valahogy így:

Függvény lkktN kiszámolására:

tmp := 1

Ciklus k := 1-től N-ig, a ciklusmagban tmp := lkkt2(tmp, xₖ)

Visszaadott érték: tmp

Függvény lkkt2(a, b) kiszámolására:

Ha a = 0 vagy b = 0, adj vissza 0-t, különben pedig:

Visszaadott érték: a * b / lnko2(a, b)

Most akkor már csak lnko2 függvény megírása van hátra, vagyis két adott szám legkisebb közös többszörösének kiszámítása. Ez már mehet az euklideszi algoritmussal:

[link]

de mehet akár a ,,hagyományos'' módon is, a prímtényezőből való összerakással.