/*
ESI CS 2506. 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 et/ou Boris Velikson
*/
#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.0f\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 - Programmation avec des structures */
struct perm {
int p1,p2,p3,p4;
};
typedef struct perm perm;
int max4(int a,int b, int c, int d) {
int m= 1;
if (a>m) m=a;
if (b>m) m=b;
if (c>m) m=c;
if (d>m) m=d;
return m;
}
int min4(int a,int b, int c, int d) {
int m= 4;
if (a<m) m=a;
if (b<m) m=b;
if (c<m) m=c;
if (d<m) m=d;
return m;
}
perm creeP() {
perm p;
int a,b,c,d;
do {
printf(" tapez les images des 4 elements separes par des espaces ");
scanf("%d %d %d %d",&a, &b, &c, &d);
if ((max4(a,b,c,d)>4) ||(min4(a,b,c,d)<1) ){
printf("au moins un des nombres est hors limites [1..4]\n");
continue;
}
else if (a*b*c*d!=24) {
printf("ce n'est pas bijectif!\n");
continue;
}
} while ( (max4(a,b,c,d)>4) ||(min4(a,b,c,d)<1)||(a*b*c*d!=24));
p.p1=a; p.p2=b; p.p3=c;p.p4=d;
return(p);
}
void afficheP(perm p) {
printf("1\t2\t3\t4\n");
printf("%d\t%d\t%d\t%d\n",p.p1,p.p2,p.p3,p.p4);
}
perm compP(perm q,perm p) {
perm r;
if (p.p1==1) r.p1=q.p1;
else if (p.p1==2) r.p1=q.p2;
else if (p.p1==3) r.p1=q.p3;
else r.p1=q.p4;
if (p.p2==1) r.p2=q.p1;
else if (p.p2==2) r.p2=q.p2;
else if (p.p2==3) r.p2=q.p3;
else r.p2=q.p4;
if (p.p3==1) r.p3=q.p1;
else if (p.p3==2) r.p3=q.p2;
else if (p.p3==3) r.p3=q.p3;
else r.p3=q.p4;
if (p.p4==1) r.p4=q.p1;
else if (p.p4==2) r.p4=q.p2;
else if (p.p4==3) r.p4=q.p3;
else r.p4=q.p4;
return (r);
}
int main_exercice4s() {
perm pp, qq;
pp=creeP();
qq=creeP();
afficheP(compP(qq,pp));
return 0;
}
/* Exercice IV - Programmation avec des tableaux */
typedef int* permutation;
/* Les elements consideres sont 1, 2, 3, 4 (classes d'equivalence)
L'indice i correspond a l'element i+1 */
permutation CreerPermutation()
/* Lit une permutation et la retourne */
{
int i, j, x, entree_correcte;
permutation P=(permutation)malloc(4*sizeof(int));
for (i=0;i<4;i++) {
do{
/* Lecture de l'image de i */
printf("Entrer l'image de %d \n",i+1);
scanf("%d",&x);
/* On verifie que cette entree ne conduit pas a un defaut d'injectivite */
entree_correcte=1;
if (i>0)
for (j=0;j<i;j++)
if (P[j]==x-1) entree_correcte=0;
if ((x<0)||(x>4)) entree_correcte=0;
} while (!entree_correcte);
P[i]=x-1;
}
return P;
}
void AfficherPermutation(permutation P)
/* Affiche la permutation donnee en parametre */
{
int i;
for (i=0;i<4;i++)
printf("%d -> %d\n",i+1,P[i]+1);
}
permutation CompositionPermutation(permutation P1, permutation P2)
/* Composition des permutations P1 et P2, retourne P1 o P2 */
{
int i;
permutation P=(permutation)malloc(4*sizeof(int));
for (i=0;i<4;i++)
P[i]=P1[P2[i]];
return(P);
}
int main_exercice4t()
{
permutation P1, P2, P3;
printf("Entrer une permutation P1 :\n");
P1=CreerPermutation();
printf("Entrer une permutation P2 :\n");
P2=CreerPermutation();
printf("P1 o P2 =\n");
P3=CompositionPermutation(P1,P2);
AfficherPermutation(P3);
return 0;
}
/* 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 %f\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_exercice4s(); main_exercice4t(); break;
case 5: main_exercice5(); break;
}
return 0;
}