/* CS 203. Correction de la feuille 2 */
/* Note : pour compiler ce fichier, il faut faire appel a la librairie mathematique avec l'option -lm */
/* Credit : certains des programmes presentes ici ont ete realises par Pierre Cohort */
#include <stdio.h>
#include <math.h> /* pour les fonctions sqrt, floor, ... */
#include <stdlib.h>
/* exercice 1 */
double conversion(int somme_en_francs)
{
const double taux=6.55957;
return (double)somme_en_francs/taux;
/* commentaire : la syntaxe (double) devant le parametre somme_en_francs
signifie que celui-ci est, dans la division, converti en double.
La conversion est en fait ici automatique (un entier divise ou multiplie
par un reel est tjrs converti en reel). */
}
void table_franc_euro(int smin, int smax, int pas)
{
int i;
for (i=smin; i<=smax; i+=pas){
printf("%d francs = %f euros\n",i,conversion(i));
}
}
/* exercice 2 */
void table1010()
{
int i,j;
for (i=0;i<=10;i++){
for (j=0;j<=i;j++){
printf("%d * %d = %d\t",i,j,i*j);
}
printf("\n");
}
}
/* exercice 3 */
int fibonacci(int n)
{
int u0=0,u1=1,u2,i;
for (i=2;i<=n;i++){
u2=u0+u1;
u0=u1;
u1=u2;
}
return u2;
}
/* commentaire : si on desire calculer a differents moments
plusieurs valeurs de la suite, la fonction precedente n'est
pas efficace car elle induit le recalcul des premiers termes
de la suite pour chaque nouvelle valeur demandee. On peut
resoudre ce probleme en conservant en memoire le dernier indice
calcule et la valeur correspondante de u. */
int Fibonacci(int n)
{
int i;
static int u0=0,u1=1,u2,_n=2;
/* en presence du mot cle static, les initialisations precedentes
sont effectuees une seule fois (au premier appel de la fonction).
Les valeurs de u0,u1,u2 et i sont ensuite conservees en memoire
entre les differents appels a la fonction. */
for (i=_n;i<=n;i++){
u2=u0+u1;
u0=u1;
u1=u2;
}
_n=n+1;
/* la variable _n contient l'indice de depart des calculs au prochain
appel. Noter que les appels successifs a Fibonacci doivent
etres faits avec une suite croissante d'entiers. */
return u2;
}
/* exercice 4 */
/* on implemente d'abord la fonction f a partir de laquelle la
suite est definie.*/
long f(int n)
{
if (n%2==0){ /* n%2==0 equivaut a n pair */
return n/2;
} else {
return 3*n+1;
}
}
/* La fonction suivante calcule les termes d'une suite de syracuse
jusqu'a verifier la conjecture ou atteindre un indice maximal
n_max fixe a l'avance. Elle retourne min(n(u0),n_max) ou n(u0) est
le plus petit k pour lequel uk=1 */
long Syracuse(long u0)
{
const long n_max=1000000;
long u=u0,n=0;
while ((u!=1)&&(n<n_max)) {u=f(u);n++;}
return n;
}
/* teste la conjecture pour u0 dans {1,...,n} */
void Collatz(long n)
{
long i;
for (i=1;i<=n;i++){
printf("u0 = %d ; u%d = 1\n",i,Syracuse(i));
}
}
/* commentaire : il est interessant de visualiser la fonction Syracuse.
Pour cela, on ecrit une fonction qui stocke les couples (u0,Syracuse(u0))
dans un fichier.
Les fichiers seront vu plus tard dans le cours, on anticipe un peu */
void writeFile(long n)
{
FILE* file=NULL;
int i;
file=fopen("syracuse.dat","w"); /* cree le fichier syracuse.dat */
if (file==NULL){ return; } /* arret si probleme d'ouverture du fichier */
for (i=1;i<=n;i++){
/* ecriture dans le fichier syracuse.dat des couples (u0,Syracuse(u0))
pour uo dans {0,...,n} */
fprintf(file,"%d %d\n",i,Syracuse(i));
}
fclose(file); /* fermeture du fichier */
}
/* Verifier que le programme a bien fonctionne en examinant
le contenu de syracuse.dat avec la commande linux
more syracuse.dat, ou en l'ouvrant avec emacs (dans ce cas, attention
a ne pas modifier le fichier). Vous pouvez visualiser les resultats graphiquement en
utilisant gnuplot (lancer gnuplot puis, sous l'invite de
commandes gnuplot, tapez plot "syracuse.dat"), ou en utilisant
matlab/scilab (en scilab : x=fscanfMat("syracuse.dat") puis
fonctions graphiques appliquees a x (voir aide du logiciel)*/
/* exercice 5 */
/* on nomme g la fonction integree pour ne pas dupliquer l'identificateur f de
l'exercice 4 */
double g(double x)
{
return x*x;
}
double trapeze(double a, double b, double pas)
{
double h=a+pas,aux1=g(a),aux2=g(a+pas),I=0;
do {
I+=(aux1+aux2)*0.5*pas;
aux1=aux2;
h+=pas;
aux2=g(h);
} while (h<b);
return I;
}
/* exercice 8 */
/* Le resultat du programme est l'affichage de "x=1, y=2".
Il ne s'est donc rien passe, malgre l'appel a la fonction
echange, censee echanger deux entiers.
Explication : Lors de l'appel de la fonction echange, les parametres
a et b sont temporairement crees et initialises avec les valeurs
de x et y. Ils sont ensuite echanges : apres
l'instruction b=auxi , on a bien a=2 et b=1 mais, en fin d'execution,
a et b sont detruits. Au resultat, x et y ne sont pas modifies.
Solution : il faut passer les adresses de x et y a la fonction echange, a l'aide
de pointeurs d'entiers : */
void echange(int* a, int* b)
{
int auxi;
auxi=*a;
*a=*b; /* *a est l'entier dont l'adresse est a */
*b=auxi;
}
/* L'appel a echange est alors echange(&x,&y) (&x est l'adresse de x en memoire).
La fonction echange agit ainsi directement sur les variables x et y. Le
resultat sera "x=2, y=1" */
/* exercice 6 */
int NombreDeFaces(int n)
/* Simule le lancer de n pieces et retourne le nombre de "face" */
{
int i, faces;
faces=0;
for (i=1;i<=n;i++)
if (random()%2==1) /* random() fourni un nombre aleatoire */
faces++; /* si ce nombre est pair con considere qu'on a pile sinon qu'on a face */
return faces;
}
int ExperienceExo6(int TypeExperience)
/* Experience prend comme argument le type d'experience :
1 pour "3 faces exactement"
2 pour "3 faces au plus"
3 pour "3 faces au moins"
Elle retourne 1 si l'experience est reussie et 0 sinon */
{
switch (TypeExperience) {
case 1: return(NombreDeFaces(10)==3); break;
case 2: return(NombreDeFaces(10)<=3); break;
case 3: return(NombreDeFaces(10)>=3); break;
}
}
void exercice6()
{
int nombretotal=1e6;
int i, j, reussi;
for (i=1;i<=3;i++) {
printf("%ie experience : ",i);
reussi=0;
for (j=1;j<=nombretotal;j++)
reussi+=ExperienceExo6(i); /* On compte les experiences reussies */
printf("la probabilite est %0.0lf\%\n",100.0*reussi/nombretotal);
}
}
/* Resultas trouves en MF 100 :
1e experience : 15/128 (approx 0.12)
2e experience : 11/64 (approx 0.17)
3e experience : 121/128 (approx 0.95) */
/* exercice 7 */
int TirageBoules(int Urne)
{
int i;
int BoulesRouges; // Contiendra le nombre de boules rouges dans l'urne
int BoulesBlanches; // Contiendra le nombre de boules blanches dans l'urne
int TypeBoule; // Contient 1 pour une boule rouge et 0 pour une boule blanche
int NumeroBoule;
int Tirage, TirageReussi;
/* On tire a pile ou face pour choisir l'urne
random() fourni un nombre aleatoire
si ce nombre est pair con considere qu'on a pile sinon qu'on a face */
if (Urne==1)
{ BoulesRouges=700; BoulesBlanches=300; }
else
{ BoulesRouges=300; BoulesBlanches=700; }
Tirage=0;
for (i=1;i<=12;i++) {
/* On suppose les boules numerotees de 1 a 1000 */
NumeroBoule=random()%(BoulesRouges+BoulesBlanches)+1;
/* Si numero de la boule est entre 1 et BoulesRouges,
on dit que la boule est rouge */
TypeBoule=(NumeroBoule<=BoulesRouges);
Tirage=2*Tirage+TypeBoule;
}
//On veut RBRRBRRRBRRR
TirageReussi=2*(2*(2*(2*(2*(2*(2*(2*(2*(2*(2*1+0)+1)+1)+0)+1)+1)+1)+0)+0)+1)+1;
//printf("Tirage=%d\tTirageReussi=%d\n",Tirage,TirageReussi);
return (Tirage==TirageReussi);
}
int ExperienceExo7()
{
int Urne; // Contiendra le numero de l'urne tiree
/* On tire a pile ou face pour choisir l'urne
random() fourni un nombre aleatoire
si ce nombre est pair con considere qu'on a pile sinon qu'on a face */
if (random()%2==1) Urne=1;
else Urne=2;
return(TirageBoules(Urne));
}
void exercice7()
{
int nombretotal=1e7;
int i, j, reussi;
for (i=1;i<=2;i++) {
reussi=0;
printf("%de experience : ",i);
for (j=1;j<=nombretotal;j++)
reussi+=TirageBoules(i); /* On compte les experiences reussies */
printf("la probabilite est %0.1le\n",(double)reussi/nombretotal);
}
reussi=0;
printf("3e experience : ");
for (j=1;j<=nombretotal;j++)
reussi+=ExperienceExo7(); /* On compte les experiences reussies */
printf("La probabilite est %0.1le\n",(double)reussi/nombretotal);
}
/* Resultas trouves en MF 100 :
1e experience : 0.7^8*0.3^4 (approx 4.6e-4)
2e experience : 0.3^8*0.7^4 (approx 1.6e-5)
3e experience : (0.7^8*0.3^4+0.3^8*0.7^4)/2 (approx 2.4e-4) */
int main()
{
printf("Exercice 1 :\n");
table_franc_euro(0, 100, 5);
printf("Exercice 2 :\n");
table1010();
printf("Exercice 3 :\n");
printf("fibonacci(12) = %d\n",fibonacci(12));
printf("Fibonacci(1) = %d\n",Fibonacci(1));
printf("Fibonacci(4) = %d\n",Fibonacci(4));
printf("Fibonacci(10) = %d\n",Fibonacci(10));
printf("Fibonacci(12) = %d\n",Fibonacci(12));
printf("Exercice 4 :\n");
Collatz(1000);
/*writeFile(1000);*/
printf("Exercice 5 :\n");
{
double a=1.0,b=2.0;
printf("valeur theorique de l'integrale de g entre %f et %f = %f\n",a,b,(b*b*b-a*a*a)/3.);
printf("valeur calculee de l'integrale de g entre %f et %f = %f\n",a,b,trapeze(a,b,0.001));
}
printf("Exercice 6 :\n");
exercice6();
printf("Exercice 7 :\n");
exercice7();
printf("Exercice 8 :\n");
{
int a=1,b=2;
printf("a=%d b=%d\n",a,b);
echange(&a,&b); /* &a est l'adresse de la variable a */
printf("a=%d b=%d\n",a,b);
}
return(0);
}