Quadratzahl=quadratsumme < Wettbewerbe < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 05:13 Mi 27.04.2005 | | Autor: | biochipm |
Ich habe die Frage in keinem Forum auf Internetseiten gestellt
Hallo
Kann mir einer bei folgenden rekursiven Programm helfen.
Es soll die Zahl [mm] 112^2 [/mm] als Summe von der Quadratzahlenmenge ermittelt werden .
Der Bereich der Quadratzahlen soll [mm] 1^2 [/mm] bis [mm] 50^2 [/mm] sein wobei jede nur einmal genutz werden darf.
In einem Delphiprogramm rekursiv lösen das alle Varianten ausgegeben werden können.
z.B ein Variante mit
1+2+4+7+8+9+11+15+16+17+18+19+24+25+27+29+33+35+37+42+50 [mm] =112^2
[/mm]
Linkeseiten die ganzen zahlen noch zu quadrieren sind !!
Vielen Dank im Voraus.
Gruss
Frank
Dateianhänge:
Anhang Nr. 1 (Typ: zip) [nicht öffentlich]
|
|
| |
|
mit solchen problemen beschäftigen sich doch kassiererinnen jeden tag. ich denke die idee ist es, von oben anzufangen.
fülle die 50 bis 1 in einen array und lege los:
i=0;
solange die summe < gesuchte zahl:
falls summe + array[i] * array[i] < gesuchte zahl
summe = summe + array[i] * array[i]
erhöhe i;
falls array am ende --> return summe;
ich könnte was übersehen haben, aber das tut es doch effizient und einfach.
hm..thread is eh alt ;) aber für die es noch interessiert.
|
|
|
| |
|
Hi,sebastian und andere
Laut googel wäre 112 x112 kleinstes perfektes Quadrat mit Computerhilfe
Aber keine Qellenangabe über Autor geschweige dessen Qellcode
Ich glaube nicht das die Lösungszeit wesentlich kürzer wird da in meinen Fall die 50 und 1 bekannt sind (Max und Min).Es muss ja von unbekannt ausgegangen werden.
In welchen Q-Zahlbereich soll gesucht werden(1-max)alles möglich auf diesen Lösungsallgorithmuss bezogen.
P.s
Gibt es den immer eine schwache oder starke Ki der Mensch muss sie bloss finden(abkucken von der Natur und modifizieren auf den Spezialfall)?(z.B Schach bekannt und mit Go (noch total unbekannt)ists nur eine Zeitfrage!!!.
Wie gesagt nur bei bekannten Bereich kann die Suchzeit s. Betreff effizienter sein da weniger Kombinationen (besserer Filter).
Wenn Lösungen gefunden werden müssen den da der Grafische Aspekt laut Aufgabenstellung unbedingt erfüllt werden .
Kann mann da im Voraus schon sicher sein?
Und wie schauts mit der dritten Dimension aus(Ein perfekter Raum) !!!!! analog zum Quadrat.
Gruss biochip
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Di 13.02.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:18 Mi 27.04.2005 | | Autor: | Karl_Pech |
Hallo Frank,
Irgendwie ist mir die Aufgabenstellung noch nicht ganz klar (wegen diesem "Beispiel", daß Du da gebracht hast).
Wer schön, wenn Du die Aufgabenstellung nochmal präzise formulieren könntest (Also vielleicht einfach vom Übungsblatt abschreiben.  )
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:40 Mi 27.04.2005 | | Autor: | biochipm |
Hallo
Kann mir einer bei folgenden rekursiven Programm helfen.
Es soll die Zahl [mm] 112^2 [/mm] als Summe aus einer Quadratzahlenmenge ermittelt werden .
Der Bereich der Quadratzahlen soll [mm] 1^2 [/mm] bis [mm] 50^2 [/mm] sein wobei jede nur einmal genutz werden darf.
In einem Delphiprogramm rekursiv lösen das alle Varianten ausgegeben werden können.
z.B ein Variante mit
1+2+4+7+8+9+11+15+16+17+18+19+24+25+27+29+33+35+37
+42+50= 12544 = 112 hoch 2
Linkeseiten die ganzen zahlen noch zu quadrieren sind !!
1 hoch 2 + 2 hoch 2 + 4 hoch 2+.......s.o...............42 hoch 2 + 50 hoch 2 = 112 hoch 2
Vielen Dank im Voraus.
-----------------------------------------------------------------------------------------------
Hi, Karl_Pech
und so sollen aus der Quadratzahmenge alle anderen kombinationen nach belieben so erstellt werden das sie alle als Summe von den Quadratzahlen die 112 hoch 2=12544 ergibt.
Im 2. schritt sollen dann die Kombinationen ausgefiltert werden die dann auch graphisch in das 112x112 Quadrat hinein passen ohne zu überlappen und ohne eine Lücke in den 112 hoch 2 Quadrat zuzulassen.
Denn würde ich bestimmt alleine hinkriegen.
Ich habe meine Aufgabe überarbeiten wollen dabei wirds korrios.
Wenn ich die Aufgabe ancklicke fehlen die Zahlenwerte zur Aufgabe und in ein paar Minuten werden sie wie von Geisterhand vor meinen Augen eigefügt Wie Manipuliert.
Ist das ein Virus ,ein Hacker , oder das spitze Dach der Tastatur das alles durcheinander bringt.
Habe deshalb " Hoch" für das Dach verwendet.
Ich weis nicht wie ich das noch besser erklären soll.
Die kleineren Quadrate ohne Doppel sollen in ein grosses exakt rein passen graphisch wie ein Puzzel beim 2. Schritt.
Gruss Frank
|
|
|
| |
|
Hallo Frank,
> Es soll die Zahl [mm]112^2[/mm] als Summe von der Quadratzahlenmenge
> ermittelt werden .
> Der Bereich der Quadratzahlen soll [mm]1^2[/mm] bis [mm]50^2[/mm] sein wobei
> jede nur einmal genutz werden darf.
>
> In einem Delphiprogramm rekursiv lösen das alle Varianten
> ausgegeben werden können.
>
> z.B ein Variante mit
>
> 1+2+4+7+8+9+11+15+16+17+18+19+24+25+27+29+33+35+37+42+50
> [mm]=112^2[/mm]
>
> Linkeseiten die ganzen zahlen noch zu quadrieren sind !!
So ganz kann das doch nicht stimmen, oder? Es gilt [mm] $112^2 [/mm] = 12544$ aber
[m]1^2 + 2^2 + 4^2 + 7^2 + 8^2 + 9^2 + 11^2 + 15^2 + 16^2 + 17^2 + 18^2 + 19^2 + 24^2 + 25^2 + 27^2 + 29^2 + 33^2 + 35^2 + 37^2 + 42^2 + 50^2 = 12509[/m]
Ich habe jetzt ein Delphi-Programm geschrieben, welches eigentlich die Additionsketten ausgeben sollte, die 12544 ergeben. Das Ergebnis meines Programms ist, daß man aus der Menge [mm] $\left\{1^2, 2^2,\ldots,50^2\right\}$ [/mm] keine solche Additionskette konstruieren kann. Zumindest hat mein Programm keine solchen Lösungen gefunden, oder mein Programm ist fehlerhaft oder der zugrundeliegende Algorithmus ist fehlerhaft.
Idee:
Der Brute-Force-Ansatz wäre, hier alle Möglichkeiten anhand eines Baumes durchzuprobieren. Wir beginnen mit 1, addieren 4 hinzu, summe ist nicht [mm] $112^2$, [/mm] wieder zurück, addieren 9 hinzu, ... . Das Problem ist, daß wir dabei sehr viele Möglichkeiten zu betrachten haben von denen viele einfach unnütz sind (z.B. ist 1+3 = 3+1). Schön wäre es, wenn wir das Kommutativgesetz in unserem Algorithmus berücksichtigen könnten, um den Suchraum einzuschränken. Jedenfalls habe ich mir mal folgendes anhand eines einfacheren Bespiels überlegt:
Aufgabe: Finde alle Additionsketten für Zahlen aus [mm] $\left\{1,2,3,4\right\}$, [/mm] um die Zahl 7 darzustellen.
Lösung:
Betrachte
1+2 = 3
1+3 = 4
1+4 = 5
Betrachte
1+2+3 = 6
1+2+4 = 7
Betrachte
1+2+3+4 = 10
Betrachte
2+3 = 5
2+4 = 6
Betrachte
2+3+4 = 9
Betrachte
3+4 = 7
Damit lauten die möglichen Summen:
1+2+4 = 7 und 3+4 = 7
Außerdem haben wir unnütze Fälle, wie 4+1+2 oder 4+3 nicht beachtet und damit das Kommutativgesetz ausgenutzt.
Leider weiß ich nicht, ob der Algorithmus wirklich alle Möglichkeiten berücksichtigt. Aber ich denke schon, denn die Idee des Algorithmus ist, daß man alle Summanden egal welcher Summe sortieren kann. Fange ich also mit einer Zahl wie 2 an, brauche ich kleinere Zahlen (also hier 1) aus der Menge nicht mehr zu berücksichtigen, denn wenn ich eine Summe kriege, die u.a. 2 und 1 beinhaltet, kann ich die Summe so sortieren, daß sie mit 1 + 2 anfängt. Diesen Fall müßte der Algorithmus aber schon vorhin als er mit 1 anfing ausgeschlossen haben. Hier ist die Implementierung in Object Pascal:
| 1: | program quadzahl;
| | 2: |
| | 3: | uses Classes,
| | 4: | SysUtils;
| | 5: |
| | 6: | procedure FindeLoesungen;
| | 7: | var
| | 8: | strlst : tstringlist;
| | 9: | szaddkette : string;
| | 10: |
| | 11: | zahlen : array[1..50] of integer;
| | 12: | anfang_bei, addkettedurchlauf, i_zahl : integer;
| | 13: |
| | 14: | summenzaehler, summe : integer;
| | 15: | begin
| | 16: | strlst := tstringlist.create;
| | 17: | szaddkette := '';
| | 18: | summe := 0;
| | 19: |
| | 20: | for i_zahl := 1 to 50 do
| | 21: | zahlen[i_zahl] := i_zahl*i_zahl;
| | 22: |
| | 23: | for anfang_bei := 1 to 50 do
| | 24: | for addkettedurchlauf := anfang_bei to 50 do
| | 25: | for i_zahl := addkettedurchlauf+1 to 50 do
| | 26: | begin
| | 27: | for summenzaehler := anfang_bei to addkettedurchlauf do
| | 28: | begin
| | 29: | summe := summe + zahlen[summenzaehler];
| | 30: | szaddkette := szaddkette + IntToStr(zahlen[summenzaehler])+
| | 31: | ' + ';
| | 32: | end;
| | 33: |
| | 34: | summe := summe + zahlen[i_zahl];
| | 35: | szaddkette := szaddkette + IntToStr(zahlen[i_zahl]);
| | 36: |
| | 37: | if abs(summe - 112*112) < 10 then
| | 38: | strlst.Add(szaddkette);
| | 39: |
| | 40: | szaddkette := '';
| | 41: | summe := 0;
| | 42: | end;
| | 43: |
| | 44: | strlst.SaveToFile('out.txt');
| | 45: | end;
| | 46: |
| | 47: | begin
| | 48: | FindeLoesungen;
| | 49: | end. |
In den Zeilen 17-22 finden Initialisierungen statt (erstelle Liste, die nachher die gefundenen Möglichkeiten abspeichern soll, summe auf 0 setzen, szaddkette ist eine gefundene Additionskette und wird in der Liste gespeichert.) Danach wird ein Array mit den entsprechenden Quadratzahlen gefüllt.
Die vier FOR-Schleifen (24-28) bilden den eigentlichen Kern der Implementierung des Algorithmus:
Zeile 24-26:
Erinnerst Du dich noch, wie ich beim 7er-Beispiel vorgegangen bin?
1,
2,3,4 nacheinander betrachten
1,2,
3,4 nacheinander betrachten
...
Die FOR-Schleife in Zeile 24 stellt also sicher, daß die Additionskette jew. um eine Zahl wächst.
Die FOR-Schleife bei 25 macht dann in jedem Wachstumsschritt diese sequentielle Betrachtung (siehe oben). Dabei muß der Anfang, der durch anfang_bei vorgegeben ist, berücksichtigt werden, da wir sonst nämlich Möglichkeiten von der Art a+b (also z.B. 1+4) überspringen würden.
Und die eigentliche sequentielle Betrachtung geschieht durch die FOR-Schleife in Zeile 26. Du mußt dir das wie eine Grenze vorstellen, die Zahl um Zahl nach rechts verschoben wird, und die Zahlen, die noch nicht betrachtet wurden, werden dann nacheinander zu den Zahlen innerhalb dieser Grenze dazuaddiert (Zeilen 28-33 und 35!). In Zeile 36 wird dann die entsprechende Additionskette schrittweise erzeugt. Zeile 38 lautete ursprünglich: if summe = 112*112 then .... Da das Programm aber keine exakten Lösungen für dein Problem gefunden hat, habe ich nun solche Lösungen zugelassen, deren Summe um weniger als 10 von [mm] $112^2$ [/mm] abweicht. Durch diese Änderung habe ich folgende Lösungen erhalten:
36 + 49 + 64 + 81 + 100 + 121 + 144 + 169 + 196 + 225 + 256 + 289 + 324 + 361 + 400 + 441 + 484 + 529 + 576 + 625 + 676 + 729 + 784 + 841 + 900 + 961 + 1024 + 1156 = 12541 (Abweichung 3)
225 + 256 + 289 + 324 + 361 + 400 + 441 + 484 + 529 + 576 + 625 + 676 + 729 + 784 + 841 + 900 + 961 + 1024 + 2116 = 12541 (Abweichung 3)
361 + 400 + 441 + 484 + 529 + 576 + 625 + 676 + 729 + 784 + 841 + 900 + 961 + 1024 + 1089 + 2116 = 12536 (Abweichung 8)
1089 + 1156 + 1225 + 1296 + 1369 + 1444 + 1521 + 1600 + 1849 = 12549 (Abweichung 5)
1225 + 1296 + 1369 + 1444 + 1521 + 1600 + 1681 + 2401 = 12537 (Abweichung 7)
1849 + 1936 + 2025 + 2116 + 2209 + 2401 = 12536 (Abweichung 8)
Viele Grüße
Karl
|
|
|
| |
|
Hi, karl
Memo1
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 435 29
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 + 30 435 28
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 + 32 435 27
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 + 35 435 26
5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 39 435 25
6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 44 435 24
7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 50 435 23
9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 36 435 22
10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 45 435 21
12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 36 435 20
13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 48 435 19
15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 31 + 44 435 18
17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 31 + 32 + 43 435 17
19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 31 + 32 + 33 + 45 435 16
21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 31 + 32 + 33 + 34 + 50 435 15
22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36 435 15
24 + 25 + 26 + 27 + 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36 + 45 435 14
27 + 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36 + 37 + 38 + 45 435 13
30 + 31 + 32 + 33 + 34 + 35 + 36 + 37 + 38 + 39 + 40 + 50 435 12
34 + 35 + 36 + 37 + 38 + 39 + 40 + 41 + 42 + 43 + 50 435 11
39 + 40 + 41 + 42 + 43 + 44 + 45 + 46 + 47 + 48 435 10
Hi,Karl
Ich habe vor langer Zeit dein Algo bekommen erstmal Danke.
Ich wollte ihn für ein anderes Problem modifizieren dabei mrkte ich das nicht alle möglichen Additionsketten in steigender Folge der Summanden gefiltert werden.
----------------------------------------------------------------------------------------------
1+2+4+6+7+8+9+11+15+16+17+18+19+24+25+27+33+35+37+42+50=435
----------------------------------------------------------------------------------------------
Diese Kette wird nicht gefunden die Quadriert eben diese magische 12544 ergibt.
Also kann das perfekte Quadrat nicht gefunden werden.I
Ich weis nicht ob der Algorithmus noch änderbar ist um auch diese Kette zu finden.
Ich hatte das Programm laut sebastian leider in c++ neu in Delphi dein Algo geändert so das die grossen Q-zahlen zuerst rückwärts zur 1 gefiltert werden.Da kann sich nur die Laufzeit verringern.
Vielen Dank im Vorraus
biochipm
p.s
hatte auf Sebastian geantwortet.
Meine Anfrage ob es auch ananalog zum p. Quadrat einen perfekten Raum geben kann.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:05 Fr 19.01.2007 | | Autor: | biochipm |
Hi, Karl
Entschuldige Bitte dein Algorithmus ist exakt !!!!!!!!!!!!!!!
Jede addkette bis abruch im staeck.
-----------------------------------------------------------------
int [mm] sum_n_square[] [/mm] = {1, 3, 14, 30, 55, 91, /* usw */ }
void findeLoesung(int z, int max)
{
if (z > 0) {
if (!max) return;
int max = MIN(sqrt(z)+1, max);
for (int i = max; i >= 1; i--) {
if (z > [mm] sum_n_square[i]) [/mm] break;
findeLoesung(z-i*i, i - 1);
}
} else if (z < 0) {
return;
} else {
/* loesung gefunden */
}
}
findeLoesung(112, 50);
-----------------------------------------------------------
Sebastians idee leider in c++ wenns keine mühe macht die paar Zeilen in Objektpascal konvertieren um zu testen.
mit den letzten i Quadraten lässt sich z gar nicht mehr
erreichen gar nicht erst auszuprobieren möchte ich laufzeitunterschied vergleichen.
Die positionen=50 da Lösung bekannt Quadrat[i]Max =50*50 und Quadratsumme =12544(soll Kleinstes laut google mit computerprogramm sein).
Wieviel Positionen bei unbekannt? um Lösung zu finden.
Und die ohne computer anfingen fanden eine Lösung im Rechteck.
p.s
Problem war auch google gestellt worden.
Finde nichts mehr oder kann
Gruss
biochipm
I quadrat zu gross in dein Algo drin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:15 So 08.05.2005 | | Autor: | biochipm |
Mein Fehler im Beispiel
In einem Delphiprogramm rekursiv lösen das alle Varianten ausgegeben werden können.
z.B ein Variante mit
2+4+6+7+8+9+11+15+16+17+18+19+24+25+27+29+33+35+37+42+50 =12544
Linkeseiten die ganzen zahlen noch zu quadrieren sind !!
Vielen Dank im Voraus.
Frank
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:44 Sa 14.05.2005 | | Autor: | Karl_Pech |
Hallo Frank,
Ich habe jetzt versucht das Problem rekursiv zu lösen. Das heißt sämtliche Möglichkeiten durch Ausnutzung des Kommutativgesetzes durchzuprobieren und bin gescheitert.
Woran bin ich gescheitert? Das Problem scheint einfach zu komplex zu sein, um alle Fälle durchzuprobieren. Ich habe jedenfalls meine Idee aus der vorigen Antwort benutzt:
Zahlen: 1,2,3,4
Resultat: 7
Betrachte
1
Betrachte
1+2
1+3
1+4
Betrachte
1+2+3
1+2+3+4
1+2+4
1+3+4
Betrachte
2+4
2+3
2+3+4
Betrachte
3+4
Betrachte
4
Ich denke ein Algorithmus, der nach diesem Schema arbeitet, sollte alle Möglichkeiten berücksichtigen. Und hier ist meine Implementierung:
| 1: |
| | 2: | program quadzahl2;
| | 3: |
| | 4: | uses Classes,
| | 5: | SysUtils;
| | 6: |
| | 7: | var
| | 8: | quadzahlen : array[1..50] of integer;
| | 9: | protokoll : tstringlist;
| | 10: |
| | 11: | procedure Init;
| | 12: | var
| | 13: | i : integer;
| | 14: | begin
| | 15: | for i := 1 to 50 do
| | 16: | quadzahlen[i] := i*i;
| | 17: |
| | 18: | protokoll := tstringlist.Create;
| | 19: | end;
| | 20: |
| | 21: | procedure FindeLoesungen(szsumme : string; summe, position : integer);
| | 22: | var
| | 23: | i, Resultat : integer; szresultat : string;
| | 24: | begin
| | 25: | for i := position to 50 do
| | 26: | begin
| | 27: | Resultat := summe + quadzahlen[i];
| | 28: | szresultat := szsumme+' + '+IntToStr(quadzahlen[i]);
| | 29: |
| | 30: | if Resultat = 112*112 then
| | 31: | protokoll.Add(szresultat);
| | 32: |
| | 33: | if quadzahlen[i] < 50*50 then
| | 34: | FindeLoesungen(szresultat, Resultat, i+1);
| | 35: | end;
| | 36: | end;
| | 37: |
| | 38: |
| | 39: | begin
| | 40: | Init;
| | 41: | FindeLoesungen('0', 0, 1);
| | 42: |
| | 43: | protokoll.SaveToFile('out.txt');
| | 44: | end.
|
Die for-Schleife stellt sicher, daß wir bei jeder der 50 Quadratzahlen mit dem Addieren anfangen. Zu jeder Anfangszahl können wir alle möglichen weiteren Summanden rekursiv durchprobieren. Dies tun wir schrittweise durch i+1 im rekursiven Aufruf. Die Idee ist die Summen der jeweiligen Addition auf dem Stack zu speichern, so daß wir beim Rücksprung zur vorherigen Summe zurückkehren können.
Das Problem ist nur, daß es offenbar sehr viele Fälle gibt, die man so ausprobieren müßte. Und das ist sogar für meinen 300 MHZ Computer zu viel. (Nach einer Stunde Rechenzeit habe ich abgebrochen.)
Offensichtlich ist dieser Algorithmus vollkommen ineffizient (und irgendwie bezweifele ich, daß es da noch etwas besseres gibt. Andererseits wer weiß, vielleicht könnten hier ja weitere mathematische Überlegungen weiterhelfen ...).
(Es gibt natürlich immer noch die Möglichkeit, daß der Algo. falsch ist, aber das bezweifele ich, obwohl meine Zweifel natürlich kein Beweis sind.)
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:16 So 15.05.2005 | | Autor: | Karl_Pech |
Hallo Frank,
Ich weiß nicht, ob es dich noch interessiert, aber ich habe jetzt deine Frage auch ![[]](/images/popup.gif) hier gestellt. Den Algorithmus, der dort von Sebastian angegeben wurde, solltest Du mal ausprobieren.
Viele Grüße
Karl
|
|
|
|
