Bankomat-Pascal

C++, C#, Visual Basic, Delphi, Perl a ostatní

Moderátor: Moderátoři Živě.cz

Odeslat příspěvekod lucas.navratil 22. 3. 2010 16:49

Zdravím,
mám menší problém. Pokouším se delší dobu naprogramovat v Pascalu bankomat, kterej rozměňuje prachy. Zkouším, aby mi vypsal veškerý možný kombinace rozměnění 100 korun. Rekurzivně, nikoliv standartně. Přikládám zdrojový kód, program se spustí a vypíše hodnoty, nicméně kombinace se opakují a já se potřebuji zbavit toho opakování. Díky za pomoc.

Kód: Vybrat vše
program rozmenovac;

{$APPTYPE CONSOLE}
uses SysUtils;

const castka=100;
     platidla: array [1..6] of integer = (50,20,10,5,2,1);


var a:integer;
   prvSez:array [1..6] of integer;
   pocet:integer;

procedure rozmen (zbyvCastka,poslCastka:integer;seznam:array of integer);
var i,j,pamet:integer;
begin

if zbyvCastka = 0 then
begin
   for i:=1 to 6 do write (seznam[i],',');
   writeln ('');
   inc (pocet);
end
else
begin

   for i:= (poslCastka+1) to 6 do
   begin
     for j:= 1 to (zbyvCastka div platidla[i]) do
     begin
      seznam[i]:=j;
       rozmen (zbyvCastka-j*platidla[i],i,seznam);
       seznam[i]:=0
     end;
   end;
end;

end;

begin
pocet:=0;
writeln ('Seznam castek v poradi 50,20,10,5,2,1');
for a:= 1 to 6 do prvSez [a]:=0;
rozmen (100,0,prvSez);
readln;

end.
Naposledy upravil Bari007 dne 22. 3. 2010 17:36, celkově upraveno 1
Důvod: Kód vložen do [code]
lucas.navratil
Kolemjdoucí

Odeslat příspěvekod gandor 22. 3. 2010 17:27

viewtopic.php?f=922&t=929499
Neviem si vysvetlit ziaden iny dovod, preco by sa tento priklad mal riesit cez rekurziu, ktoru by som tam musel umelo cpat (a riesenie bolo efektivne)...

Ale ak mi ten dovod vysvetlis, alebo ak budes chciet len konkretne nejaku cast vysvetlit, tak ti rad pomozem ;)

ps. je vhodne pouzivat [code][/code] tagy
gandor
Mírně pokročilý

Odeslat příspěvekod lucas.navratil 22. 3. 2010 17:40

No měli sme to v loňským semestru sice, ale už je dávno po........standartní cestou sem to nějak měl, ale zajímalo by mě to přes tu rekurzi.......výsledky to vypisuje, algoritmus je podle mě dobře, jen nechápu proč to vypisuje ty hodnoty tolikrát a ne jednou vždycky......kde je chyba, v tom celočísleným dělení nebo kde?:-)
lucas.navratil
Kolemjdoucí

Odeslat příspěvekod Wikan 22. 3. 2010 17:49

Podle mě nesmyslně mixuješ rekurzivní a nerekurzivní přístup.
Buď to procházej v cyklu
Kód: Vybrat vše
for i:= (poslCastka+1) to 6 do
nebo to dělej rekurzivně
Kód: Vybrat vše
rozmen (zbyvCastka-j*platidla[i],i,seznam);
Pokud ale budeš dělat obojí, tak se nemůžeš divit, že ti to bude vypisovat víckrát.
Wikan
Moderátor
Uživatelský avatar

Odeslat příspěvekod Myffis 22. 3. 2010 18:09

no rekurze je na to naroubovaná no ale rekurze byla taky v zadání :) mám dojem že delphi prostě přepíšou při návratu z rekurze to j na jedničku respektvě nedovolej tomu foru pokračovat na větší číslo když sem si to ladil s postupnym výpisem třeba pro nižší částku 4 tak to jelo takhle

dvojice i j sipka tam zpet de do dalsi rekurze nebo zpět:

