Pomoc s blbým programem – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Pomoc s blbým programem – C / C++ – Fórum – Programujte.comPomoc s blbým programem – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
14. 12. 2008   #1
-
0
-

26. Je dáno přirozené číslo N,N<=100. Vypište všechny možné výplaty N korun pomocí platidel s hodnotami 1,2,5,10,20, a 50 korun. Prosím o rady a tak jak to řešit děkuji

Nahlásit jako SPAM
IP: 213.192.8.–
Reklama
Reklama
Quiark0
Věrný člen
14. 12. 2008   #2
-
0
-

Myslím, že to bude něco na ten způsob, že zkusím všechny kombinace těch mincí a budu koukat, jestli jejich součet dá N. Tedy pro každou hodnotu první mince zkusím každou hodnotu druhé mince a pro každou kombinaci těhle dvou zkusím každou hodnotu třetí mince a tak dál:

1 1 1
1 1 2
1 1 5
1 1 10
1 1 20
1 1 50
1 2 1
1 2 2
1 2 5
1 2 10
1 2 20
1 2 50
2 1 1
2 1 2
...

samozřejmě těch mincí bude potřeba víc než jen 3.

Asi by to šlo udělat i optimálněji, možná dokonce v polynomiálním čase s dynamickým programováním, ale tím se asi nemusíš zatěžovat :)

Nahlásit jako SPAM
IP: 193.86.140.–
14. 12. 2008   #3
-
0
-

To Quiark : ahoj a mohl bys teda prosím sem dát zdroják??? děkuji

Nahlásit jako SPAM
IP: 213.192.8.–
KIIV+42
God of flame
14. 12. 2008   #4
-
0
-

dal ti navrh jak by to resil... zdrojak si muzes laskave udelat sam..

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
KIIV+42
God of flame
14. 12. 2008   #5
-
0
-

jinak ja bych to asi resil trochu opacne... nejdriv bych zjistil jaky mince tam jdou nasazet nejvetsi...
a pak jednotlive mince rozkladal... na mensi a mensi... stacilo by pak menit jen pocty jednotlivejch minci...
mohlo by to mit i reseni v "umernem" case :D tj necekat 10000let na vysledek :D

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Osiris0
Stálý člen
14. 12. 2008   #6
-
0
-

Pokud jde jen o počet těch kombinací, pak to lze převést na násobení spousty polynomů.

P1 = 1 + x^1 + x^2 + x^3 + ... + x^N
P2 = 1 + x^2 + x^4 + x^6 + x^8 + ... + x^N
P5 = 1 + x^5 + x^10 + x^15 + x^20 + ... + x^N
P10 = 1 + x^10 + x^20 + x^30 + ... + x^N
P20 = 1 + x^20 + x^40 + x^60 + x^80 + x^N
P50 = 1 + x^50 + x^N

PT = P1*P2*P5*P10*P20*P50

Tyhlety polynomy vynásobíš, a podíváš se na KOEFICIENT u x^N a tento koeficient je počet kombinací.
Pokud máš konstantní počet těch hodnot, pak to lze řešit v čase O(n log n), protože polynomy dokážeš násobit v čase O(n log n) pomocí FFT.

Jinak polynomiální algoritmus na VÝPIS jednoduše existovat nemůže, protože těch kombinací je exponenciálně mnoho.

Nahlásit jako SPAM
IP: 85.70.130.–
scd
~ Anonymní uživatel
4 příspěvky
17. 12. 2008   #7
-
0
-

ahojte neviem naco spekulujete s nejakymi polynomami. Najlepsie najrychlejsie a najjednoduchsie riesenie je to co navrhol KIIV.
a to spocitavat najvacsie mince az pokial nebude hodnota vacsia alebo rovna pozadovanemu vysledku ak je uz vacsia tak odcitat najvaciu a zasa tym istym sposobom pricitavat mensiu mincu a dokola az po najmensiu pokial sa to nebude rovnat:)

Nahlásit jako SPAM
IP: 91.127.15.–
KIIV+42
God of flame
17. 12. 2008   #8
-
0
-

To scd : problem bude ze to mozna nenajde uplne vsechny moznosti... teda aspon letmou uvahou si to myslim... muselo by si to pamatovat predchozi kroky a rozkladat to ruzne

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
scd
~ Anonymní uživatel
4 příspěvky
17. 12. 2008   #9
-
0
-

ups sory to som prehliadol ale jednu aspon najde:D

Nahlásit jako SPAM
IP: 91.127.15.–
survik1
~ Moderátor
0
Posthunter
17. 12. 2008   #10
-
0
-

To KIIV : Proč?
50 50
50 20 20 10
50 20 20 5 5
50 20 20 5 2 2 1
50 20 20 5 2 1 1 1

Nahlásit jako SPAM
IP: 89.102.156.–
Život je jen hra, která se nedá vyhrát.
KIIV+42
God of flame
17. 12. 2008   #11
-
0
-

ale treba:
50 20
20 20 20 10
ale to co by se uz neobjevilo 50 10 10 a obdobne dalsi a dalsi kombinace

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
mephi0
Expert
17. 12. 2008   #12
-
0
-

ten postup rozkladania nenajde riesenie 2 2 2 2 2 2 2 ... myslim :)
a ak ho najde tak nenajde tych 50 10 10 ...

tusim by som na to isiel rekurzivne, spustit vypis pre kazde platidlo pricom by sa v kazdej rekurzii spustili dalsie s kazdym a skoncili by az by bol sucet viac ako N.

Nahlásit jako SPAM
IP: 85.237.232.–
Program nemusi fungovat rychle, staci ze funguje dostatecne rychle.
KIIV+42
God of flame
17. 12. 2008   #13
-
0
-

To mephi : no mozna by to slo nejakym zasobnikem...

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Osiris0
Stálý člen
17. 12. 2008   #14
-
0
-

To scd : Pokud jsi můj komentář nepochopil, tak ho nekomentuj.

Nahlásit jako SPAM
IP: 85.70.130.–
KIIV+42
God of flame
17. 12. 2008   #15
-
0
-

no kdyz nad tim premejslim tak by se to dalo udelat jako DFS nebo BFS... jen by se jelo az do uplneho konce :)

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 85 hostů

Podobná vlákna

Pomoc s programem ... — založil Bublina

Pomoc s programem C++ — založil Marek

Pomoc s programem — založil Pepuna

Pomoc s programem — založil Janička

Pomoc s programem v C — založil Radyon

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý