Dr. Erhard Henkes, Stand: 05.08.2015

Zurück zum Start

Konsolen-Programme mit C++

1. Einstieg in die Programmierung

Im einfachsten Fall beschafft man sich eine IDE (integrated development environment) wie z.B. Code::Blocks oder eine kostenlose Version von MS Visual Studio (Express oder Community).

Diese IDE enthalten die notwendigen Werkzeuge Editor, Compiler und Linker. Wichtig: Auf optionale Zuschaltung der Neuerungen des C++-ISO-Standards von 2011 bei den Compilereinstellungen achten.

1.1. Was sind Konsolenprogramme?

Dieses Tutorial soll Ihnen einen Einstieg in die Erstellung von Konsolen-Programmen mit der objektorientierten Sprache C++ ermöglichen.  Konsolen-Programme sind das Gegenstück zu "Windows"-Programmen und entstammen den Anfängen der Programmierung.
Ein- und Ausgaben erfolgen hier primär textorientiert.

Obwohl diese Programme aus der "EDV-Steinzeit" stammen, sind sie zum Einstieg in C++ gut geeignet. Man konzentriert sich hier auf die eigentliche Problemlösung und die wesentlichen Programmiergrundlagen und nicht von Anfang an auf die grafische Gestaltung. 

Beginnen wir mit einem rudimentären Beispiel:

int main()
{
  return 0; // ist laut C++-ISO-Standard von 1998 nicht mehr notwendig, wird daher in Folge weggelassen.
}

Der C++-Compiler - das ist das Programm, das Ihren Sourcecode in ausführbaren Code übersetzt - sucht in C und C++ die Funktion main() als Einstiegspunkt. Vor dem main() steht ein int, das für den Variablentyp Integer (Ganzzahl) steht. Ein aktueller Compiler gibt automatisch die Null als Wert zurück, wenn das Programm normal beendet wird.

Das Ergebnis bei Ausführung der resultierenden exe-Datei sieht dann z.B. in der Konsole ("DOS-Box") von MS Windows wie folgt aus:

Was können wir auch mehr erwarten? Wenn Sie diese Ausgabe sehen, ist es Ihnen aber immerhin gelungen, mit dem Programmierwerkzeug, das Ihnen zur Verfügung steht, eine ausführbare exe-Datei zu erzeugen. 

Übrigens sehen viele Einsteiger zunächst nur ein kurzes Aufblitzen dieser Box. Daher muss man das Schließen am Programmende verhindern. Der einfachste Weg, dies zu erreichen, ist der Einbau der ursprünglich von Borland stammenden Funktion getch() bzw. _getch() aus conio.h. Dies entspricht leider nicht dem C++-Standard, ist aber unter MS Windows ziemlich praktisch.

Um portables C++ zu schreiben, verwendet man eine eigene Funktion wait() wie folgt:
#include <iostream>
#include <limits>

void wait()
{
  std::cin.clear();
  std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
  std::cin.get();
}

int main()
{
  wait();
}

Nun wollen wir sofort etwas mehr erreichen. Im nachfolgenden Programm deklarieren wir eine Integer-Variable namens zahl. Wir lesen einen Wert  über die Tastatur ein, den wir in dieser Variable speichern. Anschließend geben wir das Quadrat dieses Wertes auf dem Bildschirm aus: 

#include <iostream>
#include <limits>                           

using namespace std;

void wait(){...}                             //wie oben

int main()
{
  int zahl;
  cin  >> zahl;                              // Eingabe
  cout << zahl * zahl << endl;               // Ausgabe 

  wait();
}

/*---------------------------------------------------------*/
//Alternative: (ohne Öffnung des namespace std)

#include <iostream>
#include <limits>                           

void wait(){...} 

int main()
{
  int zahl ;
  std::cin  >> zahl ;                       // Eingabe
  std::cout << zahl * zahl << std::endl ;   // Ausgabe 

  wait();
}

Anstelle endl kann man auch '\n' schreiben. Es gibt aber einen Unterschied: endl entspricht '\n' (neue Zeile) plus flush (Ausgabepuffer leeren).

Mehrere Anweisungen werden hier zu einer Anweisungsfolge verknüpft, in dem sie nacheinander geschrieben werden.
Dies ist eine einfache Form von Kontrollstruktur, nämlich die sequenzielle Ausführung.

Zunächst wollen wir verstehen, wie eine exe-Datei aus unserem Sourcecode entsteht.
Hierzu verwenden wir (wahrscheinlich unbewusst) drei Werkzeuge:

Precompiler / Präprozessor
Compiler
Linker

Der Precompiler / Präprozessor durchforstet den Sourcecode, um spezielle Anweisungen auszuführen. Diese Anweisungen beginnen mit #.
In unserem Beispiel erkennt der Precompiler #include <iostream>  und setzt an dieser Stelle den entsprechenden Sourcecode ein. Auf diese Weise wird der gesamte Sourcecode bearbeitet. Der resultierende Sourcecode (cpp) wird dem Compiler übergeben. Dieser erzeugt eine Objektdatei (o). Diese wird vom Linker in eine lauffähige Programmdatei (z.B. exe) überführt.

In C++ verfügt man über sogenannte "namespaces". Namensräume sollen dem Programmierer helfen, bei gleichen Namen für Variablen, Klassen etc. Konflikte zu vermeiden. Der Standard-Namespace wird mit std bezeichnet. Gibt man den Namensraum nicht frei, so muss man den Namensraum zusätzlich angeben, also std::cout oder std::cin schreiben.

Betrachten wir zur Veranschaulichung folgendes C++-Programm:
#include <iostream>
#include <limits>

void wait(){...}

namespace MyCpp { double var; }

float var;

