nicht angemeldet
Hi
Mit etwas Überlegung kannst Du z.B. 125 als kleinsten Wert für Sack 10 ermitteln :-)
ja aber in den Bereich dieser unteren Schranke würde der Algo eh nie kommen .. zumindest nicht bei Zahlen so nahe an einer 2er Potenz wie 500.
wie wäre es, wenn Du Deinen Algorithmus bekannt gäbest, vielleicht kann der
eine oder andere eine Verbesserung vorschlagen.
ähm den Algorithmus hab ich doch bereist beschrieben?!?
Du meinst den JS Code? ich schick die HTML-Seite unten mit.
Die Aufwandskomplexität des Codes kann man m.E. kaum noch optimieren (fast jede zwote Rekursion spuckt eine Lösung aus)!
Interessanter wäre eine mathematische Betrachtung wie aus der Lösung für 9 Säcke sich die Lösungen für 10 Säcke konstruieren (grob gesprochen, man nimmt Münzen aus den 9 Säcken udn stopft sie so in nen 10. Sack, den man so einreiht dass die Reihenfolge gewahrt bleibt, aber keine Lösungen doppelt kosntruiert werden). Und aus dieser Mathematischen Betrachtung sollte sich mit etwas Glück auch ne Formel für die ANzahl der Lösungen ableiten lassen.
Aber ehrlich, das Problem ist ausgelutscht und nicht sonderlich ergiebig. Es gibt AFAIK Mathematiker/Informatiker die sich mit ählichen Aufgaben herumschlagen, wo man aber mit Münzen bestimmter unterschiedlicher Werte bezahlen muss. Dass hat dann auch einen echten praktischen Hintergrund, z.B. bei der Optimierung von Machinenlaufzeiten.
Viel Spass mit dem Code, ist ein Draft ... und nicht verwirren lassen dass er erst ab 1 indiziert aber trotzdem 0 ausgibt.
Salam
Aschanti
------------------------- HTML+JS-Code 500Euro.html
<html>
<head>
<title>500 Euro Rtsel</title>
</head>
<body>
<h1>500 Euro Rtsel</h1>
<script>
var s=new Array(0,1); // Scke, s[0] ignorieren, weil es keinen nullten Sack gibt
var S=new Array(0,1); // Zwischensummen
var S_min=new Array(); // minimale Schranken fr Zwischensummen
var muenzen=500;
var saecke=10;
var rec=0; // # Rekursionen
function sack(i) {
rec++;
// letzter Sack erreicht => Ausgabe falls Lsung
if ( i == saecke) {
s[i]=muenzen-S[i-1];
if ( s[i] <= S[i-1]+1 && s[i] >= s[i-1] ) {
document.writeln (l++ + ": (" +s+ ") rec:"+rec+"<br>"); // nullten Index ignorieren
}
return;
}
// ansonsten tiefer Suchen
for (var j = S[i-1]+1; j >= s[i-1]; j-- ) {
// Vorwrtszhlen liefert die Ergebnisse sehr spt
//for (var j = s[i-1] ; j <= S[i-1]+1 ; j++ ) {
s[i]=j;
S[i]=S[i-1]+s[i];
if ( S[i] >= S_min[i] ) {
sack(i+1);
}
}
}
function init_schranken() {
S_min[saecke]=muenzen;
for (var i=saecke-1 ; i > 0 ; i--) {
S_min[i]=Math.floor(S_min[i+1]/2);
}
document.writeln( "Minimale Zwischensummen:"+ S_min +"<br>");
}
var i=1; // Sack index
var l=1; // Lsung counter
init_schranken();
sack(2);
document.writeln( " Anzahl Rekursionen="+rec);
</script>
</body>
</html>
Der Martin