[link] Project Euler - Programmieraufgaben

Cyberm@ster · Apr 17, 2007

Ja, ich hab das Problem schon gelöst, schau mal 7 Posts über dir ... Suchen solltest du horizontal, vertikal, diagonal nach oben und diagonal nach unten. Ich hab in der oberen linken Ecke angefangen und mich dann nach unten durchgearbeitet, am Ende hab ich dann nochmal unten angefangen um die diagonale nach oben zu suchen. Wenn du oben links anfängst, macht es in der Tat keinen Sinn nach oben oder nach links zu suchen.

Stein · Apr 22, 2007

Hmm ich komme bei Problem 4 irgendwie nicht weiter ich kann immer ein ganz gutes Ergebnis errechne, aber der nimmt das nicht an.

995*5xx = 58xx85

hier mal mein Visualbasiccode(ich nehme vb weil ich unter c++ die Befehle ewig suchen müsste)

Public Class Form1
Function palindrom(ByVal produkt As Integer) As Boolean
Dim vorw As String, rueckw As String, i As Integer
vorw = CStr(produkt)
i = Len(vorw)
rueckw = ""
Do
rueckw = rueckw & Mid(vorw, i, 1)
i = i - 1
Loop Until i = 0
If vorw = rueckw Then
Return True
Else
Return False
End If
End Function
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim i As Integer, j As Integer, high As Integer, jhigh As Integer, ihigh As Integer
For i = 100 To 1000
For j = 100 To 1000
If palindrom(i * j) Then
high = i * j
jhigh = j
ihigh = i
End If
Next
Next
MsgBox(ihigh & "*" & jhigh & "=" & high)

End Sub

End Class

Weiß einer was ich falsch mache?

gruß stein

Cyberm@ster · Apr 22, 2007

Du brauchst eine Variabel in der du das bisher größte Ergebnis speicherst. Dann musst du bei jedem Palindrom überprüfen ob es größer oder kleiner ist, das kannst du ohne Test nicht wissen.

Stein · Apr 22, 2007

Mein Gott sowas sollte ich eigentlich sehen.... Ist eigenlich logischen wenn bei 994*999 das größe Palindrom ist wird das bei 995*xxx wieder gelöscht

gruß stein

Tara · Mai 5, 2007

Hi,

@ 136:

25 Lösungen sind richtig, 87 ist nicht unique:

37^2-29^2-21^2 = 109^2-87^2-65^2 = 87

@ 100:

"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) "

Du mußt nach einer Lösung suchen, die ohne Sqrt() auskommt, die Genauigkeit ist zu gering! (Vermutlich hat "Euler" deshalb 10^12 gewählt. - etwas gemein

)

Edit: Ups, hab grad gesehen daß die Diskussion im Januar stattfand, einfach ignorieren!

0001001 · Mai 27, 2007

Hm, hat jemand mal einen Tip für Problem 112 ?

Hier meine Lösung:

Ich komme auf 1575699, das ist aber leider falsch.

Code:

public class Problem112 {
	public static void main(String[] argv){
		int counter = 0;
		int gesamt = 0;
		
		for(int a=100;a<2000000;a++){
			gesamt++;
			String zahl = String.valueOf(a);
			int[] array = new int[zahl.length()];
			// push the digits in an array
			for(int i=0;i<zahl.length();i++){
				array[i] = Integer.parseInt(zahl.substring(i, i+1));
			}
			boolean check = true;
			boolean check2 = true;
			// check if increasing numbers
			for(int k=0;k<zahl.length()-1;k++){
				int temp = array[k];
				if(!(temp <= array[k+1])){
					check = false;
				}
			}
			if(!check){ // if you get here, the number is not an increasing number
				// check if decreasing number
				for(int m=0;m<zahl.length()-1;m++){
					int temp2 = array[m];
					if(!(temp2 >= array[m+1])){
						check2 = false;
					}
				}
			}
			if(!check2){ // if you get here, the number is neither an increasing number nor a decreasing number
				//System.out.println("bouncy number: "+a);
				counter++;				
			}
			if(proportion(counter,gesamt) == 0.990000000000){
				System.out.println(a); // print the number where the percentage is 0.990000000
			}
		}

		System.out.println(proportion(counter,gesamt));
		System.out.println(counter);
	}
	
	public static double proportion(int counter, int gesamt){
		double a = Double.valueOf(String.valueOf(counter));
		double b = Double.valueOf(String.valueOf(gesamt));
		return a/b;
	}
}

Tara · Mai 29, 2007

Hallo!

Ich kann leider kein Java und muß deshalb etwas raten.

In Zeile 4 mußt du gesamt mit 99 initialisieren, da du Zahlen < 100 überspringst.

Dann würde ich die Boolean-Variablen ab Zeile 14 IsIncreasing und IsDecreasing nennen.

