[link] Project Euler - Programmieraufgaben

Mein Ansatz für Problem 14 scheint nicht die richtige Lösung auszugeben. Vielleicht findet ja jemand den Fehler:
Code: 
#include <iostream>
using namespace std;

int main() {
    int test, i, tmp, max=0, top=0;
    for(test=0; test < 1000000; test++) {
        //cout << test;
        i = 1;
        tmp = test;
        while(tmp > 1) {
            if(tmp % 2 == 0) {
                tmp /= 2;
                //cout << "->" << tmp;
            } else {
                tmp = 3 * tmp + 1;
                //cout << "->" << tmp;
            }
            i++;
        }
        if(i>=max) {
            max=i;
            top=test;
            cout << top << ": " << max << endl;
        }
        //cout << " = " << i << endl;
        i = 0;
    }
    cout << endl << "Longest chain: " << top << ": " << max << endl;
}
 
Original von Eydeet
Mein Ansatz für Problem 14 scheint nicht die richtige Lösung auszugeben. Vielleicht findet ja jemand den Fehler:
Code: 
#include <iostream>
using namespace std;

int main() {
    int test, i, tmp, max=0, top=0;
    for(test=0; test < 1000000; test++) {
        //cout << test;
        i = 1;
        tmp = test;
        while(tmp > 1) {
            if(tmp % 2 == 0) {
                tmp /= 2;
                //cout << "->" << tmp;
            } else {
                tmp = 3 * tmp + 1;
                //cout << "->" << tmp;
            }
            i++;
        }
        if(i>=max) {
            max=i;
            top=test;
            cout << top << ": " << max << endl;
        }
        //cout << " = " << i << endl;
        i = 0;
    }
    cout << endl << "Longest chain: " << top << ": " << max << endl;
}
Zum Vergrößern anklicken....
Du machst den selben Fehler wie ich. tmp wird irgendwann groesser als der maximale Wert, den ein signed integer aufnehmen kann, und wird dann vom Rechner als negative Zahl interpretiert. Daraufhin bricht er die Schleife ab (weil ein negativer Wert nicht > 1 ist). Deklarier tmp mal als unsigned, dann sollte es funktionieren.
 
glaubt Ihr, dass es für 137 zu viel wäre, eine eigene Klasse zu schreiben, die mir einen neuen Zahlentyp definiert? :D Sowas wie bigInt, nur dass ich mich dabei dann selbst besser auskenn, weil ichs ja selbst gemacht hab... :) nen Ansatz für das Problem hab ich schon, nur sind meine verfügbaren Datentypen zu klein -.-

Haben die Formel schon mal vor Ewigkeiten auf nem Übungsblatt in dem Semester bewiesen, is eigentlich total einfach ;)
 
Original von Janus
glaubt Ihr, dass es für 137 zu viel wäre, eine eigene Klasse zu schreiben, die mir einen neuen Zahlentyp definiert? :D Sowas wie bigInt, nur dass ich mich dabei dann selbst besser auskenn, weil ichs ja selbst gemacht hab... :) nen Ansatz für das Problem hab ich schon, nur sind meine verfügbaren Datentypen zu klein -.-
Zum Vergrößern anklicken....
reicht Dir denn irgendein 64-Bit Typ nicht?

Ansonsten: mit Papier & Sift dauert es wohl ca. 25-35Min.
Mit Papier, Stift und Taschenrechner (während der Busfahrt nach Hause war kein "Großrechner" verfügbar ;) ):
ca 15-20 Min (die letzte Zahl hat mein Taschenrechner nicht mehr gepackt und ich musste mich an die "analoge" Rechenarten aus der Grundschulle erinnern :) )

Einmal nach "golden nuggets" suchen - was findet man diesbezüglich?
Dann das Groß-Phi (die Bildung) bei Wiki anschauen und die Summenformel suchen.

Bei dieser überlegen, welche Bedingung erfüllt sein muss, damit eine ganze Zahl herauskommt (sonst wäre es ja kein "nugget"). Jetzt nochmal das Groß-Phi anschauen und sich eventuell die Fibonaccifolge aufschreiben und paar Zahlen mit der Formel berechnen :)
Ich wollte es anfangs auch durch BF lösen - man merkt aber dass Floats nicht genau genug sind und BigLibs sind um Faktoren langsamer. Also wollte ich mir eine Optimierung für den BF überlegen und bin über "10 Umwege" auf die Lösung gestoßen.
 
nuja, mein Ansatz isn bisschen Brute-Force-like ^^

