Witam wszystkich.
Mam maly problem natury algorytmicznej. Nie mam mianowicie pomyslu jak rozwiazac pewien problem, byc moze ktos z szanownych forumowiczow na taki pomysl natrafi.
Chodzi o to, ze mamy dana liczbe X zapisac w postaci dodawania liczb ze zbioru 1,5,10,25,50
Tak oto liczbe 7 da sie zapisac na dwa sosoby: 1+1+1+1+1+1+1 oraz 5+1+1
liczbe 4 na jeden sposob: 1+1+1+1
myslalem ze mozna by zrobic tak:
Kazda z liczb ze zbioru rozpisac w taki wlasnie sposob tak oto:
1 mozna zapisac na 1 sposob
5 mozna zapisac na 2 sposoby
10 mozna zapisac na 4 sposoby (110 ; 5+5 ; 5+51 ; 10)
...
Moj sposob (nie dopracowany / nie dzialajacy):Teraz majac liczbe (np 14)
dziele ja przez 10 calkowicie - wynik wychodzi 1 teraz sprawdzam ze 10 mozna rozpisac na 4 sposoby
reszte 4 sprawdzam ze mozna zapisac na jeden sposob.
razem wychodzi 4+1=5 - 5 sposobow zapisu liczby 14;
Jednak nie jestem pewien (nie mam mozliwosci sprawdzenia) jak bedzie to sie zachowywac dla b.duzych liczb takich jak np. 343 itd.
Poprosilbym o jakis schemat, ktory dziala tak bym mogl sie przekonac.
Dziekuje za poswiecenie uwagi temu problemowi.