Wie würde der Greedy Algorithmus für Wechselgeld aussehen? Java?

Hi, wenn man z. B. die Münzen 1,2,5,10,25,50 hat und man erhält immer eine Integer Zahl, die man dann mit Wechselgeld zurück geben muss. Wie würde der Greedyalgorithmus aussehen dafür aussehen in Java? Könnte das mal einer zeigen, habe mir paar Videos angeschaur auch pseudocode aber überhaupt kein Plan wie man das jetzt in Code machen soll, deshalv wäre das cool wenn das einer macht, als verdeutlichung. Danke euch

3 Antworten

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, programmieren, Informatik

08.11.2021, 03:30

Du gehst die Werte in absteigender Folge durch, machst nen divmod und wiederholst bist der Restbetrag 0 ist.

Das klappt genau deswegen, weil jeder Betrag nur durch 2 oder mehr Münzen/Scheine mit kleinerem Nominalwert dargestellt werden kann.

TechPech1984

Nutzer, der sehr aktiv auf gutefrage ist

im Thema Computer

08.11.2021, 03:17

jetzt brauchst du das nur noch in Java übersetzen . das sollte nicht schwer sein , vergleichbare functionen zu schreiben .

https://www.algorithmsandme.com/coin-change-problem-greedy-algorithm/

die lösung steht da ja , wenn du meinst das man z.b. ein "278 euro schein" (scherz) wechseln will in kleiner ;)

oder meinst du die aufgabe anders ;)

LeibnitzRule

08.11.2021, 07:10

Wie auch immer der Algorithmus heißt. Der grundlegende Trick heißt Modulo

Ähnliche Fragen

Java int Variable auf unendlich setzen?

Wir sollen einen Algorithmus zum Thema Graphenalgorithmen programmieren und im Pseudocode werden manche Distanzwerte zu Beginn auf unendlich initialisiert, nur weiß ich nicht wie man das in Java realisiert.

Ich hatte eine Idee es zu umgehen, jedoch kann man die nicht so gut umsetzen, da uns eine Klasse gegeben ist die wir nicht verändern dürfen und dort eine brauchbare Funktion fehlt

...zur Frage

Java BlueJ erkennt long nicht?

Wie auf dem Bild zu sehen ist gab ich eine Zahl ein, die für Integer natürlich zu groß ist aber mit long müsste es doch gehen. Wieso erkennt das Programm nicht, dass ich da long hingeschrieben habe?

...zur Frage

Kleinstmöglichster Betrag ohne Wechselgeld berechnen?

Hallo, ich komme bei einer Hausaufgabe nicht weiter Die Aufgabe lautet:

Liesabyte, die Tochter von Prof. Bytewoman und Byteman, hat von ihrem Taschengeld die folgenden Münzen der in Bytetown verfügbaren Währung Bytecoins gespart: 7, 300, 35, 83, 1, 17, 2, 1, 17, 170, 5

Aufgabenstellung:

Welches ist der kleinst-möglichste Betrag (positiver Integer) den Liesabyte, ohne Wechselgeld entgegenzunehmen, nicht mit Ihrem Ersparten bezahlen kann?
Skizziere formell wie du zu deiner Lösung gekommen bist.

Ich habe jetzt halt keine Ahnung wie ich das machen soll und habe keine Lust das jetzt alles einzeln durchzurechnen. Kann mir einer vielleicht helfen?

...zur Frage

Java: Wie kann ich bei einer Integer-Scanner-Eingabe whitespaces verbieten?

Hallo,

ich habe ein Primzahlberechnungs-programm geschrieben, bei der man eine Zahl eingibt und es sagen soll, ob es eine Primzahl ist. jedoch möchte bei eingaben wie "3 4 23 3" oder " 23 4 1" bei der whitespaces enthalten sind "ungültige Eingabe" angezeigt bekommen. Haben Sie eine Idee wie wie man prüft, ob die Integer-Eingabe whitespaces enthält?

Code:

import java.util.Scanner;

public class Primzahl {
        public static void main(String[] args)
        {
                System.out.println("Gib ne Zahl");
                Scanner scanner = new Scanner(System.in);
                Integer Zahl = scanner.nextInt();

                for (int i = 2; i < Zahl; i++)
                {
                        if (Zahl % i == 0)
                        {
                                    System.out.println(Zahl + " ist keine Primzahl");
                                    break;
                            }
                            else
                            {
                                    System.out.println(Zahl + " ist eine Primzahl");
                                    break;
                            }
                    }
            }
}

...zur Frage

Java große integer?

Wenn man in java folgende rechenoperation hat:

5000^5000 mod 999

Dann wäre das ergebnis ja kleiner als 999 und somit als integer zu speichern

Aber kann java mit 5000^5000 überhaupt rechnen? (Die zahl hat 18000 stellen...)

Habs gerade ausprobiert jetzt kommt da 5005 raus was ja auch nicht sein kann

