Implementacja Taki algorytm jest bardziej uniwersalny, ale nieco trudniejszy w implementacji.
Przykład kodu w C++:
#define INFINITY 2147483647 // nieskończoność definiujemy umownie jako górny kres typu integer /* ... */ // a – liczba nominałów, k – żądana kwota int* T = new int[k+1]; // utwórz tablicę T o zakresie od 0 do k T = 0; // dla kwoty 0 potrzebujesz 0 monet int i; for (i=1;i<=k;++i) { // dla każdej kwoty od 1 do k T[i]=INFINITY; // potrzebujesz nieskończoność monet } for (i=1;i<=a;++i) { // dla każdego nominału wykonuj: int n; // n – aktualnie analizowany nominał cin >> n; // wczytaj nominał for (int j=0;j<=k-n;++j) { // dla j=0 do k-n wykonuj: if (T[j] < INFINITY) { // jeżeli T[j] już ma przypisaną wartość i jeżeli if (T[j]+1 < T[j+n]) { // dodanie monety zmniejszy liczbę monet dla kwoty j+n, T[j+n] = T[j]+1; // to zapisz nową liczbę monet dla zwiększonej kwoty.
Przypisy
Linki zewnętrzne Problem wydawania reszty w Encyklopedii Algorytmów
Kategoria:Algorytmika