int main()
{
  int var;
  std::cout << "globale Variable     : "  << ::var      << std::endl; // 0
  std::cout << "lokale Variable      : "  << var        << std::endl;
  std::cout << "Variable im Namespace: "  << MyCpp::var << std::endl; // 0

  wait();
}


Hier wird drei Mal eine Variable namens var ausgegeben. Die Variable innerhalb main() hat dort ihren begrenzten Scope (Sichtbarkeitsbereich). Um die globale Variable var aufzurufen, setzt man :: davor. Wir können nun ebenfalls in einem eigenen Namensbereich (hier: MyCpp) eine Variable var erzeugen. Hierbei muss man diese Variable durch Voranstellen der Bezeichnung des Namensbereiches und den Operator :: ansprechen.

cout, cin, endl gehören zum Namensbereich std. Daher wird dieser Namen vorangestellt. Wollen Sie das vermeiden, gibt es zwei Möglichkeiten:
a) Man gibt den gesamten Namensbereich std durch  using namespace std;  frei.
b) Man macht die verwendeten Elemente des Namensbereiches std gezielt bekannt:  using std::cout;  usw.


1.2. Variablen und einfache Datentypen

Mit int zahl deklarieren wir eine Integer-Variable. Wir reservieren bei einem 32-Bit-Rechner 4 Byte Speicherplatz für eine vorzeichenbehaftete Ganzzahl. 4 Byte entsprechen 4 * 8 = 32 Bit.
Damit können wir binär einen Ganzzahlenbereich von 2 hoch 32 =  4 294 967 296 abdecken.

Dieser Bereich ist für int (32 Bit) heutzutage - 2 147 483 648 ... 0 ... 2 147 483 647.

Es gibt auch die Möglichkeit nur positive Ganzzahlen und die Null zuzulassen. Hierfür stellt man ein unsigned vor das int:
unsigned int  umfaßt  0 ... 4 294 967 295 (32-Bit-Maschinen).

Sie sehen, dass int automatisch signed int bedeutet. Solche Details findet man üblicherweise in der Datei limits.h.
Dort findet man die Grenzen für die einzelnen Variablentypen: char, short, int, long, ...
 

...

#define SHRT_MIN    (-32768)        /* minimum (signed) short value */
#define SHRT_MAX      32767         /* maximum (signed) short value */
#define USHRT_MAX     0xffff        /* maximum unsigned short value */
#define INT_MIN     (-2147483647 - 1) /* minimum (signed) int value */
#define INT_MAX       2147483647    /* maximum (signed) int value */
#define UINT_MAX      0xffffffff    /* maximum unsigned int value */
#define LONG_MIN    (-2147483647L - 1) /* minimum (signed) long value */
#define LONG_MAX      2147483647L   /* maximum (signed) long value */
#define ULONG_MAX     0xffffffffUL  /* maximum unsigned long value */

#if     _INTEGRAL_MAX_BITS >= 8
#define _I8_MIN     (-127i8 - 1)    /* minimum signed 8 bit value */
#define _I8_MAX       127i8         /* maximum signed 8 bit value */
#define _UI8_MAX      0xffui8       /* maximum unsigned 8 bit value */
#endif

#if     _INTEGRAL_MAX_BITS >= 16
#define _I16_MIN    (-32767i16 - 1) /* minimum signed 16 bit value */
#define _I16_MAX      32767i16      /* maximum signed 16 bit value */
#define _UI16_MAX     0xffffui16    /* maximum unsigned 16 bit value */
#endif

#if     _INTEGRAL_MAX_BITS >= 32
#define _I32_MIN    (-2147483647i32 - 1) /* minimum signed 32 bit value */
#define _I32_MAX      2147483647i32 /* maximum signed 32 bit value */
#define _UI32_MAX     0xffffffffui32 /* maximum unsigned 32 bit value */
#endif

#if     _INTEGRAL_MAX_BITS >= 64
/* minimum signed 64 bit value */
#define _I64_MIN    (-9223372036854775807i64 - 1)
/* maximum signed 64 bit value */
#define _I64_MAX      9223372036854775807i64
/* maximum unsigned 64 bit value */
#define _UI64_MAX     0xffffffffffffffffui64
#endif

#if     _INTEGRAL_MAX_BITS >= 128
/* minimum signed 128 bit value */
#define _I128_MIN   (-170141183460469231731687303715884105727i128 - 1)
/* maximum signed 128 bit value */
#define _I128_MAX     170141183460469231731687303715884105727i128
/* maximum unsigned 128 bit value */
#define _UI128_MAX    0xffffffffffffffffffffffffffffffffui128
#endif

...


1.3. Ein- und Ausgabe mit cin und cout, Selektion mit if/else

cin ist das Standardeingabe-Objekt (Tastatur) und cout das Standardausgabe-Objekt (Bildschirm). Man bezeichnet diese Objekte auch als Streams. Der Doppelpfeil zeigt jeweils die Richtung des Datenflusses an.

Damit nach Ausgabe des Ausdruckes zahl*zahl ein Zeilenvorschub erfolgt wird entweder endl oder das Sonderzeichen '\n' gesendet.
endl leert den Ausgabepuffer (entspricht flush und setzt ein "newline"). Hier finden Sie einige Möglichkeiten für solche Sonderzeichen, die noch aus der Zeit der Programmiersprache C stammen:
 
\n Zeilenvorschub  RETURN bei der Tastatureingabe
\r Carriage Return Zeilenende besteht aus \n\r 
\b Backspace letztes Zeichen wird gelöscht 
\t Tabulator Tabulator-Sprung
\f formfeed Druckerausgabe: Seitenvorschub
\0 NULL String-Endmarkierung
\\ Backslash  erzeugt ein \ auf dem Bildschirm 
\' Hochkomma  erzeugt ein ' auf dem Bildschirm
\" Anführungszeichen erzeugt ein " auf dem Bildschirm

Wenn Sie nun die Zahl 12 eingeben, erhalten Sie die entsprechende Quadratzahl 144:

