AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Primzahl-Sudoku

Ein Thema von holle · begonnen am 18. Dez 2006 · letzter Beitrag vom 18. Dez 2006
Antwort Antwort
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
Florian H

Registriert seit: 30. Mär 2003
Ort: Mühlacker
1.043 Beiträge
 
Delphi 6 Professional
 
#2

Re: Primzahl-Sudoku

  Alt 18. Dez 2006, 15:14
wenn das in C sein soll, wäre die Frage, wieso du es in die "Object-Pascal / Delphi-Language"-Sparte eines Delphi-Forums setzt .. und nicht in die "Programmieren allgemein"-Sparte eines Delphi-Forums....

Oh.. und ich muss weg, ggf weiterführendere Antworten nachher :>

Grüßle
flo
Florian Heft
  Mit Zitat antworten Zitat
18. Dez 2006, 15:19
Dieses Thema wurde von "SirThornberry" von "Object-Pascal / Delphi-Language" nach "Programmieren allgemein" verschoben.
new32

Registriert seit: 10. Mai 2005
160 Beiträge
 
Delphi 7 Enterprise
 
#4

Re: Primzahl-Sudoku

  Alt 18. Dez 2006, 17:03
den Teil "primzahlen suchen" kannst du verzürzen, indem du nicht alle i prüfst z.b.4,6,9 weil da können keine neuen nicht-Primzahlen mit erkannt werden.
2*9=6*3
~?&/%§$§%\&?~
8)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es 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

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +2. Es ist jetzt 12:39 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf