05 | 递归（上）：泛化数学归纳，如何将复杂问题简单化？

由于暂时无法追加回复，我这里再回复一下网友debugtalk 我看了Python的实现，果然很简介👍 奖金的题目没问题。整数的因子分解有点小瑕疵，少了一些可能。比如，输入8，少了 [1, 2, 2, 2] [1, 2, 4] [1, 4, 2] [2, 1, 2, 2]

 思考题：请大神帮忙看下，输出少了个 [1,8] 输出：[2, 2, 2, 1] [2, 4, 1][4, 2, 1][8, 1] import java.util.ArrayList; /** * @Auther: yli * @Date: 2018/12/19 17:19 * @Description: */ public class Iteration { public static void recursion(long total, ArrayList<Long> result){ if (total == 1){ result.add(1L); System.out.println(result); return; }else { for(long i = 2; i <= total; i ++){ ArrayList<Long> newList = (ArrayList<Long>)(result.clone()); newList.add(Long.valueOf(i)); if(total%i !=0){ continue; } recursion(total/i, newList); } } } public static void main(String[] args){ long total = 8; recursion(total, new ArrayList<Long>()); } }

Python 实现赏金问题：https://github.com/debugtalk/geektime-notes/blob/master/programmers-mathematics/chapter5.md Python 实现思考题：https://github.com/debugtalk/geektime-notes/blob/master/programmers-mathematics/chapter5.py

整数分解 - C++代码 #include <vector> #include <iostream> #include <algorithm> using namespace std; // 输出函数 void PrintResult(vector<int> &Result) { for (size_t i = 0; i < Result.size(); ++i) { cout << Result[i] << " "; } cout << endl; } //数组中是否存在某值 bool IsExit(vector<int> &Result, int value) { vector<int>::iterator result = std::find(Result.begin(), Result.end(), value); if (result == Result.end()) { return false; } else { return true; } } //整数分解 void RecursionAlgo(int Num, vector<int> &Result) { if (Num == 1) { PrintResult(Result); return; } for (int i = 1; i <= Num; ++i) { //判断1是否在解中 if (IsExit(Result, 1)) { if (i == 1) { continue; } } if (Num%i == 0) { vector<int> newResult = Result; newResult.push_back(i); RecursionAlgo(Num/i, newResult); } } } int _tmain(int argc, _TCHAR* argv[]) { int Totalmoney = 10; vector<int> Result; RecursionAlgo(Totalmoney, Result); return 0; }

参考老师和其他同学的留言, 下面是Pythoni实现的思考题, 应该是个较为简洁的版本. import copy def prod_factors(num, result=[]): if num == 1: print('x'.join([str(_) for _ in result])) if 1 not in result: result.append(1) print('x'.join([str(_) for _ in result])) elif num < 0: return else: for i in range(1, num+1): if (i == 1 and i not in result) or (i !=1 and num % i == 0): newresult = copy.copy(result) newresult.append(i) prod_factors(num/i, newresult) prod_factors(8) 1x2x2x2 1x2x4 1x4x2 1x8 2x1x2x2 2x1x4 2x2x1x2 2x2x2 2x2x2x1 2x4 2x4x1 4x1x2 4x2 4x2x1 8 8x1

黄老师，这句“递归和循环其实都是迭代法的实现”我不太理解。 如果递归和循环都属于迭代法，那么就是说递归是从属于迭代法的。而我所理解的迭代法的核心是从1到n的递推，而递归是从n到1的逐步求解的过程，两者应该是并列的关系。希望老师能解答我的这个困惑。

老师好，我实现了一个算法，但是没有打印出来1的情况。 还有个问题就是，如果使用老师的示例输入8，结果既有 2x4，又有 4x2 这不是重复了吗？ static void getFactorization(long product, ArrayList<Long> result) { for (int i = 2; i <= product / 2; i++) { if (0 == product % i) { ArrayList<Long> newResult = (ArrayList<Long>) result.clone(); newResult.add((long) i); getFactorization(product / i, newResult); newResult.add(product / i); System.out.println(newResult); } } }

//因数分解 public static void getMultiFactors(long multi,ArrayList<Long> result){ if (multi == 1){ result.add(multi); System.out.println(result); }else{ for (long i = 2; i <= multi; i++) { if(multi % i == 0){ ArrayList<Long> newResult = (ArrayList<Long>) result.clone(); newResult.add(i); getMultiFactors(multi / i,newResult); } } } }

这个案例中的n到底是什么，是奖励总金额，还是取的纸币数？

#include <iostream> #include <vector> using namespace std; const int N = 4; int coins[N] = {1, 2, 5, 10}; vector<int> closen; void dfs(int u) { if(u > 10) return; if(u == 10) { for(int i = 0; i < closen.size(); i++) { if(i > 0) printf(" "); printf("%d", closen[i]); } puts(""); return; } for(int i = 0; i < N; i++) { closen.push_back(coins[i]); u += coins[i]; dfs(u); closen.pop_back(); u -= coins[i]; } return; } int main(void) { dfs(0); return 0; } // 老师 这样写对吗