An unserem einfachen Quadratzahl-Programm können Sie bereits eine Menge testen.

Zunächst geben wir 10 000 oder -10 000 ein und erhalten mathematisch korrekt die Quadratzahl 100 000 000.
Anders sieht es bei 100 000 aus. Hier erhalten wir nicht 10 000 000 000, sondern völlig falsch 1 410 065 408.
Das liegt daran, daß bei 2 147 483 647 plus 1 die Zählweise wieder von vorne beginnt, also bei - 2 147 483 648.
Man spricht hier von einem "Überlauf". Genau genommen liegt es daran, dass das höchste Bit das Vorzeichen signalisiert. Ist es gesetzt, ist die Zahl negativ, wenn nein, dann ist sie positiv. Solche Integer-Typen nennt man signed. Bei unsigned Typen gibt es kein Vorzeichenbit, damit kann man Ganzzahlen von 0 bis 2 ^ 32 - 1 darstellen. 

Testen Sie es selbst aus, indem Sie die Programmzeile:

cout << zahl * zahl << endl;

durch folgende Zeile ersetzen:

cout << zahl+1 << endl;

Für den Variablentyp Integer (int) spendiert ein PC typischerweise 4 Byte ( = 32 bit ). Der Datentyp int entspricht der "Maschinenbreite", die ist noch weitgehend 32 bit mit der Tendenz nach 64 bit. 

Wenn man keine Zahl, sondern z.B. den String (Zeichenfolge) "Hallo" eintippt, dann erhält man 0 (Null) als Ergebnis. Das ist genau genommen auch nicht korrekt, aber immerhin noch erträglich.

Es liegt also an Ihnen als Programmierer, diesen "Blödsinn" zu beherrschen und entsprechende Begrenzungen bei der Entgegennahme und Auswertung von Eingaben durchzuführen.

Nehmen wir den konkreten Fall. Die größte Ganzzahl, die wir mit int (4 Byte) darstellen können, ist 2 147 483 647.
Die Quadratwurzel hieraus ist abgerundet 46340. Also dürfen wir keine Eingabe größer als 46340 oder kleiner als -46340 akzeptieren.
Hierzu verwendet man z.B. eine if / else - Kontrollstruktur, einen Größenvergleich und eine logische "ODER"-Verknüpfung:
 
 
#include <iostream>
#include <limits>
using namespace std;

void wait(){...}

int main()
{
  int zahl;
  cin  >> zahl;
  if( zahl > 46340 || zahl < -46340 ) cout << "Zahl zu gross" << endl;
  else cout << zahl*zahl << endl;

  wait();
}

Die if / else - Kontrollstruktur funktioniert nach folgendem Prinzip:
 

if( Bedingung )
{
    Block 1
}
else
{
    Block 2
}

Da Grössenvergleiche und logische Verknüpfungen häufig vorkommen, hier eine Übersicht:
 
== gleich 
!= ungleich 
> größer 
>= größer oder gleich 
<  kleiner 
=<  kleiner oder gleich 
&& logisches UND
||  logisches ODER
!  Negation 

Nun fehlt noch die Anzeige für den Benutzer, was eigentlich passieren soll bzw. passiert ist.
Das erledigt man bei Konsolenanwendungen in C++ durch cout-Anweisungen (Ausgabe auf das Standardausgabe-Objekt):
 
#include <iostream>
#include <limits>
using namespace std;

void wait(){...}

int main()
{
 int zahl;
 cout << "Bitte Zahl eingeben: ";
 cin  >> zahl;
 if( zahl > 46340 || zahl < -46340 ) cout << "Zahl zu gross" << endl;
 else 
 {
  cout << "Quadratzahl: " << zahl*zahl << endl;
 }

 wait();
}

Experimentieren Sie an dieser Stelle bitte eifrig mit eigenen Ideen, z.B. verschiedene Umrechnungen (kW/PS, kcal/kJ, °C/°F/K, Währungen, ...).
Nur durch eigene Versuche erhalten Sie Routine beim Erstellen des Sourcecodes.
 

1.4. Kleine Rechenprogramme, float und double

Ein einfaches Beispiel aus der Mathematik wollen wir uns gemeinsam anschauen.

Hat man eine quadratische Gleichung x² + px + q = 0, so löst sich diese auf nach x1 = - p/2 + sqrt( p²/4 - q) und x2 = - p/2 - sqrt( p²/4 - q).
sqrt steht hier für Quadratwurzel (square root).

Zunächst soll unser Programm anzeigen, was es auszuführen gedenkt, anschließend die Eingabe von p und q fordern, die Berechnung durchführen und zum Schluß die Ergebnisse x1 und x2 ausgeben. Da wir hier mit Kommazahlen anstelle von Ganzzahlen arbeiten müssen, benötigen wir einen anderen Variablentyp als int . Dafür gibt es die entsprechenden Typen für Fließkommazahlen float oder double.

Der Datentyp float (4 Byte = 32 bit) verwendet für die Mantisse 24 bit, für den Exponenten 7 bit und für das Vorzeichen ein bit und kann daher Werte im Bereich 3.4 * 10-38 bis 3.4 * 1038 aufnehmen. Die Darstellung ist auf 6 Nachkommastellen begrenzt.

Der mächtigere Datentyp double (8 Byte = 64 bit) verwendet für die Mantisse 53 bit, für den Exponenten 10 bit und für das Vorzeichen ein bit und kann daher Werte im Bereich 1.7 * 10-308 bis 1.7 * 10308 aufnehmen. Die Darstellung ist bis auf 15 Nachkommastellen genau. Daher ist dieser Typ z.B. für einfache kaufmännische, technische und wissenschaftliche Programme geeignet.

