 |
 |
 |
 |
 |
|
|
Registriert seit: 15. Nov 2005 Ort: Uckerland 138 Beiträge Delphi 7 Enterprise |
#1
Primzahl-Sudoku
18. Dez 2006, 15:11
Hallo, ich habe versucht eine Aufgabe zu lösen.
Zitat:
Problem: die Primzahlen
Figur 1 zeigt ein Quadrat, jede Reihe, jede Zeile und die beiden Diagonalen können als fünfstellige Primzahl gelesen werden. Die Reihen werden von links nach rechts gelesen. Die Spalten von oben nach unten. Beide Diagonalen werden von links nach rechts gelesen. Schreibe ein Programm, dass solche Quadrate konstruiert und dazu die Daten in der INPUT.TXT -Datei nutzt. * Die Primzahlen müssen die gleiche Ziffernsumme haben (Im Beispiel 11) * Die Zahl in der oberen linken Ecke des Quadrates ist vordefiniert (Im Beispiel 1) * Eine Primzahl wird eventuell mehr als einmal im Quadrat benutzt * Falls es mehrere Lösungen gibt, müssen alle dargelegt werden * Eine fünfstellige Primzahl kann nicht mit Null beginnen, z.B. 00003 ist KEINE fünfstellige Primzahl.
Code:
Programmiert werden sollte das ganze in C. Das ganze funktioniert auch soweit sehr gut. Mein Problem ist nur die Laufzeit. Das Programm braucht gut 10-15 Minuten um die Lösung anzuzeigen. Ich habe schon versucht meinen Quelltext zu optimieren, es hat aber nicht viel gebracht. Wisst ihr vielleicht, was ich noch verändern könnte um die Performence zu steigern?
#include <stdio.h>
#include <stdlib.h> int quersumme(int number) { int ret = 0; int temp = number; int i; for (i = 0; i < 5; i++) { ret += temp % 10; temp /= 10; } return ret; } int main(int argc, char *argv[]) { int i, j, k, l, m; int summe; int erste; int anzahl = 0; int temp; int zahl[100000]; int lauf[100000]; int q[5][5]; // eingabe printf("SUMME: "); scanf("%d", &summe); printf("ERSTE ZAHL: "); scanf("%d", &erste); // primzahlen suchen for (i = 0; i < 100000; i++) zahl[i] = 1; for (i = 2; i <= 100000 / 2; i++) for (j = 2; j <= 100000 / i; j++) zahl[i*j] = 0; // quersumme for (i = 0; i < 100000; i++) if (quersumme(i) != summe) zahl[i] = 0; // laufzahlen for (i = 10000; i < 100000; i++) if (zahl[i] == 1) { lauf[anzahl] = i; printf("> %d\n", i); anzahl++; } printf("anzahl %d\n", anzahl); system("pause"); // lösung suchen for (i = 0; i < anzahl; i++) { if ((lauf[i] >= 10000 * erste) && (lauf[i] <= 10000 * erste + 9999)) { q[0][0] = lauf[i] / 10000; q[0][1] = (lauf[i] % 10000) / 1000; q[0][2] = (lauf[i] % 1000) / 100; q[0][3] = (lauf[i] % 100) / 10; q[0][4] = lauf[i] % 10; if ((q[0][0] != 0) && (q[0][1] != 0) && (q[0][2]) && (q[0][3]) && (q[0][4])) { for (j = 0; j < anzahl; j++) { for (k = 0; k < anzahl; k++) { for (l = 0; l < anzahl; l++) { for (m = 0; m < anzahl; m++) { q[1][0] = lauf[j] / 10000; q[1][1] = (lauf[j] % 10000) / 1000; q[1][2] = (lauf[j] % 1000) / 100; q[1][3] = (lauf[j] % 100) / 10; q[1][4] = lauf[j] % 10; q[2][0] = lauf[k] / 10000; q[2][1] = (lauf[k] % 10000) / 1000; q[2][2] = (lauf[k] % 1000) / 100; q[2][3] = (lauf[k] % 100) / 10; q[2][4] = lauf[k] % 10; q[3][0] = lauf[l] / 10000; q[3][1] = (lauf[l] % 10000) / 1000; q[3][2] = (lauf[l] % 1000) / 100; q[3][3] = (lauf[l] % 100) / 10; q[3][4] = lauf[l] % 10; q[4][0] = lauf[m] / 10000; q[4][1] = (lauf[m] % 10000) / 1000; q[4][2] = (lauf[m] % 1000) / 100; q[4][3] = (lauf[m] % 100) / 10; q[4][4] = lauf[m] % 10; if (q[0][0] + q[1][0] + q[2][0] + q[3][0] + q[4][0] == summe) { if (q[0][1] + q[1][1] + q[2][1] + q[3][1] + q[4][1] == summe) { if (q[0][2] + q[1][2] + q[2][2] + q[3][2] + q[4][2] == summe) { if (q[0][3] + q[1][3] + q[2][3] + q[3][3] + q[4][3] == summe) { if (q[0][4] + q[1][4] + q[2][4] + q[3][4] + q[4][4] == summe) { if (q[0][0] + q[1][1] + q[2][2] + q[3][3] + q[4][4] == summe) { if (q[0][4] + q[1][3] + q[2][2] + q[3][1] + q[4][0] == summe) { temp = q[0][0] * 10000; temp += q[1][1] * 1000; temp += q[2][2] * 100; temp += q[3][3] * 10; temp += q[4][4]; if (zahl[temp]) { temp = q[0][4] * 10000; temp += q[1][3] * 1000; temp += q[2][2] * 100; temp += q[3][1] * 10; temp += q[4][0]; if (zahl[temp]) { temp = q[0][0] * 10000; temp += q[1][0] * 1000; temp += q[2][0] * 100; temp += q[3][0] * 10; temp += q[4][0]; if (zahl[temp]) { temp = q[0][1] * 10000; temp += q[1][1] * 1000; temp += q[2][1] * 100; temp += q[3][1] * 10; temp += q[4][1]; if (zahl[temp]) { temp = q[0][2] * 10000; temp += q[1][2] * 1000; temp += q[2][2] * 100; temp += q[3][2] * 10; temp += q[4][2]; if (zahl[temp]) { temp = q[0][3] * 10000; temp += q[1][3] * 1000; temp += q[2][3] * 100; temp += q[3][3] * 10; temp += q[4][3]; if (zahl[temp]) { temp = q[0][4] * 10000; temp += q[1][4] * 1000; temp += q[2][4] * 100; temp += q[3][4] * 10; temp += q[4][4]; if (zahl[temp]) { printf("%d%d%d%d%d\n", q[0][0], q[0][1], q[0][2], q[0][3], q[0][4]); printf("%d%d%d%d%d\n", q[1][0], q[1][1], q[1][2], q[1][3], q[1][4]); printf("%d%d%d%d%d\n", q[2][0], q[2][1], q[2][2], q[2][3], q[2][4]); printf("%d%d%d%d%d\n", q[3][0], q[3][1], q[3][2], q[3][3], q[3][4]); printf("%d%d%d%d%d\n", q[4][0], q[4][1], q[4][2], q[4][3], q[4][4]); printf("\n"); } } } } } } } } } } } } } } } } } } } } } system("PAUSE"); return 0; } - marcel -
Marcel
|
Zitat
|
ForumregelnEs ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.
BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus. Trackbacks are an
Pingbacks are an
Refbacks are aus
|
|
Baum-Darstellung
