|
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
*/
|
