www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Wettbewerbe" - Quadratzahl=quadratsumme
Quadratzahl=quadratsumme < Wettbewerbe < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Quadratzahl=quadratsumme: 21 von 50 Quadraten(1^2-50^2
Status: (Frage) beantwortet Status 
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]
        
Bezug
Quadratzahl=quadratsumme: Antwort
Status: (Antwort) fertig Status 
Datum: 01:50 Do 16.02.2006
Autor: andi_bar

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.

Bezug
                
Bezug
Quadratzahl=quadratsumme: Beginn Grosse Q-zah->Q=1l
Status: (Frage) überfällig Status 
Datum: 17:17 Sa 13.01.2007
Autor: biochipm

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




Bezug
                        
Bezug
Quadratzahl=quadratsumme: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:20 Di 13.02.2007
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Quadratzahl=quadratsumme: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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



Bezug
                
Bezug
Quadratzahl=quadratsumme: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Quadratzahl=quadratsumme: Antwort
Status: (Antwort) fertig Status 
Datum: 14:44 Di 03.05.2005
Autor: Karl_Pech

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



Bezug
                
Bezug
Quadratzahl=quadratsumme: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 18:34 So 14.01.2007
Autor: biochipm

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.





Bezug
                        
Bezug
Quadratzahl=quadratsumme: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
        
Bezug
Quadratzahl=quadratsumme: Korektur
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Quadratzahl=quadratsumme: Ausprobieren zu ineffizient?
Status: (Mitteilung) Reaktion unnötig Status 
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



Bezug
                
Bezug
Quadratzahl=quadratsumme: weitere Diskussion
Status: (Mitteilung) Reaktion unnötig Status 
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 []hier gestellt. Den Algorithmus, der dort von Sebastian angegeben wurde, solltest Du mal ausprobieren.


Viele Grüße
Karl




Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de