Witam.
Na studiach z algorytmów mamy zrobić zadanie. Ja mam takie:
"Na ile sposobów można rozmienić 5000zł za pomocą monet 1, 2, 3, 5 i 10 złotowych?"
Dodam że już 5 dni kombinuje... W sumie zrobiłem algorytm, który działa powiedzmy do 300zł, potem nie stety obliczanie kolejnych iteracji trwa baaardzo długo. Działa on mniej więcej na takiej zasadzie:
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
short pieniadze = 18;
short tabela [5][2] = {1, 0, 2, 0, 3, 0, 5, 0, 10, 0};
short m1, m2, m3, m5, m10, xx;
short t1=4, t2=1;
short suma = 0;
long ilerazy = 0;
m1 = pieniadze - 1;
m2 = pieniadze / tabela[1][0];
m3 = pieniadze / tabela[2][0];
m5 = pieniadze / tabela[3][0];
m10 = pieniadze / tabela[4][0];
for (m10; m10 >= 0; m10--)
{
m1 = pieniadze - 1;
m2 = pieniadze / tabela[1][0];
m3 = pieniadze / tabela[2][0];
m5 = pieniadze / tabela[3][0];
suma = m10 * tabela[4][0];
if(suma != pieniadze )
{
for (m5; m5 >= 0; m5--)
{
suma = (m10 * tabela[4][0]) + (m5 * tabela [3][0]);
m1 = pieniadze - 1;
m2 = pieniadze / tabela[1][0];
m3 = pieniadze / tabela[2][0];
if (suma == pieniadze)
{
ilerazy++;
}
if (suma < pieniadze)
{
for (m3; m3 >= 0; m3--)
{
suma = (m10 * tabela[4][0]) + (m5 * tabela [3][0]) + (m3 * tabela[2][0]);
m1 = pieniadze - 1;
m2 = pieniadze / tabela[1][0];
if (suma == pieniadze)
{
ilerazy++;
}
if (suma < pieniadze)
{
m2 = pieniadze / tabela[1][0];
for (m2; m2 >= 0; m2--)
{
suma = (m10 * tabela[4][0]) + (m5 * tabela [3][0]) + (m3 * tabela[2][0]) + (m2 * tabela[1][0]);
m1 = pieniadze / tabela[0][0];
if (suma == pieniadze)
{
ilerazy++;
}
if (suma < pieniadze)
{
for (m1; m1 >= 0; m1--)
{
suma = (m10 * tabela[4][0]) + (m5 * tabela [3][0]) + (m3 * tabela[2][0]) + (m2 * tabela[1][0]) + (m1 * tabela[0][0]);
if (suma == pieniadze)
{
ilerazy++;
}
}
}
} }
}
}
}
}
else if (suma == pieniadze)
{
ilerazy ++;
}
}
//============================================ WYNIK
cout << endl << pieniadze << " zl mozna rozmienic za pomoca monet:\n1zl\n2zl\n3zl\n5zl\n10zl\nna " << ilerazy << " sposobow. \n\n";
system("PAUSE");
return EXIT_SUCCESS;
}
Wiem że mogłem to wrzucić do funkcji, jednak dopieszczać algorytm chce dopiero jak będzie działał w pełni dla 5000zł. Działa on tak, że na początku oblicza max. ilość dla 10, 5, 3, 2, 1 zł, którą możemy wydać. Potem zaczyna od 10, i sprawdza kolejno czy 10 * max10 == pieniądze. Jeżeli nie idziemy do monet 5zł. Sprawdzamy czy 10max10 + 5max5 jest równe pieniądze. Jeżeli nie, oraz jeżeli ta suma jest mniejsza niż pieniądze szukamy dalszej monety, która po dołożeniu da rezultat. Jeżeli takiej nie znajdziemy, poprzednia pętla (moneta) zmienia się o jeden w dół i powtarza proces. Za każdym razem kiedy znajdziemy rozwiązanie, powiększa nam się wynik.
Tak jak mówiłem... działa to dobrze do pewnych w sumie nie wielkich liczb. Potem następuje coraz więcej iteracji i niestety pomysł mój pada...
Może mi ktoś pomóc bo już nie mam sił do tego. Szukam jakiś zależności itp. i nie mogę nic znaleźć.
Pozdrawiam i proszę o jakieś wskazówki