Seite 2 von 4 ErsteErste 1234 LetzteLetzte
Ergebnis 16 bis 30 von 55

Thema: [PDW 9] Geldwechsel

  1. #16
    Registered User
    Registriert seit
    Jan 2001
    Beiträge
    331
    Renommee
    228

    Re: [PDW 9] Geldwechsel

    ich hab herumgesucht aber keine mathematische lösung für das ganze gefunden. is das ganze ein rucksack problem bei dem ihr testet bis ihr zur kleinsten münzzahl kommt?

  2. #17
    Moderator
    Registriert seit
    Jul 2000
    Beiträge
    3.763
    Renommee
    1214

    Re: [PDW 9] Geldwechsel

    dt meinte, es sei effizienter zu lösen.
    Wenn man es so machen könnte?
    Betrag=a*muenze1+b*muenze2+c*muenze3 ....
    die grösste münze wäre muenze1, die zweitgroessete muenze2.
    Aber da ich ja nicht weiss, wieviele Münzen das sind, hab ich ein Problem damit,
    wie ich die Koeffizienten durchprobiere
    kuchen ist dumm, weil er nur labert und nicht wirklich lernen oder verstehen will.

  3. #18
    Mastermind in Training
    Registriert seit
    Mar 2001
    Beiträge
    1.552
    Renommee
    727

    Re: [PDW 9] Geldwechsel

    Ich hatte am Anfang auch den "Gierigen Algo".
    Dann hab ich gemerkt, dass er nicht immer die richtige Antwort ausgibt. Da ich die Algos aber nicht irgendwo abgucken will, hab ich versucht den ganzen Code zu ändern.
    Meiner Meinung nach, hab ich die Aufgabe jetzt richtig gelöst, aber ich hab eine IndexOutOfBounzeException und ich weiß nicht warum.
    Ich hab ja noch zwei Tage Zeit den Fehler zu finden, aber eigentlich muss ich fürs Studium lernen. Hm, schwierige Entscheidung

    neon
    Eine Zeitung wirbt mit "Bild dir deine Meinung". Mir wäre es lieber, wenn die Menschen weniger Meinung und dafür mehr Ahnung hätten.

  4. #19
    Registered User
    Registriert seit
    Mar 2003
    Beiträge
    104
    Renommee
    15

    Re: [PDW 9] Geldwechsel

    Ich versteh das Problem vielleicht nicht ganz, hab es aber mit zwei for-schleifen geloest, mit modulo!? Bin gerade dabei die (exakte) Komplexität herauszufinden.
    Eine mathematische Loesung scheint uwar interessant, kann mich aber nicht ganz damit anfreunden, auch mit der Loesung ueber das Rucksackproblem (GA und so) kann ich nicht viel anfangen, da es ja stochastische Suchverfahren sind, wenn ich mich nicht taeusche.

    MurderDeathKill's Beispiel ist doch irrelevant da die Darstellung des Betrags mit zwei Muenzen möglich ist (ob 9,9 oder 10,8 ist doch egal) ? Gibt es da auch andere Bsp wo sichtbarer wird dass die Modulo methode nicht funktioniert (in diesem Fall werde ich den mathematischen weg einschlagen) ?
    Geändert von deez (19.06.2004 um 16:34 Uhr)

  5. #20
    Mastermind in Training
    Registriert seit
    Mar 2001
    Beiträge
    1.552
    Renommee
    727

    Re: [PDW 9] Geldwechsel

    @ deez

    Du hast das Beispiel von MurderDeathKill nicht richtig verstanden.

    Münzarten:
    10
    9
    1

    Betrag:
    18

    Wenn du mit Modulo usw arbeitest, dann kriegst du folgendes Raus:
    1 mal die Münze 10
    8 mal die Münze 1
    Das sind zusammen 9 Münzen.

    Die beste Lösung ist aber:
    2 mal die Münze 9

    Verstehst du jetzt die Problematik?
    Ich hab es am Anfang auch falsch gemacht. Aber ohne Modulo. Leider hab ich den Quellcode nicht mehr, da ich das Prog umgeschrieben hab (enthält leider noch Fehler).

    neon
    Eine Zeitung wirbt mit "Bild dir deine Meinung". Mir wäre es lieber, wenn die Menschen weniger Meinung und dafür mehr Ahnung hätten.

  6. #21
    Registered User
    Registriert seit
    Mar 2003
    Beiträge
    104
    Renommee
    15

    Re: [PDW 9] Geldwechsel

    Volkommen verstanden, danke...ich war naemlich schon dabei das Problem in Brainfuck zu loesen
    Ich glaub, es ist moeglich das mit Backtracking zu loesen, kann das sein?
    Als Gleichungssystem finde ich keinen __schoenen__ Weg, da man entweder BruteForcen oder viel viel Quellcode schreiben muss. Backtracking hat aber eine hohe Komplexitaet. Hm, freu mich schon auf eure Loesungen

  7. #22
    Moderator
    Registriert seit
    Jan 2001
    Beiträge
    1.253
    Renommee
    421

    Re: [PDW 9] Geldwechsel

    Darf ich jetzt anfangen? Das Herzstück ist bei mir ein Algorithmus der schon vor über 2000 Jahren entdeckt wurde...
    Wir denken nur, wenn wir mit einem Problem konfrontiert werden. John Dewey

  8. #23
    Moderator
    Registriert seit
    Jul 2000
    Beiträge
    3.763
    Renommee
    1214

    Re: [PDW 9] Geldwechsel

    da bin ich gespannt :>
    ggT?
    kuchen ist dumm, weil er nur labert und nicht wirklich lernen oder verstehen will.

  9. #24
    Moderator
    Registriert seit
    Jan 2001
    Beiträge
    1.253
    Renommee
    421

    Re: [PDW 9] Geldwechsel

    Zitat Zitat von Deknos
    da bin ich gespannt :>
    ggT?
    Genau. Wobei ich dann aber die "effizientere" Modulo-Variante benutze. Die kannten die Griechen glaub ich noch nicht.

    Das ganze mal in Ruby:
    Code:
    def gcd (u,v)
       u, v = v, u % v while v != 0; u
    end
    
    print "Eingabe:\nMünzwerte: "
    input  = (gets.chomp.split(',')).sort{|x,y| x.to_i <=> y.to_i}
    print "Betrag:"
    amount = gets.to_i
    output = {}; arr = []; coins = 0
    
    until amount.zero?
         if input[0].to_i > amount then raise "Nicht auflösbar!" end
         arr.clear
         input.each{|coin| arr.push([coin, amount.divmod(coin.to_i), gcd(coin.to_i, amount)])}
         arr.sort!{|x,y| y[2] <=> x[2]}.delete_if{|x| (x[2] < arr[0][2])}.sort!{|x,y| x[1][0] <=> y[1][0]}  
         
         output.update({arr[0][0] => arr[0][1][0]})
         coins += arr[0][1][0]
         amount = arr[0][1][1]
         input.delete_if{|x| (x == arr[0][0])}
    end
    
    print "\nAusgabe:\nAnzahl Münzen:#{coins}\nZerlegung:"
    output.each { |coin, number| print "#{number}*#{coin}, " }; puts
    Ich hoffe mal, dass ich nichts übersehen hab

    [edit]
    Zeile 1-3: Die Methode gcd ermittelt den gemeinsamen größten Teiler.
    Zeile6: Ließt eine Zeichenkette ein und speichert die einzelnen Elemente in ein Feld und sortiert die Geldstücke nach ihren Wert. z.B. [1,5,10,20]
    Zeile7: Ließt den Geldbetrag ein und speichert den in die Variable amount
    Zeile9: initialisiert diverser Variablen
    Zeile11: Startet die Hauptschleife, die so lange durchlaufen wird bis amount gleich Null ist.
    Zeile12: Damit aus dem Ganze nicht eine Unendlichen Geschichte gedeiht, wird überprüft ob die kleinste Münze auch kleiner als amount ist.
    Zeile14: In einem Feld werden für jedes Geldstück, der Quotient, der Restbetrag und und der ggT zu amount berechnet.
    Zeile15: Das Feld wird sortiert das die größten ggT am Anfang des Feldes stehen. Alle Einträge, die kleines als der größte ggT sind, werden gelöscht. Dann wird die Tabelle nach dem Quotienten sortiert. Auch hier steht wieder größte am Anfang des Feldes.
    Zeile17: In den Ausgabe-Hash wird das Geldstück und die Anzahl gespeichert.
    Zeile18: Die Anzahl der Geldstücke wird zum Geldstückzähler hinzu addiert
    Zeile19: Der Rest ist nun amount
    Zeile20: Das gewählte Geldstück(auch evt. doppelte Einträge) wird aus der Eingabefeld entfernt.

    Zeile24: Das Ausgabe-Hash wird ausgeben.
    [/edit]
    Geändert von Bunny (21.06.2004 um 18:36 Uhr)
    Wir denken nur, wenn wir mit einem Problem konfrontiert werden. John Dewey

  10. #25
    Moderator
    Registriert seit
    Jan 2001
    Beiträge
    1.253
    Renommee
    421

    Re: [PDW 9] Geldwechsel

    Der Schuß der Beschreibung der Zeile 15 stimmt nicht. Die mit dem kleinsten Quotienten steht am Anfang.

    Code:
    ..x[1][0] <=> y[1][0]..
    Wir denken nur, wenn wir mit einem Problem konfrontiert werden. John Dewey

  11. #26
    Registered User
    NewYearsChallenge Sieger 2010

    Registriert seit
    Oct 2002
    Beiträge
    730
    Renommee
    444

    Re: [PDW 9] Geldwechsel

    Hier mal meine Lösung in Java.
    Ich habe vorher so wie wahrscheinlich viele hier das Problem falsch verstanden, da ich auch davon ausging, dass die Münzen halbwegs sinnvolle Werte haben - Naja jetzt habe ich eigentlich die 'Brute-Force' methode gewählt... Code sollte sich selbst erklären - wenn nicht bitte fragen.


    Code:
      [...]
      //Start z.B.: über 
      int[] coins = new int[] {1, 9, 10};
      int value = 18;
        
      int[] result = getCoins(value, coins);
      [...]
    
      //Hier der eigentiche Algo
      public static int[] getCoins(final int value, final int[] coinValues)
      {
        int[] result = new int[coinValues.length];
        int coinsNeeded = Integer.MAX_VALUE;
        
        for (int start = coinValues.length - 1; start > 0; start--) {
          int[] tempResult = new int[coinValues.length];
          int tempCoinsNeeded = 0;
          int tempValue = value;
          
          for (int i = start; i >= 0; i--) {
            tempResult[i] = tempValue / coinValues[i];
            tempValue -= coinValues[i] * tempResult[i];
            tempCoinsNeeded += tempResult[i];
          }
          
          if (tempCoinsNeeded < coinsNeeded) {
            coinsNeeded = tempCoinsNeeded;
            result = tempResult;
          }
        }
        
        return result;
      }
    destructor

  12. #27
    Moderator
    Registriert seit
    Jun 2001
    Beiträge
    1.327
    Renommee
    846

    Re: [PDW 9] Geldwechsel

    @destructor
    Hmm, bei Münzen 1, 9, 10 und Wert 28 gibt der aber nicht drei aus, oder? ...

    @Bunny
    Mit dem Ruby Code muss ich etwas kämpfen. Das braucht seine Zeit.
    Funktioniert das Beispiel, das ich destructor gerade gegeben habe, denn bei dir?
    Aktuelle Probleme der Doppelwoche:
    [29 Logik] Fahnenjagd

  13. #28
    Moderator
    Registriert seit
    Jan 2001
    Beiträge
    419
    Renommee
    55

    Re: [PDW 9] Geldwechsel

    Hi,

    Hier meine brutale Lösung:

    Code:
    #include <iostream>
    
    int recurse( int currValue, int coinIndex, int coinCount, int* coins, int* permut)
    {
    
    	int bestPermut = -1;
    	int bestAmount = currValue / coins[0];
    	int amount;
    	
    	if ( currValue == 0 ) 
    	{
    		for ( int i = 0; i <= coinIndex; i++ )
    		{
    			permut[i] = 0;
    		}			
    		return 0;
    	}
    	
    	if ( (currValue / coins[coinIndex]) < 1 )
    	{
    		return -1;
    	}
    	
    	if ( coinIndex == 0 )
    	{
    		permut[coinIndex] = (currValue / coins[coinIndex]);
    		return (-1)*(currValue % coins[coinIndex]);
    	}
    	
    	for (int i=0; i <= (currValue / coins[coinIndex]); i++)
    	{
    		permut[coinIndex] = i;
    		if ( !recurse( currValue - (permut[coinIndex]*coins[coinIndex]), coinIndex-1, coinCount, coins, permut ) )
    		{
    			amount = 0;
    			for ( int j = 0; j < coinCount; j++)
    			{
    				amount += permut[j];
    			}
    			
    			if ( amount < bestAmount ) bestPermut = i;
    		}
    	}
    	
    	if ( bestPermut > -1 )
    	{
    		permut[coinIndex] = bestPermut;
    		recurse( currValue - (permut[coinIndex]*coins[coinIndex]), coinIndex-1, coinCount, coins, permut );
    		return 0;
    	}
    	else return -1;
    }
    
    int main()
    {
    	int coinCount = 3;
    	int coins[] = {1, 9, 10};
    	int permut[] = {0, 0, 0};	
    	int value = 28;	
    	
    	if ( recurse( value, coinCount-1, coinCount, coins, permut ) )
    	{
    		std::cout << "\nSorry, not solveable.\n";
    	}
    	else
    	{
    		std::cout << "\nBest Result: ";
    		for ( int i = 0; i < coinCount; i++ ) std::cout << permut[i] << "*" << coins[i] <<", ";
    		std::cout << ".\n";
    	}
    	
    	return 0;
    }
    Zur Erläuterung: Ich durchlaufe einen "binären Baum". An jeder Stelle gibts Münze A und Münze B und er probiert jede Kombination daraus und wählt die optimalste aus.

    Münze B ist dabei virtuell und in Wirklichkeit ein rekursiver Aufruf in das nächste Tiefenlevel wos dann einen neue Münze A und Münze B gibt.

    Das ganze geht bestimmt um Klassen eleganter, aber ich hab übermorgen eine Prüfung und hab das nur mal schnell in einer Stunde runterprogrammiert. Bin gespannt was ihr draus macht.

    mfg
    Work smarter, not longer

  14. #29
    Mastermind in Training
    Registriert seit
    Mar 2001
    Beiträge
    1.552
    Renommee
    727

    Re: [PDW 9] Geldwechsel

    Hi,

    ich hab das Problem wie folgt gelöst:

    Ich ermittle erst mal alle möglichen Varianten und anschließen suche ich die günstigste raus.
    Jede Variante wird als ein Objekt in einem Array abgespeichert. Das Objekt beinhaltet ein Array, welches genau so groß ist wie die Anzahl der Münzen. Dort wird dann einfach die Häufigkeit der einzelnen Münzen abgespeichert.
    Um die ganzen Varianten zu ermitteln geh ich wie folgt vor:

    Erst wird mit dem Geiz Algo eine Variante ermittelt.
    z.B.:
    Münzen
    1, 9, 10
    Betrag
    28

    Ergebniss
    10 kommt 2 mal vor
    1 kommt 8 mal vor

    Jetzt wird die Anzhal der größten Münze (vom Wert her natürlich) um 1 verrigert. Die führt dazu, dass die 10 nur noch 1 mal vorkommen darf

    Nächstes Ergebniss
    10 kommt 1 mal vor
    9 kommt 2 mal vor

    usw

    Somit ermittle ich alle Varianten . Anschließend wird in einer Methode die Anzahld er Münzen zusammengezählt und in einer for-Schleife die Lösung ausgegeben, die die kleines Anzahl der Münzen hat.

    Leider hab ich auch nicht so viel Zeit gehabt das Programm zu ende zu schreiben. Es gibt noch einen Fehler, aber ich weiß nicht woran es liegt.

    Ich werd den Code später Posten, weil ich Ihn nicht grad bei mir hab.

    neon
    Eine Zeitung wirbt mit "Bild dir deine Meinung". Mir wäre es lieber, wenn die Menschen weniger Meinung und dafür mehr Ahnung hätten.

  15. #30
    Moderator
    Registriert seit
    Jan 2001
    Beiträge
    1.253
    Renommee
    421

    Re: [PDW 9] Geldwechsel

    @DarkTom : Leider nicht. Muss ich mir nochmal genauer anschauen...
    Wir denken nur, wenn wir mit einem Problem konfrontiert werden. John Dewey

Aktive Benutzer

Aktive Benutzer

Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)

Ähnliche Themen

  1. Antworten: 4
    Letzter Beitrag: 31.05.2013, 23:00

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •