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

Du même auteur (elkasimi2007)