/*
ESI CS 2506. Correction de la feuille 5
Les fichiers departements.txt, communes.txt et dico.txt doivent etre dans le repertoire courant, ces fichiers peuvent etre telechargest sur le site web du ESI CS 2506
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 <string.h>
#include <strings.h>
#include <ctype.h>
#include <math.h>
/* exercice I */
#define MAX 10000
int is_coprime(int n1, int n2)
/* Predicat de primalite relative de deux entiers n1 et n2
ENTREE : n1 et n2
SORTIE : 1 si n1 et n2 ont un facteur autre que 1 en commun, 0 sinon
*/
{
int i; /* compteur de boucle pour les diviseurs */
int PremiersEntreEux = 1; /* passera a 0 si un contre exemple est trouve */
int min = (n1<n2)?n1:n2; /* min de n1 et n2 */
for (i=2;i<=min;i++)
/* Si n1 et n2 ont un facteur commun, ils ne sont pas premiers entre eux */
if ((n1%i==0)&&(n2%i==0)) PremiersEntreEux = 0;
return PremiersEntreEux;
}
int phi(int n)
/* Fonction Indicatrice d'Euler
ENTREE : n
SORTIE : Phi(n)
*/
{
int i;
int resultat=0;
static int tab_initialise;
static int* tab;
if (!tab_initialise) {
tab = (int*) malloc(MAX*sizeof(int));
tab[0]=1;
for (i=1;i<MAX;i++) tab[i]=0;
tab_initialise=1;
}
if (tab[n-1]>0) return tab[n-1];
else {
for (i=1;i<=n;i++)
if (is_coprime(i,n))
resultat++;
tab[n-1] = resultat;
return resultat;
}
}
int verifierconjecture (int n)
/* Verification de la conjecture de Carmichael pour n
ENTREE : n
SORTIE : 1 s'il existe un m tel que phi(n)=phi(m), 0 sinon
REMARQUE : on arrete de tester pour m>=nmax (1000000)
*/
{
int m=1;
int mmax = 1000000;
while (((phi(n)!=phi(m))||(n==m)) && (m<mmax))
m++;
printf("phi(%d)\t=\tphi(%d)\n",n,m);
return(phi(n)==phi(m));
}
int main_exercice1() {
int conjectureok = 1;
int n;
for (n=1;n<=MAX;n++)
/* Verification de la conjecture pour les 10000 premiers entiers non nuls */
conjectureok = conjectureok && verifierconjecture(n);
if (conjectureok) printf("Conjecture verifiee entre 1 et 10000\n");
else printf("Conjecture fausse\n");
return 0;
}
/* exercice II */
int main_exercice2() {
FILE *premiers;
int n, i, maxcrible=10000, nombrenombrespremiers=0;
int* Tableau=(int*)malloc((maxcrible-2)*sizeof(int));
/* 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 */
/* En C99 on aurait pu ecrire int Tableau[maxcrible-2]; */
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 ! */
/* Ecriture des nombres premiers dans un fichier */
premiers=fopen("premiers.txt","w");
if (premiers==NULL)
{
printf("Erreur en creation de fichier\n");
exit(1);
}
for (n=2;n<=maxcrible;n++)
if (Tableau[n-2]==1) {
nombrenombrespremiers++;
fprintf(premiers,"%d\n",n);
}
fclose(premiers);
printf("%d nombres premiers enregistres dans premiers.txt\n",nombrenombrespremiers);
return(0);
}
/* exercice III */
/* On reprend les fonctions de la feuille d'exercices precedente */
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;
/*
R0 est le reste de la division du numero SS par 97
Pour que la somme du numero SS et de la clef soit divisible par 97
il suffit que la clef soit 97-R0. Si R0=97 alors on pose R0=0
pour que la clef soit 97.
*/
if (R0==97) R0=0;
return(97-R0);
}
/* On ajoute ces deux fonctions */
void AfficherDepartement(int n)
/* Arguments : le departement n */
/* Affiche le nom de la ville */
{
FILE* dept=NULL;
int trouve=0;
int numero;
char nom[40], resultat[40];
dept=fopen("departements.txt","r");
if (dept==NULL){
/* arret si probleme d'ouverture du fichier */
printf("Erreur en ouverture de fichier\n");
exit(1);
}
while (!feof(dept)) {
fscanf(dept,"%d,%s\n",&numero,nom);
if (numero==n) {
trouve=1;
strcpy(resultat,nom);
}
}
fclose(dept); /* fermeture du fichier */
if (trouve==1)
printf("Departement de naissance :\t%s\n",resultat);
else printf("Departement de naissance inconnu\n");
}
void AfficherVille(int d, int v)
/* Arguments : le departement d et la ville v */
/* Affiche le nom de la ville */
{
FILE* villes=NULL;
int trouve=0;
int numerodept, numeroville;
char nom[80], resultat[80];
villes=fopen("communes.txt","r");
if (villes==NULL){
/* arret si probleme d'ouverture du fichier */
printf("Erreur en ouverture de fichier\n");
exit(1);
}
while (!feof(villes)) {
fscanf(villes,"%d,%d,%s\n",&numerodept,&numeroville,nom);
if ((numerodept==d)&&(numeroville==v)) {
trouve=1;
strcpy(resultat,nom);
}
}
fclose(villes); /* fermeture du fichier */
if (trouve==1)
printf("Ville de naissance :\t\t%s\n",resultat);
else printf("Ville de naissance inconnue\n");
}
int 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("Clef : \t\t\t\t%d\n",clef(N1,N2));
/* Affichage homme/femme */
if ((groupe1==1)||(groupe1==7))
printf("Sexe : \t\t\t\tHomme\n");
else
printf("Sexe : \t\t\t\tFemme\n");
/* Affichage du lieu de naissance */
if (groupe4==99)
printf("Ne a l'etranger\n");
else {
AfficherVille(groupe4,groupe5);
AfficherDepartement(groupe4);
}
return 0;
}
/* exercice V */
/* question 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 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 3 */
int 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);
gnuplotfile=fopen("mandelbrot.plt","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);
return(0);
}
/* Exercice V */
int main_exercice5()
{
FILE * dicofile;
char motentre[26], motdico[26]; /* anticonstitutionnellement a 25 lettres */
int longmotentre, longmotdico, i;
int positivematch; /* nombre de mots trouves */
printf("Entrez un mot incomplet : ");
scanf("%s",motentre);
longmotentre=strlen(motentre);
dicofile=fopen("dico.txt","r");
if (dicofile==NULL)
{
printf("Erreur en ouverture de fichier\n");
exit(1);
}
printf("\n");
positivematch=0;
while (!feof(dicofile)) {
fscanf(dicofile,"%s\n",motdico);
longmotdico=strlen(motdico);
if (longmotentre==longmotdico) {
/* Condition necessaire : le mot entre et le mot du dictionnaire ont la meme longueur */
i=0;
/* On parcourt le mot jusqu'a ce qu'une lettre differe */
while ((i<longmotentre)&&
((motentre[i]=='?')||(toupper(motdico[i])==toupper(motentre[i]))))
i++;
/* Si aucune lettre ne differe, on a trouve un mot */
if (i==longmotentre) {
printf("%s\n",motdico);
positivematch++;
}
}
}
if (positivematch==0)
printf("Aucun resultat n'a ete trouve\n");
fclose(dicofile);
return (0);
}
/* main */
int main()
{
int n;
printf("Feuille d'exercices 5\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;
}