Wydawanie reszty dynamicznie

Wydawanie reszty dynamicznie
0

Siemka. Mam takie zadanie, by za pomocą programowania dynamicznego wydać resztę.
Takie bardzo dynamiczne też to nie ma być, gdyż operować ma na tablicy zwykłej, o określonych rozmiarach, np. 101 elementów - czyli od 0 do 100 groszy. Ma również zwrócić ilość monet o konkretnych nominałach.
Mam tablicę nominałów - o nazwie nominały. 6 elementów typu byte. Są to {1,2,5,10,20,50}.
Czyli z tego co sądzę - ma po kolei od 0 do kwoty sprawdzać iloma to monetami można wydać, ale jakoś ma sprawdzać ile tych monet potrzeba. Jak?/

Kopiuj
for i:=0 to kwota do
begin
  if kwoty[i] <> nies then
  begin
    if (kwoty[i]+ 1) < kwoty[i+1] then
      kwoty[i+1]:=kwoty[i]+1;
  end;
end;

nies - to wartość stała - nieskończoność - są tą wartością wypełnione wszystkie elementy oprócz pierwszego tablicy kwoty
tablica kwoty - zawiera iloma monetami można tą kwotę wydać.

edytowany 1x, ostatnio: flowCRANE
0

No to tak. Udało mi się napisać odpowiednią procedurę według algorytmu opisanego tutaj: http://pl.wikipedia.org/wiki/Problem_wydawania_reszty#Algorytm_z_wykorzystaniem_programowania_dynamicznego
I tak jak być powinno - program liczy dobrze ilość monet potrzebnych do wydania reszty. Ale jak mam zrobić by wyświetlić ilość monet konkretnych nominałów, czyli np. dla kwoty 25 gr, ma być 1gr - 0szt. 2gr-0szt., 5gr - 1szt. 20gr - 1szt.
Zrobiłem tablicę dwuwymiarową - od 0 do kwoty oraz od 1 do 6 - ilość nominałów. Tam chcę zapisać ilość konkretnych nominałów.

_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:2 miesiące
0

Robisz tablicę struktur { size_t count,moneta; } jak wpisujesz do count ilość to do moneta wpisujesz którą monetę dodałeś.
więc u ciebie będzie:
Tb[25]={2,20}
Tb[5]={1,5} -> 5 = 25 - 20
Tb[0]={0,0} -> 0 = 5 - 5


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
0

No ja jednak problem z tym mam.
Ja to miałem zamiar zrobić na tej dwuwymiarowej tablicy, ale wyniki wychodzą nieprawidłowe, bo nie wiem jak wczytać poprzedni wynik, na którym "bazuję".

_13th_Dragon
- Gwoździe lepiej wbijać młotkiem. - No ja jednak problem z tym mam. Ja to miałem zamiar wbijać głową ale wyniki są marne ...
0

Rozumiem, Twoje rozwiązanie jest pewnie lepsze, ale...
Dla mnie ten przyklad jest troche niezrozumialy - nie wiem jak sie do tego zabrac.

_13th_Dragon
W count wpisujesz to co wpisywałeś dotychczas, zaś w moneta wpisujesz użytą monetę. Co tu niezrozumiałego?
TO
  • Rejestracja:prawie 20 lat
  • Ostatnio:ponad 4 lata
0

Thiago - masz do wydania 26 "czegoś". Lecisz sobie w pętli - stoisz na nominale np. 50. Sprawdzasz ile razy możesz podzielić 26 div 50 - 0, więc wpisujesz przy nominale 50 wartość 0. Idziesz do kolejnego nominału - 20. Dzielisz 26 mod 20 - wychodzi 1 - wpisujesz przy 20 wartość 1, a od kwoty reszty odejmujesz 20*(26 div 20) - zostaje ci 6 "do wydania. Idziesz do kolejnego nominału - 10. Dzielisz 6 div 10 zostaje ci 0. Przy nominale 10 wpisujesz 0. Idziesz do nominału 5. Dzielisz 6 div 5 - otrzymujesz 1. Od kwoty reszty (6) odejmujesz 5*(6 div 5) - zostaje ci 1. Idziesz do nominału 2. 1 div 2 = 0. przy nominale 2 wpisujesz 0. Idziesz do nominału 1. 1 div 1 = 1. Przy nominale 1 wpisujesz 1, a od kwoty reszty odejmujesz 1*(1 div 1). Zostaje ci 0 do wydania.

