Einzelnen Beitrag anzeigen

holle

Registriert seit: 15. Nov 2005
Ort: Uckerland
138 Beiträge
 
Delphi 7 Enterprise
 
#1

Primzahl-Sudoku

  Alt 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
  Mit Zitat antworten Zitat