[link] Project Euler - Programmieraufgaben

also wenn du anfängst mit sagen wir 10! ist das ja 1*...*10 so jetzt lässt du 1, 10 weg, da sie an der Quersumme nix ändern. dann lässt du 2 und 5 weg weil sie auch nix ändern, bleibt:

3*4*6*7*8*9

als nächstes stocken wir sagen wir mal bis 15 auf:

3*4*6*7*8*9*11*12*13*14*15

daraus wird dann (ja du hast recht ich meine natürlich die auf 2,5 enden nicht die dadurch teilbar sind^^):

3*4*6*7*8*9*(10+1)*(10+3)*(10+4)*(12*15)

woraus dann:

3*(3*4*6*7*8*9*(10+1)*(10+3)*(10+4))

sei nun Q(x) die Quersumme von x

dann ist

Q(3*(3*4*6*7*8*9*(10+1)) =Q(3*(3*4*6*7*8*9))+Q(3*(3*4*6*7*8*9))
Q(3*(3*4*6*7*8*9*(10+1)*(10+3))=Q(3*(3*4*6*7*8*9*(10+1))+Q(9*3*(3*4*6*7*8*9*(10+1))

und damit erhält man:
Q(3*(3*4*6*7*8*9*(10+1)*(10+3))=2*Q(3*(3*4*6*7*8*9))+Q(3*2*Q(3*(3*4*6*7*8*9))

wobei hier a=2 und b=3*2

habe gerade nachgeguckt, am Ende ergibt sich nich ax+bx sondern a*Q(x)+Q(b*Q(x))+Q(c*Q(x))
wobei x= 3*4*6*7*8*9 und c die ganzen Zahlen mit 2 und 5 am ende und durch 10 teilbar sind die man noch geeignet verrechnen muss. (c enthält verdammt viele Nullen, die weggekürzt werden müssen).

(Argh ich glaube das ist immer noch nicht verständlich...) Die Grundidee ist jedenfalls alles so zusammenzufassen, das man das eigentliche Produkjt außer x nicht berechnen muss. a,b,c bleiben ziemlich klein
 
Ich könnt ausflippen :D beim Problem 2 mache ich irgendwas falsch

Code: 
#include <iostream.h>
#include <conio.h>
//---------------------------------------------------------------------------

void main(void)
{
  int erg=0, zahl2=2, mille=0;
  for(int zahl1=1; mille<=1000000; zahl1=zahl2,zahl2=mille )
  {
    mille=zahl1+zahl2;
    erg+=mille;
    cout << erg;
    cout << "----";
    cout << mille;
    cout << endl;
  }
  getch();
}
 
Original von Copykill
also wenn du anfängst mit sagen wir 10! ist das ja 1*...*10 so jetzt lässt du 1, 10 weg, da sie an der Quersumme nix ändern. dann lässt du 2 und 5 weg weil sie auch nix ändern
Zum Vergrößern anklicken....

dass 1 und 10 nichts ändern habe ich verstanden, aber wieso sollen 2 & 5 nichts ändern?
beispiel: 13 -> Quersumme 4; 13*2 = 26 -> Quersumme 8
In Kombination verändern sie aber nichts, da hast du Recht: 26*5 = 130 -> Quersumme 4
wenn man jetzt aber die fakultät von 4 ausrechnen will, darf man die 2 nicht weglassen (ich weiß, ich bin ein bisschen pingelig :D)

aber ansonsten ist mir jetzt alles schonmal etwas klarer :)
Vielen Dank!
 
Original von Heinzelotto
Original von Copykill
also wenn du anfängst mit sagen wir 10! ist das ja 1*...*10 so jetzt lässt du 1, 10 weg, da sie an der Quersumme nix ändern. dann lässt du 2 und 5 weg weil sie auch nix ändern
Zum Vergrößern anklicken....

dass 1 und 10 nichts ändern habe ich verstanden, aber wieso sollen 2 & 5 nichts ändern?
beispiel: 13 -> Quersumme 4; 13*2 = 26 -> Quersumme 8
In Kombination verändern sie aber nichts, da hast du Recht: 26*5 = 130 -> Quersumme 4
wenn man jetzt aber die fakultät von 4 ausrechnen will, darf man die 2 nicht weglassen (ich weiß, ich bin ein bisschen pingelig :D)

aber ansonsten ist mir jetzt alles schonmal etwas klarer :)
Vielen Dank!
Zum Vergrößern anklicken....

13*2*5 = 130 =13 =4 also kann ich 2 und 5 weglassen (nur in kombination) bei 12 und 15 muss man schon seinen b modifikator anpassen, da 12*15 = 180 = 18 = 10+8 etc ist. Daher wäre das ganze wirklich von Hand zu machen etwas undankbar (ich gebe zu die Bemerkung mit blatt und papier war etwas ketzerisch^^) aber das ganze dient schließlich nur die Zahlen klein zu halten...
 
Die Ideen von CopyKill zur Aufgabe 2 sind zwar interessant, aber viel zu komplex im Verhältnis zum notwendigen Lösungsaufwand.

Zuerst mal ist die Aufgabe nicht eindeutig formuliert, so daß (zumindest an dieser Stelle in der Aufgabenliste) nicht feststeht, ob mit "erste" die betreffenden höher- oder niederwertigsten Ziffern gemeint sind.

Dann ist es viel einfacher als das Begreifen der Quersummenspielerei, falls man gerade keine Bibliothek zum Verrechnen großer Zahlen dabei hat, eine kleine Hilfsfunktion zu schreiben, die einem das Multiplizieren von beliebig langen Ziffernketten im Dezimalsystem erledigt: Dazu ist nur elementare Mathematik der zweiten Klasse notwendig.
Vom CPU-Rechenaufwand her ist das alles immer noch Kickifax.

Wenn man sowas wie die _höherwertigsten_ Stellen von Konstrukten wie x ^ (x ^ x) (oder auch wie hier irgendwelchen Fakultäten) berechnen will, kann man zu zwei sehr einfachen und später im "EulerProject" eh noch nützlichen Verfahren zurückgreifen:

a) skalieren, so daß das Zeug als gebrochene Zahl im Bereich von 8-Byte-Fließkomma dargestellt bleibt
b) die Produktbildung zerlegen (und damit den vermeintlich unbeherrschbar großen Exponenten wieder verfahrenstechnisch logarithmieren - so wie das in den Bibliotheken für große Zahlen auch gemacht wird)

Beides ist unabhängig nutzbar.

Wenn man nur an den niederwertigsten Stellen solcher Konstrukte interessiert ist, macht man statt Skalierung eine einfache Abschneidung der höherwertigen Stellen und Basta!
 
Original von Harry Boeck
Die Ideen von CopyKill zur Aufgabe 2 sind zwar interessant, aber viel zu komplex im Verhältnis zum notwendigen Lösungsaufwand.

...Dann ist es viel einfacher als das Begreifen der Quersummenspielerei, falls man gerade keine Bibliothek zum Verrechnen großer Zahlen dabei hat, eine kleine Hilfsfunktion zu schreiben, die einem das Multiplizieren von beliebig langen Ziffernketten im Dezimalsystem erledigt: Dazu ist nur elementare Mathematik der zweiten Klasse notwendig.
Vom CPU-Rechenaufwand her ist das alles immer noch Kickifax.
Zum Vergrößern anklicken....
Natürlich geht es so, aber du musst trotzdem die häßliche falkultät ausrechnen, da hatte ich keine Lust zu (sonst hätte ich die Sache kurz in implementiert). Wenn du riesige Fakultäten nimmst, wird das ganze trotzdem richtig häßlich speicherintensiv.
Original von Harry Boeck
a) skalieren, so daß das Zeug als gebrochene Zahl im Bereich von 8-Byte-Fließkomma dargestellt bleibt
Zum Vergrößern anklicken....
Kannst du diese Skalierung mal erklären? Wie verhindere ich denn, das mir durch die Rechenungenauigkeit Stellen verloren gehen?
 
Nein, Stellen gehen verloren, aber wenn NUR die ersten 10 Dezimalstellen oder so gewünscht sind, ein normales "double" 16 liefert und nur ein paar zig bis hundert Operationen notwendig sind, kann man MEIST diesen Seiteneffekt ignorieren. Ausnahmen sind natürlich alle Fälle, wo es um die Nähe eines Umschaltpunktes in den höheren Ziffern geht (also eine Reihe 9en oder 0en mitten drin).

Ansonsten zum Skalieren: Einfach willkürlich entweder einen Skalierungsfaktor festlegen, mit dem man im konkreten Fall über die Runden kommt, oder fallabhängig immer wieder mal um ein (paar) Zehnerpotenzen schieben... Die Stellenverschiebung ändert ja nichts an den Ziffern (dieselbe Idee wie bei dem allerdings komplexeren Verfahren von CopyKill).
 
Original von Harry Boeck
Nein, Stellen gehen verloren, aber wenn NUR die ersten 10 Dezimalstellen oder so gewünscht sind, ein normales "double" 16 liefert und nur ein paar zig bis hundert Operationen notwendig sind, kann man MEIST diesen Seiteneffekt ignorieren. Ausnahmen sind natürlich alle Fälle, wo es um die Nähe eines Umschaltpunktes in den höheren Ziffern geht (also eine Reihe 9en oder 0en mitten drin).

Ansonsten zum Skalieren: Einfach willkürlich entweder einen Skalierungsfaktor festlegen, mit dem man im konkreten Fall über die Runden kommt, oder fallabhängig immer wieder mal um ein (paar) Zehnerpotenzen schieben... Die Stellenverschiebung ändert ja nichts an den Ziffern (dieselbe Idee wie bei dem allerdings komplexeren Verfahren von CopyKill).
Zum Vergrößern anklicken....

bei der aufgabe brauche ich aber alle 158 Stellen, also stehe ich wieder vor dem problem der Zahlengröße
 
Original von Harry Boeck
Ja, richtig. Ich war mit meinen Gedanken schon wieder ganz woanders (bei Deiner Anregung "die letzten 3 Stellen von 9^9^9"...).
Zum Vergrößern anklicken....

wobei man das Problem mithilfe von Kongruenzen wirklich auf einem Blatt papier lösen kann (zahlen größer 1000 kommen nich vor)
 
Hallo Leute,

sitze hier vor Problem 124 und bin mir sehr sicher, dass ich es gelöst habe, doch leider wird mein Ergebnis als falsch angesehen.

Hier mein Ergebnis im Bereich von 1<= n <= 10:
Code: 
Unsortiert
n  rad(n) k
1    1    1
2    2    2
3    3    3
4    2    4
5    5    5
6    6    6
7    7    7
8    2    8
9    3    9
10    10    10

Sortiert
n  rad(n) k
1    1    1
2    2    2
4    2    3
8    2    4
3    3    5
9    3    6
5    5    7
6    6    8
7    7    9
10    10    10

E(6): 9

Es stimmt genau mit dem Beispiel überein.
Wenn ich E(k) jedoch für den Bereich von 1 <= n <= 100000 berechne, komm ich auf das Ergebnis:
11844

Hier mein Quellcode (Java):
Code: 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;


public class Problem124 {

	public static void main(String[] argv){
		class X{
			int n,radn;
		}
		class XComparator implements Comparator<X>{
			public int compare( X a, X b ){
				  if( a.radn < b.radn ) return -1;
				  if( a.radn > b.radn ) return 1;
				  if( a.n < b.n ) return -1;
				  if( a.n > b.n ) return 1;
				  return 0;
				}
		} 
		
		ArrayList<X> list = new ArrayList<X>();
		
		// unsortiere liste mit n und rad(n) berechnen
		for(int i = 1;i<=100000;i++){
			X x = new X();
			x.n = i;
			x.radn = (int)getf(i);
			list.add(x);
		}
		
		System.out.println("Unsortiert");
		System.out.println("n  rad(n) k");
		for(int i=0;i<list.size();i++){
			System.out.printf("%d    %d    %d\n", list.get(i).n, list.get(i).radn,i+1);	
		}
		
		// liste sortieren nach rad(n)
		Collections.sort(list,new XComparator());
		
		
		System.out.println("\nSortiert");
		System.out.println("n  rad(n) k");
		for(int j=0;j<list.size();j++){
				System.out.printf("%d    %d    %d\n", list.get(j).n, list.get(j).radn,j+1);
		}	
		
		final int GESUCHTES_ELEMENT = 10000;	// E(k) bsp E(6)
		System.out.println("\nE("+GESUCHTES_ELEMENT+"): "+list.get(GESUCHTES_ELEMENT-1).n);
		
	}

	// calculate distinct primefactors
	public static long getf(long n){
		ArrayList<Long> list = new ArrayList<Long>();
		for (long i = 2; i <= n / i; i++) {
			while (n % i == 0) {
				list.add(i);
				n = n / i;
			}
		}
		if (n > 1){	
			list.add(n);
		}
		if(list.size() > 1){
			for(int i = 1;i<list.size();){
				if(list.get(i-1) == list.get(i)){
					list.remove(i);
				}
				else{
					i++;
				}
			}
		}
		long rad=1;
		for(int k=0;k<list.size();k++){
			rad = rad * list.get(k);
		}

		return rad;
	}
}

Hat jemand von euch nen Tip wo mein Fehler liegt? Bzw hat jemand von euch die Aufgabe, die IMHO nicht so schwer sein sollte, schon gelöst?
 
Ich verzweifle an Problem 2 :baby: ;(
Hab alles versucht, aber nichts gelingt.
Code: 
int Problem2()
{
    static int Total = 0;
    static int TermOne = 0;
    static int TermTwo = 2;
    static int TermThree = 0;

    printf("Calculating Problem 2");

    while(1)
    {
        if(TermOne>1000000)
        {
            printf("\nTermOne is bigger than 999,999.\n");
            break;
        }
        if((TermOne%2)!=0)
        {
            printf("\nTermOne is not even valued.\n");
            break;
        }
        if(TermTwo>1000000)
        {
            printf("\nTermTwo is bigger than 1000,000.\n");
            break;
        }
        if((TermTwo%2)!=0)
        {
            printf("\nTermTwo is not even valued.\n");
            break;
        }

        TermThree = TermOne + TermTwo;
        TermOne = TermTwo;
        TermTwo = TermThree;
        Total += TermThree;
    }
    printf("\nSolution \"Problem 2\": %d\n\n",Total);
}

Wer kann mir helfen?
 
Hm,
meine C Kenntnisse sind beschränkt aber soweit ich das sehe, funktioniert deine Fibonacci Methode nicht richtig.
Geh das Problem folgendermaßen an:
1. Bau dir eine Methode die dir die ersten 40 Fibonacci Zahlen ausgibt und prüfe die Richtigkeit anhand von Wikipedia.
2. Bau die Überprüfung für gerade Zahlen (tmp % 2 == 0) ein
3. Bau einen summenzähler ein der die geraden Zahlen addiert
4. Bau eine Überprüfung ein, die nur Fibonacci Zahlen < 1000000 addiert

In Java sieht das Ganze so aus:
Code: 
	public static void fib(){
		int summe = 0;
	    int tmp;
	    int aktuellefib = 1;
	    int naechstefib = 2;
	    
	    // berechne 40 fibonacci zahlen
	    for (int i=1;i <= 40;i++) {
	      tmp = naechstefib;
	      naechstefib = aktuellefib + naechstefib;
	      aktuellefib = tmp;
	      
	      // nur gerade zahlen verwenden und tmp < 1000000
	      if(tmp % 2 == 0  && tmp < 1000000){
	    	  summe = summe + tmp;
	      }
	    }
	    
	    System.out.println(summe);	// Ergebnis
	}
 
Hallo,

ich sitze spaßenshalber mal wieder ein Wochenende am ProjectEuler und stöbere mal bunt durcheinander in den eigentlich leichteren Aufgaben herum...

Bei Aufgabe 155 (http://projecteuler.net/index.php?section=problems&id=155, Kombinatorik) bin ich felsenfest davon überzeugt, daß ich richtig liege (die IST trivial), aber ProjectEuler meint das Gegenteil.

Jetzt würde ich gern mal jemanden finden, der eventuell ein paar Vergleichswerte neben den sehr dürftigen zweien in der Aufgabenstellung hat oder der die magische Stelle aufzeigen kann, wo Varianten flöten gehen oder aus dem Nichts entstehen...

Meine Meinung: D(n) = 2 * D(n-1) + 1

Wer hat anderes?

Nochwas: Aufgabe 165 (http://projecteuler.net/index.php?section=problems&id=165, triviale Geometrie) ist genau so ein Ding:

Ganz abgesehen von der Tatsache, daß die Aufgabe echt vom Sinn her trivial ist, werden alle selbstgebastelten Tests erfüllt, während man sich die drei in der Aufgabenstellung vorgestellten Strecken offenbar in selten besuchte Orte stecken kann.

Offenbar gibt es hier irgendwelche Grenzfälle mit Abweichungen zwischen Eckpunkt und dran vorbeiziehender Strecke im Bereich von bis runter auf einen Bruchteil einer Einheit. Wo man halt zwingend Toleranzen einbauen muß, bis wann man einen als Schnittpunkt berechneten solchen noch als jenen gelten läßt. Und diese Toleranz scheinen die Aufgabensteller für ein streng zu hütendes Berufsgeheimnis zu halten. Und mit dem, was ich angesetzt habe (1e-6), scheint es nicht auf das streng gehütete Geheimnis hinauszulaufen. (P.S.: Habe das ganze nochmal durchgesehen und festgestellt, daß ich überall in der Rechnung exakte Integers behalte, also selbst Toleranz Null korrekte Ergebnisse liefert.)

Hatte da mal wer einen Erfolg erzielt?
Könnte da der mal ein paar Vergleichswerte reinstellen?
Zum Beispiel:
Erste 10 Strecken:
5 Schnittpunkte (bei Toleranz < 1e-4)
4 Schnittpunkte (bei Toleranz >= 1e-3)
Erste 20 Strecken: 32 Schnittpunkte (Null Toleranz)
Erste 50 Strecken: 268 Schnittpunkte (Null Toleranz)

----

@0001001 (Aufgabe 124):

Es muß ein Wert rauskommen, der etwa doppelt so hoch wie Deiner ist.
Möglicherweise ist bei Dir noch ein Fehler in der Radikalen-Ermittlung?
Hier mal eine Testreihe mit den ersten 30 Elementen...

1 - 1
2 - 2
2 - 4
2 - 8
2 - 16
3 - 3
3 - 9
3 - 27
5 - 5
5 - 25
6 - 6
6 - 12
6 - 18
6 - 24
7 - 7
10 - 10
10 - 20
11 - 11
13 - 13
14 - 14
14 - 28
15 - 15
17 - 17
19 - 19
21 - 21
22 - 22
23 - 23
26 - 26
29 - 29
30 - 30

P.S.: Deine Faktorisierung kannst Du noch beschleunigen durch "i+=2".
Ansonsten sieht das eigentlich korrekt aus.
Aber ein Fehler muß ja wohl irgendwo stecken...
 
Schön, daß auch andere noch eulern.

@ Harry Boeck:

Bei Aufgabe 155 ist schon D(5) magisch:

D(5) = 35

Brute Force scheint hier die einzig brauchbare Methode zu sein, keins der Genies aus dem Forum hat eine andere Lösung.


Für 165 gilt: Keine Toleranz! Deine ersten Ergebnisse habe ich auch raus.

n(20) = 32
n(50) = 268
n(100) = 1112
n(200) = 4865
n(1000) = 113849
 
Oh ha: Bei Aufgabe 155 ist es zwar vom Prinzip her einfach, aber bei weitem nicht GANZ so trivial wie ich zuerst ansetzte...

Meine erste Idee war, den jeweils neu hinzukommenden Kondensator einfach zu allen schon vorhandenen Positionierungsvarianten
a) parallel
b) allein
c) seriell
einzuhängen (und dabei den schon vorhandenen Rest als abgeschlossenen Block zu betrachten).

Dieses Denkprinzip ist zwar hilfreich, aber nicht ausreichend: Das zusätzliche Bauelement kann natürlich auch noch mitten in den soweit vorhandenen Block eingehängt werden.

Danke für die Aufklärung!

----

zur Aufgabe 165:

Meine Ergebnisse stimmen bis zu n(200) überein.
Bei n(1000) kommt: 113853 statt 113849

-> Es handelt sich wohl offenbar DOCH um irgendein Rundungsproblem.
Obwohl ich es mir absolut nicht erklären kann: EIGENTLICH werden bei meiner Vorgehensweise NUR Integer multipliziert, addiert und verglichen (ich mach's ganz simpel mit Determinanten und behandle die Spezialfälle auf deren Ebene).

Ich bin mal gespannt, welche 4 Fälle bei n(1000) die "schuldigen" sind...

Erst mal weitere Tests mit verschiedenen Toleranzen ergeben:
Tol -> n(1000)
0 113853
1e-6 113853
1e-5 113851
2e-5 113850
2.2e-5 113849 (am "korrektesten")
2.5e-5 113848
3e-5 113845

Gibt es irgendeinen Spezialfall, der unter den ersten 200 Strecken noch nicht vorkommt? Und der (offensichtlich) etwas mit Grenzwertigkeit zu tun hat?

Ich habe jetzt mal einfach mit dem Toleranzwert 2.2e-5 gearbeitet und erhalte für n(5000): 2868949. Das und die nächsten +/- 4 Werte sind aber offenbar auch nicht die korrekte Lösung. Was ich gern rauskriegen würde: Worin bestehen jene ominösen Spezialfälle, die ich (bei Toleranz Null) als gültig ansehe, die es aber nicht sein sollen?

@Tara: Ob Du mir mal eine Liste der Schnitt-Paare schicken kannst? (Für n(1000) würde das reichen...)
Hier ist meine momentane Liste für n(1000) (rund 1 MByte): http://harryboeck.dyndns.org/Experimente/ProjectEuler/var/schnittpaare.txt

...Ich habe ja gerade eine dunkle Ahnung...Die sich aber nicht bestätigt (Null-Strecken werden implizit zuverlässig rausgefiltert)...
Hmmmm: Vollkommen unklar...
 
@ Harry Boeck:

Ich habe eben mal auf Verdacht in meinem Programm herumeditiert und komme nun auch auf dein Ergebnis für 1000 Strecken. Es liegt nicht am Runden, sondern Du sortierst die Punkte nicht aus, die mehrfach getroffen werden. "Euler" fragt nach "distinct true intersection points". Das Ausstreichen der Mehrfachtreffer ist gerade der spaßige Teil des Problems. ;)
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben