Recursion
递归生成某集合的所有序列:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | template <class T> void Swap(T& a, T& b) { T temp = a; a = b; b = temp; } template <class T> void Permulation(T list[], int k, int m) { if (k == m) { for (int i = 0; i <= m; i++) cout << list[i]; cout << endl; } else { for (int i = k; i <= m; i++) { Swap(list[k], list[i]); Permulation(list, k+1, m); Swap(list[k], list[i]); } } } |
递归生成某集合的所有子集：
思想：
设集合X (A1, A2, A3,…, An)的所有子集为S[X(n)]，从集合X中移走A1的子集X(n-1)的所有子集集合记为S[X(n-1)]
S[X(n)] = S[X(n-1)] ∪ {S[X(n-1)]每个子集加上A1}
例如 集合{A, B, C}
{A}:
{} {A}
{A B}:
{} {A} ∪ {B} {A B}
{A B C}:
{} {A} {B} {A B} ∪ {C} {A C} {B C} {A B C}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | template <class T> void FindSubSets(T list[], int lowIndex, int highIndex, vector< set<T> > &results) { if (lowIndex == highIndex) { set<T> empty; set<T> oneElem; oneElem.insert(list[lowIndex]); results.push_back(empty); results.push_back(oneElem); } else { FindSubSets(list, lowIndex+1, highIndex, results); int existedSetSize = results.size(); for (int jj = 0; jj < existedSetSize; jj++) { set<T> newSet(results[jj]); newSet.insert(list[lowIndex]); results.push_back(newSet); } } } |
斐波那契数列计算：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 递归： int r_Fibonacci(int n) { if ( n < 2) return n; return r_Fibonacci(n-1) + r_Fibonacci(n-2); } 非递归： int fibonacci(int n) { if ( n < 2) return n; int f0 = 0; int f1 = 1; for (int ii = 1; ii < n; ii++) { f1 = f1 + f0; f0 = f1 - f0; } return f1; } |
递归查找：
1 2 3 4 5 6 7 8 | template <class InputIter, class T> InputIter find(InputIter begin, InputIter end, const T& val) { if (begin != end && *begin != val) return find(begin+1, end, val); else return begin; } |
分类: C&&C++
近期评论