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

Odpowiedz Nowy wątek
2011-10-19 12:19
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 + 5*max5 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

Pozostało 580 znaków

2011-10-19 12:40
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.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.

Pozostało 580 znaków

2011-10-19 13:19
0

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


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-10-19 13:22
0

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

Pozostało 580 znaków

2011-10-19 13:48
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?


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2011-10-19 13:49

Pozostało 580 znaków

2011-10-19 13:53
0

http://wazniak.mimuw.edu.pl/i[...]82ad_7:_Funkcje_tworz%C4%85ce
Choć, jak widać, da się zaprząc do tego programowanie dynamiczne.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-10-19 14:01
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ę ;)

Pozostało 580 znaków

2011-10-19 14:15
bo
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?

Pozostało 580 znaków

2011-10-19 14:40
0

Nie ma znaczenia.

Pozostało 580 znaków

2011-10-19 15:25
0

Poszukaj o równaniach diofantycznych i metodzie Eulera.


"Robienie w Javie moge porównac do spuszczania wody w kiblu za pomoca wiadra z wodą przyniesioną ze studni zza 7 gór, którą się dodatkowo samemu wykopało łyżeczką do słodzenia herbaty."

Pozostało 580 znaków

2011-10-20 10:39
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

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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