wir haben das ja wie gesagt in der uni schon ma bewiesen, dass man den Wert dieser Summe direkt berechnen kann. Von dieser Gleichung hab ich dann eben den positiven Wert der Umkehrfunktion genommen und da kommt halt ne Wurzel vor. Da ich da nur ganze Zahlen reinstopfe, steht unter der Wurzel ne ganze Zahl. Damit der ganze Ausdruck dann rational wird, muss also unter der Wurzel auch eine Quadratzahl stehen. Und jetz überprüf ich einfach, welche Zahlen i^2 = Ausdruck unter der Wurzel sind, wobei ich halt erst x laufen lass und innendrin i (ich wieß, performance is scheiße ^^) und da werden die zahlen halt doch relativ groß, wenn ich se quadriere... und deswegen hab ich mir gedacht, bau ich mir meinen eigenen BigInt, der eben die Anforderungen erfüllt, die ich brauch, d.h. im Grunde genommen nur Multiplikation...

Und nebenbei kann ich den dann auch für andere Aufgaben nehmen, z.B. für die letzen paar Ziffern von 100! ;)
 
Hat jemand zu Problem 136 eine Lösung? Hab mal was in Java geschrieben um die Behauptung zu prüfen, es gäbe unter 100 nur 25 eindeutige Lösungen. Ich komme aber auf 26.... Vielleicht kann sich das ja jmd mal anschauen.
Code: 
public class Problem136 {
	public static final int grenze = 100;
	public static final int maxvorkommen = 1;
	public static void main(String[] argv){	
		int zaehler = 0;
		for(int n=1;n<grenze;n++){
			if(dothecheck2(n,grenze,maxvorkommen)){
				System.out.println("eindeutige zahl: "+n);
				zaehler++;
			}
		}	
		System.out.println("Anzahl der "+maxvorkommen+" mal vorkommenden Zahlen: "+zaehler);

	}	
	public static boolean dothecheck2(int n, int grenze, int maxvorkommen){
		int zaehler = 0;
		boolean check = false;
		for(int y=grenze-1;y>=1;y--){
			int tempd = grenze -y;
			if(tempd>=y){
				tempd =y-1;
			}
			for(int d=tempd;d>=1;d--){
				int x = y+d;
				int z = y-d;
				if((x*x)-(y*y)-(z*z)== n && y > d){
					System.out.println(x+"?-"+y+"?-"+z+"?="+n);
					zaehler++;
				}
			}
		}
		if(zaehler == maxvorkommen){
			check = true;
		}
		return check;
	}	
}
Code: 
4?-3?-2?=3
3?-2?-1?=4
9?-7?-5?=7
14?-11?-8?=11
8?-6?-4?=12
6?-4?-2?=16
24?-19?-14?=19
13?-10?-7?=20
29?-23?-17?=23
18?-14?-10?=28
39?-31?-23?=31
54?-43?-32?=43
28?-22?-16?=44
59?-47?-35?=47
16?-12?-8?=48
33?-26?-19?=52
74?-59?-44?=59
84?-67?-50?=67
43?-34?-25?=68
89?-71?-53?=71
48?-38?-28?=76
99?-79?-59?=79
26?-20?-14?=80
37?-29?-21?=87
58?-46?-34?=92
25?-19?-13?=95

Anzahl der 1 mal vorkommenden Zahlen: 26
 
