/*	euklid.C -- Programm kürzt einen Bruch mittels des euklidischen Algorithmus	*/
/*	mit "gcc -DTEST -o euklid euklid.c" kompilieren, um die Zwischenergebnisse	*/
/*	mit ausgegeben zu bekommen							*/


#include <stdio.h>


#ifdef TEST
/* ---- globale Variable ops, zählt die Schleifendurchläufe/Rekursionsaufrufe ---------	*/
int ops;
#endif


/* ---- tausche() für das Tauschen zweier Zahlen --------------------------------------	*/
void tausche(int *zahl1, int *zahl2){
        int hilf=*zahl1;
        *zahl1=*zahl2;
        *zahl2=hilf;
}

/* ---- ggt() für den klassischen Euklidischen Algorithmus ----------------------------	*/
int ggt(int u, int v){
        while(u>0){
        	#ifdef TEST
		printf("%d, %d, ", u, v);
		ops++;
		#endif
		if(u<v)
        		tausche(&u, &v);
        	u=u-v;
	}
        return v;
}

/* ---- ggt_mod() für den Euklidischen Algorithmus mit %-Operator ---------------------	*/
int ggt_mod(int u, int v){
        int hilf;
	while(u>0){
		#ifdef TEST
		printf("%d, %d, ", u, v);
		ops++;
		#endif
		hilf=u;
		u=v%u;
		v=hilf;
        }
        return v;
}


/* -- ggt_rek() für das rekursive Aufrufen des klassischen Euklidischen Algorithmus --- */
int ggt_rek(int u, int v){
	if(u>0){
		#ifdef TEST
		printf("%d, %d, ", u, v);
		ops++;
		#endif
		if(u<v)
			return ggt_rek(v-u, u);
		else
			return ggt_rek(u-v, v);
	}
	else
		return v;
}

/* ---- ggt_mod_rek() für ein rekursives ggt_mod() ------------------------------------	*/
int ggt_mod_rek(int u, int v){
	if(u>0){
		#ifdef TEST
		printf("%d, %d, ", u, v);
		ops++;
		#endif
		return ggt_mod_rek(v%u, u);
	}
	else
		return v;
}


/* ---- ggt_rek2() für einen einzeiligen rekursiven Eukl. Alg. ------------------------	*/
int ggt_rek2(int u, int v){
	return ((u>0) ? ((u<v) ? ggt_rek2(v-u, u) : ggt_rek2(u-v, v)) : v);
}

/* ---- ggt_mod_rek2() für einen einzeiligen rekursiven Eukl. Alg. mit % --------------	*/
int ggt_mod_rek2(int u, int v){
	return ((u>0) ? ggt_mod_rek2(v%u, u) : v);
}


/* ---- main() ------------------------------------------------------------------------	*/
int main(void){
	int ggteiler, u, v;
	short negativ=0;

	do{
		printf("...Geben sie einen zu kuerzenden Bruch an: ");
		scanf("%d/%d", &u, &v);
	}while(u==0 || v==0);
	
	if(u<0){
		u-=u*2;
		negativ=1;
	}
	if(v<0){
		v-=v*2;
		negativ=1;
	}

	#ifdef TEST
	ops=0;
	printf("-----------------------------------\n");
	printf("Zwischenergebnisse ggt():\n");
	#endif
	ggteiler=ggt(u, v);
	#ifdef TEST
	printf("\nSchleifendurchlaeufe: %d\n", ops);
	#endif
	printf(" ==> ggt()=%d\n", ggteiler);
	
	#ifdef TEST
	ops=0;
	printf("-----------------------------------\n");
	printf("Zwischenergebnisse ggt_mod():\n");
	#endif
	ggteiler=ggt_mod(u, v);
	#ifdef TEST
	printf("\nSchleifendurchlaeufe: %d\n", ops);
	#endif
	printf(" ==> ggt_mod()=%d\n", ggteiler);
	
	#ifdef TEST
	ops=0;
	printf("-----------------------------------\n");
	printf("Zwischenergebnisse ggt_rek():\n");
	#endif
	ggteiler=ggt_rek(u, v);
	#ifdef TEST
	printf("\nRekursionsaufrufe: %d\n", ops);
	#endif
	printf(" ==> ggt_rek()=%d\n", ggteiler);
	
	#ifdef TEST
	ops=0;
	printf("-----------------------------------\n");
	printf("Zwischenergebnisse ggt_mod_rek():\n");
	#endif
	ggteiler=ggt_mod_rek(u, v);
	#ifdef TEST
	printf("\nRekursionsaufrufe: %d\n", ops);
	#endif
	printf(" ==> ggt_mod_rek()=%d\n", ggteiler);
	
	#ifdef TEST
	ops=0;
	printf("-----------------------------------\n");
	printf("Keine weiteren Anzeigen für ggt_rek2()...\n");
	#endif
	ggteiler=ggt_rek2(u, v);
	printf(" ==> ggt_rek2()=%d\n", ggteiler);
	
	#ifdef TEST
	ops=0;
	printf("-----------------------------------\n");
	printf("Keine weiteren Anzeigen für ggt_mod_rek2()...\n");
	#endif
	ggteiler=ggt_mod_rek2(u, v);
	printf(" ==> ggt_mod_rek2()=%d\n", ggteiler);

	printf("===================================\n");
	printf("...%d/%d gekuerzt lautet: %d/%d\n", u, v, u/ggteiler, v/ggteiler);
	printf("===================================\n");


	return 0;
}