Boolean IsIncreasing = False;
Boolean IsDecreasing = False;

Die Zahl ist bouncy, wenn mindestens eine Ziffer größer ist als die vorangehende und eine Ziffer kleiner.

Code:

for(int k=0;k<zahl.length()-1;k++)
{
  if(!(array[k] > array[k+1]))
    IsDecreasing = True;

  if(!(array[k] < array[k+1]))
    IsIncreasing = True; 
}

evtl. sind die Klammern nicht ganz richtig gesetzt

Wenn beide Bools True sind wird counter hochgezählt, dann getestet ob counter = 0.99*gesamt.

Mitamber · Jun 1, 2007

In den beiden vorangegangen Beträgen von 0001001 und Tara ist derselbe Fehler enthalten. Ich werde das mal am Beispiel von Tara?s Code verdeutlichen:

Tara schrieb:

Code:

 for(int k=0;k<zahl.length()-1;k++)
{
  if(!(array[k] > array[k+1]))
    IsDecreasing = True;

  if(!(array[k] < array[k+1]))
    IsIncreasing = True; 
}

Dieser Code reduziert sich effektiv zu folgendem Code:

Code:

int k=zahl.length()-2;
if(!(array[k] > array[k+1]))
    IsDecreasing = True;

 if(!(array[k] < array[k+1]))
    IsIncreasing = True;

Daher werden also jeweils nur die letzten beiden Ziffern für die Bestimmung von increasing oder decreasing berücksichtigt; der Rest geht verloren, da die Abbruchbedingung der Schleife unvollständig ist.

So habe ich überprüft, ob eine Zahl bouncy ist:

Eine Zahl ist gemäß der Aufgabenstellung bouncy, wenn sie nicht increasing und nicht decreasing ist.

Code:

bool IsBouncy(unsigned num)
{
  unsigned dig0, dig1;

  bool decreasing = true;
  bool increasing = true;

  dig0 = num % 10;
  num /= 10;
  
  while(num && (decreasing || increasing))
  {
    dig1 = num % 10;
    num /= 10;

    if(increasing)
      increasing = (dig1 >= dig0);
    if(decreasing)
      decreasing = (dig1 <= dig0);

    dig0 = dig1;          
  }

  return !(decreasing || increasing);
}

Ich hoffe das war hilfreich.

Tara · Jun 3, 2007

Huch??

Das würde ja bedeuten, daß 0001001 mit einem völlig falschen Algorithmus zu einem Ergebnis gekommen ist, das weniger als 1% von der richtigen Antwort entfernt ist. Das wäre aber ein großer Zufall. Naja, ich kann kein Java und pfusche besser auch nicht mehr damit herum.

0001001 · Jun 3, 2007

hm, ganz kann ich dir da nicht folgen. Wieso werden in meinem Code nur die letzten beiden Ziffern für den Test herangezogen?
Vor der Schleife und den If-Abfragen setze ich check=true.
Wenn jetzt beim Durchlauf der Schleife einmal eine Ziffer kleiner ist als eine vorherige Ziffer dann ist check = false und wird nie wieder auf true gesetzt.

lagalopex · Jun 3, 2007

Was Mitamber gesagt hat, stimmt so nicht. Alle drei Algorithmen zur Prüfung sind korrekt und arbeiten, wie sie es sollen (Tara sollte nur >= und <= benutzen... oder dieses negieren lassen

)
Evtl. kleinere Abweichungen können entstehen, da Gleitkommazahlen benutzt wurden.
Ich habs so gelöst, dass alle bouncy Zahlen gezählt wurden und dann einfach über:
"bouncy == 99 * (x - bouncy))" geprüft wird. Zumindest stimmt mein Ergebnis genau

Mitamber · Jun 4, 2007

Ok, Ihr habt Recht. Ich ziehe die Aussage, dass die Schleife nicht funktioniert, zurück. Ich habe sie falsch gelesen, da sie etwas unübersichtlich gestaltet ist.

-sorry Mitamber

Eydeet · Nov 25, 2007

Ich brauche mal ein wenig Hilfe bei Problem 26. Es geht darum bei Brüchen von 1 / (1..1000) den Teiler zu finden, der die längste sich wiederholende Nachkommastelle ergibt. Die längste, die ich momentan finde ist die von 1 / 69, bei der sich 69 Ziffern wiederholen:

Code:

1/69 = 0,0012033694344163658243080625752105896510228640192539109506618531889290012033...

Das wird aber nicht als richtiges Ergebnis akzeptiert.
Hat vielleicht jemand einen Tipp für mich, was an meinem Code falsch ist?

Code:

#include <iostream>
using namespace std;

