做百度网站找谁,wordpress的搭建教程,微信公众号登陆,外贸添加外链网站原始问题描述#xff1a;对于给定的正整数n#xff0c;计算n有多少种不同的分解式。例如#xff0c;当n12时#xff0c;有8种不同的分解式#xff1a;1212,1262,1243,1234,12322,1226,12232 ,12223对n的每个因子递归搜索#xff0c;代码如下#xff1a;void solve (int …原始问题描述对于给定的正整数n计算n有多少种不同的分解式。例如当n12时有8种不同的分解式1212,126×2,124×3,123×4,123×2×2,122×6,122×3×2 ,122×2×3对n的每个因子递归搜索代码如下void solve (int n){if (n1)total;elsefor (int i2; in; i)if (n%i0)solve (n/i);}扩展问题一能否输出各种具体的分解表达式思路可以设置一个栈如果是因子则将这个因子压入栈中递归到因子为1时分解完毕将整个栈中元素输出。一次递归结束后将栈顶的元素弹出(本例中用的vector容器模拟栈)。代码如下void solve(int n){if (n 1){total;print_vector(ivec);//输出栈中的元素}elsefor (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);//输出栈中的元素}elsefor (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 ivec){assert(ivec.size() 0);for (vector::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);//输出栈中的元素}elsefor (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();//出栈}}参考资料北京科技大学 罗熊 算法设计与分析 第三章课件