oczywiście - po drodze warto dorobić zabezpiczenie przed nadmiermym sprawdzaniem, jeżeli wyższymi nominałami uda ci sie wcześniej wydać (np mając do wydania 50 - resztę wydasz już w pierwszym kroku).

Tym mechanizmem załatwisz też ilość dostępnych sztuk elementów danego nominału (banknotów, bilonu czy orzeszków ziemnych) - wystarczy, że będziesz miał zmienną informującą o ilości dostępnych elementów danego typu, a przy odejmowaniu odejmiesz nie więcej niż to co jest dostępne.

edytowany 1x, ostatnio: toyman
_13th_Dragon
Ten algorytm nie działa przy dziwnych nominałach, np 1,5,7 kwota 10 wg tego algorytmu będzie 7+1+1+1 zaś lepiej jest 5+5. Dla takiego rodzaju zadań służą algorytmy dynamiczne.
TO
Widzę, że musze uzupełnić sporą działkę wiedzy.
wb2000
@toyman: Niczego nie musisz. To nie Twój problem. To problem Thiago - to ON musi doczytać. Miałeś dobrą wolę, aby pomóc rozwiązać niejasno (źle!) postawiony problem, poświęciłeś swój czas, a nikt Ci nawet nie podziękował. Parę lat temu poszedłem do Biblioteki Uniwersyteckiej w Warszawie i popatrzyłem na setki regałów z książkami w wielodostępie - tysiące książek - i wtedy doznałem "oświecenia": nawet, gdybyś spędził tu resztę życia, dzień i noc, to i tak nie przeczytasz wszystkich tych książek. Życie jest jednak zbyt krótkie, aby móc zajmować się wszystkim.
TO
Ale ja nie oczekiwałem tyrad pochwalnych. Odpisuję jak mogę. Jak nie mogę to się nie odzywam. Nie spodziewam się, że ktoś mnie będzie chwalił i wielbił, bo napisałem dwa słowa. Temat programowania dynamicznego wydaje się dawać skuteczne rozwiązania tam, gdzie klasyczne podejście algorytmiczne nie jest idealne (miałem kilka takich przypadków, że przyjąłem metodę uproszczoną, obarczoną kilkoma założeniami, która produkowała przeciętne efekty)
wb2000
@toyman: Bez obrazy. Przeczytaj uważnie, jeszcze raz pierwsze wpis Thiango powyżej kodu. Twoje rozwiązanie jest prawidłowe dla tak postawionego problemu - nominały są podane explicite, więc nie ma żadnych "dziwnych" i algorytm dynamiczny nie jest tu potrzebny. Podałeś rozwiązanie najprostsze. Prawdziwy problem jest taki, czy autor zadania (nauczyciel w szkole?) wprost zlecił algorytm dynamiczny do rozwiązania tego problemu, czy sam Thiango wymyślił sobie, że zrobi to "dynamicznie". Gdyby autor chciał algorytmu dynamicznego, to właśnie dałby "dziwne" nominały, a nie dał.
TO
Ale czym ty się stresujesz ? Cztery dni od ostatniego wpisu Thiago do mojej odpowiedzi to dość czasu, żeby sobie poradzić. Równie dobrze mogłem kłuć dawno zimnego kotleta. Na prawdę nie ma powodu, żeby angażować się emocjonalnie w mało ważną kwestię.
wb2000
@toyman: Chodzi o sposób myślenia. Przez chwilę wyobraziłem sobie, że jesteś moim szefem... Ale czy człowiek, który nie szanuje swojej pracy potrafiłby uszanować moją?
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)