char *floatDiv1(int divisor, int digits)
{
        char *flt = new char[digits+1];
        int quotient = 1;
        for (int i = 0; i < digits; ++i) {
                if (quotient < divisor) {
                        flt[i] = '0';
                        quotient *= 10;
                        continue;
                } else {
                        flt[i] = '0' + quotient / divisor;
                        quotient = (quotient % divisor) * 10;
                }
        }
        flt[digits] = 0;
        return flt;
}

int isRecurring(char *fract) {
        int genau = strlen(fract);
        int maxRecur = 0;
        for (int b1 = 0; b1 < genau; b1++) {
                for (int b2 = b1+1; b2 < genau; b2++) {
                        if (fract[b1] == fract[b2]) {
                                int recur = 1;
                                // check the digits between and after: are they the same? 
                                // If yes, b2-b1 recurring digits were found
                                for (int k = 1; k < (b2 - b1) && b1+k < b2; ++k) {
                                        if (fract[b1+k] == fract[b2+k]) {
                                                ++recur;
                                        } else {
                                                recur = 0;
                                                break;
                                        }
                                }
                                if (maxRecur < recur) maxRecur = recur;
                                break;
                        }
                }
        }
        return maxRecur;
}

int main()
{
        int genau = 1000;
        int maxRec = 0;
        int maxNum;
        for (int i = 0; i < 1000; ++i) {
                if (i % 5 == 0) continue;
                char *fract = floatDiv1(i, genau);
                int rec = isRecurring(fract);
                if (maxRec < rec) {
                        maxRec = rec;
                        maxNum = i;
                }
                cout << i << " : " << rec << endl;
        }
        char * fract = floatDiv1(maxNum, genau);
        cout << "1 / " << maxRec << " = " << fract << " (" << isRecurring(fract) << " digits recurring)" << endl;
}

0001001 · Nov 25, 2007

Kann leider kein C, aber mit 69 bist du noch weit von der der richtige Lösung entfernt.
Hier mal mein, zugegeben ziemlich chaotischer Code (Java):

Code:

import java.math.*;

public class Problem26 {
	public static void main(String[] argv){
		int temp = 0;
		int temp2 = 0;
		for(double i = 2;i<1000;i++){
			BigDecimal i2 = new BigDecimal(String.valueOf(i));
			BigDecimal eins = new BigDecimal("1");
			MathContext mc = new MathContext(1500);
			BigDecimal result =  eins.divide(i2,mc);
			String s = result.toString();
			if(s.length()>15){			
				if(check(s)>temp && check(s) != 1480){
					temp = check(s);
					temp2 = (int) i;
				}
				//System.out.println(check(s)+"  --  "+result+"  --  "+(int)i);

			}
		}
		System.out.println("Die Zahl: "+temp2+" hat "+temp+" Stellen");
	}
	public static int check(String s){
		String checkstring = s.substring(5, 10);
		s = s.substring(8, s.length());
		int i = 0;
		while(i<1480 && !(s.substring(8+i,8+i+5)).equalsIgnoreCase(checkstring) && !s.substring(8, 9).equalsIgnoreCase(s.substring(9,10))){
			i++;
		}
		return i;
	}
}

Eydeet · Nov 25, 2007

Vielen Dank! Nachdem ich mir deinen Algorithmus angeschaut habe, habe ich mein Programm endlich zum Laufen bekommen

Wen es interessiert:

Code:

#include <iostream>
using namespace std;

char *floatDiv1(int divisor, int digits)
{
        char *flt = new char[digits+1];
        int quotient = 1;
        for (int i = 0; i < digits; ++i) {
                if (quotient < divisor) {
                        flt[i] = '0';
                        quotient *= 10;
                        continue;
                } else {
                        flt[i] = '0' + quotient / divisor;
                        quotient = (quotient % divisor) * 10;
                }
        }
        flt[digits] = 0;
        return flt;
}

int cntRecur(char *fract) {
        int posA = 5, posB = 6, nCheck = 5;
        for (unsigned int i = 0; i < strlen(fract)-nCheck; ++i) {
                // compare
                bool matching = true;
                for (int k = 0; k < nCheck; ++k) {
                        if (fract[posA+k] != fract[posB+k]) {
                                matching = false;
                        }
                }
                if (matching) {
                        return (posB - posA);
                }
                ++posB;
        }
        return 0;
}

int main()
{
        int genau = 1000;
        int maxRec = 0;
        int maxNum;
        for (int i = 0; i < 1000; ++i) {
                if (i % 5 == 0) continue;
                char *fract = floatDiv1(i, genau);
                int rec = cntRecur(fract);
                if (maxRec < rec) {
                        maxRec = rec;
                        maxNum = i;
                }
                cout << i << " : " << rec << endl;
        }
        char * fract = floatDiv1(maxNum, genau);
        cout << "1 / " << maxNum << " = " << fract << " (" << maxRec << " digits recurring)" << endl;
}

0001001 · Nov 25, 2007

Dann ist es ja gut, denn ich versteh meinen Code nicht mehr ;-)

