[数据结构与算法]邓俊辉 数据结构 习题4-18 Fermat-Lagrange定理代码实现

习题如下：

其中核心段落在于void Lagrange(int n)函数，其中有针对a)的简化版，更容易理解，如有需要可与我联系

#include "Stack.h"

struct Po {
	int base;
	Po(int i = 1) :base(i) {}
	friend int operator+(int a, Po b);
	friend int operator*(int a, Po b);
};

int operator+(int a, Po b) 
	{return a + std::pow(b.base, 2);}

int operator*(int a, Po b) 
	{ return a * std::pow(b.base, 2); }

ostream& operator<<(ostream& out, Stack<Po>& stk)
{
	out << "{ ";
	for (int i = 0; i < stk.size(); ++i) {
		out << stk[i].base;
		i == stk.size()-1 ? out << " " : out << ", ";
	}
	out << "}" << "^2";
	return out;
}

int sum(Stack<Po>& stk) {
	int sum = 0;
	for (int i = 0; i < stk.size(); ++i) { sum = sum + stk[i]; }
	return sum;
}

void backTrack(Po& p, Stack<Po>& stk) {
	//if (stk.size() < 2)		return;//防火墙
	stk.pop();
	p.base = ++(stk.top()).base;
}

void Langrange(int n) {
	Po p(0);//默认从0^2开始
	Stack<Po> stk;
	//从（0，0，0，0）这种初始情况开始
	for (int i = 0; i < 4; ++i) { stk.push(p); }
	//stk.push(p); stk.push(p); stk.push(p); p.base = 3; stk.push(p);
	std::vector<Stack<Po>> pv;

	//只要栈元素和不等于n就继续寻找，循环中又分为<n、>n两种情况
	int _sum;
	while ( (_sum = sum(stk)) != n && (4 * stk[0]) <= n) {
		//如果栈元素和<n，就需要试探将栈顶递增或入栈新元素（栈未满时）
		if (_sum < n) {
			if (stk.size() < 4) { stk.push(p); }//如果栈未满就将p入栈
			else { ++stk.top().base; }//如果栈满，则栈顶递增
		}
		//如果栈元素和>n，那么就需要回溯了，即次栈顶递增
		else	{backTrack(p, stk);}
		//如果栈元素总和==n
		if (sum(stk) == n) {
			//未满，此时也需要回溯(backTrack)
			if (stk.size() != 4)	{backTrack(p, stk);}
			//已满，一个解加入向量，回溯，探寻下一个解
			else					{ pv.push_back(stk); backTrack(p, stk);}
		}
	}
	
	cout << "n: " << n << " ";
	for (std::vector<Stack<Po>>::iterator it = pv.begin(); it != pv.end(); ++it) 
		{ cout << *it<<"        "; }
	cout << endl;
}