Danke Danke:  0
Gefällt mir Gefällt mir:  0
Dislikes Dislikes:  0
Ergebnis 1 bis 12 von 12

Thema: 100 Gramm aus Euro Münzen

  1. #1
    Member of Honour Avatar von ivegotmail
    Registriert seit
    28.05.03
    Danke (erhalten)
    1
    Gefällt mir (erhalten)
    4

    Standard 100 Gramm aus Euro Münzen

    Anzeige
    Folgende Aufgabe wurde von dutchman2006 eingereicht:

    Eine Goldwaage soll kalibriert werden, dazu wird allerdings ein 100-Gramm-Gewicht benötigt.
    Ein solches ist aber nicht verfügbar, daher muss ein 100-Gramm-Gewicht aus anderen Gegenständen "gebastelt" werden: in dieser Aufgabe Euro-Münzen.
    Eine Tabelle des exakten Gewichtes aller Euromünzen gibt es hier: *klick*.

    Die Aufgabe besteht nun darin, (die genaue Anzahl aller möglichen) Münz-Kombinationen zu finden, die exakt 100 Gramm ausmachen.
    Achtet darauf, dass Kombinationen die sich nur in der Reihenfolge der Münzen unterscheiden nicht doppelt gezählt werden.
    http://livehabo.hackerboard.de | http://livebb.sourceforge.net

  2. #2

    Registriert seit
    25.08.07
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    0

    Standard

    Hi, ich bin leider noch sehr unerfahren in C++, aber ich hoffe, das mein Prog den Anforderungen genügt.
    Laut Logik müsste es stimmen. Ich hoffe es schreibt noch jemand eine Lösung in C++, die einen besseren Programmierstil hat. *g*
    Angehängte Dateien Angehängte Dateien

  3. #3
    Avatar von Eydeet
    Registriert seit
    14.04.06
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    5

    Standard

    Ich brauch mal ein wenig Hilfe. Mein Programm gibt je nach Datentyp (float oder double) für die Berechnung der Summe ein anderes Ergebnis zurück (float: 2119 Kombinationen; double: 2426 Kombinationen)
    Vielleicht weiß ja ein erfahrener C-Coder rat, aber ich habe echt keine Ahnung, was falsch sein könnte. Ich habe stichprobenartig einige Ergebnisse nachgerechnet, habe aber überall das Ergebnis "100" herausbekommen.

    Hier mein Code (rekursiver Ansatz):
    coincomb.cpp   
    Code:
    #include <iostream>
    
    using namespace std;
    
    void coinComb(short coins[], double sum, int mod);
    
    const double weight[8] = {8.50, 7.50, 7.80, 5.74, 4.10, 3.92, 3.06, 2.30};
    
    int c100 = 0;
    
    int main()
    {
        short coins[] = {0, 0, 0, 0, 0, 0, 0, 0};
        coinComb(coins, 0, 0);
        cout << "Genau 100g bei " << c100 << " Kombinationen" << endl;
    }
    
    void coinComb(short coins[], double sum, int mod)
    {
        while (sum < 100) {
            if (mod != 7 && sum + weight[7] < 100.01) {
                // copy coins
                short coinsCopy[8];
                for (int i = 0; i < 8; ++i) coinsCopy[i] = coins[i];
                coinComb(coinsCopy, sum, mod + 1);
            }
            ++coins[mod];
            sum += weight[mod];
        }
        if (sum < 100.01) {
            c100++;
            for (int i = 0; i < 8; ++i) {
                cout << coins[i] << ' ';
            }
            cout << "sum=" << sum << endl;
        }
    }

  4. #4

    Registriert seit
    25.08.07
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    0

    Standard

    @Eydeet :Bei mir geht dein Prog so fast überhaupt nicht, der zählt einmal sum im 8,5 er Schritt hoch und dann ist Schluss- bei der Ausgabe kommt dann, das es 0 Kombinationen gäbe. K.A. -ich habs einfach mal kopiert und ausgeführt... hm- mahc ich irgendwas verkehrt? Also bei mir springt der Quasi nie in die erste if- Abfrage rein.

    PS.: Mein Prog kommt nur auf 276 Möglichkeiten- ich finde das klingt auch realistischer.

  5. #5
    Avatar von Eydeet
    Registriert seit
    14.04.06
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    5

    Standard

    Ich hab das Ganze noch mal auf Integer umgeschrieben, vielleicht läuft das ja bei dir. Ich bekomme allerdings jetzt 4674 Möglichkeiten ^^. Vielleicht kannst du ja mal deine Ergebnisse posten, und ich guck dann, ob ich Kombinationsmöglichkeiten finde, die du noch nicht hast.

    Meine Ausgabe habe ich als Anhang angehängt. Mein Beitrag wäre sonst einfach viel zu lang geworden.

    muenzcombo-int.c   
    Code:
    #include <stdio.h>
    
    void coinComb(short coins[], short sum, short mod);
    
    const int weight[8] = {850, 750, 780, 574, 410, 392, 306, 230};
    
    short c100 = 0;
    
    int main()
    {
        short coins[] = {0, 0, 0, 0, 0, 0, 0, 0};
        coinComb(coins, 0, 0);
        printf("~ %i passende Kombinationen gefunden\n", c100);
        return 0;
    }
    
    void coinComb(short coins[], short sum, short mod)
    {
        while (sum < 10000) {
            if (mod != 7) {
                short coinsCopy[8];
                short i;
                for (i = 0; i < 8; ++i) coinsCopy[i] = coins[i];
                coinComb(coinsCopy, sum, mod + 1);
            }
            ++coins[mod];
            sum += weight[mod];
        }
        if (sum == 10000) {
            short i;
            c100++;
            for (i = 0; i < 8; ++i) {
                printf("%2i ", coins[i]);
            }
            printf("\n");
        }
    }


    PS: Das mit den C-Gurus habe ich geschrieben, weil es kein C++-Spezifisches Problem war, aber grundsätzlich hast du natürlich Recht. Die neue Version ist übrigens schönes, oder zumindest standardkonformes C
    Angehängte Dateien Angehängte Dateien

  6. #6

    Registriert seit
    25.08.07
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    0

    Standard

    ich hab meins jetzt auch noch mal in integer umgeschrieben, und siehe da, ich komme ebenfalls auf 4674 Möglichkeiten! Und ich hatte auch rausgefunden, das der bei double die anderen Möglickeiten auch durchläuft, auch auf 100 kommt, aber komischerweise diese nicht gezählt hat...K.A. woran das liegt. Ich bin dem gestern noch mal auf den Grund gegangen, bin aber bis jetzt zu keinem richtigen Ergebnis gekommen, hab aber noch rausgefunden, dass der total spinnt, wenn ich Ergebnis von long double auf double geändert hab. Irgendwie glaub ich, dass ich ein sehr ähnliches Problem wie du hattest, hatte.
    Hier noch mal mein Prog:

    Ich hab meine Ergebnisliste ebenfalls angehängt, dürfte jetzt aber irrelevant sein. Dein Prog ist ja auf der gleichen Logik wie meins aufgebaut ist, nur halt eleganter gelöst. Leider bin ich nicht auf den rekursiven Ansatz gekommen...P.S.: Dein erstes Prog ging bei mir gestern schon, so wie von dir beschrieben, ich hab blos vergessen, das die Konsole ja nicht undenlich viele Zeichen aufnimmt :-), halt Anfängerfehler...hab dann die Ausgabe umgeleitet, und schwubs waren alle Ergebnisse da.
    Angehängte Dateien Angehängte Dateien

  7. #7
    Moderator Avatar von CDW
    Registriert seit
    20.07.05
    Danke (erhalten)
    29
    Gefällt mir (erhalten)
    831

    Standard

    Ich denke mal, dass der Ansatz mit der Einschränkung des Suchraums der einzig tragbare ist. Denn der naive Ansatz:
    Code:
    //startaufruf mit sum=10000
     public  void getCombination(LinkedList result,int[] coins,int sum)
        {
        	if (sum>0) 
        		for (int coinWeight:coins) getCombination(result,coins,sum-coinWeight);
    braucht sehr sehr lange. Meiner groben Einschätzung nach muss man dann nämlich ca 18^8 Möglichkeiten untersuchen (Durchschnittsgewicht einer Münze= 5.36 -> für 100 Gramm braucht man ca 18 Stück).Und das sind 11 Mrd irgendwas.
    java   

    Code:
    import java.util.List;
    
    public class Main
    {
            final static int WEIGHT=100*100;    
    	final static int coins[]={230,306,392,410,574,780,750,850};  
    	
    	public static void main(String[] args)
    	{
    		Combinator comb=new Combinator(coins,WEIGHT);
    		List result=comb.getCombinations();
    		
    		for (Object array:result)
    	    	{
    			   System.out.println();
    			   for (int i:(int[])array)
    				   System.out.print(i+" ");
    				 
    	    	}
    	    		
    		System.out.println("gesamt: "+result.size());
    	}
    
    }
    
    
    import java.util.LinkedList;
    import java.util.List;
    
    public class Combinator
    {
       private int[] weight;
       private int limit;
       private int[] comb;
       private LinkedList result=new LinkedList();
       
       private Combinator(){};
       
       public Combinator (int[] combinations,int limit)
       {
    	   this.weight=combinations.clone();
    	   comb=new int[weight.length];
    	   this.limit=limit;	   
       }
       
       private int getSum()
       {
    	   int sum=0;
    	   for (int i=0;i<comb.length;i++)
    		   sum=sum+(weight[i]*comb[i]);
    	   return sum;
       }
       
       private boolean next()
    	{
    	   comb[0]++;	
    	   for (int i=0;(i < comb.length-1)&&(getSum()>limit);i++)
    		{
    			comb[i] = 0;
    			comb[i + 1]++;
    		}
    	  if (getSum() > limit)
    		return false;
    	  else
    		return true;
    
    	}
       
       public List getCombinations()
       {
    	   while (next())
    		   if (getSum()==limit)
    			   result.add(comb.clone());
    	   
    	   return result;
       }
    }
    Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
    Selig, wer nichts zu sagen hat und trotzdem schweigt.

  8. #8
    Avatar von Eydeet
    Registriert seit
    14.04.06
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    5

    Standard

    Ich hab einen kleinen Counter in beide Programme (deins & meins) eingebaut. (Bei mir: 1. Zeile der coinComb-Funktion, bei dir: 1. Zeile der next-Funktion).
    Das Ergebnis:
    Code:
    CDW   : 3487996 Durchläufe
    Eydeet:  600516 Durchläufe
    Außerdem habe ich auch irgendwie das Gefühl, dass meine Lösung schneller läuft, rein subjektiv natürlich Mathematisch kann ich das leider nicht belegen, aber an deiner Rechnung scheint irgendwas falsch zu sein.

  9. #9

    Registriert seit
    14.11.07
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    0

    Standard So ists Richtig

    Ich hab mir die Aufgabe angeguckt aber eure Lösungsansätze sind bischen komisch weil sie irgendwie etwas Kompliziert gedacht sind auf jedenfall hab ich es auch mal versucht dieses Progrämschen zu Programieren. Bei mir kommen auch 4674 verschiedene Kombinationen raus ich denke das ist richtig hab das stichprobenartig mal nachgerechnet und ich kam immer auf 100.....
    Angehängte Dateien Angehängte Dateien

  10. #10
    Moderator Avatar von CDW
    Registriert seit
    20.07.05
    Danke (erhalten)
    29
    Gefällt mir (erhalten)
    831

    Standard

    btw:
    eure Lösungsansätze sind bischen komisch weil sie irgendwie etwas Kompliziert gedacht
    Eine zig verschachtelte Schleife mit hartkodierten Werten (zur Einschränkung des Suchraums) nutzen und über andere meckern? ne ne ne .

    Problembeschreibung=>Problemlösung   

    Code:
    muenze(850).  %ganze zahlen als Gewicht nutzen
    muenze(780).
    muenze(750).
    muenze(574).
    muenze(410).
    muenze(392).
    muenze(306).
    muenze(230).
    
    	                             %ist das Gewicht=0, so ist die Kombination trivial (0 Muenzen)
    kombination(0,_).
    	                             %ansonsten ist das bestenfalls zusammengesetztes Gewicht,
    	                             %somit ist die Loesung eine Kombination aus mehreren Muenzen
    kombination(Gew,Vor):-  
    		                     %es gibt eine Loesung, sofern:
    	Gew>0,                       %das Gewicht positiv ist	
            muenze(Teil_gew),            %und es eine Muenze gibt,
    	Teil_gew=<Vor,               %die weniger/genausoviel wiegt wie 
    	                             %die Vorgaengermuenze,
    	Rest is Gew-Teil_gew,        % und diese Muenze und der Rest des Gewichts
    	kombination(Rest,Teil_gew).  %zusammen das Wunschgewicht bilden,
    	                             %wobei dieser Rest sich natuerlich auch als Muenzkombination
    	                             %darstellen laesst
    kombinationen(Gew,Erg):-
    	Gewicht = Gew*100,
    	findall(_,kombination(Gewicht,Gewicht),Anzahl),
    	length(Anzahl,Erg).
    Die Vorgängermünze wird in der Lösung betrachtet, um Lösungen, die sich nur in der Reihenfolge der Münzen unterscheiden, auszuschließen.

    wegen findall/length: es wurde SWI Prolog benutzt - findall bildet eine Liste mit allen Lösungen und length bestimmt die Länge einer Liste.

    Ausgabe:
    Code:
    ?- kombinationen(100,Anzahl).
    Anzahl = 4674.
    kombinationen(90,Anzahl).
    Anzahl = 2564.
    ?- kombinationen(50,Anzahl).
    Anzahl = 115.
    Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
    Selig, wer nichts zu sagen hat und trotzdem schweigt.

  11. #11

    Registriert seit
    14.11.07
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    0

    Thumbs down

    Ja ich versteh was du meinst aber vom Verständnis her meine ich da brauchst du bei meinem Programm nicht mal richtiger Programmierer zu sein um es zu checken
    des halb hab ich es gesagt aber sonst sind die anderen doch nicht falsch im gegensatz ich fand einige von denen sogar sehr gut

    LG

  12. #12

    Registriert seit
    21.04.08
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    0

    Standard

    Anzeige
    Dank CDW kann ich auch eine Lösung (Java) posten:

    Code:
    public class WeightInEuros {
    	
    	public static void main(String[] args) {
    		System.out.println("Euro-Münzen Kombinationen die exat 100g ergeben!");
    		System.out.println("Anzahl: "+ new WeightInEuros().new Combinator().getCounter());
    	}
    	
    	class Combinator {
    		
    		private final int limit = 100*100;
    		private final int[] coins = { 230, 306, 392, 410, 574, 780, 750, 850 };
    		
    		private int counter = 0;
    		
    		public Combinator() {
    			doIt(0, 0);
    		}
    		
    		private void doIt(int sum, int index) {
    			if (sum == limit){
    				counter++; 
    				return;
    			}
    			if (sum > limit) {
    				return;
    			}
    			if (sum < limit) {
    				while (index < coins.length){
    					int weight = sum + coins[index];
    					doIt(weight, index);
    					index++;
    				}
    			}
    		}
    		
    		public int getCounter() {
    			return counter;
    		}
    		
    	}
    
    }

Ähnliche Themen

  1. PC für 400 Euro
    Von Stein im Forum Kaufberatung
    Antworten: 2
    Letzter Beitrag: 09.09.09, 19:14
  2. Euro-Münzen für 100g
    Von Ook! im Forum Code Kitchen
    Antworten: 7
    Letzter Beitrag: 15.06.08, 22:53
  3. Grafikkarte für <=200 Euro
    Von weau im Forum Hardware Probleme
    Antworten: 0
    Letzter Beitrag: 15.12.07, 12:41
  4. Grafikkarte bis 100 Euro.
    Von DER_CONNY im Forum Kaufberatung
    Antworten: 1
    Letzter Beitrag: 24.09.07, 23:19
  5. Euro?
    Von Dreamer im Forum (Web-) Design und webbasierte Sprachen
    Antworten: 11
    Letzter Beitrag: 22.09.02, 19:04

Berechtigungen

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