[link] Project Euler - Programmieraufgaben

Harry Boeck · Feb 19, 2008

@Tara: Danke!

Wobei: Das hätte in die "schöngeistige" Beschreibung der Aufgabenstellung aufgenommen werden müssen und ins Beispiel aufgenommen werden können. Immerhin wird dort nur anhand der Betrachtung jeweils zweier Strecken zueinander diskutiert.

Erst nach Deinem Hinweis fällt mir der WINZIGE Zusatz "distinct" im allerletzten Satz der seitenlangen Beschreibung auf. Ich schreibe den Jungs mal einen Hinweis...

OZET · Apr 21, 2008

Problem 4 in C++

Hier mein Problem 4 in C++

[hidden]

Code:

// Project Euler Problem 4 - Größtes Palindrom aus 3-stelligen Faktoren
#include <iostream>

using namespace std;

bool isPalindrome (int x)
{
	char buffer[13];
        sprintf_s(buffer, "%d", x); // Zahl in Zeichenkette buffer schreiben
	int len = strlen(buffer);
	for (int i = 0; i < len/2; i++)
	{
		if (buffer[i] != buffer[len -i -1]) return false;
	}
	return true;
}

int main () 
{
	int maximum = 0, temp = 0;
	cout << "Project Euler Problem 4" << endl;
	cout << "Größtes Palindrom aus 3-stelligen Faktoren" << endl;
	cout << "Rechne.." << endl;
	for (int i = 100; i <= 999; i++) 
	{
		for (int p = 100; p <= 999; p++) 
		{
			temp = i*p;
			if (isPalindrome(temp) && temp > maximum) 
			{
				maximum = temp;
				cout << i << " * " << p << " = " << maximum << endl ;
			}
		}	
	}
	cout << "Die Lösung ist " << maximum << endl;

	return 0;
}

[/hidden]

Ich weiß ich hab noch nicht so lange mit C++ zu tun, man hätte die Zahl auch als Vektor nehmen können.

Harry Boeck · Apr 22, 2008

Da gibt's nichts zu entschuldigen: Eine Funktion zu schreiben ist in Zeiten von objektorientierter Analyse und Design von Pattern-gestützten Application Frameworks mit strenger Organisation nach dem Model-View-Controller-Prinzip auf Basis von Managed Code Programming Models ein schweres Verbrechen!

Punkt.

</sarkasmus>

Und jetzt, OZET, im Ernst: Vergiß, Dich dafür zu "entschuldigen", daß Du eine Aufgabe effektiv mit einfachst möglichen Mitteln und bestmöglich verständlich löst!
Dein Progrämmchen ist funktionell wie optisch sauber organisiert, enthält aus Sicht der Programmierung keinerlei Redundanz und ist somit ein Musterbeispiel.
Sowas zu sehen wünsche ich mir zur Zeit in meinen Lehrgängen...

:::Lük::: · Apr 28, 2008

So, jetzt hab ich mich auch mal an Project Euler begeben und habe gleich ein Problem mit Problem 4 (

)

Mein Code:

Code:

#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>

using namespace std;
int main() {
	long res;
	bool pali = true;

	for (long p1 = 999; p1 >= 100; p1--) {
		for (long p2 = 999; p2 >= 100; p2--) {
			res = p1 * p2;

			stringstream sstr;
			sstr << res;
			string resS = sstr.str();

			for (unsigned int i = 0; i < resS.size(); i++) {
				if (resS[i] != resS[resS.size() - 1 - i]){
					pali = false;
				}
			}

			if (pali) {
				cout << "\nLösung: " << p1 << " * " << p2 << " = " << res << endl;
				system("PAUSE");
			} else {
				cout << p1 << " * " << p2 << " = " << res << " (kein Palidrom)" << endl;
			}
			pali = true;
		}
	}
	system("PAUSE");
	return 0;
}

995 * 583 = 580085

Wo soll ich denn jetzt das höhere Palidrom übersprungen haben?

EDIT://Alles klar hab den Fehler gefunden

Stein · Jan 21, 2009

hat einer mal Aufgabe 45 versucht? Mein Algorithmus ist im Grunde richtig und ich konnte ihn auch etwas beschleunigen, aber er ist immer noch viel zu langsam. Wenn einer ne Idee zum beschleunigen hat bitte posten:

Code:

public class ka{
    public static int[] tab_tri;
    public static int[] tab_pen;
    public static int[] tab_hex;
    public static void mk_tab_tri(int n){
        int anz = anz_tab_tri(n);
        tab_tri = new int[anz];
        for(int i = 0; i < anz; i++){
            tab_tri[i] = i*(i+1)/2;
        }
    }
    public static int anz_tab_tri(int n){
        int tri = 0;
        int a = 0;
        while (tri < n){
            a++;
            tri = a * (a + 1)/2;
        }
        return a;
    }
    public static void mk_tab_pen(int n){
        int anz = anz_tab_pen(n);
        tab_pen = new int[anz];
        for(int i = 0; i < anz; i++){
            tab_pen[i] = i*((3*i)-1)/2;
        }
    }
    public static int anz_tab_pen(int n){
        int pen = 0;
        int a = 0;
        while (pen < n){
            a++;
            pen = a * ((3*a) - 1)/2;
        }
        return a;
    }
    public static void mk_tab_hex(int n){
        int anz = anz_tab_hex(n);
        tab_hex = new int[anz];
        for(int i = 0; i < anz; i++){
            tab_hex[i] = i*((2*i)-1);
        }
    }
    public static int anz_tab_hex(int n){
        int hex  = 0;
        int a = 0;
        while (hex < n){
            a++;
            hex = a * ((2*a) - 1);
        }
        return a;
    }
      public static void main(String[] args){
        int ende = 2000000;
        mk_tab_tri(ende);
        mk_tab_pen(ende);
        mk_tab_hex(ende);
        System.out.println("Anzahl der generierten Hexagonalzahlen: " + tab_hex.length);
        for(int i = 0; i < tab_hex.length; i++){
            if(is_tri(tab_hex[i])){
                if(is_pen(tab_hex[i])){
                    System.out.println(tab_hex[i]);
                }
            }
        }
    }
}

Lesco · Jan 21, 2009

Ich habe deinen Algorithmus jetzt nicht genauer angesehen, aber schau dir mal jeweils die ersten paar hexagonalen Zahlen an und vergleiche sie mit der Folge der "Triangle"-Zahlen. Dabei kann einem die erste größere Optimierung einfallen.
Desweiteren lässt sich bei einer gegebenen Zahl in konstanter Zeit prüfen, ob die Zahl eine der drei Eigenschaften aufweist(man beachte die gegebenen Formeln), was evtl. schneller ist als die Generierung der Tabellen(Außerdem wäre es besser diese während des Überprüfens zu generieren und nach einem Fund abzubrechen).
Noch ein kleiner Hinweis am Rande: Das Ergebnis passt in kein Java-int.

0001001 · Jan 22, 2009

kleiner Tip: Alle Hexagonalen Zahlen sind auch Triangle Zahlen

Stein · Jan 22, 2009

Original von Lesco
Ich habe deinen Algorithmus jetzt nicht genauer angesehen, aber schau dir mal jeweils die ersten paar hexagonalen Zahlen an und vergleiche sie mit der Folge der "Triangle"-Zahlen.

Ich glaube das war hiermit gemeint. Ich werde mal gucken wie ich den Algorithmus weiter ausbauen kann.

sadmarvin · Aug 29, 2010

problem 174

Hi, habe mich grad hier angemeldet, weil ich eine Frage zum Problem 174 habe. Und zwar verstehe ich nicht was genau mit N

gemeint ist.

Code:

 Let N(n) be the number of t ≤ 1000000 such that t is type L(n); for example, N(15) = 832.

wäre cool wenn mir diesen Satz mal jemand erklären könnte. Ist so ähnlich wie Problem 173, das habe ich schon gelöst. Bei 174 haperts daran das ich nicht genau weiss was eigentlich gesucht ist.

Eydeet · Aug 30, 2010

Es gibt verschiedene t, die vom Typ L

sind. N

gibt deren Anzahl an, wobei nur t ≤ 1000000 gezählt werden.
So würde ich den Satz zumindest verstehen.

sadmarvin · Aug 30, 2010

hm..

ich habs jetzt rausgefunden.

N

= "mit wie vielen (unterschiedlichen) t < 1.000.000 kann man n verschiedene lamina legen?"

ist das das was du geschrieben hast?

p.s.
Bei Problem 174 war für mich nicht das Lösen die eigentliche Aufgabe, sonder das verstehen der Frage.