/* B E S C H R E I B U N G
Induktiv werden Zahlen definiert:
Man beginnt mit 3 und 5.
Jeweils zwei verschiedene Zahlen werden addiert und geben eine neue Zahl.
3, 5
3, 5, 8
3, 5, 8, 11
3, 5, 8, 11, 14, 16, 19, 
...

Alle diese Zahlen ergeben die Menge D der wundersamen Zahlen
*/

#include "stdafx.h"

void anfuegen(int feld[], int zahl);
void vermehren(int feld[]);
int min(int feld[], int i1, int i2);
void vertausche(int feld[], int index1, int index2);
void sortieren(int feld[], int i1, int i2);
int istWundersam(int zahl);
int istEnthalten(int feld[], int zahl);

const int feldLen=50000;

int main(){
	int i;
	int erg;
	int feld[feldLen];
	int zahl;
	int ausgangszahl1;
	int ausgangszahl2;

	ausgangszahl1= 3;
	ausgangszahl2 = 5;

	for(i=0;i<feldLen;i++)
		feld[i]=0;

	anfuegen(feld, ausgangszahl1);
	anfuegen(feld, ausgangszahl2);


	for(i=0;i<8;i++){
		vermehren(feld);
		sortieren(feld, 1, feld[0]);
	}


	printf("Feldlaenge = %d\n", feld[0]);	
	printf("Hier die Ausgabe der ersten %d wundersamen Zahlen, zusaetzlich noch sortiert:\n\n",feld[0]);	
	for(i=1;i<=feld[0];i++)
		printf("%d ", feld[i]);
	printf("\n\n");	

	return 0;


}

/**************************************************************/
/**                                                          **/
/**  void anfuegen(int feld[], int zahl)                     **/
/**                                                          **/
/*#************************************************************/
/*
Parameter:  
  (i/o) int feld[]   :  Feld, das aus Zahlen besteht. 
  (i) int zahl       :  Zahl, die an das Feldende angefügt wird.
 
Return:
  kein
 
Beschreibung:
  Wenn die Zahl "zahl", nicht in dem Array "feld" vorkommt, wird 
  diese an das Feldende angefügt.
  Wenn die Zahl "zahl", in dem Array "feld" vorkommt, geschieht nichts.
  Das Element feld[0] ist tabu (geht den Programmierer nichts an) 
  und darf nicht benutzt werden, denn an dieser Stelle wird intern 
  die Länge des Feldes gespeichert. Diese Länge wird automatisch um 
  eins erhöht, wenn eine Zahl angefügt wird.

Beispiel:
  int feld [6] : 2 9 12 6 7 9
  anfuegen(feld, 1)

  liefert:
  feld [6] : 3 9 12 1 7 9
*/ 
void anfuegen(int feld[], int zahl){
	int len;
	int i;
	
	len = feld[0];
	for(i=1;i<=len;i++){
		if(zahl==feld[i]){
			return;
		}
	}
	len++;
	feld[len]=zahl;
	feld[0]=len;

}

/**************************************************************/
/**                                                          **/
/**  void vermehren(int feld[])                              **/
/**                                                          **/
/*#************************************************************/
/*
Parameter:  
  (i/o) int feld[]   :  Feld, das aus Zahlen besteht und das vermehrt wird 
 
Return:
  kein
 
Beschreibung:
  Jeweils 2 verschiedene Elemente des Feldes "feld" werden miteinander addiert 
  (ergibt sum) und an das Ende des Feldes angefügt, falls sum nicht schon im 
  Feld "feld" vorkommt.
  Die Länge des Feldes wird in feld[0] verwaltet.

Beispiel:
  int feld [1000] : 3 3 5
  vermehren(feld) liefert:
  feld: 4 3 5 8 
  vermehren(feld) liefert:
  feld: 6 3 5 8 11 13
*/ 

void vermehren(int feld[]){
	int len;
	int i, j;
	int erg;
	
	len = feld[0];
	for(i=1;i<=len;i++){
		for(j=1;j<=len;j++){
			if(feld[i]!=feld[j]){
				erg=feld[i]+feld[j];
				anfuegen(feld,erg);
			}
		}
	}
}


/**************************************************************/
/**                                                          **/
/**  int istWundersam(int zahl)                              **/
/**                                                          **/
/*#************************************************************/
/*
Parameter:  
  (i) int zahl     :  Zahl
 
Return:
  1: die Zahl "zahl" ist Element von D (oben definiert)
  0: sonst
 
Beschreibung:
  Prüft nach, ob eine Zahl zu D gehört oder nicht.

Beispiel:
  e(3) = 1
  e(6) = 0 
*/


