Egy kis matek

Offtopic

Lenne egy példa, és valahogy leblokkoltam az egyszerű megoldás tekintetében.
Van 5 szám, az 1 2 3 4 5.
Ezeket számokat úgy kell variálni, hogy egy háromjegyű osztandót és egy kétjegyű osztót képezve a legkisebb egész eredményt kapjunk. Pl.: 123/45 vagy 154/32

Valami megoldást segítsetek találni, hogy ne a teljes kombinációt kelljen végig zongorázni.
Csak az alapműveleteket lehet használni.

  • 1596 megtekintés

Első gondolatom, hogy szerintem kézzel is brute force, max annyi eltéréssel, hogy ügyes oszthatósági szabályokkal hogy bontod csoportokra és mennyi megoldást zársz ki ezzel könnyen.

A programon is lehet fejleszteni, kicsit túlbonyolítottam pl. ennyi elég:
> filter (\[a,b,c,d,e] -> (100*a+10*b+c) `mod` (10*d+e)==0) $ permutations [1..5]

=> [[5,3,2,1,4],[2,1,5,4,3]]

Ha tudjuk(de honnan? :), hogy az eredmény 5, akkor:

a*100 + b*10 + c = f*(d*10 + e)
a*100 + b*10 + c = f*d*10 + f*e

c = f*d*10 + f*e - a*100 - b*10

ha f = 5
c = d*50 + e*5 - a*100 - b*10
c = 5(d*10 + e - a*20 - b*2)

ha c = 5
d*10 + e - a*20 - b*2 = 1
e - 1 = a*20 + b*2 - d*10
e - 1 = 2(a*10 + b - d*5)

ha e = 3
a*10 + b - d*5 = 1
b - 1 = d*5 - a*10
b - 1 = 5(d - a*2)

ha b = 1
d = a*2

ha a = 2, d = 4
215/43

( neutrino v | 2011. 11. 15., k – 15:36 )

154/32
-------------------------
127.0.0.1 SWEET 127.0.0.1
AMD Athlon X2 245E@3,1 GHz OC, MSI Radeon 6770 1 Gb GDDR5, Seagate Barracuda, Windows 7 Enterprise

( GCS v | 2011. 11. 15., k – 15:56 )

Nekem is van egy hasonló matematikai kérdésem.
a/bc+d/ef+g/hi összeg legyen kerek 1 egész úgy, hogy a..i betűk 1..9-nek feleljenek meg és itt is egy szám csak egyszer használható.

( carlcolt | 2011. 11. 15., k – 16:07 )

En tipikusan az a felhasznalo vagyok, aki a szamhaborut is bruteforce-szal kezdi, ugyhogy a megoldas es a menete engem is erdekelne. :) Mar csak azert is, mert a fejemben mar van ra egy kod, de lusta vagyok megirni

( ironcat | 2011. 11. 15., k – 16:35 )

Kérdések:
1. Mindig csak öt számjeggyel kell végrehajtani a programot?
2. Ez egy HF?

Az 1-es esetben a brute force módszert nagyon gyorsan le lehet kódolni, és a futási idő is elhanyagolható lesz egy mostani számítógépen.

A 2-es esetben kell kreálni csak algoritmust. Alapelv (kicsit favágó módszer ez is): Képezzük a lehető legkisebb osztandót, valamint a lehető legnagyobb osztót. Ha a hányados egész szám, akkor örülünk. Ha nem, akkor csökkentsük az osztót, és természetesen ezzel együtt növeljük az osztandót, majd újra ellenőrizzük a hányadost. Tegyük ezt mindaddig, amíg nem örülünk. Ez tulajdonképpen nem más, mint a brute force módszer, csak "felülről kezdve".

-----
"Ember embernek farkasa." Ezért aztán "Holló a hollónak nem vájja ki a szemét."

Lehetséges osztók:
1.) 5 számjegyből 20 kétjegyű számot rakhatsz össze. Van tehát 20 osztód.
2.) Az 5-re végződő osztókat nyugodtan diszkvalifikálhatjuk, mert csak 5-re meg 0-ra végződő számokat osztanának, azok meg nem játszanak. Így már csak 15 osztó van.
3.) A 2-re vagy 4-re végződő számok csak páros számot oszthatnak, esetünkben 2 vagy 4-végűt. A 42 így kiesett. Marad 14 osztó.

Osztandók száma:
1.) Általánosan a maradék 3 számjegyből osztónként 6 osztandót képezhetsz.
2.) Páros osztók esetében csak 4-et, mert az osztandónak is párosnak kell lennie.

Tehát van 14 osztód, ebből 6 páros. Az esetek száma így 6*4 + 8*6 = 72. Ez már egész emberi papír-ceruza módszerhez :-)

Biztos lehet még kizárni eseteket, nekem most ennyi jutott eszembe.

-
J

És ez hogy tetszik?

Felírjuk szozásként AB*X=CDE
- X a hányados
- az öt szám közül az egyiket úgy kell megszorozni, hogy utolsó számjegyként egy másik szám jöjjön ki
- X minimum 2, de a legnagyobb 2 jegyű * 2 nem lesz 123:)
- ha X 3, akkor B-nek 1-nek kellene lennie, de 3*5 nem 24 , sem 42 ahogy 3*4 sem 25, sem 52 ezért nem jó a 3 sem
- ha X 4, akkor B megint 1 lehet, de 4*5 nem 23 sem 32, illetve 4*3 sem 15 vagy 51
- Így az X 5 lesz
- Ekkor a B lehet 1 megint de 5*4 nem 23 sem 32, illetve 3*5 sem 12 vagy 21. de ha B =3, akkor 5*3 =15, megy tovább az egy, és 4*5 =20 meg 1 az 21
Szóval a megfejtés 215 :43

Hasonló módon, hogy miért nem lehet 5-nél kisebb:
1 nem lehet, mert az osztandó szám három jegyű, az osztó pedig két jegyű
2 nem lehet, mert az osztónak ekkor minimum 62-nek kellene lennie, de 6-os jegy nincsen.
3 nem lehet, mert az osztó ekkor 41-54 lehet,
1 vég kizárva (1xy miatt) 2, 3 vég kizárva (3-as modulus miatt)
45, 54 marad csak amelyek ellenőrizve nem jók
4 nem lehet, mert az osztó ekkor 31-54 lehet
31-45-ig 1 vég kizárva (1xy miatt) 2, 3 vég kizárva (3-as modulus miatt)
34, 35, 45 marad, amelyek ellenőrizve nem jók
51-54-ig 2 vég kizárva (2xy miatt) 3 vég kizárva (3-as modulus miatt)
51, 54 marad, amelyek ellenőrizve nem jók

Tehát a már ismert 5 a legkisebb eredmény.