#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <iostream.h>

// prototypes des fonctions
void   Exo_Interrupteurs(int n);
void   Exo_Cartes(int n);
void   Exo_Aleatoire(int n,int k);
void   Exo_Permutations(int n,int k);

// pour le 2
#define TAILLE   100
typedef int bigEntier[TAILLE];

void   SaisieEntier(bigEntier x);
void   MettreEntier(int e,bigEntier x);
void   Affichage(bigEntier x);
void   Somme(bigEntier a,bigEntier b,bigEntier r);
void   Difference(bigEntier a,bigEntier b,bigEntier r);
void   Produit(bigEntier a,bigEntier b,bigEntier r);

void   Exo_Factorielle(int n);

// le main
int    main(int argc,char* argv[])
{
	int n;
	int k;

	cout << "factorielle de? ";
	cin >> n;
	Exo_Factorielle(n);
	cout << endl << endl;


	cout << "Nb d'interrupteurs? ";
	cin >> n;
	Exo_Interrupteurs(n);
	cout << endl << endl;

	cout << "Nb de cartes? ";
	cin >> n;
	Exo_Cartes(n);
	cout << endl << endl;

	cout << "Taille du tableau? ";
	cin >> n;
	cout << "nombres tires entre 1 et ? ";
	cin >> k;
	Exo_Aleatoire(n,k);

	cout << "Taille des permutations? ";
	cin >> n;
	cout << "Nombres de tirages? ";
	cin >> k;
	Exo_Permutations(n,k);
	cout << endl << endl;



}

// exo 1.1
// les interrupteurs qui restent allumes sont ceux dont le numero est
// le carre d'un entier
// 0=eteint ; 1=allume
void   Exo_Interrupteurs(int n)
{
	if ( n <= 0 ) {
		cout << "pas d'interrupteurs\n";
		return;
	}
	// on initialise le tableau avec des lampes eteintes
	int  lampes[n];
	for (int i=0;i<n;i++) lampes[i]=0;
	// bien remarquer que lampes[i] est la (i+1)ieme lampe

	for (int div=1;div<=n;div++) {
		// on change toutes le lampes dont le numero est multiple de div
		for (int i=div;i<=n;i+=div) {
			// rappel: la i-eme lampe est lampes[i-1]
			if ( lampes[i-1] == 0 ) {
				lampes[i-1]=1;
			} else {
				lampes[i-1]=0;
			}
		}
	}
	// il ne reste plus qu'a afficher
	cout << "les lampes encore allumees ont les numeros:\n";
	for (int i=0;i<n;i++) {
		if ( lampes[i] ) cout << i+1 << " ";
	}
	cout << endl;
}

// exo 1.2
//d'autres solutions ont ete proposees :
//1 - Allouer un tableau deux fois plus grand et copier les cartes gardees a la suite
//    dans le tableau. (montrer que deux fois la taille est suffisant).
//2 - Faire plusieurs fois le tour du tableau en marquant les cartes supprimees
void   Exo_Cartes(int n)
{
	if ( n <= 0 ) {
		cout << "pas de cartes\n";
		return;
	}
	// on initialise le tableau avec des cartes numerotees de 1 a n
	int  *cartes=(int*)malloc(n*sizeof(int));
	for (int i=0;i<n;i++) cartes[i]=i+1;

	// nbCartes compte le nombre de cartes restant dans le paquet
	int   nbCartes=n; 
	while ( nbCartes > 1 ) {
		// on garde le numero de la premiere carte
		int  premiere=cartes[0];
		// on decale toutes les autres (la 3eme devient la 1ere, la 4eme devient
		// la 2eme...)
		for (int i=0;i<nbCartes-2;i++) cartes[i]=cartes[i+2];
		// on enleve une carte et on met la premiere a la fin
		nbCartes--;
		cartes[nbCartes-1]=premiere;
	}
	cout << "il reste la carte: " << cartes[0] << endl;
	// cartes n'etant pas automatiquement detruit, il faut le faire
	free(cartes);
}