int istWundersam(int zahl){
	int len;
	int i, j;
	int erg;
	int feld[feldLen];
	int beenden=0;
	int max;
	
	len = feld[0];
	feld[0]=2;
	feld[1]=3;
	feld[2]=5;;
	while(beenden==0){
		vermehren(feld);
		sortieren(feld,1,feld[0]);
		max=feld[feld[0]];
		if(max>zahl)
			beenden=1;
	}
	erg=istEnthalten(feld, zahl);
	return erg;
}

/**************************************************************/
/**                                                          **/
/**  int istEnthalten(int feld[], int zahl)                  **/
/**                                                          **/
/*#************************************************************/
/*
Parameter:  
  (i) int feld[] :  Feld, das aus Zahlen besteht. 
  (i) int zahl   :  zahl  
 
Return:
  1: zahl ist im Feld enthalten
  0: sonst
 
Beschreibung:
  Prüft nach, ob die Zahl "zahl" im Feld "feld" enthalten ist.
  Wichtig: feld[0] ist tabu, da dort die Länge des Feldes 
  verwaltet wird.

Beispiel:
  feld: 3 10 7 9
  istEnthalten(feld, 3) liefert 0, da 3 nicht im Feld vorkommt.
  Denn feld[0]=3 ist die Feldlänge und deshalb tabu.
*/

int istEnthalten(int feld[], int zahl){
	int i;
	int len;
	len=feld[0];

	for(i=1;i<=len;i++){
		if(feld[i]==zahl)
			return 1;
	}
	return 0;
}

/**************************************************************/
/**                                                          **/
/**  void sortieren(int feld[], int i1, int i2)              **/
/**                                                          **/
/*#************************************************************/
/*
Parameter:  
  (i/o) int feld[] :  Feld, das aus Zahlen besteht. 
  (i) int i1       :  kleinere Grenze
  (i) int i2       :  größere Grenze
 
Return:
  kein
 
Beschreibung:
  Sortiert eine Folge von Zahlen zwischen den Indizes (Stellen) 
  i1 und i2 nach aufsteiegender Größe.

Beispiel:
  int feld [6] : 6 5 6 3 7 1
  i1 = 1
  i2 = 4

  int feld [6] : 6 5 6 3 6 1

  liefert:
  feld [6] : 6 3 5 6 6 1
*/
void sortieren(int feld[], int i1, int i2){
	int i;
	int indexVomMinimum;

	for(i=i1;i<=i2;i++){
		indexVomMinimum=min(feld, i, i2);
		if(feld[i]>feld[indexVomMinimum])
			vertausche(feld, i, indexVomMinimum);
	}
}


/**************************************************************/
/**                                                          **/
/**  int min(int feld[], int i1, int i2)                     **/
/**                                                          **/
/*#************************************************************/
/*
Parameter:  
  (i) int feld[] :  Feld, das aus Zahlen besteht. 
  (i) int i1 :  1. Index  des Felds
  (i) int i2 :  2. Index  des Felds  
 
Return:
  Index des Minimums
 
Beschreibung:
  Bestimmt das Minimum des Feldes innerhalb des Index i1 und i2 
  (je einschließlich) und gibt den Index dieses Minimums zurück,

Beispiel:
  feld: 3 -5 7 9 -2 -12 4
  i1=0
  i2=4 
  Rückgabe: -5
*/

int min(int feld[], int i1, int i2){
	int i;
	int indexVomMinimum=i1;
	int minimum=feld[i1];

	for(i=i1;i<=i2;i++){
		if(feld[i]<minimum){
			minimum=feld[i];
			indexVomMinimum=i;
		}
	}
	return indexVomMinimum;

}

/**************************************************************/
/**                                                          **/
/**  void vertausche(int feld[], int index1, int index2)     **/
/**                                                          **/
/*#************************************************************/
/*
Parameter:  
  (i) int feld[] :  Feld, das aus Zahlen besteht. 
  (i) int i1 :  1. Index  des Felds
  (i) int i2 :  2. Index  des Felds  
 
Return:
  kein
 
Beschreibung:
  vertauscht in dem Feld das Element feld[i1] mit dem 
  Element feld[i2]
*/

void vertausche(int feld[], int index1, int index2){
	int temp1, temp2;

	temp1=feld[index1];
	temp2=feld[index2];
	feld[index1]=temp2;
	feld[index2]=temp1;
}