rozbijanie podanej kwoty na liczbe banknotow i monet

0

witam, mam napisac program ktory rozbija podana kwote na minimalna liczbe banknotow i monet;

int liczba_zlotych;
int zl[8] ={0};

int tab_zl[8] ={200,100,50,20,10,5,2,1};

for (int i=0;i<8;i++)
{
    zl[i] = liczba_zlotych/tab_zl[i];
    liczba_zlotych -= zl[i]*tab_zl[i];
}

czy to jest poprawne myslenie ??

ma ktos moze jakis pomysl i moze pomoc dziekuje

0

jeżeli masz nieograniczoną liczbę każdego z nominałów to w ten sposób użyjesz ich najmniej.
można to zrobić oczywiście na wiele sposobów. i np. 388 można rozmienić na 1 677 713 sposobów
jFGya

0

Najlepiej będzie chyba sprawdzać od największego nominału, sprawdzać mniejsze itd. np. 355zł
100zł, 100zł, 100zł, (kolejna setka się nie mieści więc sprawdzamy 50-tki)
50zł, (kolejna 50-tka się nie mieści, sprawdzamy 10, potem piątki)
5zł (i mamy naszą liczbę, więc wychodzimy z pętli)


int licznik = kwota = x; //za x wstaw kwotę do rozbicia 
int il_setek=0,il_piecdziesiatek=0, il_dziesiatek=0, il_piatek=0, il_dwojek=0, il_jedynek=0;
while(licznik>=100)
{
     il_setek+=1;
     licznik = licznik - 100;
}
while(licznik>=50)
{
     il_piecdziesiatek+=1;
     licznik = licznik - 50;
}
while(licznik>=10)
{
     il_dziesiatek+=1;
     licznik = licznik - 10;
}
while(licznik>=5)
{
     il_piatek+=1;
     licznik = licznik - 5;
}
while(licznik>=2)
{
     il_dwojek+=1;
     licznik = licznik - 2;
}
while(licznik>=1)
{
     il_jedynek+=1;
     licznik = licznik - 1;
}
//tutaj wyświetl sobie zmienne il_* które wyświetlą Ci nominały w takiej ilości, aby było ich najmniej. 
0

Podejdz do tego problemu algorytmami genetycznymi.

0

Algorytm wydawania reszty:

  • jeśli nominały spełniają pewne wymagania to wystarczy algorytm zachłanny (to co napisałeś)
  • w innym przypadku algorytm dynamiczny
    Kiedy algorytm zachłanny nie zadziała poprawnie? Załóżmy że masz nominaly takie jak PLN, ale nie masz 1 zł i próbujesz wydać 6 złotych
    Twój algorytm spróbuje wydać 5 + X ale nie ma 1zł, więc algorytm sie "wysypie". Algorytm dynamiczny poradziłby sobie i wydał 2+2+2.

Jeśli więc nominały spełniają pewne wymagania i masz nieograniczoną ilość każdego nominału to mozesz robic tak jak robisz. Jeśli nie, to musisz napisać rozwiązanie dynamiczne.

0

Jak masz tylko po jednym banknocie:

 #include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#define ui unsigned int
int main() {
    ui lbanknotow;
    scanf("%u", &lbanknotow);
    std::vector<unsigned int>W;
    W.resize(lbanknotow);
    for(ui i=0; i<lbanknotow; i++)
        scanf("%u", &W[i]);
    std::sort(W.begin(), W.end());
    ui wydaj;
    scanf("%u", &wydaj);
    ui tab[wydaj+1];
    memset(tab, 1, (wydaj+1)*sizeof(unsigned int));
    tab[0]=0;
    for(; W.size()>0; W.pop_back())
    {
        for(int i=wydaj-W.back(); i>0; i--)
            if(i>0)
                if(tab[i]<16843009 && tab[i+W.back()]>tab[i])
                    tab[i+W.back()]=tab[i]+1;
        tab[W.back()]=1;
                if (tab[wydaj]!=16843009) break;
    }           
    if(tab[wydaj]==16843009)
    {
        printf("-1");
        return 0;
    }
    printf("%u", tab[wydaj]);
} 

Jak masz nieograniczoną liczbę banknotów:

 #include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#define ui unsigned int
int main() {
    ui lbanknotow;
    scanf("%u", &lbanknotow);
    std::vector<unsigned int>W;
    W.resize(lbanknotow);
    for(ui i=0; i<lbanknotow; i++)
        scanf("%u", &W[i]);
    std::sort(W.begin(), W.end());
    ui wydaj;
    scanf("%u", &wydaj);
    ui tab[wydaj+1];
    memset(tab, 1, (wydaj+1)*sizeof(unsigned int));
    tab[0]=0;
    for(; W.size()>0; W.pop_back())
    {
        for(ui i=0; i<=wydaj-W.back(); i++)
            if(tab[i]<16843009 && tab[i+W.back()]>tab[i])
                    tab[i+W.back()]=tab[i]+1;
        tab[W.back()]=1;
            if(tab[wydaj]!=16843009)
                break;
    }           
    if(tab[wydaj]==16843009)
    {
        printf("-1");
        return 0;
    }
    printf("%u", tab[wydaj]);
} 

Dane pobierane ze standardowego wejścia: liczba banknotów, później nominały, na końcy kwota do wydania.

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