Java Programm

[vera]

Hey Zusammen,

ich studiere BWL und muss ab und zu als ein paar Zusatzaufgabe programmieren und online einreichen. Bisher hat das auch ganz gut geklappt. Leider hänge ich aber bei der folgenden Aufgabe (siehe Anhang) total. Normal versuche ich es immer alleine weil das meiner Meinung nach am meisten bringt aber leider hab ich nicht mal ansatzweise eine Ahnung *.*. Wär super lieb wenn ihr mir weiterhelfen könntet

Das hier ist der vorgegebene Code:

class List<T> {
T head;
List<T> tail;

List(T head, List<T> tail) {
this.head = head;
this.tail = tail;
}

/** Generic helper function for list creation. You DO NOT NEED to call this function. */
static <U> List<U> node(U head, List<U> tail) {
return new List<U>(head, tail);
}
}

public class Muenzen {

/**
* Counts the number of possibilities to get a total value of exactly {@code max} using
* only the values given in {@code remainingCoins}.
* @param sum the accumulated value
* @param max the maximum value
* @param remainingCoins a list of coins
* @return the number of possibilities
*/
static int numPossibilities(int sum, int max, List<Integer> remainingCoins) {
// TODO

}
}

public static void main(String[] args) {
// Given a list of coins...
List<Integer> coins = List.node(1, List.node(2, List.node(5, List.node(10,
List.node(20, List.node(50, List.node(100, List.node(200, null))))))));

// For example, the number of possibilities to get a total value of 175 is 41454.
int result =

System.out.println("There are " + result + " number of ways.");
}

}



Vielen Dank im Voraus
Liebe Grüße
Verena

 

[WinKill]

Hi,

Rekursion bedeutet, Du hast immer wieder den gleichen Schritt und führst den durch -> Du rufst immer wieder die selbe Funktion auf.

Dein Funktionsrumpf hier wird wohl so ähnlich aussehen:

int count = 0;
foreach(integer i in remainingCoins)
{
if( sum+i < max)
count + numPossibilities(sum+i, max, remainingCoins);
if(sum+i == max)
count + 1)
}
return count;

jetzt schnell getippt, also ehr pseudocode.

Dann noch Rekursionsstart in der Main und es sollte laufen. Schaus Dir Mal in ruhe an.

Viele Grüße
Winni

 

[Hancock]

Rekursion schon verstanden?
numPossibilities gibt dir die Anzahl der Möglichkeiten zurück.

Nehmen wir an, es sei keine Münze erlaubt (max==0), dann gibt es eine Möglichkeit, falls sum=0 und keine sonst.
Das ist ein Teil der Abbruchbedingungen, wenn du das rekursiv aufrufst.

BTW: Was ist das für ne List-Klasse und warumheißt der Parameter remainingCoins, du hast doch unbegrenzt viele?
Ich hätt Coins als int[] definiert.

 

[BlooDFreeZe]

Ich denk mal remainingCoins wird dazu da sein um die verschiedenen Größen durchzugehen. Das wäre dann auch schon ein Hinweis darauf wie es umgesetzt werden soll.

 

[vera]

Vielen Dank für die schnellen Antworten!

Also wie Rekursion geht weiß ich schon. Generics bin ich nicht so fit - wobei ich das hier ja eigentlich nicht brauche ?!
Der Code war so vorgegeben und wir müssen numPossibilities und die main Methode ergänzen.

Versuch das gerade macht mich aber leicht fertig.

 

[BlooDFreeZe]

Ja Generics brauchst nicht wirklich. Musst nur wissen das du dich in eine Richtung durch die Liste arbeiten kannst oder solltest. Die gefundenen Ergebnisse musst du per Rekursion am Ende aufaddieren. Du musst alle Möglichkeiten ausprobieren bis du über max bist und somit nix gefunden hast, oder genau bei max gelandet bist. Könntest du aus dem Ansatz von WinKill schon etwas rauslesen?

 

[Hancock]

Zuerst kannst du ja alle Möglichkeiten finden, um diese Summe zu bilden, dann musst du nur eine eindeutige Sortierung finden, um Permutationen nicht mehrfach zu zählen.

main Methode schreiben sollte nicht so schwer sein, das geht komplett unabhängig von der numPossibilities-Methode.
numPossibilities funktioniert via Rekursion und einer Schleife.

 

[Hardliner93]

Hallo Verena,
erstmal willkommen im Forum.
Wenn ich das richtig sehe, auch mit dem rekursiven Aufruf,
fehlt dir in der main() nur noch folgendes:

[COLOR=#ff0000] int result = Muenzen.numPossibilities(0, 175, coins);[/COLOR] // 0 für aktuelle Summe
//175 als Beispiel für total value(siehe Kommentar darüber);
//coins als Liste

für die Methode numPossibilities:

/**
	 * Counts the number of possibilities to get a total value of exactly {@code max} using
	 * only the values given in {@code remainingCoins}.
	 * @param sum the accumulated value
	 * @param max the maximum value
	 * @param remainingCoins a list of coins
	 * @return the number of possibilities
	 */
	static int numPossibilities(int sum, int max, List<Integer> remainingCoins) {
    int returnCounter = 0;
    if(remainingCoins.head > max){ // dann kann es nicht funktionieren logischerweise
        return 0;
    }
    for(int i = 0; sum <= max; i++){  //iteriere solange, bis max erreicht wird, aber erhöhe i immer um 1...
        if(remainingCoins.tail != null){ //Abbruchbedingung der Rekursion (s. Definition der Liste)
            returnCounter += numPossibilities(sum, max, remainingCoins.tail); //... damit nach jedem Schritt hier rekursiv weitergemacht werden kann
        }
        sum += remainingCoins.head; //erhöhe momentane Summe
        if(sum == max){
            returnCounter++; //dann ist eine Möglichkeit gefunden worden
        }
    }
    return returnCounter;
}

Das ist was mir jetzt in den Kopf kam, natürlich ohne Garantie. So beim durchdenken klingt es aber sinnvoll. Und da ich vor der ersten Antwort angefangen habe zu schreiben, bitte ich eventuelle Überschneidungen zu entschuldigen

Gruß Hardliner

 

[diRAM]

https://www.computerbase.de/forum/threads/fragen-hausaufgaben-co.1767679/
Bitte künftig beachten.