/*--------------------------*/
/* feuille 12 td correction */
/* ---- Révisions ----------*/
/*------ LG déc. 2004 ------*/

#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 1000
#define VRAI 1
#define FAUX 0;
#define NMAX 20

/*fonction hasard*/
int hasard(int inf, int sup)
{
  int rando = rand();
  return (inf + (rando % (sup - inf +1)));
}

/*exo1 triangle de Pascal on suppose que n,p sont inférieurs stricts à NMAX*/
/* on va remplir comme ca : (pour p=3)*/
/* 1 */
/* 1 1 */
/* 1 2 1 */
/* 1 3 3 1  */

void exo1(void)
{
  int i,j,k;
  int p;
  int t[NMAX][NMAX]; /*pour stocker les nombres*/

  printf("donnez p\n");
  scanf("%d",&p);
  
  /*initialisation à 0*/
  for (i=0;i<NMAX;i++)
    {
      for (j=0;j<NMAX;j++)
	{
	  t[i][j] = 0;
	}
    }
  /*on va remplir ligne par ligne jusqu'à la ligne p 
    -- la ligne i contiendra les C(k,i) pour k<=i*/
  /*on imprime en même temps*/

  t[1][1] = 1;
  printf("%d\n" , t[1][1]);
  
  for (i=2;i<=p;i++) /*remplissage ligne i*/
    {
      t[i][1]= 1;
      printf("%d  ",t[i][1]);      
      for (j=2;j<=i;j++) /*on met i nombres en tout*/
	{
	  t[i][j] = t[i-1][j]  + t[i-1][j-1]; /*en ayant bien vérifié les indices !*/
	  printf("%d  ",t[i][j]);
	}
      printf("\n");
    }
}
/*pour la version 1d, remarquer que l'on n'a besoin de */
/* se rappeler que la ligne précédente*/

/*exo2 fonction auxiliaire*/
/*cherche un élément dans le tableau, en s'arrêtant au pire à l'indice 
  donné en paramètre*/
int chercher_element_jusque(int el, int t[100], int ind)
{
  int i;
  for (i=0;i<=ind;i++)
    {
      if (t[i] == el) return VRAI;
    }
  return FAUX;
}

/*exo2*/
void exo2(void)
{
  int i;
  int courant = 0;
  int tab[100];
  int x;
  int continuer = VRAI;
  int res;

  /*initialisation, c'est plus sûr*/
  for (i=0;i<100;i++)
    {
      tab[i]=0;
    }
  
  /*on lit un nb, on cherche si il a déjà été lu, si oui on arrete */
  /* sinon on ajoute à la case courante du tableau*/
  while (continuer)
    {
      scanf("%d",&x);
      /*on attend un x valable*/
      while ((x<0) || (x>99))
      {
	printf("Je veux x entre 0 et 99\n");
	scanf("%d",&x);	
      }
      res = chercher_element_jusque(x,tab,courant-1);
      if (!res)
	{
	  tab[courant] = x;
	  courant++;
	}
      else
	{
	  continuer = FAUX;
	}
    }
  for (i=0;i<courant;i++)
    {
      printf("%d ",tab[i]);
    }  
  printf("\n");
}

/*exo 3*/
/*imprimer une chaine*/
void imprime_chaine(char u[MAX])
{
  int i=0;
  while ((i<MAX) && (u[i]!='\0'))
  {
    putchar(u[i]);
    i++;
  }
  putchar('\n');
}

/* on suppose que tout se passe bien avec les indices*/
/*pour les besoins de la fonction suivante, on passe l'indice de fin*/
int copie_a_l_indice(char u[MAX], char t[MAX], int i)
{
  int j=i;
  
  while ((j<MAX) && (u[j-i] !='\0'))
    {
      t[j] = u[j-i];
      j++;
    }
  /*on copie ensuite le caractère de fin de chaine*/
  t[j] = '\0';
  return (j);
}

/*et concaténer devient un jeu d'enfant...*/
void concatener_chaines(char u[MAX], char v[MAX], char t[MAX] )
{
  int d;
  d = copie_a_l_indice(u,t,0);
  d = copie_a_l_indice(v,t,d);
}

/*exercice 4, une partie (ie 50 tirages)*/
/*on renvoie le nombre de piles*/
int une_partie(void)
{
  int i;
  int hop;
  int cpt=0;

  for (i=1;i<=50;i++)
    {
      hop = hasard(0,1); /*1 c'est pile*/
      if (hop==1)
	{
	  cpt++;
	}
    }
  return cpt;
}

/*exercice 4, 10000 parties et histogramme*/
/*normalement, on fait tout ca avec des constantes pour 10000 et 50*/
void exo4(void)
{
  int i;
  int k;
  int j;
  int resultats[51]; /*la case i contiendra le nb de parties avec i piles*/
  int partie;

  /*initialisation du tableau des parties*/
  for (k=0;k<50;k++)
    {
      resultats[k] = 0;
    }

  /*remplissage du tableau des parties*/
  for (i=1;i<=10000;i++)
    {
      partie = une_partie(); /*nombre entre 0 et 50*/
      resultats[partie] = resultats[partie] + 1;
    }

  /*impression des résultats*/
    for (k=0;k<50;k++)
    {
      printf("Ligne %d : ",k);
      /*taille proportionnelle à resultat[k]*/
      for (j=1;j<=resultats[k]/12;j++)
	{
	  printf("*");
	}
      printf("\n");
    }
}

