Zerlegung in Quadratzahlen

Diskutiere Zerlegung in Quadratzahlen im C/C++ Forum im Bereich Programmieren unter Linux/Unix; Hallo Leute. Ich versuche gerade ein eigentlich simples Problem zu lösen - ich will eine Zahl n in zwei Quadratzahlen zerlegen, sofern möglich....

  1. #1 Bloodsurfer, 22.04.2007
    Bloodsurfer

    Bloodsurfer Gentoo-User

    Dabei seit:
    15.10.2005
    Beiträge:
    243
    Zustimmungen:
    0
    Hallo Leute.
    Ich versuche gerade ein eigentlich simples Problem zu lösen - ich will eine Zahl n in zwei Quadratzahlen zerlegen, sofern möglich.
    In etwa so:
    Die Zahl 9 ist zerlegbar in 3^2 + 0^2.
    Die Zahl 10 ist zerlegbar in 3^2 + 1^2.

    Ne kleine Lösung hab ich schnell gebastelt:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    int main(int argc, char** argv) {
    	
    	if (argc != 2) {
    		printf("Bitte genau eine Zahl als Argument eingeben!\n");
    		return 1;
    	}
    
    	long n=atol(argv[1]); //wandelt erstes Argument der Kommandozeile in Zahl um
    	long qz1=0;
    	long qz2=0;
    
    	//suche erste Quadratzahl die ein Teil von n ist
    	while ((qz1*qz1)<=n) {
    	
    		//suche zweite Zahl
    		while (((qz1*qz1)+(qz2*qz2)) <= n && qz2<=qz1) {
    			
    			//gebe Zahlen aus falls das Ergebnis passt
    			if (((qz1 * qz1) + (qz2 * qz2)) == n) {
    				printf("Die Zahl %d ist zerlegbar in %d^2 + %d^2.\n", n, qz1, qz2);
    			}
    			
    			qz2 ++;
    		}
    		qz1 ++;
    		qz2=0;
    	}
    }
    
    Das funktioniert mit kleinen Zahlen einwandfrei, aber es ist zugegebenermaßen sehr ineffizient und bei grossen Zahlen, wie z.B. 72003446399952, kann man es vergessen, würde ja stundenlang laufen.
    Daher meine Frage: Hat jemand einen Vorschlag, wie ich das effizienter gestalten könnte um auch bei sehr grossen Zahlen zu einem Ergebnis zu kommen?
     
  2. #2 matzeed7, 23.04.2007
    matzeed7

    matzeed7 Mitglied

    Dabei seit:
    28.10.2006
    Beiträge:
    38
    Zustimmungen:
    0
    vielleicht mit einem divide and conquer Algorithmus oder einfach
    einen randomisierten Algorithmus entwerfen!
     
  3. #3 b00, 23.04.2007
    Zuletzt bearbeitet: 23.04.2007
    b00

    b00 Haudegen

    Dabei seit:
    28.03.2007
    Beiträge:
    597
    Zustimmungen:
    0
    Ort:
    /root
    .. ich glaube für dieses problem kenn keiner eine lösung auf liniarkomputern in polinomialzeit

    ich empfehle dir einen quantencomputer mit wehnigstens 128qbit :D

    also random walk ist ein guter lösungsansatz ich würde aber eher matizenmutation verwenden

    da hasst du dir aber ein problem ausgesucht über dem du :oldman wirst

    .oO( ach du schreck hab ich doch glatt eine mathe vorlesung verpennt )
     
Thema: Zerlegung in Quadratzahlen
Besucher kamen mit folgenden Suchen
  1. zerlegung in quadratzahlen