Meilleure méthode pour calculer un puissance

Commenter

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 :)

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

S'inscrire maintenant

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.

Du même auteur (elkasimi2007)