Hackerboard Wiki HaboBlog
Hackerboard bei Facebook Hackerboard bei Google+ Hackerboard bei Twitter

[HaBo]

 
Programmieraufgaben Hier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann.

100 Gramm aus Euro Münzen

Diskussion: 100 Gramm aus Euro Münzen im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Folgende Aufgabe wurde von dutchman2006 eingereicht: Eine Goldwaage soll kalibriert werden, dazu wird allerdings ein 100-Gramm-Gewicht benötigt. Ein solches ist ...

Antwort
Alt 23.08.07, 15:21   #1 (permalink)
Member of Honour
 
Benutzerbild von ivegotmail
 
Registriert seit: 28.05.03
ivegotmail Leistung: Z3
Likes: 3
Standard 100 Gramm aus Euro Münzen

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
ivegotmail ist offline   Mit Zitat antworten
Alt 25.08.07, 00:56   #2 (permalink)
 
Registriert seit: 25.08.07
Burny Leistung: Facit NTK
Likes: 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
Dateityp: rar muenzgewicht.rar (649 Bytes, 69x aufgerufen)
Burny ist offline   Mit Zitat antworten
   
HaBOT
 

Werbung ist gerade online    
Alt 25.08.07, 16:03   #3 (permalink)
 
Benutzerbild von Eydeet
 
Registriert seit: 14.04.06
Eydeet Leistung: Facit NTK
Likes: 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;
    }
}
Eydeet ist offline   Mit Zitat antworten
Alt 25.08.07, 16:38   #4 (permalink)
 
Registriert seit: 25.08.07
Burny Leistung: Facit NTK
Likes: 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.
Burny ist offline   Mit Zitat antworten
Alt 25.08.07, 22:55   #5 (permalink)
 
Benutzerbild von Eydeet
 
Registriert seit: 14.04.06
Eydeet Leistung: Facit NTK
Likes: 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
Dateityp: txt output.txt (114,1 KB, 77x aufgerufen)
Eydeet ist offline   Mit Zitat antworten
Alt 26.08.07, 13:19   #6 (permalink)
 
Registriert seit: 25.08.07
Burny Leistung: Facit NTK
Likes: 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
Dateityp: rar output.rar (18,5 KB, 27x aufgerufen)
Dateityp: rar muenzgewicht.rar (627 Bytes, 20x aufgerufen)
Burny ist offline   Mit Zitat antworten
Alt 27.08.07, 15:56   #7 (permalink)
CDW
Moderator
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPR
Likes: 596
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.
CDW ist offline   Mit Zitat antworten
Alt 27.08.07, 18:51   #8 (permalink)
 
Benutzerbild von Eydeet
 
Registriert seit: 14.04.06
Eydeet Leistung: Facit NTK
Likes: 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.
Eydeet ist offline   Mit Zitat antworten
Alt 21.02.08, 14:51   #9 (permalink)
 
Registriert seit: 14.11.07
Cyber_Puma Leistung: Facit NTK
Likes: 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
Dateityp: txt WageKalibrieren.txt (1,6 KB, 47x aufgerufen)
Cyber_Puma ist offline   Mit Zitat antworten
Alt 07.06.08, 02:27   #10 (permalink)
CDW
Moderator
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPRCDW Leistung: WOPR
Likes: 596
Standard

btw:
Zitat:
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.
CDW ist offline   Mit Zitat antworten
Alt 07.06.08, 19:15   #11 (permalink)
 
Registriert seit: 14.11.07
Cyber_Puma Leistung: Facit NTK
Likes: 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
Cyber_Puma ist offline   Mit Zitat antworten
Alt 24.06.08, 22:17   #12 (permalink)
 
Registriert seit: 21.04.08
Ook! Leistung: Facit NTK
Likes: 0
Standard

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;
		}
		
	}

}
Ook! ist offline   Mit Zitat antworten
Antwort
   
- Anzeige -

Werbung ist gerade online    

[HaBo] » Software Home » Code Kitchen » Programmieraufgaben » 100 Gramm aus Euro Münzen
Themen-Optionen
Ansicht

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks sind aus
Pingbacks sind aus
Refbacks sind aus


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


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62