Das Palindromproblem lautet: Ergibt sich bei jeder Startzahl des Spiegel-Additions-Prozesses nach endlich vielen Schritten ein Palindrom?
1. Beispiel
| 1.1 | 18 + 81 = 99 | ® (ein Schritt) | ||||||
| 1.2 | 19 + 91 = 110 | ® 110 + 011 = 121 | ® (zwei Schritte) | |||||
| 1.3 | 68 + 86 = 154 | ® 154 + 451 = 605 | ® 605 + 506 = 1111 | ® (drei Schritte) | ||||
2. Aufgabe
| 2.1(a) | Bitte geben Sie alle Zahlen zwischen 1 und 1000 an, die erst nach mehr als 24 Schritten zu einem Palindrom führen! | |
| 2.1(b) | Bitte geben Sie die Zahl zwischen 1 und 10000 an, die das größte Palindrom ergibt! | |
| 2.2 | Bitte prüfen Sie eine Menge von gegebenen Zahlen auf das Palindromproblem. D.h. bitte geben Sie die Anzahl der gelesenen Zahlen aus und die Anzahl der "Palindromzahlen" aus dieser Menge. Bitte lesen Sie Zahlen von einer Datei ein. Der Dateiname wird vom Benutzer eingegeben. Die Zahlen sind zeilenweise - d.h. eine Zahl pro Zeile - gespeichert. |
3. Durchführung
| 3.1 | Entwickeln Sie einen Lösungsalgorithmus für die unter (2.) gestellte Aufgabe. Die Ausprägung des Algorithmus soll in einem Struktogramm nachgewiesen werden. | |
| 3.2 | Erzeugen Sie ein C-Programm nach dem unter (3.1) entwickelten Struktogramm. |
/***************************************************************************************
Name des Projekts: Umsetzung des Palindromproblemes
Name der Autoren: Olaf Gramkow, Björn Schweinsberg
Version/Generation: 1.0
Änderungs-Historie: 02.03.2000
Bekannte Probleme/Einschränkungen: - Palindromproblem wird nur bis zu 1000 Schritten geprüft
****************************************************************************************/
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Funktion zum Testen ob Zahl eine Palindromzahl ist
bool IsPalindrom(unsigned long Number)
{
int i, lang;
char str[100], strOriginal[100], ch;
bool palindrom = true;
// Zahl in einen String umwandeln
sprintf(str, "%lu", Number);
// String str nach strOriginal kopieren
strcpy(strOriginal, str);
// Länge des Strings ermitteln
lang = strlen(str);
// Umdrehen der Zahl
for (i=0; i < lang / 2; i++)
{
ch = str[i];
str[i] = str[lang - i - 1];
str[lang - i - 1] = ch;
}
// Prüfen ob Palindrom
for (i = 0; i < lang; i++)
{
if (str[i] != strOriginal[i])
palindrom = false;
}
return palindrom;
}
// Funktion zum lösen des Palindromproblems
long CheckPalindrom(unsigned long Number, long &schritte)
{
unsigned long newNumber;
int i, lang;
char str[100], str2[100], ch;
bool palindrom;
// Variable schritte auf 0 setzen
schritte = 0;
do
{
// Variable palindrom auf "wahr" setzen
palindrom = true;
// Zahl in einen String umwandeln
sprintf(str, "%ul", Number);
// Länge des Strings ermitteln
lang = strlen(str);
// Umdrehen der Zahl
for (i=0; i < lang / 2; i++)
{
ch = str[i];
str[i] = str[lang - i - 1];
str[lang - i - 1] = ch;
}
// Originalzahl und gedrehte Zahl addieren
newNumber = Number + (unsigned long)atol(str);
// neue Zahl in einen String umwandeln
sprintf(str, "%ul", newNumber);
// String str nach str2 kopieren
strcpy(str2, str);
// Länge des Strings ermitteln
lang = strlen(str2);
// Umdrehen der Zahl
for (i=0; i < lang / 2; i++)
{
ch = str2[i];
str2[i] = str2[lang - i - 1];
str2[lang - i - 1] = ch;
}
// Prüfen ob Palindrom
for (i = 0; i < lang; i++)
{
if (str[i] != str2[i])
palindrom = false;
}
// Variable schritte um 1 erhöhen
schritte++;
// Palindrom nach 1000 Schritten noch nicht berechnet!
if (schritte == 1000 && !palindrom)
return -1;
// neue Zahl für nächsten Durchlauf in die Variable Number kopieren
Number = newNumber;
}
while (!palindrom); // solange Ausführen bis Variable palindrom "wahr" ist
return atol(str2);
}
// Funktion um auf einen Tastendruck zu warten
void WaitForChar()
{
cout << "Bitte Return-Taste druecken" << endl;
getchar();
}
// Hauptfunktion
int main()
{
unsigned long i, Palindrom, bigPalindrom = 0, bigZahl = 0;
long schritte;
cout << "********************************************************" << endl;
cout << "* Palindromproblem - Version 1.0 *" << endl;
cout << "* *" << endl;
cout << "* copyright (c) 2000 Olaf Gramkow, Bjoern Schweinsberg *" << endl;
cout << "********************************************************" << endl << endl;
for (i = 1; i <= 1000; i++)
{
Palindrom = CheckPalindrom(i, schritte);
// Aufgabe 2.1a
if (schritte > 24)
{
cout << "Zahl : " << i << endl;
if ((long)Palindrom == -1)
cout << "Palindrom nach 1000 Schritten noch nicht ermittelt." << endl << endl;
else
cout << "Palindrom: " << Palindrom << endl << endl;
// auf Tastendruck warten
WaitForChar();
}
// Aufgabe 2.1b
if (Palindrom > bigPalindrom)
{
bigZahl = i;
bigPalindrom = Palindrom;
}
}
// Aufgabe 2.1b
cout << endl << endl << "Groesstes Palindrom: " << bigZahl << " (" << bigPalindrom << ")" << endl;
// auf Tastendruck warten
WaitForChar();
// Aufgabe 2.2
char str[255];
cout << endl << "Bitte Dateinamen eingeben: ";
cin.getline(str, 255);
if (strlen(str) != 0)
{
// Datei öffnen
ifstream file(str);
// Variablen Palindrom und i auf 0 setzen
Palindrom = i = 0;
// erste Zeile aus der Datei lesen
file.getline(str, 255);
while (!file.eof())
{
i++;
// Testen ob Zahl eine Palindromzahl ist
if (IsPalindrom(atol(str)))
Palindrom++;
// nächste Zeile aus der Datei lesen
file.getline(str, 255);
}
// Datei schließen
file.close();
cout << "Gelesene Zahlen: " << i << endl;
cout << "Palindromzahlen: " << Palindrom << endl;
}
else
cout << "Es wurde kein Dateiname eingegeben!" << endl;
// auf Tastendruck warten
WaitForChar();
return 0;
}
Struktogramme für das C++ Programm