Algorytm: Na ile sposobów można rozmienić 5000zł na monety 1, 2, 3, 5, 10 zł.

0

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

0

Za ten problem trzeba się wsiąść z głową, jeśli ma działać dla tak dużej sumy przy tak małych i licznych nominałach.
Zwykła rekurencja (którą de facto rozpisałeś) nie jest dobrym rozwiązaniem, bo wiele razy będziesz obliczał dokładnie to samo (np ile kombinacji jest dla kwoty 3000 dla monet 1 2 3, bo będziesz liczył to dla różnych kombinacji monet 5 i 10 na sumę 2000).
Moja podpowiedź to zapamiętuj wyniki pośrednie by je potem ponownie wykorzystać w innych iteracjach.
Zdecydowanie rozpisz to na funkcje/obiekty(metody), bo się pogubisz.

0

A z funkcji tworzących nie da rady skorzystać?

0

funkcje tworzące? Możesz rozwinąć?

0

Wibowitowi chodzi chyba o to żebyś to równanie rekurencyjnie zwyczajnie rozwiązał na kartce a w programie zaimplementował tylko wyliczanie rozwiazania na podstawie otrzymanej funkcji.
Jeśli chodzi o samą implementację rozwiązania to jakie są zalożenia? Masz podać ilość różnych podzbiorów nominałów czy podciągów?
Rozwiązanie które pokazałeś to tragedia. Tak byś to pisał jakby nominałów było na przykład 1000?

0

http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Wyk%C5%82ad_7:_Funkcje_tworz%C4%85ce
Choć, jak widać, da się zaprząc do tego programowanie dynamiczne.

0

Shalom:

po prostu mam wyliczyć na ile sposobów 5000zł można wydać/rozmienić w monetach (stałe, sa podane raz na zawsze) 1, 2, 3, 5, 10 zł.

Wibowit:

też myślałem żeby z wyników programu dla kolejnej sumy pieniędzy jakąś funkcję wykombinować ale nie miałem pojęcia w jaki sposób. Myślę że jak przeanalizuje wiadomości z twojego linku jakoś do tego dotrę ;)

0

Nie rozróżniasz podzbiorów i podciągów.
wydania 10+10+10+....+10+5+5
oraz 5+5+10+10+...+10
są takie same czy różne?
Inaczej, czy kolejność wydawania monet ma znaczenie?

0

Nie ma znaczenia.

0

Poszukaj o równaniach diofantycznych i metodzie Eulera.

1 użytkowników online, w tym zalogowanych: 0, gości: 1