Zerlegung in Quadratzahlen

Dieses Thema im Forum "C/C++" wurde erstellt von Bloodsurfer, 22.04.2007.

  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. Anzeige

    Schau dir mal diese Kategorie an. Dort findest du bestimmt etwas.
    Registrieren bzw. einloggen, um diese und auch andere Anzeigen zu deaktivieren
  3. #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!
     
  4. #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