Projekt Euler | über 130 Programmieraufgaben

WhiskeyCola16 · 02.02.2007

wenn man logisch denk dann kommt man drauf.
ich hab die lösung für das problem nie in der schule gehört

Anno1989 · 02.02.2007

Okay, isprime ist ne gute lösung, ich hab mir da selber ein prorgamm zusammengeschrieben, das ist dann wohl nicht so ellegant

WhiskeyCola16 · 02.02.2007

gibts die eigentlich in c#? da hab ich sie mir nämlich selbst geschrieben, weil ich sie nicht gefunden hab. weder msdn noch brauchbare lösung bei :google:

Data · 03.02.2007

Scorn07 schrieb:
Edit: Womit programmiert ihr eigentlich und wie weit seid ihr?

Ich programmiere mit Visual Basic (Microsoft Visual Studio 8 - Express Edition) und habe schon fünf Aufgaben gelöst.

deepinpowder schrieb:
Gut, da müsseb aber dann auch die doppelten Zahlen ausgeschlossen werden. 15 ist durch 3 und 5 teilbar.

Wieso doppelt? Es darf doch auch Vielfache von 3 und 5 geben. In der Aufgabe steht zwar or, aber logisch gesehen ist es kein entweder-oder. Ich habe jedenfalls das richtige Ergebnis bekommen.

Anno1989 schrieb:
Die Aufgaben sind zum Teil ziemlich knifflig, [...] Aber das macht irgendwie Spaß.

Da stimme ich dir zu. :goil:

WhiskeyCola16 · 03.02.2007

Data schrieb:
Wieso doppelt? Es darf doch auch Vielfache von 3 und 5 geben. In der Aufgabe steht zwar or, aber logisch gesehen ist es kein entweder-oder. Ich habe jedenfalls das richtige Ergebnis bekommen.

ich glaube das:

WhiskeyCola16 schrieb:
(...)
wenn zahl%x==0 dann auch zahl%(zahl/x)==0;
x und zahl/x sind teiler von zahl

war gemeint

Data · 04.02.2007

WhiskeyCola16 schrieb:
aufgabe 10 dauert bei mir 3 sekunden. tipp: IsPrime funktion optimieren

Also das kann ich ehrlich gesagt nicht nachvollziehen (was nicht heißt, dass ich es dir nicht glaube

). Bei mir hat ID 10 einige Minuten gebraucht.

WhiskeyCola16 · 04.02.2007

Data schrieb:
Also das kann ich ehrlich gesagt nicht nachvollziehen (was nicht heißt, dass ich es dir nicht glaube ). Bei mir hat ID 10 einige Minuten gebraucht.

Code:

[SIZE=2][COLOR=#008000]// funktion zur überprüfung ob ToBeChecked eine Primzahl ist[/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]private [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]static [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]bool[/COLOR][/SIZE][SIZE=2] IsPrime([/SIZE][SIZE=2][COLOR=#008080]Int64[/COLOR][/SIZE][SIZE=2] ToBeChecked) {[/SIZE]
[SIZE=2][COLOR=#008080]   Int64[/COLOR][/SIZE][SIZE=2] check = ToBeChecked / 2;[/SIZE]
[SIZE=2][COLOR=#0000ff]   for[/COLOR][/SIZE][SIZE=2] ([/SIZE][SIZE=2][COLOR=#008080]Int64[/COLOR][/SIZE][SIZE=2] i = 2; i < check + 1; i++) {[/SIZE]
[SIZE=2][COLOR=#0000ff]       if[/COLOR][/SIZE][SIZE=2] (ToBeChecked % i == 0)[/SIZE]
[SIZE=2][COLOR=#0000ff]           return [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]false[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2]       check = ToBeChecked / i;[/SIZE]
[SIZE=2]   }[/SIZE]
[SIZE=2][COLOR=#0000ff]   return [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]true[/COLOR][/SIZE][SIZE=2];[/SIZE]
[SIZE=2]}[/SIZE]
 
[SIZE=2][COLOR=#008000]// summe aller primzahlen unter 1.000.000[/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]private [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]void[/COLOR][/SIZE][SIZE=2] btnAufg10_Click([/SIZE][SIZE=2][COLOR=#0000ff]object[/COLOR][/SIZE][SIZE=2] sender, [/SIZE][SIZE=2][COLOR=#008080]EventArgs[/COLOR][/SIZE][SIZE=2] e) {[/SIZE]
[SIZE=2][COLOR=#008080]   Int64[/COLOR][/SIZE][SIZE=2] summe = 0;[/SIZE]
[SIZE=2][COLOR=#0000ff]   for[/COLOR][/SIZE][SIZE=2] ([/SIZE][SIZE=2][COLOR=#0000ff]int[/COLOR][/SIZE][SIZE=2] i = 2; i < 1000000; i++) {[/SIZE]
[SIZE=2][COLOR=#0000ff]        if[/COLOR][/SIZE][SIZE=2](IsPrime(i)) summe+=i;[/SIZE]
[SIZE=2]   }[/SIZE]
[SIZE=2][COLOR=#008080]   MessageBox[/COLOR][/SIZE][SIZE=2].Show([/SIZE][SIZE=2][COLOR=#800000]"Summe: "[/COLOR][/SIZE][SIZE=2] + summe);[/SIZE]
[SIZE=2]}[/SIZE]

bis ich auf diese Lösung von IsPrime gekommen bin, hab ich ganz ehrlich schon ein bissel gebraucht. wenn jmd. noch eine bessere bzw. eine optimierung weiß, bitte sagen

lg,
patrick

peterfido · 04.02.2007

Such mal nach: Sieb des Eratosthenes

WhiskeyCola16 · 04.02.2007

peterfido schrieb:
Such mal nach: Sieb des Eratosthenes

das sieb des eratosthenes ist mir bekannt. zu beginn war dies auch mein ansatz. jedoch komplizierter in der durchführung, und meiner meinung überlegung nach, müsste es auch langsamer sein. ich lasse mich aber gerne vom gegenteil überzeugen.

also, falls jemand diese lösung schon gemacht hat, wie lange dauert diese möglichkeit?

lg,
patrick

peterfido · 04.02.2007

Aufgabe 10 unter VB 6: 2,3157 Sek. Allerdings in der IDE Ausgeführt.
Als EXE 2,2 Sek.
Mit Hilfe des Siebs des Eratosthenes.

Dafür verstehe ich Problem 3 irgendwie nicht...

WhiskeyCola16 · 04.02.2007

zu aufgabe 3:

Code:

[SIZE=2][COLOR=#008000]// primfaktorzerlegung - liefert größten primfaktor[/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]private [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]void[/COLOR][/SIZE][SIZE=2] btnAufg3_Click([/SIZE][SIZE=2][COLOR=#0000ff]object[/COLOR][/SIZE][SIZE=2] sender, [/SIZE][SIZE=2][COLOR=#008080]EventArgs[/COLOR][/SIZE][SIZE=2] e) {[/SIZE]
[SIZE=2][COLOR=#008080]  Int64[/COLOR][/SIZE][SIZE=2] zahl = 317584931803;[/SIZE]
[SIZE=2][COLOR=#008080]  Int64[/COLOR][/SIZE][SIZE=2] maxPrim = 2;[/SIZE]
[SIZE=2][COLOR=#008080]  Int64[/COLOR][/SIZE][SIZE=2] check = zahl;[/SIZE]
[SIZE=2][COLOR=#0000ff]  for[/COLOR][/SIZE][SIZE=2] ( [/SIZE][SIZE=2][COLOR=#008080]Int64[/COLOR][/SIZE][SIZE=2] p = 2; p <= check; p++) {[/SIZE]
[SIZE=2][COLOR=#0000ff]      if[/COLOR][/SIZE][SIZE=2] ( IsPrime(p) ) {[/SIZE]
[SIZE=2][COLOR=#0000ff]          if[/COLOR][/SIZE][SIZE=2] ( check%p == 0 ) {[/SIZE]
[SIZE=2][COLOR=#0000ff]              if[/COLOR][/SIZE][SIZE=2] (p > maxPrim) {[/SIZE]
[SIZE=2]                  maxPrim = p;[/SIZE]
[SIZE=2]              }[/SIZE]
[SIZE=2]              check /= p;[/SIZE]
[SIZE=2]              p--;[/SIZE]
[SIZE=2]          }[/SIZE]
[SIZE=2]      }[/SIZE]
[SIZE=2]  }[/SIZE]
[SIZE=2][COLOR=#008080]  MessageBox[/COLOR][/SIZE][SIZE=2].Show([/SIZE][SIZE=2][COLOR=#800000]"Primfaktor: "[/COLOR][/SIZE][SIZE=2] + maxPrim);[/SIZE]
[SIZE=2]}[/SIZE]

@peterfido: könntest du deine lösung zu ID10 mit dem sieb mal posten?
mit meiner IsPrime funktion dauert ID10 3,2 sekunden.

nic_power · 04.02.2007

Hallo,

WhiskeyCola16 schrieb:
das sieb des eratosthenes ist mir bekannt. zu beginn war dies auch mein ansatz. jedoch komplizierter in der durchführung, und meiner meinung überlegung nach, müsste es auch langsamer sein. ich lasse mich aber gerne vom gegenteil überzeugen.

Komplizierter ist das Sieb nicht, es benoetigt nur deutliche mehr Speicher. Bei grossen Primzahlen wird es damit nicht mehr praktikabel.

Vergleich mal die Anzahl der Operationen und Funktionsaufrufe zwischen dem Sieb und Deiner Loesung. Du uerberpruefst jede Zahl aufs neue von vorne, ob sie bestimmte Teiler hat oder nicht, ausserdem ist die Modulo-Funktion sehr "teuer" im Vergleich zu einfachen Multiplikationen.

Nic

WhiskeyCola16 · 04.02.2007

ist mir bei genauerer überlegung klar geworden... wobei eine nur 1/3 längere laufzeit in dieser größenordnung nicht wirklich ins gewicht fällt...

hänge nun selbst bei aufgabe 12. bin anscheinend schon betriebsblind, nachdem ich schon den ganzen tag aufgaben löse. hat hier jemand einen vernünftigen lösungsansatz?

nic_power · 04.02.2007

Hallo,

WhiskeyCola16 schrieb:
hänge nun selbst bei aufgabe 12. bin anscheinend schon betriebsblind, nachdem ich schon den ganzen tag aufgaben löse. hat hier jemand einen vernünftigen lösungsansatz?

Momentan nicht, da die Datenbank offensichtlich down ist.

Nic

Data · 04.02.2007

Hallo whiskey, ich mache jetzt mal von deinem Angebot Gebrauch und möchte deine Meinung zu meinem Quelltext von ID 4 haben. Ich meine zu wissen, dass das höchste Palindrom (995599) errechnet wird, aber dies ist nach Euler nicht der Fall

. Findest du da einen Fehler?

Code:

[COLOR="Blue"]Private[/COLOR] [COLOR="blue"]Sub[/COLOR] Button1_Click([COLOR="blue"]ByVal[/COLOR] sender [COLOR="blue"]As[/COLOR] System.Object, [COLOR="blue"]ByVal[/COLOR] e As System.EventArgs) [COLOR="blue"]Handles[/COLOR] Button1.Click
    MsgBox([COLOR="Sienna"]"Das größte Palindrom ist"[/COLOR] & [COLOR="sienna"]" "[/COLOR] & [COLOR="blue"]CStr[/COLOR](Calculate()) & [COLOR="sienna"]"."[/COLOR], MsgBoxStyle.Information)
[COLOR="Blue"]End[/COLOR] [COLOR="blue"]Sub[/COLOR]
[COLOR="blue"]Private Function[/COLOR] Calculate() [COLOR="blue"]As Integer[/COLOR]
    [COLOR="blue"]Dim[/COLOR] i, j [COLOR="blue"]As Integer[/COLOR]

    [COLOR="blue"]For[/COLOR] i = 999 * 999 [COLOR="blue"]To[/COLOR] 10000 [COLOR="blue"]Step[/COLOR] -1
        [COLOR="blue"]If[/COLOR] [COLOR="blue"]CStr[/COLOR](i) = StrReverse([COLOR="blue"]CStr[/COLOR](i)) [COLOR="blue"]Then[/COLOR]
            [COLOR="blue"]For[/COLOR] j = 999 [COLOR="blue"]To[/COLOR] 100 [COLOR="blue"]Step[/COLOR] -1
                [COLOR="blue"]If[/COLOR] i [COLOR="blue"]Mod[/COLOR] j = 0 [COLOR="blue"]Then[/COLOR]
                    [COLOR="blue"]Return[/COLOR] i
                [COLOR="blue"]End[/COLOR] [COLOR="blue"]If[/COLOR]
            [COLOR="blue"]Next[/COLOR]
        [COLOR="blue"]End[/COLOR] [COLOR="blue"]If[/COLOR]
    [COLOR="blue"]Next[/COLOR]
[COLOR="blue"]End[/COLOR] [COLOR="blue"]Function[/COLOR]

In der Zwischenzeit schaue ich mir mal dein Problem 12 an.

WhiskeyCola16 · 04.02.2007

hmmm... du fängst mit 999*999 an und gehst ab da immer 1 runter... weil ja nicht jede zahl unter 999*999 ein produkt von 2 3stelligen zahlen ist, willst du das dann mit einer modulo operation abfragen... was aber so nicht (unbedingt immer) gehen kann. denn zB (999*999-1)%100 = 0. aber (999*999-1)/100=9980. also eine zahl größer als 999. daher rührt das falsche ergebnis.

meine lösung:

Code:

[SIZE=2][COLOR=#0000ff]private [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]void[/COLOR][/SIZE][SIZE=2] btnAufg4_Click([/SIZE][SIZE=2][COLOR=#0000ff]object[/COLOR][/SIZE][SIZE=2] sender, [/SIZE][SIZE=2][COLOR=#008080]EventArgs[/COLOR][/SIZE][SIZE=2] e) {[/SIZE]
[SIZE=2][COLOR=#0000ff]   int[/COLOR][/SIZE][SIZE=2] maxProd = 1;[/SIZE]
[SIZE=2][COLOR=#0000ff]   for[/COLOR][/SIZE][SIZE=2] ([/SIZE][SIZE=2][COLOR=#0000ff]int[/COLOR][/SIZE][SIZE=2] i = 100; i < 1000; i++) {[/SIZE]
[SIZE=2][COLOR=#0000ff]       for[/COLOR][/SIZE][SIZE=2] ([/SIZE][SIZE=2][COLOR=#0000ff]int[/COLOR][/SIZE][SIZE=2] j = 100; j < 1000; j++) {[/SIZE]
[SIZE=2][COLOR=#0000ff]           int[/COLOR][/SIZE][SIZE=2] aktProd = i * j;[/SIZE]
[SIZE=2][COLOR=#0000ff]           string[/COLOR][/SIZE][SIZE=2] strProd = aktProd.ToString();[/SIZE]
[SIZE=2][COLOR=#0000ff]           char[/COLOR][/SIZE][SIZE=2][] arVerkProd = strProd.ToCharArray();[/SIZE]
[SIZE=2][COLOR=#0000ff]           string[/COLOR][/SIZE][SIZE=2] strVerkProd = [/SIZE][SIZE=2][COLOR=#0000ff]string[/COLOR][/SIZE][SIZE=2].Empty;[/SIZE]
[SIZE=2][COLOR=#0000ff]           for[/COLOR][/SIZE][SIZE=2]([/SIZE][SIZE=2][COLOR=#0000ff]int[/COLOR][/SIZE][SIZE=2] k = arVerkProd.Length-1; k>=0; k--) {[/SIZE]
[SIZE=2]               strVerkProd += arVerkProd[k];[/SIZE]
[SIZE=2]           }[/SIZE]
[SIZE=2][COLOR=#0000ff]           if[/COLOR][/SIZE][SIZE=2] (strProd.Equals(strVerkProd)) {[/SIZE]
[SIZE=2][COLOR=#0000ff]               if[/COLOR][/SIZE][SIZE=2] ([/SIZE][SIZE=2][COLOR=#0000ff]int[/COLOR][/SIZE][SIZE=2].Parse(strProd) > maxProd) {[/SIZE]
[SIZE=2]                   maxProd = [/SIZE][SIZE=2][COLOR=#0000ff]int[/COLOR][/SIZE][SIZE=2].Parse(strProd);[/SIZE]
[SIZE=2]               }[/SIZE]
[SIZE=2]           }[/SIZE]
[SIZE=2]       }[/SIZE]
[SIZE=2]   }[/SIZE]
[SIZE=2][COLOR=#008080]   MessageBox[/COLOR][/SIZE][SIZE=2].Show([/SIZE][SIZE=2][COLOR=#800000]"MaximalPalindrom: "[/COLOR][/SIZE][SIZE=2] + maxProd);[/SIZE]
[SIZE=2]}[/SIZE]

"MaximalPalindrom: 906609"

Data · 04.02.2007

aber (999*999-1)/100=9980. also eine zahl größer als 999

Aber es sollen ja dreistellige Faktoren sein. 9980 wäre ja vierstellig. Außerdem habe ich der Modulo-Abfrage noch i / j > 99 hinzugefügt, um sicherzugehen, dass es ein dreistelliger Faktor ist. Werde mir mal noch deinen Quelltext genauer betrachten.

WhiskeyCola16 · 04.02.2007

*gääähn* es ist krass spät für mathe *rofl*
das mein ich ja. anscheinend geht deine abfrage an der stelle nicht so auf wie du möchtest.
wenn du zB i als den einen faktor und j als den anderen nehmen würdest, wie ich, kämst du nicht in die situation eine zahl zu prüfen die gar nicht mit 2 3stelligen faktoren zu erreichen ist.

peterfido · 05.02.2007

Code:

Option Explicit

' Summe der Primzahlen bis 1000000 ermitteln
Public Function Aufgabe10(Optional ByVal lngBis As Long = 1000000) As Double
  Dim I As Long, lngPrimzahl As Long
  Dim ablnSieb() As Boolean
  
  lngBis = 1000000
    
  ' Nach der Re-Dimensionierung haben alle Elemente
  ' den Wert 0 = False
  ReDim ablnSieb(1 To lngBis)
    
  ' Die geradzahligen Elemente werden auf True gesetzt
  For I = 4 To lngBis Step 2
    ablnSieb(I) = True
  Next I
  ' Die "1" ist keine Primzahl
  ablnSieb(1) = True
    
  lngPrimzahl = 3
  Do Until (lngPrimzahl * lngPrimzahl) > lngBis
    If ablnSieb(lngPrimzahl) = False Then
      For I = (lngPrimzahl * lngPrimzahl) To _
        lngBis Step (lngPrimzahl + lngPrimzahl)
        ablnSieb(I) = True
      Next I
    End If
    lngPrimzahl = lngPrimzahl + 2
  Loop
    
  ' Die "2" ist die kleinste Primzahl
  Aufgabe10 = 2
  For I = 3 To lngBis Step 2
    If ablnSieb(I) = False Then
        Aufgabe10 = Aufgabe10 + CStr(I)
    End If
  Next I
  
End Function

Data · 05.02.2007

ID 12? View the Code, Cola.

Code:

[COLOR="Blue"]Private[/COLOR] [COLOR="blue"]Sub[/COLOR] Calculate_Click([COLOR="blue"]ByVal[/COLOR] sender [COLOR="blue"]As[/COLOR] System.Object, [COLOR="blue"]ByVal[/COLOR] e As System.EventArgs) [COLOR="blue"]Handles[/COLOR] Calculate.Click
    MsgBox([COLOR="blue"]CStr[/COLOR](GetTriangle(divisors.Value)) & [COLOR="Sienna"]" "[/COLOR] & [COLOR="sienna"]"ist die erste Dreieckszahl mit mehr als"[/COLOR] & [COLOR="sienna"]" "[/COLOR] & [COLOR="blue"]CStr[/COLOR](divisors.Value) & [COLOR="sienna"]" "[/COLOR] & [COLOR="sienna"]"Divisoren."[/COLOR], MsgBoxStyle.Information)
[COLOR="Blue"]End[/COLOR] [COLOR="blue"]Sub[/COLOR]
[COLOR="blue"]Private[/COLOR] [COLOR="blue"]Function[/COLOR] GetTriangle([COLOR="blue"]ByVal[/COLOR] divisors [COLOR="blue"]As[/COLOR] [COLOR="blue"]Integer[/COLOR]) [COLOR="blue"]As[/COLOR] [COLOR="blue"]Integer[/COLOR]
    [COLOR="blue"]Dim[/COLOR] i [COLOR="blue"]As[/COLOR] [COLOR="blue"]Integer[/COLOR] = 1 [COLOR="SeaGreen"]'increments triangle[/COLOR]
    [COLOR="Blue"]Dim[/COLOR] isTriangle [COLOR="blue"]As[/COLOR] [COLOR="blue"]Boolean[/COLOR] = [COLOR="blue"]False[/COLOR]
    [COLOR="blue"]Dim[/COLOR] j, k [COLOR="blue"]As[/COLOR] [COLOR="blue"]Integer[/COLOR]

    [COLOR="blue"]Do[/COLOR] [COLOR="blue"]Until[/COLOR] isTriangle = [COLOR="blue"]True[/COLOR]
        GetTriangle += i

        [COLOR="blue"]If[/COLOR] GetTriangle > divisors [COLOR="blue"]Then[/COLOR]
            k = 0 [COLOR="SeaGreen"]'counts divisors[/COLOR]

            [COLOR="Blue"]For[/COLOR] j = 1 [COLOR="blue"]To[/COLOR] GetTriangle
                [COLOR="blue"]If[/COLOR] GetTriangle [COLOR="blue"]Mod[/COLOR] j = 0 [COLOR="blue"]Then[/COLOR]
                    k += 1
                [COLOR="blue"]End[/COLOR] [COLOR="blue"]If[/COLOR]
            [COLOR="blue"]Next[/COLOR]
            isTriangle = k > divisors
        [COLOR="blue"]End[/COLOR] [COLOR="blue"]If[/COLOR]

        i += 1
    [COLOR="blue"]Loop[/COLOR]
[COLOR="blue"]End[/COLOR] [COLOR="blue"]Function[/COLOR]

Ist eine ziemlich große Zahl. Hat bei mir eine Viertelstunde, vielleicht auch eine halbe Stunde oder länger gebraucht. Wenn ich an die Eine Minute-Regel denke...
Ich weiß, du wolltest einen Lösungsansatz, stehe im Moment aber unter Zeitdruck, um klar denken zu können

.

Projekt Euler | über 130 Programmieraufgaben

WhiskeyCola16

Anno1989

WhiskeyCola16

Data

WhiskeyCola16

Data

WhiskeyCola16

peterfido

WhiskeyCola16

peterfido

WhiskeyCola16

nic_power

WhiskeyCola16

nic_power

Data

WhiskeyCola16

Data

WhiskeyCola16

peterfido

Data

Projekt Euler | über 130 Programmieraufgaben

ANGEBOTE & SPONSOREN

Neueste Beiträge

Statistik des Forums