/* CS 203. Correction de la feuille 3 */
/* 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 <assert.h>
#include <math.h>
/* exercice 1 */
void crible(int maxcrible)
{
int Tableau[maxcrible-1];
int n, i;
/* Le tableau des entiers. Attention : la case i reprente l'entier i+2 */
/* a la fin de la procedure Tableau[n-2]=1 si n est premier et 0 sinon */
for (i=0;i<=maxcrible-2;i++)
Tableau[i]=1;
/* Tout entier est presume premier jusqu'a ce que la preuve de sa non primalite soit
apportee au cours de la bouble suivante */
for (n=2;n<=sqrt(maxcrible);n++)
if (Tableau[n-2]==1) // Si n est premier...
for (i=2;i<=maxcrible/n;i++) // ... alors n*2, n*3, ...
Tableau[i*n-2]=0; // ... ne le sont pas !
for (n=2;n<=maxcrible;n++)
if (Tableau[n-2]==1)
printf("%d ",n);
printf("\n");
}
/* exercice 2 */
void PiecesARendre(int MontantARendre, int TypeDePiece)
/* Affiche le nombre de pieces (de type TypeDePiece) a rendre
pour le montant MontantARendre
ENTREE : MontantARendre est le montant a rendre en centimes d'euros
TypeDePiece est la valeur de la piece en centimes d'euros
SORTIE : Aucune mais le programme affiche les messages a l'ecran
*/
{
int ARendre;
ARendre=MontantARendre/TypeDePiece;
printf("Rendre %d piece(s) de %.2f euro(s)\n",ARendre,(float)TypeDePiece/100);
}
int ResteARendre(int MontantARendre, int TypeDePiece)
/* Indique ce qui reste a rendre une fois que les pieces TypeDePiece ont
ete rendues.
ENTREE : MontantARendre est le montant a rendre en centimes d'euros
TypeDePiece est la valeur de la piece en centimes d'euros
SORTIE : Montant restant a rendre
*/
{
return (MontantARendre%TypeDePiece);
}
void RenduMonnaie (int PrixArticle, int MontantPaye)
/* Affiche le nombre de pieces a rendre afin de minimiser le nombre de
pieces rendues.
ENTREE : PrixArticle est le prix de l'article achete
MontantPaye est le montant paye par l'acheteur
SORTIE : Aucune mais le programme affiche les messages a l'ecran
*/
{
int MontantARendre, Reste;
MontantARendre=MontantPaye-PrixArticle;
assert(MontantARendre>=0);
PiecesARendre(MontantARendre,200);
Reste=ResteARendre(MontantARendre,200);
PiecesARendre(Reste,100);
Reste=ResteARendre(MontantARendre,100);
PiecesARendre(Reste,50);
Reste=ResteARendre(MontantARendre,50);
PiecesARendre(Reste,20);
Reste=ResteARendre(MontantARendre,20);
PiecesARendre(Reste,10);
assert(ResteARendre(MontantARendre,10)==0);
}
void main_exercice2()
/* On verifie sur l'exemple */
{
RenduMonnaie(430,570);
}
/* exercice 3 */
/* question 3.1 */
/*
Notons Qi le quotient de la division entiere de Ni par 97.
On a N1=97Q1+R1 et N2=97Q2+R2.
D'autre part N0=10^6N1+N2 ainsi
N0=10^6(97Q1+R1)+(97Q2+R2)=97*(10^6Q1+Q2)+10^6R1+R2
Or 10309*97=999973 donc 10^6=10309*97+27, par suite
N0=97*(10^6Q1+Q2+10309)+27R1+R2
ainsi R0=N0 mod 97=97*(10^6Q1+Q2+10309)+27R1+R2 mod 97
donc R0=27R1+R2 mod 97
*/
/* question 3.2 */
int clef (long int N1, long int N2)
/*
Calcul de la clef d'un numero de securite sociale
ENTREE : N1 les 7 premiers chiffres du numero SS
N2 les 6 derniers chiffres du numero SS
SORTIE : clef du numero SS
Cette fonction utilise la formule etablie dans la question 1
*/
{
int R0, R1, R2;
R1=N1%97;
R2=N2%97;
R0=(27*N1+N2)%97;
return(97-R0);
}
/* question 3.3 */
void main_exercice3()
{
int groupe1, groupe2, groupe3, groupe4, groupe5, groupe6;
long int N1, N2;
printf("Entrez le numero de securite sociale en separant les 6 groupes par un espace.\n");
scanf("%d %d %d %d %d %d",&groupe1,&groupe2,&groupe3,&groupe4,&groupe5,&groupe6);
// N1 comprend les 7 premiers chiffres et N2 les 6 deriniers
N1=groupe4+100*groupe3+10000*groupe2+1000000*groupe1;
N2=groupe6+groupe5*1000;
// Affichage de la clef
printf("La clef associee a ce numero est %d\n",clef(N1,N2));
// Affichage homme/femme
if ((groupe1==1)||(groupe1==7))
printf("L'individu est un homme\n");
else
printf("L'individu est une femme\n");
// Affichage du lieu de naissance
if (groupe4==99)
printf("L'individu est ne a l'etranger\n");
else
printf("L'individu est ne en France\n");
}
/* exercice 4 */
/* question 4.1 */
typedef struct compl {
float re, im;
} complexe;
complexe CreerComplexe (float a, float b)
/* Creation d'un nombre complexe
ENTREE : a partie reelle et b partie imaginaire de type float
SORTIE : a+ib de type complexe
*/
{
complexe z;
z.re=a;
z.im=b;
return z;
}
float PartieReelle (complexe z)
/* Partie reelle d'un nombre complexe
ENTREE : z de type complexe
SORTIE : partie reelle de z, de type float
*/
{
return(z.re);
}
float PartieImaginaire (complexe z)
/* Partie imaginaire d'un nombre complexe
ENTREE : z de type complexe
SORTIE : partie imaginaire de z, de type float
*/
{
return(z.im);
}
complexe SommeComplexe (complexe z1, complexe z2)
/* Somme de deux nombres complexes
ENTREE : z1 et z2 de type complexe
SORTIE : z1+z2 de type complexe
*/
{
float a, b;
complexe z;
a=PartieReelle(z1)+PartieReelle(z2);
b=PartieImaginaire(z1)+PartieImaginaire(z2);
z=CreerComplexe(a,b);
return z;
}
complexe ProduitComplexe (complexe z1, complexe z2)
/* Produit de deux nombres complexes
ENTREE : z1 et z2 de type complexe
SORTIE : z1*z2 de type complexe
*/
{
float a, b;
complexe z;
a=(PartieReelle(z1))*(PartieReelle(z2))-(PartieImaginaire(z2))*(PartieImaginaire(z2));
b=(PartieReelle(z1))*(PartieImaginaire(z2))+(PartieImaginaire(z1))*(PartieReelle(z2));
z=CreerComplexe(a,b);
return z;
}
float ModuleComplexe (complexe z)
/* Module d'un nombre complexe
ENTREE : z de type complexe
SORTIE : |z| de type float
*/
{
return(sqrt((PartieReelle(z))*(PartieReelle(z))+(PartieImaginaire(z))*(PartieImaginaire(z))));
}
void AfficherComplexe (complexe z)
/* Affichage d'un nombre complexe
ENTREE : z de type complexe
EFFET : affichage du complexe sur stdout
*/
{
if (PartieImaginaire(z)>0)
printf("%.5f+%.5fi\n",PartieReelle(z),PartieImaginaire(z));
if (PartieImaginaire(z)<0)
printf("%.5f-%.5fi\n",PartieReelle(z),fabs(PartieImaginaire(z)));
if (PartieImaginaire(z)==0)
printf("%.5f\n",PartieReelle(z));
}
/* question 4.2*/
int EstDansM (complexe K)
/* Fonction indicatrice de l'ensemble de Mandelbrot
ENTREE : un complexe K
SORTIE : 1 si K est dans l'ensemble de Mandelbrot, 0 sinon.
REMARQUE : On suppose qu'une suite de complexes est bornee ssi
les modules des 250 premiers termes sont inferieurs a 4
*/
{
complexe z; // contient le zn
float module, MaxModule; // module et plus grand module
int n; // variable de boucle
z=CreerComplexe(0.0,0.0);
MaxModule=0.0;
for (n=1;n<=250;n++)
{
z=SommeComplexe(ProduitComplexe(z,z),K);
module=ModuleComplexe(z);
if (module>MaxModule) MaxModule=module;
}
return (MaxModule<=4);
}
/* question 4.3*/
void main_exercice4()
{
float x1, x2, y1, y2;
int n1, n2, j, l;
complexe z;
FILE * gnuplotfile;
printf("Entrez x1 x2 y1 et y2 separes par des espaces\n");
scanf("%f %f %f %f",&x1,&x2,&y1,&y2);
printf("Entrez n1 et n2 separes par des espaces\n");
scanf("%d %d",&n1,&n2);
/* En plus de ce qui est demande (l'affichage des points de l'ensemble
de Mandelbrot) on cree le fichier mandelbrot.gnuplot qui contient
ces points, ecrits sur deux colonnes, la premiere contient les
parties reelles et la seconde les parties imaginaires.
Pour afficher les points avec gnuplot, on tapera (dans le shell)
gnuplot puis (dans gnuplot) plot "mandelbrot.gnuplot"
*/
gnuplotfile=fopen("mandelbrot.gnuplot","w");
if (gnuplotfile==NULL)
{
printf("Erreur en creation de fichier\n");
exit(1);
}
for (l=0;l<=n2;l++)
for (j=0;j<=n1;j++)
{
z=CreerComplexe(x1+j*(x2-x1)/n1,y1+l*(y2-y1)/n2);
if (EstDansM(z)==1)
{
AfficherComplexe(z);
fprintf(gnuplotfile,"%f %f\n",PartieReelle(z),PartieImaginaire(z));
}
}
fclose(gnuplotfile);
}
int main()
{
printf("Exercice 1\n");
crible(1000);
printf("\n\n\n");
printf("Exercice 2\n");
main_exercice2();
printf("\n\n\n");
printf("Exercice 3\n");
main_exercice3();
printf("\n\n\n");
printf("Exercice 4\n");
main_exercice4();
printf("\n\n\n");
return 0;
}