#1 23. 11. 2010 21:14
- VojtechSejkora
- Příspěvky: 176
- Reputace: 5
Rozložení čísla
Chci se zeptat jak se dá najít nejbližší kombinace čísel k zadanému
dostanu na vstupu zadáno jedno číslo K
pad další číslo L
a k tomu K mám najít nejbližší součet jednotlivých částí, přičemž jednotlivé části jsou velké
pro 1 je to L, pro 2 je to (L-2)*2 pro 3 (L-3)*3... atd.
tak 1 zmenšení jsem našel, jelikož se to číslo má jen blížit tak mi stačí dělat tu jednotlivé části do velikosti
L/2
ale pak už nevím jak to mám udělat.... napadlo mě porovnávat každou možnost, ale to pak je O(x^L) což je šíleně hodně:(.... nenapadá vás někoho jak to udělat elegantněji a s nižší časovou složitostí?
nemusíte psát hned celé řešení, stačí mi pokud mi naznačíte postup...
Offline
- (téma jako vyřešené označil(a) VojtechSejkora)
#2 25. 11. 2010 11:30
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: Rozložení čísla
Jde to naprogramovat pomoci algoritmu podobneho Dijkstrove algoritmu. Priblizne tak, ze se vytvori tabulka tech jednotlivych casti L, (L-1)*2, (L-2)*3 ... a pole s K prvky (nebo K+1). To K pole bude ze zacatku cele nulove. Pak v kazdem kroku vezmes nove indexy v tom poli K (v prvnim kroku jen index 0), a ke kazdemu z nich prictes vsechna ta cisla z tabulky L a vytvoris takhle nove prvky v K (ale jen na mistech, kde K byli nulova). Nevim, jestli tohle vysvetleni staci, nejspis bude existovat i neco efektivnejsiho. (casovou slozitost si netroufam odhadnout)
Offline
#3 25. 11. 2010 11:50 — Editoval kotipelto (25. 11. 2010 11:54)
- kotipelto
- Místo: Klimkovice
- Příspěvky: 40
- Škola: VŠB
- Pozice: Z půli student z půli těžce pracující
- Reputace: 0
Re: Rozložení čísla
Já bych to dělal v cyklu, dokud (L - i) * i vetsi nez K, a ukládal všechny hodnoty do pole, potom bych vzal největší z těchto čísel a odečetl jej od K, vyšlo by číslo C, které bych binárně vyhledával v tomto uspořádaném poli, pokud takové číslo není, vezmu předposlední, odečtu od K atd. atd... Samozdřejmě, pokud jsem správně pochopil zadání
Offline
#4 25. 11. 2010 14:40 — Editoval VojtechSejkora (25. 11. 2010 16:08)
- VojtechSejkora
- Příspěvky: 176
- Reputace: 5
Re: Rozložení čísla
↑ Lumikodlak:↑ kotipelto:
oběma děkuji za návrh, ale bohužel jsem ani jeden nepochopil:(
mohli by jste mi ukázat prosím nějaký příklad s datama např 50 6 jak by ten váš algoritmus fungoval? děkuji mnohokrát
korektní výstup by pro toto byl například
1x L
1x (L-1)*2
1x (L-2)*3
1x (L-3)*4
protože součet tohoto se rovná 50
Offline
#5 25. 11. 2010 16:21
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: Rozložení čísla
L (L-x)*(1+x)
6 = 6*1
10 = 5*2
12 = 4*3
Takze cisla 6, 10, 12 (dejme tomu mnozina K)
M jsou oznaceny minule prvky, X jsou oznacene nove generovane - ty vznikaji pricitanim vsech K k tem M prvkum. 'O' jsou nejake predchozi.
Zacatek:
___________________________________________________
1. krok
6 10 12
______X___X_X______________________________________
2. krok
10 121012
______M___M_M___X_X_X_X_X__________________________
6 12
3. krok
______O___O_O___M_M_M_M_M_X_X_X_X_X_X______________
4. krok
______O___O_O___O_O_O_O_O_M_M_M_M_M_M_X_X_X_X_X_X__
5. krok
______O___O_O___O_O_O_O_O_O_O_O_O_O_O_M_M_M_M_M_M_X
V 5. kroku jsme uz u 50, takze zpetne se da ziskat treba 12+12+10+10+6
Ale obavam se, ze z toho to moc pochopitelne neni. Nevim, jak to jinak zapsat, bylo by to hodne velke asi. Mohl bych poslat i cely program, ale to az pozdeji.
Offline
#6 25. 11. 2010 16:36 — Editoval VojtechSejkora (25. 11. 2010 16:38)
- VojtechSejkora
- Příspěvky: 176
- Reputace: 5
Re: Rozložení čísla
↑ Lumikodlak:
jestli to tedy dobře chápu tak tu vpodstatě děláš to že odčítáš postupně množiny toho čísla?
jako že dáš
50-6
zkontroluješ ještli je větší jak 0
50-10
o5 kontroloa
50-12
.... a tak dále dokud nedojdeš té 0 nebo méně?
pokud ot takto není tak jsem to opravdu nepochopil...:(
a nebo to je tak že nejprve zkusím 1 prvek každej zvlášť pak 2 prvky pak 3 atd.? a pokud chci vyzkoušet kombinaci každej s každým tak tu máme exponenciální složitost a to mi je celkem naprd:(
Offline
#7 25. 11. 2010 16:53
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: Rozložení čísla
↑ VojtechSejkora:
Rekl bych, ze to tak je. V dalsim kroku by se kontrolovalo
44-6
44-10
44-12
40-6
40-10
40-12
38-6
38-10
38-12
ale nektere by se vynechaly, protoze napriklad 44-12=38-6, takze by to byly - 34, 32, 30, 28, 26.
Offline
#8 25. 11. 2010 16:58
- VojtechSejkora
- Příspěvky: 176
- Reputace: 5
Re: Rozložení čísla
↑ Lumikodlak:
a teď by mě zajímal program, který by toto dělal... jeho kód pokud možno v céčku...
takto mě to taky napadalo dělat, ale nevěděl jsme jak to naprogramovat a nebyl jsem si jist, jestli dokáže udělat i třeba
98 100
Offline
#9 25. 11. 2010 18:55
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: Rozložení čísla
Myslis 98 K a 100 L, nebo 100 K a 98 L? V jednom pripade to nebude mit reseni, a ve druhem tu bude proste to 98. (Neni treba dostat se na nulu, ale projit vsechny mozna cisla a pak vzit to nejmensi)
Offline
#10 25. 11. 2010 19:05
Re: Rozložení čísla
↑ VojtechSejkora: A nechceš, aby to za teba ešte aj odovzdali?
Do you follow my way? Or you just see a black stain swimming in the Milky Way ...
KSP je určený pre študentov základných a stredných škôl, ktorí majú záujem naučiť sa niečo z oblasti algoritmov, logických úloh, programovania a informatiky.
Offline
#11 25. 11. 2010 19:06
- VojtechSejkora
- Příspěvky: 176
- Reputace: 5
Re: Rozložení čísla
↑ Lumikodlak:
myslím k=98 a L=100
a má to řešení...jelikož jsem psal že hledáme nejbližší kombinaci
ještě jsme to mohl napsat nejbližší vyšší
takže správné řešení by pak bylo 1x L
Offline
#12 25. 11. 2010 19:09
- VojtechSejkora
- Příspěvky: 176
- Reputace: 5
Re: Rozložení čísla
↑ pizet:
:D ne nechci.... akorát jak tak na to koukám je napadají jen takové řešení, které napadli už i mě a neuměl jsem je naprogramovat, a nebo byli k ničemu kvůli časové složitosti
prostě O(x^L) je příliš mnoho
a mě spíše zajímalo jestli na to už někde nějaký algoritmus není vymyšlen... navíc v pravidlech KSP není nikde psáno, že se nemůžeš radit s částmi jednotlivých cvičení... já celou dobu myslel že KSP je tu proto, aby se člověk naučil něco řešit a nejvíce se člověk učí tím, že pokud na ot nepříjde sám tak o dané problematice diskutuje
Offline
#13 25. 11. 2010 19:21
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: Rozložení čísla
To jsem si predtim neuvedomil, jestlize i nejblizsi vyssi, tak se to bude muset trochu upravit, ale to uz je jednoduche. Jestli je nejaky algoritmus vymyslen, to nevim, a ani jsem nehledal.
Offline
#14 25. 11. 2010 20:28
- VojtechSejkora
- Příspěvky: 176
- Reputace: 5
Re: Rozložení čísla
↑ Lumikodlak:
tak kamarád mi poradil, že je to podobné jako problém batohu... tak se na to kouknu v kuchařce a snad na to příjdu
díky za pomoc
Offline