// exo 1.3
void   Exo_Aleatoire(int n,int k)
{
	if ( n <= 0 ) {
		cout << "pas de tirages\n";
		return;
	}
	if ( k <= 1 ) {
		cout << "pas de hasard\n";
		return;
	}
	// on reserve le tableau pour stocker les valeurs
	int     *tirages=new int[n];
	// on le rempli avec des nombres aleatoires
	for (int i=0;i<n;i++) {
		// random()%k est entre 0 et k-1, donc il faut decaler pour
		// etre entre 1 et k
		tirages[i]=random()%k +1; 
	}
	// recherche du min/max
	int min=tirages[0],max=tirages[0];
	for (int i=0;i<n;i++) {
		if ( tirages[i] > max ) max=tirages[i];
		if ( tirages[i] < min ) min=tirages[i];
	}
	cout << "minimum= " << min << " ; maximum= " << max;

	// pour chaque valeur possible entre 1 et k on va calculer 
	// le nombre d'occurrences de la valeur dans le tableau
	// on utilise un tableau pour stocker les nombres d'occurrences
	int   occur[k];
	// on initialise tout a 0 occurrences
	for (int j=0;j<k;j++) occur[j]=0;
	// puis on parcourt le tableau des tirages et on compte
	for (int i=0;i<n;i++) {
		// les tirages[i] sont entre 1 et k, donc il faut redecaler
		occur[tirages[i]-1]++;
	}
	// la frequence de x est (nb occurrences de x)/(nb tirages)
	cout << "frequences:\n";
	for (int j=0;j<k;j++) {
		float   freq=occur[j];
		freq/=n;
		cout << "  " << j+1 << " -> " << freq << endl;
	}
	
	// pour la distribution, on va proceder sans tableau (c'est plus lent
	// qu'en utilisant un tableau annexe)
	// sinon on peut se rendre compte que la distribution est la frequence
	// de la frequence
	cout << "distribution:\n";
	for (int x=0;x<=n;x++) {
		// on parcourt le tablequ occur a la recherche des nombres
		// apparaissant x fois; s compte combien il y en a
		int   s=0;
		for (int j=0;j<k;j++) {
			if ( occur[j] == x ) s++;
		}
		if ( s > 0 ) {
			cout << "  " << x << " fois -> " << s << " nombres\n";
		}
	}

	delete [] tirages;
}


// exo 1.4

// fonction annexe pour generer une permutation aleatoire
// tab est le tableau et n sa taille
void   Genere(int n,int* tab)
{
	// on initialise a la permutation identite
	for (int i=0;i<n;i++) tab[i]=i+1;
	// on fait les n-1 echanges aleatoires
	for (int k=0;k<=n-2;k++) {
		// on tire un nombre l entre 1 et n-k
		int l=random()%(n-k) +1;
		// on echange (ne pas oublier que le tableau est indice de 0 a n-1
		// alors que les valeurs vont de 1 a n
		int swap=tab[l-1];
		tab[l-1]=tab[n-k-1];
		tab[n-k-1]=swap;
	}
}
void   Exo_Permutations(int n,int k)
{
	if ( n <= 0 ) {
		cout << "permutations de taille nulle\n";
		return;
	}
	if ( k <= 0 ) {
		cout << "aucun tirage\n";
		return;
	}
	// on fait le tableau pour stocker les permutations
	int*  permu=new int[n];

	// on fait k tirages et on regarde si on obtient l'identite
	// s compte le nombre de fois ou on l'a obtenue
	int s=0;
	for (int i=0;i<k;i++) {
		// on genere
		Genere(n,permu);
		// on teste
		bool  cebon=true;
		for (int j=0;j<n;j++) {
			if ( permu[j] != j+1 ) {
				// ca peut plus etre l'identite
				cebon=false;
				break;
			}
		}
		if ( cebon ) s++;
	}
	{
		float freq=s;
		freq/=k;
		cout << "frequence de l'identite: " << freq << endl;
	}

	// meme chose mais avec une permutation donnee (on en prend une au hasard)
	// test est le tableau de la permutation fixee
	{
		int   test[n];
		Genere(n,test);
		cout << "permutation test:\n";
		for (int i=0;i<n;i++) cout << test[i] << " ";
		cout << endl;
		// on y va...
		s=0;
		for (int i=0;i<k;i++) {
			// on genere
			Genere(n,permu);
			// on teste
			bool  cebon=true;
			for (int j=0;j<n;j++) {
				if ( permu[j] != test[j] ) {
					// ca peut plus etre la permutation test
					cebon=false;
					break;
				}
			}
			if ( cebon ) s++;
		}
		{
			float freq=s;
			freq/=k;
			cout << "frequence de la permuation test: " << freq << endl;
		}		
	}
	delete [] permu;
}


