/*
CS 203. Correction de la feuille 3
Pour compiler ce fichier, il faut faire appel a la librairie mathematique avec l'option -lm
Credit : certains des programmes presentes ont ete realises par Pierre Cohort
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
/* La macro suivante simplie l'ecriture de irreductibleQ dans l'exerice V */
#define min(a,b) ((a)<(b)?(a):(b))
/* Exercice I */
/* 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;
}
long Syracuse(long u0)
/* Cette fonction calcule les termes d'une suite de syracuse
jusqu'a verifier la conjecture ou atteindre un indice maximal
n_max fixe a l'avance.
ENTREE : u0 la condition initiale
SORTIE : min(n(u0),n_max) ou n(u0) est le plus petit k pour lequel uk=1
*/
{
const long n_max=1000000;
long u=u0, n=0;
while ((u!=1)&&(n<n_max)) {
u=f(u);
n++;
}
return n;
}
void Collatz (long n)
/* Test la conjecture pour u0 dans {1,...,n}
ENTREE : n
*/
{
long i;
for (i=1;i<=n;i++){
printf("u0 = %ld ; u%ld = 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)
/* Test la conjecture pour u0 dans {1,...,n}
ENTREE : n
SORTIE : les couples (u0,Syracuse(u0)) dans le fichier syracuse.dat
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)
*/
{
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 %ld\n",i,Syracuse(i));
}
fclose(file); /* fermeture du fichier */
}
int main_exercice1() {
Collatz(1000);
writeFile(1000);
return 0;
}
/* Exercice II */
double g(double x)
{
return x*x;
}
double trapeze(double a, double b, double pas)
/* Integration par la mathode des trapezes
ENTREE : les bornes de l'intervalle a et b (a<b)
pas, le pas d'integration
SORTIE : une valeur approchee de l'integrale de f entre a et b
*/
{
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;
}
int main_exercice2()
{
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));
return 0;
}
/* Exercice III */
int NombreDeFaces(int n)
/* Simule le lancer de n pieces
ENTREE : nombre de lancer n
SORTIE : 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 experience_exercice3(int TypeExperience)
/* Realise l'experience
ENTREE : le type d'experience :
1 pour "3 faces exactement"
2 pour "3 faces au plus"
3 pour "3 faces au moins"
SORTIE : Elle retourne 1 si l'experience est reussie et 0 sinon */
{
int res;
assert ((TypeExperience>=1)&&(TypeExperience<=3));
switch (TypeExperience) {
case 1: res=NombreDeFaces(10)==3; break;
case 2: res=NombreDeFaces(10)<=3; break;
case 3: res=NombreDeFaces(10)>=3; break;
}
return(res);
}
int main_exercice3()
{
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+=experience_exercice3(i); /* On compte les experiences reussies */
printf("la probabilite est %0.0lf\n",100.0*reussi/nombretotal);
}
return 0;
}
/* 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 IV */
int TirageBoules(int Urne)
/* Simule le tirage dans l'urne Urne
ENTREE : Urne, numero de l'urne
SORTIE : 1 si le tirage a reussi, 0 sinon */
{
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 experience_exercice4()
/* Realise l'experience
SORTIE : Elle retourne 1 si l'experience est reussie et 0 sinon */
{
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 main_exercice4()
{
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+=experience_exercice4(); /* 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) */
/* Exercice V */
typedef struct rationnel { int N, D; } Q;
Q creerQ (int num, int den)
/* ENTREE : le numerateur num et le denominateur den!=0
SORTIE : le nombre rationnel num/den */
{
Q resultat;
assert(den!=0);
resultat.N=num;
resultat.D=den;
return(resultat);
}
void afficherQ (Q r)
/* ENTREE : le nombre rationnel r
Affichage de r sur le standard output */
{
printf("%d/%d",r.N,r.D);
/* Le buffer n'est pas flushe pour permettre l'ecriture de plusieur */
/* nombres rationnels sur une meme ligne, si necessaire. */
}
double approximerQ (Q r)
/* ENTREE : le nombre rationnel r
SORTIE : une approximation reele de r */
{
return((double)r.N/r.D);
/* Attention a ne pas oublie le type casting */
/* pour ne pas faire une division entiere */
}
int egalQ (Q r1, Q r2)
/* ENTREE : deux nombres rationnels r1 et r2
SORTIE : 1 si r1=r2 et 0 sinon */
{
return(r1.N*r2.D==r1.D*r2.N);
/* Attention a bien faire les produits croises et ne pas simplement */
/* comparer numerateurs et denomniateurs (2/3=4/6) */
}
Q produitQ (Q r1, Q r2)
/* ENTREE : deux nombres rationnels r1 et r2
SORTIE : r1*r2 */
{
Q resultat;
resultat.N=r1.N*r2.N;
resultat.D=r1.D*r2.D;
return(resultat);
}
Q divisionQ (Q r1, Q r2)
/* ENTREE : deux nombres rationnels r1 et r2!=0
SORTIE : r1/r2 */
{
Q resultat;
assert(r2.N!=0);
resultat.N=r1.N*r2.D;
resultat.D=r1.D*r2.N;
return(resultat);
}
Q sommeQ (Q r1, Q r2)
/* ENTREE : deux nombres rationnels r1 et r2
SORTIE : r1+r2 */
{
Q resultat;
resultat.D=r1.D*r2.D; /* on met au meme denominateur */
resultat.N=r2.N*r1.D+r1.N*r2.D;
return(resultat);
}
Q irreductibleQ (Q r)
/* ENTREE : un nombre rationnel r
SORTIE : r sous forme irreductible */
{
int n;
/* On commence par regarder si 2 est un facteur commun
au numerateur et au denominateur */
n=2;
while (n<=min(r.N,r.D)) {
if ((r.N%n==0)&&(r.D%n==0))
{
/* si c'est le cas on simplifie */
r.N/=n;
r.D/=n;
}
/* sinon on passe a l'entier suivant */
/* (le nombre premier suivant serait suffisant) */
else n++;
}
return r;
}
int main_exercice5()
{
Q r, r1, r2, r3, r4;
r1=creerQ(1,2);
r2=creerQ(1,4);
r3=creerQ(2,9);
r4=creerQ(1,7);
r=divisionQ(sommeQ(r1,r2),sommeQ(r3,r4));
r=irreductibleQ(r);
printf("r=");
afficherQ(r);
printf(" et sa valeur approchee est %lf\n",approximerQ(r));
return 0;
}
/* main */
int main()
{
int n;
printf("Feuille d'exercices 3\n");
printf("Choix de l'exercice : ");
scanf("%d",&n);
switch (n) {
case 1: main_exercice1(); break;
case 2: main_exercice2(); break;
case 3: main_exercice3(); break;
case 4: main_exercice4(); break;
case 5: main_exercice5(); break;
}
return 0;
}