原始问题描述:
对于给定的正整数n,计算n有多少种不同的分解式。
例如,当n=12时,有8种不同的分解式:
12=12,
12=6×2,
12=4×3,
12=3×4,
12=3×2×2,
12=2×6,
12=2×3×2 ,
12=2×2×3
对n的每个因子递归搜索,代码如下:
void solve (int n) { if (n==1) total++; else for (int i=2; i<=n; i++) if (n%i==0) solve (n/i); }
扩展问题一:能否输出各种具体的分解表达式?
思路:可以设置一个栈,如果是因子,则将这个因子压入栈中,递归到因子为1时分解完毕,将整个栈中元素输出。一次递归结束后将栈顶的元素弹出(本例中用的vector容器模拟栈)。代码如下:
void solve(int n) { if (n == 1) { total++; print_vector(ivec);//输出栈中的元素 } else for (int i = 2; i <= n; i++) if (n % i == 0) { //如果i是n的因子,则将i压入栈 ivec.push_back(i); solve(n / i); ivec.pop_back();//出栈 } }
扩展问题二:能否输出不重复的分解表达式?
第一种思路:经过多次试验发现,如果递归结束时,模拟栈中的元素是无序的,则本次分解一定重复。以12为例,有3种情况为:2×2×3、2×3×2、3×2×2,后两种之所以重复,是因为它们都是无序的,因此,在上问题一的基础上,只须在输出之前判断一下模拟栈中的元素是否有序便可,若序时,才进行输出。代码如下:
void solve(int n) { if (n == 1) { total++; if (isOrderVector(ivec))//只有有序时,才输出 print_vector(ivec);//输出栈中的元素 } else for (int i = 2; i <= n; i++) if (n % i == 0) { //如果i是n的因子,则将i压入栈 ivec.push_back(i); solve(n / i); ivec.pop_back();//出栈 } }
其中判断模拟栈是否为有序的代码如下:
bool isOrderVector(vector<int> & ivec) { assert(ivec.size() > 0); for (vector<int>::iterator i = ivec.begin() + 1; i != ivec.end(); i++) if (*i < *(i-1)) return false; return true; }
问题二的进一步优化:其实slove()函数内层循环中i没有必要循环到n,只须要循环到sqrt(n)便可,当然,需要再补上缺失的一种情况:当i为n时,代码如下:
void solve(int n) { …… else { for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { //如果i是n的因子,则将i压入栈 ivec.push_back(i); solve(n / i); ivec.pop_back();//出栈 } } { ivec.push_back(n); slove(1); ivec.pop_back(); } } }
第二种思路[章磊同学提供]:既然为了保持模拟栈中元素的顺序,那每次i入栈之前先同栈顶元素进行比较,如果i大于栈顶元素,则不入栈,这种方法更简洁,代码如下:
void solve(int n) { if (n == 1) { total++; print_vector(ivec);//输出栈中的元素 } else for (int i = 2; i <= n; i++) if (n % i == 0) { //若栈不为空,且i比栈顶元素小,说明 //再压栈己没有意义,直接结束本次循环。 if ((ivec.size() > 0) && i < ivec[ivec.size()-1]) continue; //如果i是n的因子,则将i压入栈 ivec.push_back(i); solve(n / i); ivec.pop_back();//出栈 } }
参考资料:北京科技大学 罗熊 算法设计与分析 第三章课件