Extinction · Dez 7, 2007

Hallo!
Ich will mich auch nochmal des Problems 10 annehmen. Allerdings mit dem Atkins Sieb, wie auf Seite 1 beschrieben. Leider bekomme ich nicht das richtige Ergebnis und finde den Fehler nicht. Mein Ergebnis:
Anzahl: 3676 Laufzeit: 0.14 Sekunden

Wikipedia über das Atkins Sieb:
http://en.wikipedia.org/wiki/Sieve_of_Atkin

Der Code:

Code:

#include <cstdlib>
#include <iostream>
#include <cmath>
#include <time.h>

using namespace std;

int main() {
    int zaehler=3;
    //unsigned long long sum=2;
    bool is_prime[1000000];
    is_prime[0] = 2;
    is_prime[1] = 3;
    is_prime[2] = 5;
    unsigned long long n;
    double time1=clock(), time2;
    int limit=1000000;
    double SQRTlimit= sqrt(1000000);
    for (int x=1;x<SQRTlimit;x++)
    {
        for (int y=1;y<SQRTlimit;y++) //Das Feld X*Y wird bis zur Wurzel des Suchlimits abgearbeitet
        {
            n=4*(x^2)+(y^2);
            if (n <= limit)
               if (n%12 == 1 || n%12 == 5) is_prime[n]=true;
               
            n=3*(x^2)+(y^2);
            if (n <= limit)
               if (n%12 == 7) is_prime[n]=true;
               
            n=3*(x^2)-(y^2);
            if (x>y)
               if (n <= limit)
                  if (n%12 == 11) is_prime[n]=true;
        }    
    }
    int k;
    int i,x;
    for (i=5;i<=SQRTlimit;i++)
    {
        if (is_prime[i]==true)
        {
              for (k=1;k<SQRTlimit;k++) //normalerweise limit, das forciert aber nen Crash
              {
                  x=k*(i^2);
                  is_prime[x]=false;                  
              }  
        }           
    }
    for (i=5;i<limit;i++)
        if(is_prime[i]) zaehler++;
    time2 = (clock() - time1) / CLOCKS_PER_SEC;
    cout << "Anzahl: " << zaehler << " Laufzeit: " << time2 << " Sekunden" << endl;// << " Summe: " << sum
    system("PAUSE");
    return EXIT_SUCCESS;
}

Währe toll, wenn jemand den Wurm findet. Sitze nämlich schon gut 1,5Std daran...

Edit: Hab mal alle Primzahlen unter 100 ausgeben lassen:
5, 11, 13, 17, 23, 25, 29, 37, 41, 47, 53, 59, 61, 65, 71, 73, 79, 83, 85, 89, 97
Die Zahlen 19, 31, 43, 61, 67 fehlen und 25, 65, 85 sind keine Primzahlen!

0001001 · Dez 11, 2007

Wenn es dir nur darum geht das Ganze mit dem Sieb zu lösen, dann kann ich dir nicht weiterhelfen.

Ansonsten kann ich dir, falls du das noch nicht selbst weisst, sagen dass 78498 Primzahlen zwischen 1 und 1000000 liegen, die du finden und addieren musst.

/etc/shadow · Dez 11, 2007

Also, ich habe prob 10 mit java gelöst.
und zwar mit Sieb des Eratosthenes.

So sieht mein ergebnis aus :

Code:

es gibt 78498 Primzahlen kleiner als 1000000
***********.0 ist die summe der zahlen
ben÷tigte Zeit: 18 Sekunden

Die Lösung hab ich natürlich entfernt, sonst macht projecteuler keinen Sinn mehr

Ich habe volgendes gemacht :

Code:

array[1000000] gesetzt und alle felder mit false gemacht.
factor = counter = value = 0
solange counter < 1000000 mache {
   if array[counter] = true dann {
               solange((counter * factor) <= (999999)) {
                            value = counter * factor;
                            array[value] = false;
                            factor++;
                }
                counter++;
           }
  else { counter++;   }
  value = factor = 2;         }
  counter = 0;
  //alle felder die true sind, zurueckgeben
  solange (counter < 1000000) {
           if(array[counter]) {
             summe = summe.add(BigDecimal.valueOf(counter));
             }
           counter++;
         }

Congratulations, the answer you gave to problem 10 is correct.

falls du fragen hast, frag einfach

//edit: Ich habe die ersten Seiten nicht gelesen

Extinction · Dez 11, 2007

Es ging ja nicht um das Lösen der Aufgabe an sich. Mit C++ hat's bei mir mit ner Geschwindigkeit von 2,8sek geschafft.

Das Ergebnis wurde ja auch schon auf Seite 1 gepostet...
Es geht Darum, das ich das Sieb von Atkins verwenden will, nur irgendwo nen Fehler drinn hab ^^