Hogy kell a lagnagybb kőzös osztó, legkisebb közös többszörös témából a következő feladatokat meg oldani?

Bármilyen számrendszerből 10-es számrendszerbe átváltás:

a,

34056_{8} = 6*8^{0} + 5*8^{1} + 0*8^{2} + 4*8^{3} + 3*8^{4}

= 6 + 40 + 0 + 2048 + 12288 = 14382_{10}.

b,

10111101_{2} = 1*2^{0} + 0*2^{1} + 1*2^{2} + 1*2^{3} + 1*2^{4} + 1*2^{5} + 0*2^{6} + 1*2^{7} = 1 + 0 + 4 + 8 + 16 + 32 + 128 = 189_{10}

c,

22302_{5} = 2*5^{0} + 0*5^{1} + 3*5^{2} + 2*5^{3} + 2*5^{4} = 2 + 0 + 75 + 250 + 1250 = 1577_{10}

Remélem látod az algoritmusát, hogy miképp kell megcsinálni bármilyen ilyen jellegű feladatot.

Gondolom, az első feladatnál a törzstényezőre bontás megy. ( akasztófa ) A szabályokat is tudod. Így néz ki a megoldás:

[link]

1425|3

475|5

95|5

19|19

1|1

1725|3

575|5

115|5

23|23

1|1

1425 = 3 * 5^{2} * 19

1725 = 3 * 5^{2} * 23

LNKO: 3 * 5^{2} = 75

LKKT: 3 * 5^{2} * 19 * 23 = 32775

LNKO-nál azokat a tényezőket vesszük, amelyek mindkettőben megvannak (és annyiszor, ahányszor mindkettőben megvannak), LKKT-nél pedig az összes tényezőt vesszük, minél a szorzatokban szereplő legnagyobb hatványon.

A legnagyobb közös osztót és legkisebb közös többszöröst a következőkben ismeretett (könnyen megjegyezhető) módszerrel is kiszámíthatod. A számokat prímtényezőkre bontod, ezután felsorolod az összes előforduló prímszámot. A számokat a felsorolt összes prímszám megfelelő hatványának szorzataként írod fel. (Ha van olyan prímszám a felsoroltak között amelyikkel a szám nem osztható, akkor annak a kitevője nulla lesz.) Ezután a legnagyobb közös osztót (rövidítve: LNKO) a nevével "ellentétben" úgy kapod meg, hogy az összes prímszámot az előforduló legkisebb kitevőre hatványozod és összeszorzod. A legkisebb közös többszöröst (rövidítve: LKKT)szintén a nevével "ellentétben" úgy kapod meg, hogy az összes prímszámot, az előforduló legnagyobb kitevőre hatványozod és összeszorzod.

Nézzük egy példát!

1425 prímtényezős felbontása: 3*19*5^2

1725 prímtényezős felbontása: 3*23*5^2

Az összes előforduló prímszám: 3, 5, 19, 23.

1425 = 3^1 * 5^2 * 19^1 * 23^0

1725 = 3^1 * 5^2 * 19^0 * 23^1

LNKO(1425,1725)= 3^1 * 5^2 * 19^0 * 23^0 =3*25=75

LKKT(1425,1725)= 3^1 * 5^2 * 19^1 * 23^1 =3*25*19*23=32775

Ellenőrzésként jó tudni, hogy LNKO*LKKT=a számok szorzata.

75*32775=1425*1725