/*le max est assez grand*/
/*renvoie le nb d'éléments rentrés par l'utilisateur*/
int demande_et_stocke_ligne(int t[MAX])
{
  int i=0;
  int x; /*stocke l'entier de l'utilisateur*/

  printf("Rentrez des nombres >=0, un nb négatif termine l'entrée\n");
  scanf("%d",&x);
  /*on arrête quand l'utilisateur rentre un négatif*/
  while(x >=0 && i<MAX)
    {
      t[i] = x;
      scanf("%d",&x);
      i++;
    }
  if (i==MAX) 
    {return MAX-1;} 
  else 
    {return i;}
}

/*On suppose ici que le nb d'entiers de la première ligne est connu*/
/*t est la première ligne*/
void calcule_et_affiche_2d(int nb_entiers, int t[MAX])
{
  /*tableau 2d où seront stockés les lignes*/
  int lignes[nb_entiers][nb_entiers]; 
  int i,j,k;

  /*on calcule*/
  /*recopie de la première ligne*/
  for (j=0;j<nb_entiers;j++)
    {
      lignes[0][j] = t[j];
    }
  /*calcul des autres lignes*/
  /* pour la ligne i, il y a nb_entiers -i entiers à calculer*/
  for (i=1;i<nb_entiers;i++)
    {
      for (j=0;j<nb_entiers - i;j++)
	{
	  lignes[i][j] = lignes[i-1][j] + lignes[i-1][j+1];
	}
    }
  
  /*impression du tableau*/
  for (i=0;i<nb_entiers;i++)
    {
      for (k=1;k<3*i;k++) /* espaces au début */
	{
	  printf(" ");
	}
      
      for (j=0;j<nb_entiers -i ;j++)
	{ 
	  printf("%d",lignes[i][j]);
	  printf("     ");
	}
      printf("\n");
    }
}

/*fonction auxiliaire de la version 1d*/
/*impression de la ligne avec espaces au debut*/
void imprime_ligne_avec_espaces(int nb_espaces, int t[MAX], int jusque)
{
  int k;
  for (k=0; k<nb_espaces;k++)
    {
      printf(" ");
    }
  for (k=0; k<=jusque;k++)
  {
      printf("%d   ",t[k]);
    }
  printf("\n");

}

/*version 1d*/
/*on retourne l'unique entier de la dernière ligne*/
int calcule_et_affiche_1d(int nb_entiers, int t[MAX])
{
  int i,j;
  int ligne[MAX]; /*ligne courante*/


  /*copie de t dans ligne*/
  for (j=0;j<nb_entiers;j++)
    {
      ligne[j] = t[j];
    }

  /*calculs, affichage*/

  imprime_ligne_avec_espaces(0,ligne,nb_entiers-1);  
  // return 0;
  for (i=1;i<nb_entiers;i++) /* calcul de la ligne i, et affichage*/
    {
      for (j=0;j<nb_entiers -i;j++)
	{
	  ligne[j] = ligne[j] + ligne[j+1];
	}
      imprime_ligne_avec_espaces(3*i,ligne, nb_entiers-i-1);
    }
  return ligne[0];
}

/*calcul des coefficients multiplicatifs*/
/*on génère les lignes de taille n avec n-1 zéros et un 1*/
/*sur chacune de ces lignes  on appelle calcule_et_affiche_1d */
/*on récupère le coeff et on stocke dans un tableau coeffs passé en param.*/
void genere_lignes_et_calcule_coeffs(int n, int coeffs[MAX])
{
  int i,k;
  int ligne[MAX];
  for (i=n;i<MAX;i++)
    {
      ligne[i] = -1; // pour plus de sécurité.
    }

  /*1ere ligne*/
  for (i=1;i<n;i++)
    {
      ligne[i] = 0;
    }
  ligne[0] = 1;
  coeffs[0] = calcule_et_affiche_1d(n,ligne);

  /*autres lignes : indice de ligne = k*/
  for (k=1;k<n;k++)
    {
      ligne[k] = 1;
      ligne[k-1] = 0;
      coeffs[k] = calcule_et_affiche_1d(n, ligne);
    }
}

/*comparaison des 2 stratégies*/
int compare(int t[MAX], int n)
{
  int res1;int res2=0;
  int coeffs[MAX];
  int i;

  res1 = calcule_et_affiche_1d(n,t);

  genere_lignes_et_calcule_coeffs(n,coeffs);

  for (i=0;i<n;i++)
    {
      res2 = coeffs[i]*t[i] + res2;
    }

  if (res2 == res1)
    {
      return VRAI;
    }
  else
    {
      return FAUX;
    }
}

/*exercice 5*/
void exo5(void)
{
  int nb;
  int res1;
  int t[MAX];
  int resu;

  nb = demande_et_stocke_ligne(t);

  /*calcule_et_affiche_2d(nb,t);*/
  res1 = calcule_et_affiche_1d(nb,t);
  printf("Résultat de l'exo :  %d\n",res1);

  resu = compare(t,nb);
  printf("%d\n", resu);

}

/*PROGRAMME PRINCIPAL*/
int main(void)
{
  char v[MAX];

  /*exo1*/
   exo1();
  
  /*exo2*/
  exo2();

  /*exo3*/
  concatener_chaines("hop","la",v);
  imprime_chaine(v); /*imprime hopla*/

  /*exo4*/
  srand(time(NULL));
  exo4();

  /*exo5*/
  exo5();
  /*on s'apercoit que les coeffs sont les coefficients binomiaux*/
}