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.

0

Dzięki wszystkim za pomoc. Poszukam pouczę się tych rzeczy które zaproponowaliście i postaram się to rozwiązać. Jak mi się uda napisze wam co wykombinowałem :) Naprawdę jestem bardzo wdzięczny

0

na ideone.com 25 linijkom w C zajęło 0,03 sekundy wykonanie 14'182'337 dodawań by otrzymać 87'536'780'112.
w sieci jest wiele rozwiązań, ja mnożę wielomiany (funkcje tworzące)

0

To jest zadanie z propabilistyki. Znajdz kogos kto dobrze to ogarnia i wyprowadzi Ci wzor ogolny dla takiego zadania. na pewno beda tu jakies kombinacje z powtorzeniami. Sam nie jestem zbyt dobry z tego, wiec wole nie pomagac bo bardzo mozliwe ze gdzies zrobie blad, ale na zajeciach robilismy tego typu zadania.

0

Tak sie składa że na forum matematyczne też dałem to zadanie tylko że samą treść i na razie nikt nie kwapi się żeby odpisać ;)

0

robiłem tak:<latex>

             [5000/k]
    ____      __
    |  |      \   ki
    |  |      /_ x
k=1,2,3,5,10   i=0

</latex>gdzie [] to floor
o TeX znowu działa :-)

0

A nie da się tego rozwiązać problemem plecakowym? Skoro jest to wprowadzenie do algorytmów to na pewno problem plecakowy omawialiście. Poza tym, czy na tym przedmiocie nie piszecie czasem pseudokodów zamiast kodów źródłowych jakiegoś języka?

0

Tak pseudokodem. Ale żeby zobaczyć czy działa no to sobie w C++ programuje ;) Jak bedzie działało to i będzie pseudokod.

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