|
Registriert seit: 15. Nov 2005
Ort: Uckerland
138 Beiträge
Delphi 7 Enterprise
|
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:
#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;
}
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?
- marcel -
Marcel
|