Van egy számhalmaz (40 db szám). Szét lehet-e válogatni kétfelé ezeket a számokat úgy, hogy mindkét csoportban azonos legyen a számok összege?
40 db számról van szó: 1-40-ig a számok 6. hatványa, azaz:
1^6, 2^6, 3^6, ... 40^6 ; vagy
[1, 64, 729, 4096, 15625, 46656, 117649, ... 4096000000]
válasza:Nem működik a fórum? :D
---
Valószínűségi alapon? Nagy valószínűséggel igen, vagy nem?
Számítások, tippek?
válasza:Szerintem a gyorsközelítő eljárással kell kezdeni:
"A" és "B" csoportot csinálunk.
A legnagyobb számot "A" csoportba tesszük, az egyre kisebbeket mindig a kisebb összegű csoportba.
1 function find_partition( S ):
2 A {}
3 B {}
4 sort S in descending order
5 for i in S:
6 if sum(A) <= sum(B)
7 add element i to set A
8 else
9 add element i to set B
10 return {A, B}
Így lesz két csoport aminek az összege "majdnem" egyenlő.
És itt jönne a nehéz része, a variálgatás...
válasza:A gyors közelítő eljárás eredménye
{{11390625, 1, 3518743761, 887503681, 531441, 4826809, 15625, 1291467969, 148035889, 117649, 85766121, 244140625, 1771561, 594823321, 729, 2565726409, 47045881, 1838265625, 387420489, 24137569},{64, 4096, 481890304, 64000000, 262144, 2985984, 7529536, 4096000000, 191102976, 1073741824, 2176782336, 308915776, 1544804416, 729000000, 34012224, 3010936384, 1000000, 113379904, 16777216, 46656]}}
Hogyan tovább?
Nem jó, valamit félreértettél.
Nem egyet ide, egyet oda, hanem a köv. legnagyobbat mindig a kisebb összegű csoportba.
1. ->A
2. ->B
3. ->B !!!
válasza:Nem úgy haladtam, hogy egyet ide egyet oda, hanem úgy ahogy mondod rendezetlen halmazba tároltam az elemeket.
Rendezve ugyan az:
{{1, 729, 15625, 117649, 531441, 1771561, 4826809, 11390625, 24137569, 47045881, 85766121, 148035889, 244140625, 387420489, 594823321, 887503681, 1291467969, 1838265625, 2565726409, 3518743761},{64, 4096, 46656, 262144, 1000000, 2985984, 7529536, 16777216, 34012224, 64000000, 113379904, 191102976, 308915776, 481890304, 729000000, 1073741824, 1544804416, 2176782336, 3010936384, 4096000000}}
A hiba az volt, hogy növekvő sorrendbe haladtam.
Jól:
{{4096000000, 2565726409, 1838265625, 1544804416, 887503681, 729000000, 481890304, 244140625, 148035889, 113379904, 47045881, 34012224, 11390625, 7529536, 2985984, 531441, 117649, 46656, 15625, 4096, 729, 64, 1},
{3518743761, 3010936384, 2176782336, 1291467969, 1073741824, 594823321, 387420489, 308915776, 191102976, 85766121, 64000000, 24137569, 16777216, 4826809, 1771561, 1000000, 262144}}
Összegek:
12 752 427 364
12 752 476 256
A nehéz részét hogy lehet megoldani?
Ez már jó! Az összegekhez képest csak 48892 az eltérés.
De a végső megoldáshoz ezt még sokkal kisebbre kell leszorítani. A köv.képpen képzelem:
Az előző módszert kellene sokszor megismételni, pici "hibákkal": kb. az 5. és 25. szám között véletlenszerűen 1-2-3 helyen ellenkezően dönteni, a másik csoportba rakni.
(Az elején nem érdemes, a végén meg nem szabad változtatni, hogy az algoritmus helyrehozza a hibákat.)
Így biztos hogy kisebb eltéréseket is lehet találni!
válasza:Megvan a megoldás:
t1=[1, 15625, 262144, 531441, 1000000, 1771561, 2985984, 4826809, 7529536, 16777216, 24137569, 64000000, 113379904, 148035889, 191102976, 308915776, 594823321, 729000000, 887503681, 1544804416, 1838265625, 2176782336, 4096000000]
t2=[64, 729, 4096, 46656, 117649, 11390625, 34012224, 47045881, 85766121, 244140625, 387420489, 481890304, 1073741824, 1291467969, 2565726409, 3010936384, 3518743761]
sum(t1), sum(t2), sum(t1)+sum(t2)-sum(t)
(12752451810, 12752451810, 0)
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!