Ich komm auf 28 ?(
Code: 
#include <iostream>
using namespace std;

bool check_unique(int n, int max) {
    int x,y,z,sub,solution,count=0;
    int save[4] = {0,0,0,0};
    for(x=0; x<max; x++) {
        for(sub=1; sub<x-sub*2; sub++) {
            y = x - sub;
            z = y - sub;
            solution = x*x - y*y - z*z;
            if(solution == n) {
                if(count == 1) return false;
                save[0]=x; save[1]=y; save[2]=z; save[3]=solution;
                count++;
            }
        }
    }
    if(count == 1) {
        cout << save[0] << "^2 - " << save[1] << "^2 - " << save[2] << "^2 = " << save[3] << endl;
        return true;
    }
    return false;
}

int main() {
    int i,count=0,max=100;
    for(i=0; i<max; i++) {
        if(check_unique(i,max)) {
            count++;
        }
    }
    cout << "Count: " << count << endl;
}
Code: 
4^2 - 3^2 - 2^2 = 3
3^2 - 2^2 - 1^2 = 4
9^2 - 7^2 - 5^2 = 7
14^2 - 11^2 - 8^2 = 11
8^2 - 6^2 - 4^2 = 12
6^2 - 4^2 - 2^2 = 16
24^2 - 19^2 - 14^2 = 19
13^2 - 10^2 - 7^2 = 20
29^2 - 23^2 - 17^2 = 23
18^2 - 14^2 - 10^2 = 28
39^2 - 31^2 - 23^2 = 31
11^2 - 8^2 - 5^2 = 32
54^2 - 43^2 - 32^2 = 43
28^2 - 22^2 - 16^2 = 44
59^2 - 47^2 - 35^2 = 47
16^2 - 12^2 - 8^2 = 48
33^2 - 26^2 - 19^2 = 52
74^2 - 59^2 - 44^2 = 59
84^2 - 67^2 - 50^2 = 67
43^2 - 34^2 - 25^2 = 68
89^2 - 71^2 - 53^2 = 71
48^2 - 38^2 - 28^2 = 76
99^2 - 79^2 - 59^2 = 79
26^2 - 20^2 - 14^2 = 80
37^2 - 29^2 - 21^2 = 87
18^2 - 13^2 - 8^2 = 91
58^2 - 46^2 - 34^2 = 92
25^2 - 19^2 - 13^2 = 95
Count: 28
 
Original von Eydeet
Ich komm auf 28 ?
Zum Vergrößern anklicken....
Dein Code scheint auch nicht ganz zu funktionieren, hier die beiden die bei dir nicht richtig sind:
11?-8?-5?=32
7?-4?-1?=32
und
18?-13?-8?=91
12?-7?-2?=91

Kannst du deinen Code mal auf Problem 135 loslassen?
Dort wird behauptet, 1155 ist die erste Zahl, die 10 Lösungen für die Gleichung x?-y?-z?=n hat.
Hier komme ich mit meinem Code auf 9 Lösungen.
 
Wenn ich max auf 10000 stelle, bekomme ich folgende 10 Ergebnisse:
Code: 
40^2 - 21^2 - 2^2 = 1155
50^2 - 33^2 - 16^2 = 1155
52^2 - 35^2 - 18^2 = 1155
74^2 - 55^2 - 36^2 = 1155
100^2 - 77^2 - 54^2 = 1155
134^2 - 105^2 - 76^2 = 1155
208^2 - 165^2 - 122^2 = 1155
290^2 - 231^2 - 172^2 = 1155
482^2 - 385^2 - 288^2 = 1155
1444^2 - 1155^2 - 866^2 = 1155
Ich hab meinen Code verbessert und komme jetzt auch auf 26 Resultate...
 
Aufgabe 138

Muss man bei Aufgabe 138 die Summe der Schenkellängen L1,L2, ... L12 rechnen oder die Summe aller Schenkellängen, also 2*L1 + 2*L2 ... Ich habe beides versucht, aber mein Resultat ist falsch, obwohl mein Programm eigentlich funktionieren sollte ... Hab ich was falsch verstanden? Ich bitte um Aufklärung :)

###################

Aufgabe 100

Code: 
var res:boolean;
    all,blue:real;

begin
 res := false;
 // all:=119;                                      Zum Testen...
 all:=1E12-1;                                   // 1'000'000'000'000' - 1
  while res = false do
   begin
    all:=all+1;
    blue := ( sqrt( 2*sqr(all)-2*all+1 )+1)/2; // Algorithmus für 120 getestet
    if Frac(blue) = 0 then res := true;        // wenn Nachkomma-Anteil 0 dann
   end;
  writeln('Gesamtzahl der Kugeln: ',all);
  writeln('Anzahl blauer Kugeln:  ',blue);
  readln;
end.

Könnte sich das bitte jemand anschauen und mir sagen warum es bei 120 Kugeln geht, bei 1E12 Kugeln aber nicht? (Es ist Delphi 6 Quelltext)
 
Hallo,
@Cybermaster: Ich habe das gleiche Problem, mein Prog. funktioniert soweit, aber die Summe wird nicht akzeptiert.
Ich habe folgendes raus:
87xxx7755 (bei der einfachen Addition von L)

Auch wenn ich die beiden gegebenen Dreiecke entferne, akzeptiert die Seite nicht die Summe. Hab es mit beiden Varianten, also mit der Verdopplung, probiert, ohne Erfolg.

Wenn du weiter kommst, gib bitte bescheid.
 
Ich hab das Resultat jetzt nicht im Kopf, aber ich bekomme was von der gleichen Grössenordnung raus. Da ich nicht weiter wusste und sich hier auch niemand gemeldet hat (an dieser Stelle ein Dankeschön an dich ;)) hab ich "Euler" eine Mail geschrieben weil ich dachte ich hätte vielleicht was bei der Angabe falsch verstanden. Doch es ist so wie ich schon dachte, das Sigma steht wie sonst auch für Summe und man muss einfach nur die Länge L der 12 Dreiecke adieren... Ich weiss echt nicht weiter.

Hast du dir mal meinen Code für Problem 100 angeschaut? Da werd ich auch nicht schlau warum das falsch sein soll. Ich hab gedacht dass es vielleicht an einem Overflow oder so liegt, aber das scheint mir unwahrscheinlich.
 