...zur Frage

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

...zur Frage

Java, wie kann ich 2 Integer in eine Funktion übertragen?

Hallo, ich habe gestern angefangen mit Java und versuche mich grade mit funktionen aueinander zu setzen. Ich weis schon wie man eine variable Importiert aber wie kann man 2 oder mehr Importieren? Die meinenummer ist schon drinn aber die variable "zahl" weis ich nicht wo die hinkommen soll... Danke für jede Hilfe

...zur Frage

Haskell Funktion Frage?

Wenn man eine Funktion erstellen soll, bei der die Funktion zwei Werte nimmt und prüft, ob ein Wert durch den anderen teilbar ist, wie schreibt man das in Haskell als Code?

nehmen wir an:

isDivisible -> Integer -> Integer -> Bool

Wie schaut dann der Rest aus? So?

isDivisible x % y == 0 = true else false

y % x == 0 = true else false?? Das klingt so bescheuert aber ich weiß sonst nicht wie es aussehen sollte! Kann mir da wer weiterhelfen?

Zusätzlich müsste ich dann auch eine Funktion schreiben, die so aussieht:

isPrime -> Integer -> Bool

welches eine Zahl nimmt und ausgibt ob diese eine Primzahl ist oder nicht, dafür soll ich die vorherige Funktion benutzen, jedoch komm ich da eben nicht weiter. Und bei der hier bin ich mir auch nicht sicher, wie würde da der Code aussehen?

...zur Frage

(Java)Wie macht man aus dem String einen Integer?

Ich habe den String : String number = "2y";

Das sollen 2 jahre sein. Wie bekomme ich die Zahl ohne das 'y' heraus?

Integer.parseInt geht nicht!(Denke ich)

...zur Frage

Wie kann man einen String und einen Int gleichzeitig einlesen lassen (Java)?

Hallo ich soll eine Seriennummer eines Geldscheines einlesen inklusive Buchstabe also zb. Z 6016220022-6 (Trennstrich ist nur für die Lesbarkeit) ich weiß aber nicht wie man ein integer mit einer string gleichzeitig einliest in Java ... Normalerweise mach ich das ja immer so :

system.out.println("Geben sie ihre gewünschte Zahl ein:")
    a= Input.nextInt();

das geht hier aber nicht ...

...zur Frage

Random generator java zwischen 1 - 100 Programmieren?

Ich möchte einen Random generator programmieren, der eine Zahl zwischen 1-100 generiert und die man dann erraten soll. Wenn diese Zahl generiert ist wird sie erstmal nicht angezeigt sondern man muss eine Zahl eingeben. So bis hier her schaffe ich es noch, aber bei der if Anweisung verzweifel ich weil ich die Eingabe als String und die Random Zahl als integer gespeichert habe. Kann ich einen String und einen Integer irgendwie in eine if Anweisung packen. Ich kann ja die Random Zahl nicht als String speichern und die Eingabe nicht als Integer. Gibt es irgendeine Möglichkeit beides in einem Datentyp zu speichern?

Sry das ich so viel geschrieben habe :c

...zur Frage

Zahlen von 1-999 in Java in Worten ausgeben?

Guten Abend,

das Ziel ist es in Java die Zahlen von 1 bis 999 in Worten auszugeben. (Bsp. 12=zwölf). Da ich noch recht frisch in Java unterwegs bin soll bei der Aufgabe grundlegend nur mit if- und switch Anweisungen gearbeitet werden. Nun muss man also einen Algorithmus finden. Ich weiß, dass man die Zahl in "einser", "zehner" und "hunderter" aufteilen muss. Jedoch weiß ich nicht wie ich das in Java schreibe und zu einem String zusammenfüge.

Mfg

Metrox

...zur Frage

Wie funktioniert Math.random() in Java?

Math.random() erzeugt eine "zufällige" Zahl zwischen 0 und 1. Aber wie genau wird diese erzeugt. Habe dazu im Internet noch nichts gefunden.

Ich wäre über einen Link dankbar, in dem der Algorithmus erklärt wird, bzw. wie man den Wert vorhersagen kann.

...zur Frage

Wie kann man bei Java ein Integer in einzelne ziffern runterbrechen und jede ziffer in einem eigenen Feld in einem array speichern?

Hallihallo,

ich soll ein programm schreiben, bei dem eine 8 stellige zahl eingelesen wid, die nur aus 4 ziffern besteht und jede ziffer entspricht einem zeichen anschließend soll mein programm die ziffern in die entsprechenden zeichen umwandeln und in die ausgabe schreiben. meine idee war ein array anzulegen, dass 8 felder besitzt und dann quasi für jedes feld zu prüfen welchem zeichen es entspricht ...

wie liest man also eine ganze zahl ein, bricht sie dann in ziffern herunter und speichert jede einzelne zahl in einem array feld?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen