Forum de Ti-Gen.org, le site francophone des TI

Bienvenue Invité ! Se connecter Mes sujets	Administrer
Utilisateurs actifs : Aucun membre + 1 visiteur

Avant de poster sur le forum, il y a des régles de bases à respecter pour une bonne entente et un respect de tous.
Veuillez lire la charte du forum.

:: Index » Forum TI-Nspire » Algorithmie et optimisation » fonction puissance (6 réponse(s))

./POST DE DEPART (post n°0) Marquer comme non lu.

cricrinature

Ecrit le: Mardi 30 mai 2006 à 14:24

Membre: Newbie

Messages: 1

Membre n°1361

Inscrit le 30 mai 2006

Bonjour, j'aimerai créer un programme qui calcule a^n en décomposant n en base 2.

exemple :

a^11
11=2^3 + 2^1 + 2^0
donc a^11=a^(2^0)*a^(2^1)*a^(2^3)
=a*a^2*a^8

Pouvez-vous m'aider à créer un tableau contenant la décomposition de n en base 2

exemple : 11 = 1101

puis faire la somme des termes 2^i ou i désigne la case du tableau précédent où se trouve un 1

exemple : a^11 = a*(2^0)*a^(2^1)*a^(2^3)

Merci d'avance.

./Post n°1 Marquer comme non lu.

Jfg

Ecrit le: Mardi 30 mai 2006 à 17:22

Administrateur

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 1260

Membre n°60

Inscrit le 23 février 2004

c'est plus un problème de programmation que d'algorithmie, car pour décomposer un nombre en puissance de 2, il suffit de lire les bits un par un.

Pour t'aider d'avantage, il faudrait qu'on sache si tu comptes programmer en Basic ou en C.

Kill Mario

./Post n°2 Marquer comme non lu.

geogeo

Ecrit le: Mardi 30 mai 2006 à 20:59

Fondateur

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 4258

Membre n°3

Inscrit le 29 janvier 2004

(11)10 = (1011)2 plutôt
Pour décomposer ton nombre en base 2, l'idée est la suivante:

for (unsigned int i=0; valeur; ++i) {
  if (valeur & 1)  printf("2^%d", i);
  if (i!=0)        printf("+");
  valeur >>= 1;
}

Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic

./Post n°3 Marquer comme non lu.

Xantares

Ecrit le: Mardi 27 juin 2006 à 20:56

Membre: Habitué

Messages: 63

Membre n°875

Inscrit le 09 juin 2005

ca t'interressera ptet : l'exponentiation rapide.

c basé sur ca :
n pair : x^n = (x^(n/2))^2
nimpair x^n = x * x^(n-1)
plus le cas de base de la recursivité : x^0 = 1

c vachement rapide en recursif, mais ptet t'y gagne en iteratif sur des puissances élevées,
puis en c++ ca doit etre possible d'acceder aux bits facilement avec des &, ou des >>......
je suis pas specialiste....

float puissance(float x, int n)
{
        if(n==0) then return 1;
        else if(n%2==1) then return x*puissance(x,n-1);
        else return sqr(puissance(x,n/2));
}

en fait la decomposition en base 2 de n est faite lors des appels successifs, exemple : x^5
puissance(x,5)
x*puissance(x,4)
x*puissance(x,2)^2
x*puissance(x,1)^4
x*x^4
on a bien (x^4)^1*(x^2)^0*(x^1)^1
et 5 = 101 en binaire
donc c gagné

je sais pas si la fonction carré c sqr comme en pascal donc c à vérifier dans le code.

merci les cours de sup'

-Edité le Mardi 27 juin 2006 à 21:02 par Xantares-
-Edité le Samedi 1er juillet 2006 à 09:01 par Xantares-

./Post n°4 Marquer comme non lu.

Onur

Ecrit le: Mercredi 28 juin 2006 à 01:44

Membre: Maître Ultime

Groupe: Orage Studio

Messages: 1604

Membre n°341

Inscrit le 02 juillet 2004

x^n = (x^(n/2))^2

algorithme aussi appelé "diviser pour regner"

Je ne veux pas faire quelque chose de bien, je cherche l'excellence:ETP Studio...

et autres projets à finir avant 2010

./Post n°5 Marquer comme non lu.

Xantares

Ecrit le: Samedi 1er juillet 2006 à 09:05

Membre: Habitué

Messages: 63

Membre n°875

Inscrit le 09 juin 2005

"diviser pour régner" ?? t sûr ?

moi j'appele ca l'exponentiation rapide je croyais que "diviser pour régner" ca s'appliquait comme méthode générale de programmation, genre les algorithmes en plusieurs phases : par ex le trifusion ou il faut des procedures pour diviser et une autre pour rassembler le tout.

fin bon ca doit pas etre super important.

pis l'expression est ringarde :]

./Post n°6 Marquer comme non lu.

Kevin Kofler

Ecrit le: Dimanche 2 juillet 2006 à 00:15

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4815

Membre n°40

Inscrit le 08 février 2004

Oui, c'est un concept plus général, mais ceci est bien une application de ce concept.

Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!