(1,0)(2,0)(3,0)(4,0)(5,1) -> (6,1) (6,2 vypis) <- ale ted nastane ten problem opet je hodnota (5,1) -> (6,1) (6,2 vypis ale ten uz byl) <- (6,1) (6,2 ... atd ted proste napise rozmenění 4 jedniček a skončí ...

proč ale neezvýšil ten for hodnotu j po navratu z rekurze vnitřní parametry rekurze mi její pozdější prvky přece nemůžou přepsat (pokud to neni fce a nevrací se v podobě hodnoty ... ale chová se to jako by se to přepisovalo
Myffis
Kolemjdoucí

Odeslat příspěvekod Nargon 22. 3. 2010 19:45

Mno ja jsem mozna natvrdlej, ale jake je presne zadani?
Kdyz mu zadas 100, tak chces aby ti vyplivnul vsechny mozny kompinace, kterejma tu stovku das dohromady. Tj 2x50 nebo 50+2x20+10 nebo 50+20+3x10 ... az 100x1?

A v tomto ti vadi duplicity?
Pokud ti to jinak pocita spravne, tak osobne bych to resil tak ze bych si vytvoril nejakej seznam tech vystupu (tj hned nevypisovat, ale vsechno cpat do toho seznamu) a pak ten seznam seradit, vyhodit duplicity (diky serazeni budou vzdy zasebou) a zbytek vypsat.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod gandor 23. 3. 2010 00:32

To je principialne zly a neoptimalny postup...

Len tak z hlavy:
Normalne logicke riesenie je vo while cykle zamienat vsetky moznosti od najmensiej po najvecsiu a tie postupne vypisovat (potom nieje nutne starat sa o duplicity, lebo sa k vecsim cislam nikdy nevracias)...
Pokial to ale nasilu musim riesit cez rekurziu, tak by som pouzil nieco, co by sa trochu podobalo prehladavaniu do hlbky. Rekurzia by prijimala 3 parametre (alebo len 1 ak by bolo povolene pouzit 2 globalne premenne - IMO lepsie riesenie) a to dynamicke (nie staticke, neexistuje maximalna dlzka, kedze aj limit = 100 nieje fixny) pole doteraz pouzitych cisiel (toto je jediny povinny parameter), celkovy sucet ktory to ma dosiahnut (t.j. teraz cislo 100) a pole existujucich bankoviek...

Rekurzia by fungovala tak, ze by sa vzdy pokusila vlozit co najvecsii prvok z pola bankoviek (a postupne mensi a mensi) do pola z pouzitimy bankovkami a ak je sucet vlozenych bankoviek < ako sucet dosiahnutia, tak by sa zavolala x krat dana rekurzia vzdy z polom doteraz vlozenych prvkov + skusaneho a vsetkych mensich (x je teda pocet bankoviek - pocet tie ktore sposobia presiahnutie hranice [suctu celeho pola] = hodnoty 100)
pokial je sucet vlozenych bankoviek = sucetu dosiahnutia (hodnoty 100) tak sa vypise, inak koniec rekurzie....

Teraz staci tento text prepisat do pascalu. Ten si zial moc dobre nepamatam a uprimne, nechce sa mi spominat si (uz na neho nemam ani ziaden kompilator a kvoli tomuto nejaky stahovat)... O:-)
V C by som to vedel (relativne) lahkon napisat...

Stale plati, ze riesenie cez rekurziu je neoptimalne, ale je to jedine dalsie "rozumne" riesenie ktore mi napadlo. V kazdom pripade zoradovat pole a vyhadzovat duplicity to fakt nieeee. Taketo quickfixi (lebo 1 nikdy nestaci...) casto krat nezachytia/dodatocne vytvoria chyby, ktore sa neodladia ani za 2x tak dlhy cas ako by sa napisalo cele zadanie od zaciatku (vravim zo skusenosti. 3 sme mali identicke zadanie, ja a dalsi sme to spravili spravne a tretiemu sme riesili kod a ani za 3 hodky sme ho neopravili... To ja osobne som ten kod pisal len 2 hodiny)...

ps. verim, ze zo slovneho opisu sa to tazko chape, ale tak hadam sa aspon zakladna idea sa dala pochopit. Pripadne sa pokusim lepsie vysvetlit ked bude zaujem o niektoru cast... :))
gandor
Mírně pokročilý

Odeslat příspěvekod IgnorStoupa 23. 3. 2010 10:03

Rekurzi lze udelat - a je optimalni reseni pro neznamou menu (kdy nevime, jaky sytem pouziva) - tedy na 1,2,5, ci 1, 2.5, 5 nebo 1,3,5.
Dokonce je funkcni pro mix systemu.

Rekurze se vola s dvema parametry - bankovkou a vektorem pripustnych nizsich bankovek/minci. V dalsim kroku se pak vola procedura bankomatu se "zbytkovou" bankovkou po odebrani nejvyssi pripustne bankovky a zkousi se primy match existujici bankovkou (nalezena distribuce, tisk) a volanim procedury pro "zbytkovou" bankovku. Kazde dalsi volani procedury tak znamena bud nalezeni dalsi distribuce nebo konec. A pak se jede rekurze pro vektor bankovek s odebranou nejvyssi atd. az do nejnizsi bankovky. Vlastne jsou to dva typy vnorene rekurze - rozklad existujici a odebrani dalsiho typu bankovky z distribuce. Aspon takhle nejak se to resilo pred 20 lety jako skolni priklad. Jde to variace kombinatoriky / nechci opakovani, proto se vylucuje z vektoru bankovek.
Neni dano vubec nic. Sestrojte parabolu.
IgnorStoupa
Mírně pokročilý
Uživatelský avatar


Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 0 návštevníků