Damit wir sqrt() benutzen können, müssen wir cmath (Datei math.h) einbinden.
Damit erhalten wir im ersten Ansatz folgenden Sourcecode:
 
 
#include <iostream>
#include <limits>
#include <cmath>  // notwendig fuer sqrt(...)
using namespace std;

void wait(){...}

int main()
{
 cout << "Berechnung quadratischer Gleichungen vom Typ x*x + p*x + q = 0"
      << endl << endl;

 double p, q, x1, x2;
 cout << "Bitte p eingeben: ";
 cin  >> p;
 cout << "Bitte q eingeben: ";
 cin  >> q;

 x1 = -p/2 + sqrt( p*p/4.0 - q );
 x2 = -p/2 - sqrt( p*p/4.0 - q );

 cout << endl << "x1 = " << x1 << endl << "x2 = " << x2 << endl;

 wait();
}

Hier folgt ein erstes Rechenbeispiel mit diesem Programm:

Wir wollen nicht auf den Fall eingehen, wenn  p*p/4.0 - q negativ wird.
Sie wissen ja bereits, wie man mit if/else solche Fälle unterscheiden und abfangen kann.

Vielleicht fragen Sie sich, warum wir p*p/4.0 und nicht einfach p*p/4 geschrieben haben. Dies ist ein wichtiger Punkt!

Das Anfügen von ".0" wandelt Ganzzahlen in Fließkommazahlen um. Kommen in einem Ausdruck sowohl ganze Zahlen als auch Kommazahlen vor, so stellt der Compiler sicher, dass zu jeder Rechnung auf beiden Seiten des Rechenzeichens der gleiche Typ vorliegt. Hierzu wird z.B. eine ganze Zahl in eine Fließkommazahl umgewandelt.

In obigem Fall spielt es keine Rolle, ob wir 4 oder 4.0 schreiben, aber es gibt auch tückische Fälle, die ohne Warnung zu falschen Resultaten führen. Hätten wir z.B. nicht geschickt p*p/4.0 - q codiert, sondern 1/4*p*p - q, dann wäre die Misere sofort da!

Probieren Sie unser Programm mit folgenden fehlerhaften Zeilen aus:

x1 = -p/2 + sqrt( 1/4*p*p - q );
x2 = -p/2 - sqrt( 1/4*p*p - q );

Wie Sie sehen, ist das Ergebnis falsch! Woran liegt das genau?

Der Grund liegt darin, dass 1/4 als Ergebnis 0 liefert. 1 und 4 sind Ganzzahlen, daher wird das Ergebnis von 1/4 auch als Ganzzahl gewertet, und hier wird 0.25 durch Abrundung umgewandelt in 0. Testen Sie das Programm zur Überprüfung mit folgenden Zeilen:

x1 = -p/2 + sqrt( 0 - q );
x2 = -p/2 - sqrt( 0 - q );

Wie Sie sehen, erhalten Sie obiges falsches Ergebnis. Daher muss(!) man die Integer-Schreibweise 1/4 in die float/double-Schreibweise 1.0/4.0 umwandeln, dann klappt das:

x1 = -p/2 + sqrt( 1.0/4.0*p*p - q );
x2 = -p/2 - sqrt( 1.0/4.0*p*p - q );

Machen Sie sich diesen Zusammenhang bitte vollkommen durch eigene Experimente klar.
 

Fazit:
In Kombination mit Fließkommazahlen sollte man ganze Zahlen immer mit dem Anhang .0 versehen, damit sie als Fließkommazahlen behandelt werden und man korrekte Resultate erhält.


Aufgabe:
Basteln Sie sich bitte eine angepasste Routine für die Gleichung a*x2 + b*x + c:

Die Ausdrücke

   (-b + sqrt(4*a*c - b*b))/2/a
   (-b - sqrt(4*a*c - b*b))/2/a

stehen für die Nullstellen des quadratischen Polynoms a*x2 + b*x + c (falls vorhanden).

Wir betrachten noch ein weiteres einfaches Beispiel zur Berechnung des Kugelvolumens aus dem Radius:
 
#include <iostream>
#include <limits>
using namespace std;

void wait(){...}

int main()
{
    const double PI = 3.141592; //Konstante
    double r, v;

    cout << "Berechnung des Kugelvolumens: " << endl;
    cout << "Bitte Radius eingeben." << endl; 
    cout << "Radius = ";
    cin  >> r; 

    v = 4.0 / 3.0 * PI * r * r * r ; //Formel

    cout << "Das Volumen betraegt " << v; 
    cout << endl;

    wait();
}

Hier wird die in der Mathematik wichtige Konstante Pi benötigt.
Solche Konstanten schreibt man groß und definiert sie unter Hinzufügen des Schlüsselwortes const.


Schreiben Sie ein Programm, das die Berechnung des Umfangs

U = 2.0 * Pi * r

und/oder die Fläche des Kreises mit Radius r

F = r * r * Pi

ermöglicht.

Derartige Aufgaben sind natürlich eines Computers nicht würdig. Dafür würde auch ein wissenschaftlicher Taschenrechner reichen.
Daher werden wir uns nun einem Problem zuwenden, das sehr viele Berechnungen innerhalb möglichst kurzer Zeit erfordert.
Das ist eine typische Aufgabe für schnelle Rechner.
 

1.5. Collatz-Folge

Bekannt ist dieses Thema unter dem Namen Collatz-Problem oder 3n+1-Folge. Was verbirgt sich dahinter?
Im Jahre 1937 behauptete Herr Collatz, dass eine Folge, die dadurch entsteht, dass man gerade Zahlen halbiert und ungerade Zahlen mit drei multipliziert und eins addiert, immer auf dem Zyklus 4 - 2 - 1 - 4 - 2 - 1 - ... endet.


Diese Behauptung ist bis heute weder bewiesen noch widerlegt. Sie können also Mathematik-Geschichte schreiben. Falls Sie es mit einzelnen Zahlen probieren wollen:

Wichtige Links:

http://matheroboter.de/collatz
http://www.ieeta.pt/~tos/3x+1.html
http://www.ericr.nl/wondrous/index.html
http://de.wikipedia.org/wiki/Collatz-Problem

Also wie war das noch mal? Nehmen wir die Zahl 7.
Das ergibt diese Folge: 7 - 22 - 11 - 34 - 17 - 52 - 26 - 13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1
Die Elementanzahl H(n) ist 17. Man kann auch die Schritte zählen. Dies nennt man dann z.B. Delay(n) = H(n) -1.
Delay(n) = Odd(n) + Even(n).

Der Kern des Programms könnte also wie folgt aussehen:

if( zahl % 2 == 0 ) 
    nächste_zahl = zahl / 2 ;
else                
    nächste_zahl = 3 * zahl + 1 ;

Das %-Zeichen (Modulus-Operator) ergibt den Rest einer Division. Der Modulus-Operator arbeitet ausschließlich mit Integer-Operanden und kann mit Gleitkomma-Operanden nichts anfangen. Bei geraden Zahlen ist das Ergebnis in unserem Fall 0, bei ungeraden Zahlen 1.

Aufbauend auf dieser Prüfung kann man eine if/else-Kontrollstruktur aufbauen.  

Dann fehlt noch eine Schleife (hier mit while), denn wir wollen die Folge vom Ausgangswert bis zum Zyklus 4 - 2 - 1 berechnen und die einzelnen Werte ausgeben. Eine zweite äußere Schleife (hier mit for) erlaubt die Berechnung mehrerer Folgen.

Wenn man eine Schleife erzeugt, benutzt man einfach nur eine Variable zahl, ansonsten müsste man noch die Zuweisung zahl = nächste_zahl einfügen. Das gesamte Programm sieht im ersten Schritt wie folgt aus:
 
// Berechnung der "Collatz-Folge"

#include <iostream> 
#include <limits>

using namespace std;

void wait(){...}

int main()
{
  unsigned long start ;               // Beginn der Berechnung bei 'start'
  unsigned long end ;                 // Ende der Berechnung bei 'end'

  /**************************** Eingabebereich ****************************/
  cout << "Erste Zahl:  " ;   cin  >> start ;
  cout << "Letzte Zahl: " ;   cin  >> end ;
  /**************************** Eingabebereich ****************************/

  unsigned long zahl ;  // Element der Folge 
  unsigned long i ;     // Zählvariable für die Folgenlänge

  for( unsigned long j = start; j < end+1; j++ )
  {
    zahl = j ; 
    i = 1 ;
    cout << "\n" <<  j << " " ; // Ausgangswert

    while( zahl != 1 ) // Prüfung auf Zyklus 4-2-1 
    {
        if( zahl % 2 == 0 )  zahl /=  2 ;           // Collatz-Folge
        else                 zahl = 3 * zahl + 1 ;  // Collatz-Folge

        cout << zahl << " "; // Element der Folge 
        i++ ; 
    }

    if( zahl == 1 ) cout << "\tH(n): "  <<  i << endl ; // H(n) Länge der Folge
  }
  wait();
}

Gibt man hier die Ausgangswerte 1 bis 10 ein erhält man diesen Bildschirmausdruck:

Das Programm ist bereits so ausgerüstet, dass man auch bei längeren Folgen noch den Überblick behält:

Nachdem wir uns überzeugt haben, dass unser Programm richtig arbeitet, wollen wir nun Zahlen auf die Richtigkeit der Behauptung von Herrn Collatz "checken". Wie machen wir das? Wir nehmen einfach die Ausgabe der einzelnen Elemente und einen Zeilenumbruch aus dem Programm:
 
...
for( unsigned long j = start; j < end+1; j++ )
  {
       zahl = j ; 
    i = 1 ;
       cout << /*"\n" <<*/ j << " " ; // Ausgangswert

    while( zahl != 1 ) // Prüfung auf Zyklus 4-2-1 
       {
            if( zahl % 2 == 0 )  zahl /=  2 ;           // Collatz-Folge
            else                 zahl = 3 * zahl + 1 ;  // Collatz-Folge

   // cout << zahl << " "; // Element der Folge 
            i++ ; 
       }

       if( zahl == 1 ) cout << "\tH(n): "  <<  i << endl ; // H(n) Länge der Folge
  }
...

Hier ein Beispiel für die Zahlen von von 100 bis 120:

Lassen Sie nun eine Zahlenkolonne von 1 bis 100000 an Ihnen vorbei rollen. Was ist hier so langsam?
Ganz einfach: die Ausgabe in unserer Konsole!

Da müssen wir etwas unternehmen. Wir brauchen eine Begrenzung der Ausgabe. Da wir nur an riesigen Folgen interessiert sind, die irgendwie Probleme machen, setzen wir den Ausgabewert für H(n) einfach so hoch, dass wir nur die Extreme als Ausdruck erhalten.
Zum Experimentieren schaffen wir hier also eine zusätzliche Eingabe eines "Ausgabe-Limits":
 
// Berechnung der "Collatz-Folge"

#include <iostream> 
#include <limits>

using namespace std;

void wait(){...}

