Accueil     Soft. MacOSX     Soft. MacOS/PC     PHP     ROMS GBA     TP d'info     TI-92     DBZ-GT     Martingales     Galeries     Liens     @  

TP 2 Ex1-2

Exercice1:
#include <stdio.h>

/* Declaration des protoss, euh non, des prototypes ;-) */
int fibo(int n);
void n_premier(int n);
void somme(int n,int *s);

void main(void){
/* Debut du main */
int a,s;

printf("Ex1: Fibonacci\n\n");
do{
printf("Quel ordre ?\n");
scanf("%d",&a);
} while(a<0);

n_premier(a);
s=0;
somme(a,&s);
printf("\nSomme= %d\n",s);

/* ©2002 All Rights Reserved to www.Software-DS.com 02/02/02 */
} /* Fin du main */


int fibo(int n){
/* On utilise la recurrence ;-) */
if ((n==0) || (n==1))
return 1;
else
return (fibo(n-1)+fibo(n-2));
}
/* Fin de fibo */


void n_premier(int n){
/* On peut aussi le faire de manière itérative ! */
if (n>0) {
n_premier(n-1);
printf("f(%d)= %d\n",n,fibo(n));
}
}
/* Fin de n_premier */


void somme(int n,int *s){
if (n>0) {
(*s)+=fibo(n);
somme(n-1,s);
}
}
/* Fin de somme */


Affichage:
Ex1: Fibonacci

Quel ordre ?
7
f(1)= 1
f(2)= 2
f(3)= 3
f(4)= 5
f(5)= 8
f(6)= 13
f(7)= 21
Somme= 53



Exercice2: (L'exponentiation indienne)
#include <stdio.h>

void * expo(void* x,int n,void* (*ad)(void*,void*));
void * multip_int(void* p,void* q);

void main(void){
/* Exponentiation Indienne générique */
int n,x;
void * res;

printf("\n Exponentiation indienne (générique)\n\n\n");
printf("Calcul de x^n:\n\n");

printf("x= ");
scanf("%d",&x);

printf("n= ");
scanf("%d",&n);

res=expo((void*)x,n,multip_int);

printf("\n%d^%d= %d \n",x,n,(int *)res);

printf("\n\nhttp://www.Software-DS.com\n");

/* ©2002 All Rights Reserved to www.Software-DS.com 02/02/02 */
}
/* Fin du main */


void * expo(void* x,int n,void*(*ad)(void*,void*)){
if (n==0)
return (void*)1;
else if ((n%2)==0)
return expo(ad(x,x),n/2,ad);
else
return ad(x,expo(x,n-1,ad));
}
/* Fin de expo */


void * multip_int(void* p,void* q){
return (void*)(((int)p)*((int)q));
}
/* Fin de multip_int */


Commentaire:
L'exponentiation indienne

On pose f(x,n)=x^n tel que:

_ f(x,2*p)=f(x^2,p) pour p>0

_ f(x,2*p+1)=x.f(x,2*p)

_ f(x,0)=1 (pour x=0 , par continuité)


Si l'on fait une étude de la complexité de l'exponnentiation indienne
on s'apercoit qu'il est plus rentable de calculer x^n par l'exponentiation
indienne que par sa formulation naturelle:
x^n = x * x^(n-1)

Cette version est differente de celle demande dans l'exercice2 du TP2.
Ma version ci-dessus est une version générique et je pense que peu de personne seront capable de la comprendre, mais bon, c'était pour m'amuser ;-)

Ci dessous la version qui correspond a ce que demande l'exercice2:

#include <stdio.h>

float expo(float x,int n);

void main(void){
int n;
float x;

printf("\nExponentiation indienne\n\n");
printf("Calcul de x^n:\n\n");
printf("x= ");
scanf("%f",&x);
do{
printf("n= ");
scanf("%d",&n);
}while(n<0);

printf("\n%f^%d= %f \n",x,n,expo(x,n));

printf("\nhttp://www.Software-DS.com\n");

/* ©2002 All Rights Reserved to www.Software-DS.com 02/02/02 */
}


float expo(float x,int n){
if (n==0)
return 1;
else if ((n%2)==0)
eturn expo(x*x,n/2);
/* <=> expo(x,n/2)*expo(x,n/2); */
else
return x*expo(x,n-1);
}
/* Fin de expo */





Haut de la page - Page précédente - Page générée en 0.00081 sec.
Recherche personnalisée
 

1786418 visiteurs.   ©2001-2019 All Rights Reserved to Software-DS.com
Made with a mac  
Confidentialité