递归生成某集合的所有序列:
template <typename T>
void Swap(T &a, T &b)
{
T temp = a;
a = b;
b = temp;
}
template <typename 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}
template <typename T>
void FindSubSets(T list[], int lowIndex, int highIndex, vector<set> &results)
{
if (lowIndex == highIndex)
{
set empty;
set 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 newSet(results[jj]);
newSet.insert(list[lowIndex]);
results.push_back(newSet);
}
}
}斐波那契数列计算：
递归实现：
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;
}递归查找：
template <typename InputIter, typename T>
InputIter find(InputIter begin, InputIter end, const T &val)
{
if (begin != end && *begin != val)
return find(begin + 1, end, val);
else
return begin;
}