int main()
{
  unsigned long start ;               // Beginn der Berechnung bei 'start'
  unsigned long end ;                 // Ende der Berechnung bei 'end'
  unsigned long ausgabe_limit ;       // Ausgabe ab H(n) > 'ausgabe_limit' 

  /**************************** Eingabebereich ****************************/
  cout << "Erste Zahl:  " ;   cin  >> start ;
  cout << "Letzte Zahl: " ;   cin  >> end ;
  cout << "H(n) ab:     " ;   cin  >> ausgabe_limit ;
  /**************************** Eingabebereich ****************************/

  unsigned long zahl ;  // Element der Folge 
  unsigned long i ;     // Zählvariable für die Folgenlänge

  for( unsigned long j = start; j < end+1; j++ )
  {
    zahl = j ; 
    i = 1 ;

    while( zahl != 1 ) // Prüfung auf Zyklus 4-2-1 
    {
      if( zahl % 2 == 0 )  zahl /= 2 ; 
      else                 zahl = 3 * zahl + 1 ; 

      i++ ; 
    }

    if( ( zahl == 1 ) && ( i >= ausgabe_limit ) ) 
    {
      cout << j ; // Ausgangswert
      cout << "\tH(n): "  <<  i << endl ; // H(n) Länge der Folge
    }
  }
  wait();
}

Jetzt geht das alles ganz fix! Wenn wir die Folgen für die Ausgangszahlen von 1 bis 100000 berechnen lassen und hierbei die Ausgabegrenze für H(n) auf 320 setzen, dann benötigt das Programm nur noch einen Sekundenbruchteil. 


 

Wir testen noch einen weiteren Fall mit den Zahlen bis 10.000.000 mit H(n)>500. Zeitverbrauch: < 1 Minute.

Interessant ist auch der Geschwindigkeitsvergleich der beiden Möglichkeiten im Sourcecode:

     if( zahl % 2 == 0 )  zahl /= 2 ;            // Collatz-Folge
     else                 zahl = 3 * zahl + 1 ;  // Variante 1

     ( zahl % 2 == 0 ) ? zahl /= 2 : zahl = 3 * zahl + 1 ; // Collatz-Folge Variante 2

In beiden Fällen benötigt das kompilierte Programm die gleiche Zeit. Das können wir also abhaken.
Wir behalten hier die if/else-Schreibweise bei, da diese verständlicher ist.

Jetzt können wir die Milliarde innerhalb einer Stunde schaffen, insbesondere mit den heute üblichen Prozessoren der Gigahertz-Klasse.

Wer eine Klasse höher mitmischen will, sollte unsigned long long ( 2 hoch 64 = 18.446.744.073.709.551.616 ) einsetzen.
Nachfolgend ein rudimentäres Beispiel für das Testen des Zahlenbereiches zwischen 10^15 und 2*10^15:
 
//Version für Compiler mit dem 64 Bit Integer unsigned long long:

// Berechnung der "3n+1"-Folge (Collatz-Folge)
#include <iostream>
#include <limits>

using namespace std;

void wait(){...}

int main()
{
  /*********************************************************** Eingabebereich ****************************/
  const unsigned long long element_limit       =             1000000 ; // Maximum H(n)
  const unsigned long long element_print_limit =                 500 ; // Ausgabe nur, wenn H(n) > element_print_limit
  const unsigned long long start               =    1000000000000000 ; // Beginn der Berechnung bei start
  const unsigned long long end                 =    2000000000000000 ; // Ende der Berechnung bei end
  /*********************************************************** Eingabebereich ****************************/

  for( unsigned long long j = start; j < end; j++ )
  {
       unsigned long long zahl = j ;
       unsigned long long    i = 1 ;
       while( ( zahl != 1 ) && ( i <= element_limit ) )
       {
            if( zahl % 2 == 0 )
                zahl /= 2 ;
            else
                zahl = 3 * zahl + 1 ;
            i++ ;
       }

       if( zahl == 1 )
       {
            if( i > element_print_limit )
            {
                cout << "Startzahl: " << j;
                cout << "\tAnzahl: "  << i << endl;
            }
       }
       else
       {
           cout << "Startzahl: " << j;  
           cout << "kein Resultat (Anzahl-Limit erhoehen)" << endl;
       }

       if( i > element_limit ) cerr << "Anzahl zu hoch" << endl;
  } 
   
  wait();
}



Konsolen sind für solche "blutleeren" Anwendungen ideal, wie Sie sehen. Viel Spaß damit!

Diese Grenze von 18.446.744.073.709.551.616 ist allerdings störend vor allem wegen des unberechenbaren 3n+1, das ab 1 Trillion schnell diese Grenze überspringt, daher benötigt man eine spezielle Bibliothek für wirklich große Zahlen.

Hier eine einfache Bibliothek als Einstiegsbeispiel:

http://mattmccutchen.net/bigint/  C++ Big Integer Library von Matt McCutchen.

... und hier ein dazu passendes Programm, mit dem man nun in unerforschtem Gebiet analysieren kann, allerdings nur mit deutlich eingeschränkter Geschwindigkeit:

// Berechnung der "3n+1"-Folge (Collatz-Folge)
#include <iostream>
#include <limits>
#include <string>
#include "BigIntegerLibrary.h"

using namespace std;

void wait()
{
  std::cin.clear();
  std::cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n');
  std::cin.get();
}

int main()
{
  /*********************************************************** Eingabebereich ****************************/
  BigUnsigned element_limit(1000000) ;      // Maximum H(n)
  BigUnsigned element_print_limit(4103) ;    // Ausgabe nur, wenn H(n) > element_print_limit
 
  string s("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");               // Beginn der Berechnung bei start
  BigUnsigned start = easyStringToBI(s);

  s = "10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000";                    // Ende der Berechnung bei end
  BigUnsigned end = easyStringToBI(s); 
  /*********************************************************** Eingabebereich ****************************/

  for( BigUnsigned j = start; j < end; j++ )
  {
       BigUnsigned zahl = j ;
       BigUnsigned    i = 1 ;
       while( ( zahl != BigUnsigned(1) ) && ( i <= element_limit ) )
       {
            //cout << zahl << '\t';
            BigUnsigned rest = zahl % BigUnsigned(2);
            if( rest != BigUnsigned(1) )
                zahl /= BigUnsigned(2) ;
            else
                zahl = BigUnsigned(3) * zahl + BigUnsigned(1) ;
            i++;
       }

       if( zahl == BigUnsigned(1) )
       {
            if( i > element_print_limit )
            {
                cout << "Startzahl: " << j;
                cout << "\tAnzahl: "  << i << endl;
            }
       }
       else
       {
           cout << "Startzahl: " << j; 
           cout << "kein Resultat (Anzahl-Limit erhoehen)" << endl;
       }

       if( i > element_limit ) cerr << "Anzahl zu hoch" << endl;
  }
  
  wait();
}

