Kopfnuss - 2 - Seite 4

finsternacht · 01.05.2013, 02:22

C++ und GMPlib ist ganz nett. Da kann man dann die "großen" Zahlen mit den ganz normalen Operatoren verwenden.

wieschoo · 01.05.2013, 19:20

Da ich am Anfang überrascht war, habe ich mal ein bissel mit geproggt.
Nach mehreren Fehlschlägen die Mpir zu kompilieren bin ich jetzt auf ttmath umgestiegen. Gefällt mir wesentlich besser! Das ist nun mein 4. Algorithmus.

D:\PROJECTS\Cplusplus\counter\Release>counter.exe 19
10510505506657796201260422960831791522973765163701 9975757755051314
Time taken: 164.175s

auf einem "Intel Core 2 Duo T9300 2.5Ghz".

Cheese · 04.05.2013, 19:40

Hab dir mein Code und ne Dokumentation wie ich zu dem Algo gekommen bin zugeschickt,
alle dran denken morgen 14 Uhr ist Deadline, freue mich die Lösungen von paar anderen Leuten zu sehen.

wieschoo · 04.05.2013, 20:11

Jo, ist angekommen. Da hast du mich wohl geschlagen

. Ich habe nun auch meine Quelltexte beisammen und Erklärungen zu meinem Programmen geschrieben.

Alles, was bis 14:00 Uhr ankommt packe ich einfach in ein ZIP-Archiv sozusagen als offzielle Lösungssammlung, die ich dann als Anhang zusätzlich zu den NoPaste-Links poste.

wieschoo · 05.05.2013, 14:59

Anbei sind alle abgegebenen Lösungen inklusive Erklärungen.

finsternacht · 05.05.2013, 15:01

Ist ja schade, nach dem so viel Aktivität hier war am Anfang dann doch nur 3 Abgaben zu haben.

wieschoo · 05.05.2013, 15:03

Ich für meinen teil jedenfalls bin über die anderen Ideen völlig überrascht. Kompliment an dich und cheese!

Danke für die Abgaben. Einfach war die Aufgabe wirklich nicht. Erst nachdem hier Lösungen für n>10 standen, habe ich mich selbst noch einmal dran geklemmt, um nicht unter zu gehen.

Vielleicht bekommen wir noch eine schnellere Lösung hin.
Ich versuche gerade deine Matrix zu konstruieren, die du potenzieren möchtest. Schau dir mal den fremden PARI-code oder alternativ meine Übersetzung nach C an. Das ist glaube ich deine Idee.

finsternacht · 05.05.2013, 15:10

Den PARI/pg hatte ich auch gefunden, der ist aber nicht besonders spannend. Spannender wäre Robert Gerbicz C-Code gewesen. Mit dem wurde nämlich die Tabelle berechnet.
bzgl der Matrizen, in numpy kann ich die multiplizieren, habe aber halt unendlich viel overhead.

Ansonsten vllt mal auf den b2h irc kommen?

wieschoo · 05.05.2013, 15:15

Schau mal hier:

http://www.cap-lore.com/MathPhys/BitArray/2Dn.c

Wie lautet die url für b2h irc?

Domenic · 05.05.2013, 15:26

Jetzt wo die Lösungen öffentlich sind, möchte ich mal erklären wie ich daran gegangen bin und woran es bei mir gescheitert ist. Bei mir entstand wahrscheinlich ein Integer Fehler durch eine Division. Ich hatte mich nämlich entschieden für die Aufgabe die mathematische Binomialkoeffizient zu verwenden.

Ich bemerkte, solange n > 1 ist, können aufgerundet maximal n * n / 2 Felder gesetzt werden. Da man keine benachbarten Felder besetzen darf, kann man das ganze Feld ganz einfach Spiegeln solange n > 1 und n % 2 = 0 ist. Wenn n % 2 = 1, dann muss die letzte Spiegelung ausgelassen werden. Mit Spiegelung meine ich in diesem Fall, dass alle setzbaren Möglichkeiten von 0 bis n * n / 2 abgerundet, auf eine ganze Zahl dupliziert werden, da sie ebenfalls auf anderen Feldern stehen können.

Mein Code sieht wie folgt aus...


			
BigInteger getPossibilites(unsigned int n)

{

    BigInteger result = 1;

    unsigned int middleValue = n * n / 2;

    n % 2 ? middleValue += 1 : 0;



    for(int i = 1; i <= middleValue; i++)

    {

        BigInteger c = 1;

        for(int m = 1; m <= i; m++)

            c = c * (middleValue + 1 - m) / m;

        n > 1 ? n % 2 && i == middleValue ? result += c : result += c * 2 : result += c;

    }

    return result;

}

Vielleicht findet jemand den Fehler, ich habe ihn nicht gefunden bzw. hatte keine Lust mehr und habe aufgegeben.

Liebe Grüße,
Domenic