nicht angemeldet
Lieber Patrick
1: (0,1,2,4,8,16,32,64,--- mehr sehe ich nicht, da ein Fenster davor stand, alle Reichen sind an der Kante abgeschnitten)
Der Code ist ein Hack ... aber wer lesen kann ist klar im Vorteil ... ich schrieb
"und nicht verwirren lassen dass er erst ab 1 indiziert aber trotzdem 0 ausgibt."
und im Code steht nochmal "nullten Index ignorieren"
Um analog zum beschriebenen Algo zu bleiben hab ich das Array
ab 1 indiziert, deswegen gibt er auch einen "0-ten Sack" aus.
Würde dein IE nicht beim Rendern zusammenbrechen, hättest du gesehen dass pro Zeile 11 Zahlen ausgegeben werden.
Habe nochmal rumoptimiert, und dieses "0-ter-Index-Feature" rausgeschmissen.
Die Optimierung hat aber wie befürchtet nur wenig
an Geschwindigkeit gebracht ich erhalte jetzt:
Anzahl Rekursionen= 28258321
Anzahl Lösungen= 24813353
habe also 165 Rekursionen und 1 Lösung eingespart (letzteres würde ich als Bug bezeichnen, den zu finden ich dem Forum überlasse)[*]
Ach ja dass die Browser Probleme haben 24 Millionen Zeilen auszugeben ist nachvollziehbar, deswegen habe ich auch beim 10 Sack-Fall die Ausgabe der Lösungen in Opera auskommentiert.
Um es dir einfacher zu machen hab ich dir jetzt ne GUI eingebaut, ob die allerdings in deinem IE funktioniert kann ich dir mangels Windoof nicht sagen (dafür gehen meine Umlaute beim cut&paste aus emacs flöten ... ).
Salam nach FFM
Ashanti
[*] ich habs, ich habs!!! (TIP: das Alte Ergebnis war falsch)
---------------- neue version 500Euro.html
<html>
<head>
<title>500 Euro Rtsel</title>
</head>
<body>
<h1>500 Euro Rtsel </h1>
Aufgabestellung siehe
<a href="http://www.mindfile.org/Spiele/Eurosack">
http://www.mindfile.org/Spiele/Eurosack
</a>
<p>
<form>
Muenzen <input name="muenzen" value="500"><br>
Scke <input name="saecke" value="9"><br>
Ausgabe <input type="checkbox" name="ausgabe" checked>
<input type="submit" value="leg los" onClick="main()">
</form>
<script>
function main() {
var s=new Array(); // Scke,
var S=new Array(); // Zwischensummen
s[1]=1;S[1]=1; //s[0] ignorieren, weil es keinen nullten Sack gibt
var S_min=new Array(); // minimale Schranken fr Zwischensummen
var s_max=new Array(); // maximale Schranken fr Scke
// Defaultwerte fr onLoad-Ausfhrung
var muenzen=500;
var saecke=10;
//var muenzen=250;
var saecke=9;
var ausgabe="on";
var l=0; // init Lsung counter
var rec=0; // init # Rekursionen
// Parameter einlesen
saecke=document.forms[0].saecke.value;
muenzen=document.forms[0].muenzen.value;
ausgabe=document.forms[0].ausgabe.checked;
document.open();
document.writeln( "<pre>");
init_schranken();
document.writeln( "<hr><h3>BERECHNUNG:</h3>" );
start=write_Time();
sack(2); // Rekursion starten
ende=write_Time();
document.writeln( "Dauer: "+(ende-start)+" millisec" );
document.writeln( "<hr><h3>ERGEBNIS:</h3>" );
document.writeln( "Anzahl Rekursionen=\t"+rec );
document.writeln( "Anzahl Lsungen=\t"+l );
document.writeln( "</pre>");
document.close();
function sack(i) {
rec++;
// letzter Sack erreicht => Ausgabe falls Lsung, Rekursion abbrechen
if ( i == saecke) {
s[i]=muenzen-S[i-1];
if ( s[i] <= S[i-1]+1 && s[i] >= s[i-1] ) {
l++;
if (ausgabe ) {
document.writeln (l + ":\t <b>" +s.join(" ")+ "</b>\t rec:"+rec); // Ausgabe hier auskommentieren
}
}
return;
}
// ansonsten tiefer Suchen
var max,min;
max=S[i-1]+1;
max=Math.min( max, s_max[i] );
min=s[i-1];
s_min=S_min[i] -S[i-1]; // wg S[i] = S[i-1]+j >= S_min[i]
min=Math.max( min, s_min);
for (var j = max ; j >= min ; j-- ) {
// Abwrtsszhlen liefert eher Ergebnisse als Aufwrts
//for (var j = min ; j <= max ; 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);
}
// da Saecke aufsteigend sortiert, kann i-ter Sack hoechstens soviele
// Muenzen enthalten wie man noch maximal in alle groeeren stecken kann.
for (var i=saecke ; i >0 ; i--) {
var kleinere_saecke=i-1;
var groessgleich_saecke=saecke-kleinere_saecke;
s_max[i]=Math.floor( (muenzen-kleinere_saecke)/groessgleich_saecke);
}
document.writeln( "<hr><h3>INIT:</h3>");
document.writeln( "Minimale Zwischensummen:"+ S_min.join("\t"));
document.writeln( "Maximale Sackfllung:\t"+ s_max.join("\t") );
document.writeln( "Muenzen/Saecke:\t" + muenzen+" "+saecke );
}
function write_Time() {
var Jetzt = new Date();
document.writeln("Zeit: "+Jetzt.toLocaleString());
var Zeit = Jetzt.getTime();
return Zeit;
}
}
</script>
</body>
</html>
Der Martin