Viel Spaß damit!

1.6. Goldbach-Vermutung

"Jede gerade Zahl größer als 2 kann als Summe zweier Primzahlen geschrieben werden."  Dies ist die Goldbach-Vermutung.

Das ist doch ein gefundenes Fressen für eine interessante Konsolenanwendung.

#include <iostream>
#include <limits>
#include <cmath>
#include <ctime>

using namespace std;

void wait()
{
    cin.clear();
    cin.ignore(std::numeric_limits<streamsize>::max(), '\n');
    cin.get();
}

namespace MyMath
{
    bool IsPrime(unsigned int number)
    {
        for (unsigned int i=2; i<number; i++)
        {
            if (number%i == 0)
                return false;
        }
        return true;
    }
}

int main()
{
    clock_t zeit1 , zeit2;
    unsigned int a;
    zeit1 = clock();
    bool gegenbeweis = true;

    for (unsigned int i=6; i<=500000; i+=2)
    {
        if (i%25000 == 0)
        {
            zeit2 = clock();
            cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl;
        }

        for (unsigned int a=2; a<i; a++)
        {
             if ((MyMath::IsPrime(a)) && (MyMath::IsPrime(i-a)))
             {
                 gegenbeweis = false;
                 //cout << a << " " << i-a << "    ";
                 break;
             }
        }

        if (gegenbeweis)
        {
            cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl;
            wait();
        }
    }

    //wait();
 }

Bei mir auf dem PC sieht die zeitliche Betrachtung hierbei wie folgt aus:

25000   time: 621 ms
50000   time: 2491 ms
75000   time: 5619 ms
100000  time: 9994 ms
125000  time: 15593 ms
150000  time: 22437 ms
175000  time: 30544 ms
200000  time: 39916 ms
225000  time: 50438 ms
250000  time: 62218 ms
275000  time: 75245 ms
300000  time: 89397 ms
325000  time: 104800 ms
350000  time: 121441 ms
375000  time: 139344 ms
400000  time: 158445 ms
425000  time: 178884 ms
450000  time: 200550 ms
475000  time: 223375 ms
500000  time: 247545 ms

Experimentieren und optimieren Sie mit dem Programm. Schauen Sie sich nicht gleich eine mögliche Lösung an.

// Beschleunigte Variante (Danke an das c-plusplus.de Forum, namentlich erwähnen möchte ich Volkard Henkel)

#include <iostream>
#include <limits>
#include <ctime>
#include <cstdint>
 
using namespace std;
 
void wait()
{
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    cin.get();
}
 
bool IsPrime(uint64_t number)
{
    if(number<2)    return false;
    if(number==2)   return true;
    if(number%2==0) return false;
 
    for(uint64_t i=3; i*i<=number; i+=2)
    {
        if(number%i == 0) return false;
    }
    return true;
}
 
bool ZweiPrimzahlenGefunden(uint64_t i)
{
    for(uint64_t a=2; a<i; a++)
    {
        if(IsPrime(a) && IsPrime(i-a))
            return true;
    }
    return false;
}
 
int main()
{
    clock_t zeit1 , zeit2;
    zeit1 = clock();
 
    for(uint64_t i=6; i<=5000000; i+=2)
    {
        if(!ZweiPrimzahlenGefunden(i))
            cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl;
 
        if (i%100000 == 0)
        {
                zeit2 = clock();
                cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl;
        }
    }
 
    wait();
 }

Mit -O3 und 64 bit: 5.000.000 time: 18652 ms!

... und nun geben wir richtig Gas. Danke an Volkard, Bengo, Arcoth u.a. aus dem C++-Forum. Dort finden auch Sie volle Unterstützung in Fragen von C++.

Ich habe die BigIntegerLibrary (Alternative: gmp mit gmpxx) eingebunden, um über 2^64 zu gelangen und x64 als Ziel angegeben:

#include <iostream>
#include <iomanip>
#include <cstdint>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include "BigIntegerLibrary.hh"

using namespace std;

void wait()
{
    cout << "Press any key to continue." << endl;
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    cin.get();
}

//calculates (a * b) % c
BigUnsigned mulmod(BigUnsigned a, BigUnsigned b, BigUnsigned mod)
{
    BigUnsigned x = 0;
    BigUnsigned y = a % mod;

    while (b > 0)
    {
        if (b % 2 == 1)
        {
            x = (x + y) % mod;
        }
        y = (y * 2) % mod;
        b /= 2;
    }
    return x % mod;
}

BigUnsigned powmod_Volkard(BigUnsigned base, BigUnsigned exp, BigUnsigned modul)
{
    //rechnet 'base hoch exp mod modul'
    BigUnsigned a1 = base, z1 = exp, x = 1, m = modul;
    while (z1 != 0)
    {
        while ((z1 % 2) == 0)
        {
            z1 /= 2;
            a1 = mulmod(a1, a1, m);
        }
        --z1;
        x = mulmod(x, a1, m);
    }
    return x;
}