Hallo,
hmm evt. ist real zu ungenau und representiert die Zahl nicht richtig, bzw. in einer späteren Rechnung.

Aber ich habe nun Problem 138 gelöst.
Das Problem ist, dass double zu ungenau ist, du errechnest dort dann Längen von x.9999999995434 was dann in Double auf Glatte x+1 gerundet wird, und somit die Bedingung erfüllt, weil es ja kein Nachkomma-Anteil hat.


Ich habe meinen Code nun auf ausschließlich long (64 Bit) umgeschrieben und bin gerade am Rechnen, hab die ersten 10 Dreiecke "schon".


Kleiner Tipp:
Nicht viel Programmieren, sondern erst Mathematisch angehen, so kann man seinen Algorithmus extrem verbessern, denn das 10. Dreieck ist im Bereich von 3 Billionen!
Also am besten die ersten 6 Dreiecke untersuchen und feststellen, welche Gemeinsamkeiten die haben, sonst läuft der Code ewig (meiner etwa 10 Minuten jetzt).

Die ersten 6 Dreiecke:
b: 16 l: 17
b: 272 l: 305
b: 4896 l: 5473
b: 87840 l: 98209
b: 1576240 l: 1762289
b: 28284464 l: 31622993


Edit:
Arg ein Überlauf in long.
Man muss echt aufpassen dabei.

Vorallem das Quadrat ist problematisch, denn dadurch dürfen die Zahlen nur 32 Bit groß sein, sonst Überlauf in der Quadration der Höhe :/

Jetzt habe ich dies umgestellt auf eine mixture von Decimal und ulong.
Die bisherigen 8 Dreiecke sind richtig. Mal hoffen das ich keins übersehen habe.
 
@ Janus

Nicht viel Programmieren, sondern erst Mathematisch angehen, so kann man seinen Algorithmus extrem verbessern
Zum Vergrößern anklicken....

Schnapp dir mal einen Taschenrechner und bemüh deine grauen Zellen ein bisschen ;) Ich bin nicht sicher ob es richtig ist, aber ich habe eine Zahlenfolge gefunden mit der sich b (und dank Pythagoras also auch l) bestimmen lässt. Ich hab aber erst die Rohform.
 
Hallo,
Original von Janus
habt Ihr da nen intelligenten Ansatz? Ich hab mal wieder (wie immer) nen BruteForce-Ansatz ^^
Zum Vergrößern anklicken....
Also wenn man sich die Formel anschaut, stellt mal relativ schnell fest, welche bestimmte Eigenschaft b erfüllen muss, um überhaupt der Überprüfung wert zu sein.


Dann mein anderes Theorem kann ich mathematisch zwar nicht beweisen, aber die ersten 7 Dreiecke bestätigen dieses.
Musst einfach schauen, welche Gemeinsamkeiten die Zahlen so haben.


Edit:
*Freu* Habs geschafft.

Original von Janus
Ich hab mal wieder (wie immer) nen BruteForce-Ansatz ^^
Zum Vergrößern anklicken....
Nicht zu empfehlen.

Mein Programm braucht nur 0,016 Sekunden und benötigt nur 170 Rechnungen! 8o

Wenn du dies per Brute Force machst, benötigst du fast 1 Billiarde (10^15) Rechnungen und entsprechend viel Zeit. Nur durch die Bestätigung des zweiten Theorems kann man den Algorithmus so verschlanken.


Was so kompliziert war, war dass ich keine vernünftigen Datentypen habe.
ulong (64 Bit) ist bei dem 8. Dreieck übergelaufen, double war zu ungenau. Dann benutzte ich bis zum 12. Dreieck decimal (128 Bit und 29 Stellen genau), allerdings für das 12 Dreieck ist auch dieser Datentyp übergelaufen und ich musste auf BigInteger/String-Arithmetik zurückgreifen.

Wie gesagt, nur per Brute Force kann man diese Aufgabe nicht lösen, sondern man muss die Zahlen genauer betrachten. Dies geht soweit, dass man die Aufgabe fast per Hand lösen kann, wären die Zahlen nicht so groß.
 
Hi, freut mich, dass du es geschafft hast! Ich hab auch ne Idee wie ich es lösen kann. Ich werds mal mit Pen & Paper versuchen wenn mein Taschenrechner das verkraftet, ich bin nämlich nicht so scharf auf das ganze Datentypen gebastel ...

Bin etwas erstaunt zu welcher Grösse dieser Thread angewachsen ist :D
 
Hallo,
hmm würde vom handelsüblichen Taschenrechner abraten, da dieser zu ungenau ist.


Sonst gibt es auf Codeporject.com eine BigInteger Klasse, die echt super leicht zu bedienen ist, womit man fast so wie mit normalen Zahlen rechnen kann (also +-*/ klappt alles super).
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben