Meilleure méthode pour calculer un puissance
Soyez le premier à donner votre avis sur cette source.
Snippet vu 11 416 fois - Téléchargée 19 fois
Contenu du snippet
la méthode la plus naive pour calculer par ex:
x^15 = x*...*x(14 operations)
----------
mieux:
x * x = x2
x2 * x2 = x4
x4 * x4 = x8
x4 * x8 = x12
x12 * x2 = x14
x14 * x = x15(6 operations)
----------
n × n = n2
n2 × n = n3
n3 × n3 = n6
n6 × n6 = n12
n12 × n3 = n15
(5 operations)
ce programme donne les enchainements possible pour la plus rapide
méthode de calculer la puissance :)
x^15 = x*...*x(14 operations)
----------
mieux:
x * x = x2
x2 * x2 = x4
x4 * x4 = x8
x4 * x8 = x12
x12 * x2 = x14
x14 * x = x15(6 operations)
----------
n × n = n2
n2 × n = n3
n3 × n3 = n6
n6 × n6 = n12
n12 × n3 = n15
(5 operations)
ce programme donne les enchainements possible pour la plus rapide
méthode de calculer la puissance :)
Source / Exemple :
#include<iostream>
#include<set>
#include<queue>
#include<vector>
#define MAX 200
using namespace std;
int operations[MAX + 1] = {0};
// A tree struct
struct Tree
{
int Key, Level;
Tree * Parent;
vector<Tree* > children;
Tree(int Key, Tree* Parent)
{
this->Key = Key;
this->Parent = Parent;
if(Parent != NULL)
this->Level = Parent->Level + 1;
else
this->Level = 0;
}
};
// testing if all nodes are all computed
bool AllComputed()
{
for(int k = 1;k <= MAX;k++)
if(!operations[k])
return false;
return true;
}
// building tree with a given node and a range limit
void stacking(int n,Tree * T)
{
queue<Tree*> Q;
// using algorithm to parse a tree by levels
Q.push(T);
while (!Q.empty() && !AllComputed())
{
Tree * X = Q.front();
Q.pop();
Tree * Iterator = X;
int Value = X->Key;
//process node X
while(Iterator != NULL)
{
int TmpValue = Iterator->Key + Value;
if((!operations[TmpValue]|| operations[TmpValue]
== X->Level + 1)&& TmpValue <= n)
{
operations[TmpValue] = X->Level + 1;
(X->children).push_back(new Tree(TmpValue,X));
}
Iterator = Iterator->Parent;
}
int L = (int)(X->children).size();
for (int i = 0;i < L;++i)
{
Q.push((X->children)[i]);
}
}
}
void search(int k,Tree * T)
{
if(T->Key == k)
{
Tree * Iter = T;
set<int> S;
while (T != NULL)
{
S.insert(T->Key);
T = T->Parent;
}
for(set<int>::iterator iter = S.begin();;)
{
cout << *iter;
++iter;
if(iter != S.end())
cout << "->";
else
{
cout << endl;
break;
}
}
}
else
{
vector<Tree *> v = T->children;
int L = (int)v.size();
for(int i = 0;i < L;++i)
search(k,v[i]);
}
}
int main()
{
Tree * T = new Tree(1,NULL);
stacking(MAX,T);
int key;
cout << "if you want to know how to obtain minimum number of operations :" << endl;
cout << "enter a positive number or (0) to quit" << endl;
cin >> key;
while(key)
{
cout << operations[key] << endl;
search(key,T);
cin >> key;
}
return 0;
}
A voir également
- Meilleure méthode pour calculer un puissance
- Récursivité : fonction de calcul de puissance et factorielle - Conseils pratiques - PHP
- Calcul de puissance - Codes sources - C / C++ / C++.NET (.Net)
- Calculateur de puissance - Codes sources - C / C++ / C++.NET (Maths & Algorithmes)
- C / C++ / C++.NET : Méthode simplexe, calculs matriciels, systeme d'equation linéaire - Guide
- Calcul de puissance - Codes sources - C / C++ / C++.NET (Maths & Algorithmes)
on peut chronométrer les threads ?
- Messages postés
-
6535
- Date d'inscription
- lundi 16 décembre 2002
- Statut
- Modérateur
- Dernière intervention
- 22 août 2010
7- Méthode naive
- Méthode un peu meilleure
- Recherche de la meilleure méthode et application de cette méthode
Tu as une idée?
généralement ma méthode est utilisé pour un operateur
* qlq par exemple:
object X;
étant donné operateur * assez compliqué, on s'interressera
plutot à minimiser le nombre d'appel à l'operateur que minimiser le nombre de cases mémoire alouées.
c'est vrai pour le cas d'un operateur simple * pour les entiers ça parait inutile.
excuse moi,car j'ai pas eu le temps de déchiffrer les
<< ,le sizeof et les ! pour comprendre le but de ton code :)
- Messages postés
-
280
- Date d'inscription
- dimanche 7 septembre 2003
- Statut
- Membre
- Dernière intervention
- 8 juillet 2014
4ce que j'ai mis comme code c'est le code utilisé habituellement pour calculer une puissance entière
pour x^15 il fait
x2 = x*x
r = x*x2
x4 = x2*x2
r = r * x4
x8 = x4*x4
r = r * x8
--> 6 opérations, mais il n'utilise que 2 temporaires et là il y a une différence je pense, donc pourquoi ta façon est-elle meilleure (c'est ça que je n'ai pas étudié comme problème mais je suppose que toi oui) ?
d'abord on fait une recherche en profondeur pour trouver
toutes les operations minimum
ensuite on cherche à trouver la suite des multiplication
possible on fait une recherche en largeur car le nombre de
multiplication augmente de niveau en niveau.
Pour ACX01B je n'ai pas bien saisi ce que tu veut dire : tu veux dire que je dois utiliser des fonctions au lieu de blocs d'instructions ou que j'utilise des instructions complexe pour rien faire??
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.