bool IsPrimeMillerRabinOptimized(BigUnsigned n)
{
    /*
    example:
    step: "calculate s and d"
    n = 1001
    n-1 = 1000
    s = 3
    d = 125
    1000 / 2^3 = 125

    step: "test with base a"
    ad = a^d mod n  (cf. function powmod)


    */

    if (n == 2)
        return true;
    // "s" is the logarithm to base base 2 of the biggest number 2^s dividing n-1
    // d = (n-1)/(2^s)
    // calculate d and s
    BigUnsigned d = n - 1;
    BigUnsigned s = 0;
    while ((d & 1) == 0)
    {
        ++s; d >>= 1;
    }

    // We do not use random base a = {2 ... n-1}, but fix it to a = 2
    BigUnsigned a = 2; // base ("witness")
    BigUnsigned ad = (powmod_Volkard(a%n, d, n)); // (a^d) mod n

    if (ad == 1)
        return true; // a^d mod n == 1
    if ((s > 0) && (ad == (n - 1)))
        return true; // a^d mod n == -1 (tests (a^d)^(2^0))

    // test for r = {0 ... s-1}
    for (BigUnsigned r = 1; r < s; ++r)
    {
        // ad is currently ad^(2^(r-1)), thus we square it to get ad^(2^r))
        ad = mulmod(ad, ad, n);
        if (ad == (n - 1))
            return true; // tests (a^d)^(2^(r+1)))
    }
    return 0; // false, composite
}

bool IsPrimeDivisionTest(BigUnsigned number)
{
    if (number<2)    return false;
    if (number == 2)   return true;
    if (number % 2 == 0) return false;
    for (BigUnsigned i = 3; i*i <= number; i += 2)
    {
        if (number%i == 0) return false;
    }
    return true;
}

bool IsPrime(vector<bool>& primes, BigUnsigned number, BigUnsigned primeLimit)
{
    if (number <= primeLimit)
        return primes[number.toUnsignedLong()]; // lookup from bitset (in the RAM)
    return IsPrimeMillerRabinOptimized(number);
}

bool PrimePairFound(vector<bool>& primes, BigUnsigned i, const BigUnsigned primeLimit)
{
    bool retVal = false;
    BigUnsigned grenze = i / 2;
    BigUnsigned a = 0;
    for (a = 3; a <= grenze; a += 2)
    {
        if (IsPrime(primes, a, primeLimit) && IsPrime(primes, i - a, primeLimit))
        {
            retVal = true;
            break;
        }
    }

    cout << i << "  " << setw(5) << a << " ";
    return retVal;
}


int main()
{
    BigUnsigned startNumber = stringToBigUnsigned("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
    BigUnsigned endNumber   = stringToBigUnsigned("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000");

    uint64_t const primeLimit = 100000000; //200000000000;
    cout << "We generate vector<bool>(primes) up to: " << primeLimit << endl; // (this amount depends on the capability of your RAM)

    vector<bool> primes(primeLimit); // processed numbers;
    time_t startTime, endTime;         // measuring execution time
    uint64_t global_count = 0;         // total number of primes
    time(&startTime);

    // initialize the number array
    primes[0] = false;
    primes[1] = false;
    for (uint64_t i = 2; i<primeLimit + 1; ++i)
    {
        primes[i] = true;
    }

    // sieving loop
    uint64_t iMax = (uint64_t)sqrt((double)primeLimit) + 1;
    for (uint64_t i = 2; i<iMax; ++i)
    {
        if (primes[i])
        {
            for (uint64_t j = 2 * i; j<primeLimit + 1; j += i)
            {
                primes[j] = false;
            }
        }
    }

    time(&endTime);

    // count the number of primes
    for (uint64_t i = 0; i<primeLimit + 1; ++i)
    {
        if (primes[i])
            global_count++;
    }

    cout << "In " << difftime(endTime, startTime) << " s we found " << global_count
        << " prime numbers (2 to " << primeLimit << " )." << endl << endl;

    cout << "Now Goldbach first prime number pair will be detected" << endl;

    clock_t zeit1, zeit2, zeit2_old;
    zeit2 = zeit1 = clock();


    for (BigUnsigned i = startNumber; i <= endNumber; i += 2)
    {
        if (!PrimePairFound(primes, i, BigUnsigned((unsigned long)primeLimit)))
        {
            cout << "Counterevidence found for this number: " << i << endl;
            wait();
        }

        zeit2_old = zeit2;
        zeit2 = clock();

        cout << "time: " << 1000 * (zeit2 - zeit2_old) / CLOCKS_PER_SEC << " ms" << endl;
    }
    wait();
}




1.7. Argumente hinter Programmname auswerten

Wenn beim Start des Programms Argumente - getrennt durch einen Whitespace - durch einfaches Anhängen hinter den Programmnamen übergeben werden, so möchte man diese innerhalb main() {...} auswerten können. Das gelingt wie folgt:

#include <iostream>
#include <limits>

void wait(){...}

int main( int argc, char *argv[] )
{
  for( int i=0; i<=argc; ++i)
  {
    std::cout << i << ": " << argv[i] << std::endl;
  }

  wait();
}

Eingabe:   main.exe arg1 arg2

Ausgabe:
0: main.exe
1: arg1
2: arg2
3:

1.8. Farbe in der Konsole

Manche mögen bereits in der Konsole etwas mehr Komfort, z.B. farbige Texte. Hier ein Vorschlag, wie man das auf einfache Art erledigen kann:

#include <limits>
#include <iostream>
#define NOMINMAX     //wegen Konflikt mit max(). Alternative:  #undef max  nach windows.h
#include <windows.h> //warning: no C++ standard!

using namespace std;

void wait()
{
  std::cin.clear();
  std::cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n');
  std::cin.get();
}

void textcolor(unsigned short color=15)
{
    SetConsoleTextAttribute(::GetStdHandle(STD_OUTPUT_HANDLE), color);
}

int main()
{
  for (int i=1; i<15; ++i)
  {
      textcolor(i);
      cout << "Hello World!" << endl;
  }

  textcolor();
  cout << "\nColorless C++ ISO Standard:" << endl;
  cout << "hello, world" << endl;

  wait();
}    

Als Ausgabe findet man:



Zurück zum Start