#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;
}