// Exo 2.1
// ici les entiers sont de taille fixe
void   SaisieEntier(bigEntier x)
{
	// on demande une chaine de caracteres et on recuperera tous les chiffres
	// un par un; on suppose que l'operateur ne rentre que des chiffres
	cout << "Nombre (entier) ? ";
	char chaine[TAILLE+1]; // +1 pour le 0 terminal
	cin >> chaine;
	// on initialise x a 0
	for (int i=0;i<TAILLE;i++) x[i]=0;
	// puis on lit la chaine jusqu'au 0 terminal
	// p est la position sur la chaine
	int p=0;
	while ( chaine[p] != 0 ) {
		x[p]=chaine[p]-'0';
		if ( x[p] < 0 ) x[p]=0;
		if ( x[p] > 9 ) x[p]=9;
		p++;
	}
	// fini!
}
// on met l'entier e dans le bigEntier x
void   MettreEntier(int e,bigEntier x)
{
	for (int i=0;i<TAILLE;i++) x[i]=0;
	int p=0;
	while ( e > 0 ) {
		x[p]=e%10;
		// et en avant pour le chiffre suivant
		e/=10;
		p++;
	}
}
void   Affichage(bigEntier x)
{
	cout << "entier: ";
	// on recupere d'abord le nombre de 0 en tete de l'entier
	int n=0;
	for (int i=TAILLE-1;i>=0;i--) {
		if ( x[i] != 0 ) break;
		// si on est ici c'est que x[i] est toujours 0
		n++;
	}
	for (int i=TAILLE-n-1;i>=0;i--) {
		cout << x[i];
	}
	if ( n>= TAILLE ) cout << "0";
	cout << endl;
}
void   Somme(bigEntier a,bigEntier b,bigEntier r)
{
	// c'est l'addition du primaire...
	// a et b sont les nombres ajoutes, r le resultat
	// l'operateur est suppose donner r different de a et b
	int retenue=0;
	for (int i=0;i<TAILLE;i++) {
		int   somme=a[i]+b[i]+retenue;
		r[i]=somme%10; // on prend le chiffre des unites
		retenue=somme-r[i];
		retenue/=10;
	}
}
void   Difference(bigEntier a,bigEntier b,bigEntier r)
{
	// memes remarques que pour la somme
	// on attend un resultat positif...
	int retenue=0;
	for (int i=0;i<TAILLE;i++) {
		int   difference=a[i]-b[i]+retenue;
		r[i]=difference%10; // on prend le chiffre des unites
		if ( r[i] < 0 ) r[i]+=10; 
		retenue=difference-r[i];
		retenue/=10;
	}
}
void   Produit(bigEntier a,bigEntier b,bigEntier r)
{
	// idem
	// on initialise r a 0
	for (int i=0;i<TAILLE;i++) r[i]=0;
	for (int i=0;i<TAILLE;i++) {
		int   x=b[i];
		int 	retenue=0;
		// la taille des entiers est bornee, donc on risque de faire
		// des erreurs quand ils sont trop grands
		for (int j=0;j<TAILLE-i;j++) { // pas besoin d'aller plus loin
			int   somme=x*a[j]+r[j+i]+retenue;
			r[j+i]=somme%10;
			retenue=somme/10;
		}
	}
}
void   Exo_Factorielle(int n)
{
	bigEntier fact;
	MettreEntier(1,fact);
	for (int i=2;i<=n;i++) {
		bigEntier  x;
		MettreEntier(i,x);
		bigEntier temp;
		Produit(fact,x,temp);
 		// on copie temp dans fact
		for (int j=0;j<TAILLE;j++) fact[j]=temp[j];
	}
	Affichage(fact);
}