[php] Operacja na pieniądzach, ilość możliwości wydania złotówki Opcje

[nexis]

Jak powinien wyglądać kod programu pozwalający obliczyć liczbę sposobów wydania reszty równej 1 zł.

Do dyspozycji mamy oczywiście monety: 1gr, 2gr, 5gr, 10gr, 20gr, 50gr, 1 zł.

Np.

100*1gr - 1 sposób
50gr+50gr-2 sposób
itd.

Dziękuję z góry za pomoc!

[Sedziwoj]

Ogólnie to problem jest kombinatoryczny, i można na kartce to policzyć, tylko że ja nigdy w tym mocny nie byłem.

100 50 20 10 5 2 1
1 0 0 0 0 0 0
0 1 0 0 0 0 50
0 1 0 0 0 1 48
...
0 1 0 0 0 25 0
0 1 0 0 1 0 45
0 1 0 0 1 1 43
...
0 1 0 0 1 22 1
...
0 1 0 0 10 0 0

Może niezbyt ładnie ale to powinno zadziałać (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif)
Czyli zagnieżdżone pętle z warunkami.

tylko bez pierwszego i zaczynać od końca (od 1gr), czyli nie 50 na start a
0 0 0 0 0 0 100
i grosze zawsze uzupełniają, jeśli przy iteracji np. 2 przekroczy się 100 to pętla break aby z iterować 5.

Ten post edytował Sedziwoj 23.11.2006, 19:17:27