LenyBomba Temat założony przez niniejszego użytkownika |
Zadanie domowe- kasa fiskalna » 2019-12-11 19:59:35 Witajcie! Problem wydaje się łatwy, jednak w rzeczywistości (lub dla mnie) nie jest, musze zaiplikować algorytm dynamiczny który rozwiąże wydawanie reszty w optymalny sposób. Uczę sie programować 2 miesiące, cały kurs z tej strony jak i youtube(Mirosława Zelenta) już za mną, jednak niestety nadal często się gubie i tracę siły... W tym wypadku poddałem się totalnie i potrzebuje pomocy. Na zajęcia z Algorytmów i Struktur danych dostaliśmy zadanie stworzyć kase fiskalną. Kasa ta ma pytać o swój stan>podliczyć sume>obsłużyć klienta wydając reszte w optymalny sposób. No właśnie... optymalny. Na jednych zajęciach profesor już "zgasił" jednego z nas, ponieważ każdy z nas zrobił to zadanie algorytmem zachłannym, a pan profesor dał do kasy 50 zł, 3x 20zł i 10 razy po złotówce. Oczywiście algorytm zamiast użyć tylko 3 nominałów używał ich 11... Od poniedziałku walcze z problemem, rozumiem że musze rozwiązać ten problem dynamicznie, ale niestety po prostu nie umiem... Obejrzałem mase filmików na YouTube o problemie plecakowym itd. niestety nadal nie jestem w stanie poradzić sobie z problemem Mój kod na ten moment wygląda tak #include <iostream>
#include <cstdlib>
#include <conio.h>
#define INFINITY 2147483647
using namespace std;
struct Banknot {
string nazwa;
float wartosc;
int ilosc[ 15 ];
};
float Suma( Banknot kasa[], int n )
{
float suma = 0;
for( int i = 0; i < n; i++ )
{
suma += kasa[ i ].ilosc[ i ] * kasa[ i ].wartosc;
}
return suma;
}
int wpisz( Banknot kasa[], int n )
{
for( int i = 0; i < n; i++ )
{
cout << "Ile banknotow warosci " << kasa[ i ].nazwa << " ma byc w kasie" << endl;
cin >> kasa[ i ].ilosc[ i ];
}
}
int SumaNom( Banknot kasa[], int iLiczb )
{
int SumaNom = 0;
for( int i = 0; i < iLiczb; i++ )
{
SumaNom += kasa[ i ].ilosc[ i ];
}
return SumaNom;
}
int main()
{
int ilosc[ 15 ];
Banknot kasa[ 15 ] = {
{ "500", 500, ilosc[ 0 ] },
{ "200", 200, ilosc[ 1 ] },
{ "100", 100, ilosc[ 2 ] },
{ "50", 50, ilosc[ 3 ] },
{ "20", 20, ilosc[ 4 ] },
{ "10", 10, ilosc[ 5 ] },
{ "5", 5, ilosc[ 6 ] },
{ "2", 2, ilosc[ 7 ] },
{ "1", 1, ilosc[ 8 ] },
{ "0.5", 0.5, ilosc[ 9 ] },
{ " 0.2", 0.2, ilosc[ 10 ] },
{ "0.1", 0.1, ilosc[ 11 ] },
{ "0.05", 0.05, ilosc[ 12 ] },
{ "0.02", 0.02, ilosc[ 13 ] },
{ "0.01", 0.01, ilosc[ 14 ] },
};
wpisz( kasa, 15 );
float suma = Suma( kasa, 15 );
int Sumanominalow = SumaNom( kasa, 15 );
cout << "w kasie jest : " << suma << "PLN w " << Sumanominalow << " nominalach \n";
cout << "ile pieniedzy wydajemy :) ?" << endl;
float wydatek, reszta;
cin >> wydatek;
reszta = suma - wydatek;
cout << "reszta to " << reszta;
Niestety nawet nie wiem jak zaimplikować gotowca z Wikipedii... Czy mógłby mi ktoś pomóc z problemem? Mam czas do piątku i obawiam się że sobie nie poradzę, tym bardziej że jutro czeka mnie nauka na kolokwium z Informatyki (na szczęście to tylko wstęp i materiał uważam za prosty)[/i] |
|
pekfos |
» 2019-12-11 20:48:46 Wyrzuć wszystkie nominały zaczynające się na 2, albo wszystkie zaczynające się na 5 i algorytm zachłanny będzie optymalny. Problem jest z wyborem miedzy 20 a 50, bo jedno nie jest wielokrotnością drugiego. Nie ma też sensu brać 5 dwudziestek, gdy można dwie pięćdziesiątki, więc bierz 50 zł, ale w wielokrotnościach 20. Gdy zostaje mniej niż 100, trzeba spróbować wszystkich możliwości (20, 40, 50, 60, 50+20, 50+40) i dla nich zobaczyć, która reszta będzie lepiej się układać z niższymi nominałami. Gałęzie powstającego drzewa możesz ucinać metodą "alfa-beta" (nie ma czego min-maksować, więc wystarczy porównywać z globalnym minimum).
Tak na boku: nie używaj liczb zmiennoprzecinkowych do pieniędzy! Chyba że też chcesz być zgaszony przez profesora przy sprawdzaniu zadania. Pieniądze możesz bezpiecznie wyrazić ich wartością w groszach. |
|
LenyBomba Temat założony przez niniejszego użytkownika |
» 2019-12-12 18:47:47 #include <iostream>
#include <cstdlib>
#include <conio.h>
#define INFINITY 2147483647
using namespace std;
struct Banknot {
string nazwa;
int wartosc;
int ilosc[ 15 ];
};
int Suma( Banknot kasa[], int n )
{
int suma = 0;
for( int i = 0; i < n; i++ )
{
suma += kasa[ i ].ilosc[ i ] * kasa[ i ].wartosc;
}
return suma;
}
int wpisz( Banknot kasa[], int n )
{
for( int i = 0; i < n; i++ )
{
cout << "Ile banknotow warosci " << kasa[ i ].nazwa << " ma byc w kasie" << endl;
cin >> kasa[ i ].ilosc[ i ];
}
}
int SumaNom( Banknot kasa[], int iLiczb )
{
int SumaNom = 0;
for( int i = 0; i < iLiczb; i++ )
{
SumaNom += kasa[ i ].ilosc[ i ];
}
return SumaNom;
}
void WypiszNom( Banknot kasa[], int iLiczb )
{
for( int i = 0; i < iLiczb; i++ )
cout << kasa[ i ].ilosc[ i ] << " sztuk(a/i) " << kasa[ i ].nazwa << endl;
}
int main()
{
int ilosc[ 15 ];
Banknot kasa[ 15 ] = {
{ "500 PLN", 50000, ilosc[ 0 ] },
{ "200 PLN", 20000, ilosc[ 1 ] },
{ "100 PLN", 10000, ilosc[ 2 ] },
{ "50 PLN ", 5000, ilosc[ 3 ] },
{ "20 PLN", 2000, ilosc[ 4 ] },
{ "10 PLN", 1000, ilosc[ 5 ] },
{ "5 PLN", 500, ilosc[ 6 ] },
{ "2 PLN", 200, ilosc[ 7 ] },
{ "1 PLN", 100, ilosc[ 8 ] },
{ "0.5 PLN", 50, ilosc[ 9 ] },
{ "0.2 PLN", 20, ilosc[ 10 ] },
{ "0.1 PLN", 10, ilosc[ 11 ] },
{ "0.05 PLN", 5, ilosc[ 12 ] },
{ "0.02 PLN", 2, ilosc[ 13 ] },
{ "0.01 PLN", 1, ilosc[ 14 ] },
};
wpisz( kasa, 15 );
float suma = Suma( kasa, 15 );
int Sumanominalow = SumaNom( kasa, 15 );
cout << "w kasie jest : " << suma / 100 << "PLN w " << Sumanominalow << " nominalach \n";
WypiszNom( kasa, 15 );
cout << "ile pieniedzy wydajemy ?" << endl;
float wydatek, reszta;
cin >> wydatek;
wydatek = wydatek * 100;
reszta = suma - wydatek;
cout << "reszta to " << reszta / 100;
Poprawiłem na grosiki, dziękuje bardzo za uwage. Niestety mamy z góry założone że problem ma być rozwiązany algorytmem dynamicznym, a w tym temacie po prostu kuleje i to strasznie. Mieliśmy o tym jeden wykład, czasu na zrozumienie/przyswojenie tematu brak... Kombinuje na ślepo z kodem z Wiki, ale nawet nie moge ruszyć programu int * T = new int[ reszta + 1 ];
T[ 0 ] = 0;
for( int i = 1; i <= reszta; i++ )
T[ i ] = INFINITY;
for( int i = 1; i < 15; i++ )
{
kasa[ i ].wartosc;
}
for( int j = 0; j <= reszta - kasa[ i ].wartosc; i++ )
{
if( T[ j ] < INFINITY )
{
if( T[ j ] + 1 < T[ j + kasa[ i ].wartosc )
T[ j + n ] = T[ j ] + 1;
}
}
Znalazłem również temat " http://cpp0x.pl/forum/temat/?id=24036 " z podobnym problemem, tylko nawet jeśli zaimplikowałbym jakimś cudem rozwiązanie do mojego programu to nadal nie byłoby to co Profesor oczekiwał... Bo stan kasy musi sie aktualizować. Przepraszam bardzo za moja głupkowatość w temacie, dopiero zaczynam swoją przygodę z kodem, a to mnie przerasta |
|
darko202 |
» 2019-12-13 09:33:34 1. zacznij od przeczytania http://www.cs.put.poznan.pl/arybarczyk/TeoriaAiSD3.pdfjest tam dokładnie wytłumaczona idea algorytmu dynamicznego tzn. " Proces projektowania algorytmu opartego na programowaniu dynamicznym mozna podzielić na cztery etapy: 1) Scharakteryzowanie struktury optymalnego rozwiązania. 2) Rekurencyjne zdefiniowanie kosztu optymalnego rozwiązania. 3) Obliczenie optymalnego kosztu metodą wstępującą (ang. bottom-up) – czyli rozpoczynając od najmniejszych podproblemów, rozwiązywać coraz większe, wykorzystując zapamiętane rozwiązania mniejszych. 4) Konstruowanie optymalnego rozwiązania na podstawie wyników wcześniejszych obliczeń. " jest też pokazana różnica w stosunku do metody zachłannej która jest prostym algorytmem liniowym gdy algorytm dynamiczny rozpina drzewa możliwych rozwiązań dlatego w realizacjach tego algorytmu używa się tablic wielowymiarowych np. http://algorytmy.ency.pl/artykul/problem_wydawania_reszty_programowanie_dynamicznenie sprawdzałem, czy zaprezentowana implementacja jest tym opisywanym algorytmem dlatego musisz to zrobić sam 2. inną sprawą jest sprawność operowania językiem C++ którego się uczysz zwróć uwagę na kasa[ i ].ilosc[ i ] - nie ma sensu ( odwołujesz się do i- tego elementu pole ilość - a coś takiego nie istnieje) kasa[ i ].ilość - ma sens ( odwołujesz się do pole ilość i elementu tablicy w zmiennej kasa ) 3. każdy kompilator zawsze zwraca komunikaty - czytanie ich i zrozumienie wiele rozjaśnia (np. nam z czym masz problem) przydaje się też poznać i korzystać z techniki debugowania kodu stosowanie tego ułatwi Ci to życie (programowanie) w 99% Powodzenia |
|
LenyBomba Temat założony przez niniejszego użytkownika |
» 2019-12-15 10:00:21 #include <iostream>
#include <cstdlib>
#include <conio.h>
using namespace std;
struct Banknot {
string nazwa;
int wartosc;
int ilosc;
};
int Suma( Banknot kasa[], int n )
{
int suma = 0;
for( int i = 0; i < n; i++ )
{
suma += kasa[ i ].ilosc * kasa[ i ].wartosc;
}
return suma;
}
int wpisz( Banknot kasa[], int n )
{
for( int i = 0; i < n; i++ )
{
cout << "Ile banknotow/monet wartosci " << kasa[ i ].nazwa << " ma byc w kasie" << endl;
cin >> kasa[ i ].ilosc;
}
}
int SumaNom( Banknot kasa[], int iLiczb )
{
int SumaNom = 0;
for( int i = 0; i < iLiczb; i++ )
{
SumaNom += kasa[ i ].ilosc;
}
return SumaNom;
}
void WypiszNom( Banknot kasa[], int iLiczb )
{
for( int i = 0; i < iLiczb; i++ )
cout << kasa[ i ].ilosc << " sztuk(a/i) " << kasa[ i ].nazwa << endl;
}
int zmieniarkadynamiczna( int reszta1, Banknot kasa[], int C[], int s[] )
{
C[ 0 ] = 0;
for( int j = 1; j <= reszta1; j++ ) {
C[ j ] = INT_MAX;
for( int i = 0; i < 15; i++ ) {
if( j >= kasa[ i ].wartosc && 1 + C[ j - kasa[ i ].wartosc ] < C[ j ] &&( kasa[ i ].ilosc >= 1 ) ) {
C[ j ] = 1 + C[ j - kasa[ i ].wartosc ];
s[ j ] = i;
}
}
}
return C[ reszta1 ];
}
int main()
{
int ilosc = 0;
Banknot kasa[ 15 ] = {
{ "1 grosza", 1, ilosc },
{ "2 groszy", 2, ilosc },
{ "5 groszy", 5, ilosc },
{ "10 groszy", 10, ilosc },
{ "20 groszy", 20, ilosc },
{ "50 groszy", 50, ilosc },
{ "1 PLN", 100, ilosc },
{ "2 PLN", 200, ilosc },
{ "5 PLN", 500, ilosc },
{ "10 PLN", 1000, ilosc },
{ "20 PLN", 2000, ilosc },
{ "50 PLN ", 5000, ilosc },
{ "100 PLN", 10000, ilosc },
{ "200 PLN", 20000, ilosc },
{ "500 PLN", 50000, ilosc },
};
wpisz( kasa, 15 );
float suma = Suma( kasa, 15 );
int Sumanominalow = SumaNom( kasa, 15 );
cout << "w kasie jest : " << suma / 100 << "PLN w " << Sumanominalow << " nominalach \n";
WypiszNom( kasa, 15 );
cout << "ile pieniedzy wydajemy ?" << endl;
float wydatek, reszta;
cin >> wydatek;
wydatek = wydatek * 100;
reszta = suma - wydatek;
cout << "reszta to " << reszta / 100 << "zl" << endl;
int reszta1 = reszta;
int * C = new int[ reszta1 + 1 ];
int * s = new int[ reszta1 + 1 ];
int minim = zmieniarkadynamiczna( reszta1, kasa, C, s );
cout << "minimalna liczba monet= " << minim << endl;
cout << "uzyte monety: ";
int k = reszta1;
while( k ) {
double b = kasa[ s[ k ] ].wartosc;
cout << b / 100 << " ";
k = k - kasa[ s[ k ] ].wartosc;
}
delete[] C;
delete[] s;
return 0;
} Dzięki wielkie. Faktycznie, dzieki Tobie zrozumiałem strukturę i to jak na niej działać... Algorytm napisany, test profesora zaliczy, ale mnie to nie satysfakcjonuje. Otóż maszyna nie działa dla groszy... Dając mu 10 razy grosika, 3 razy 20 groszy i raz 50 groszy wydaje za pomoca 11 monet omijajac calkowicie 20gr. Nie moge znaleźć powodu dlaczego, każda kwota liczona jest na intach i wypisywana jako float/double po to aby bylo to zrozumiale dla uzytkownika. edit>>poprawiłem cout<<"ile pieniedzy wydajemy ?"<<endl; float wydatek,reszta; cin>>wydatek; wydatek=wydatek*100; reszta=suma-wydatek; na float wydatek,reszta; cin>>wydatek; wydatek=wydatek*100; wydatek=(int)wydatek; reszta=suma-wydatek; i działa. Dziękuje bardzo @darko202 i @pefkos za pomoc, bez was już bym sie poddał. Mógłby ktoś ocenić powyższy algorytm... bo nawet nie wiem czy znajdują sie tam jakieś błedy/można było coś lepiej zapisać Profesor nawet nie zajrzał w kod więc nie mam pojęcia czy nie ma tam takich giga błedów typu ilosc[] |
|
darko202 |
» 2019-12-16 10:19:57 1.
mogę tylko powtórzyć
"zapoznaj się z techniką debugowania kodu"
oglądasz bieżący stan każdej zmiennej - widzisz gdy program nie robi tego czego się po nim spodziewałeś
2.
analizując tylko kod widzę
kasa.wartosc może mieć wartości od 1 do 50000
j ?
(int j = 1; j <= reszta1; j++ )
stąd odwołanie
C[ j - kasa[ i ].wartosc ];
wydaje się sięganiem często poza zakres tablicy
|
|
| « 1 » |