存档

2011年9月 的存档

Divide And Conquer

2011年9月2日 Jarod Lee 没有评论

Merge Sort:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void Merge(int list[], int lowIndex, int highIndex, int midIndex)
{
   int *tempList = new int[highIndex-lowIndex+1];
   int firstLow = lowIndex;
   int secondLow = midIndex + 1;
   int index = 0;
   while(firstLow <= midIndex && secondLow <= highIndex)
   {
      if (list[firstLow] < list[secondLow])
         tempList[index++] = list[firstLow++];
      else
         tempList[index++] = list[secondLow++];
   }

   while (firstLow <= midIndex)
   {
      tempList[index++] = list[firstLow++];
   }

   while (secondLow <= highIndex)
   {
      tempList[index++] = list[secondLow++];
   }

   for (int ii = 0; ii < index; ii++)
   {
      list[lowIndex+ii] = tempList[ii];
   }
   delete[] tempList;
}

void MergeSort(int list[], int lowIndex, int highIndex)
{
   if (lowIndex < highIndex)
   {
      int midIndex = lowIndex + (highIndex-lowIndex)/2;
      MergeSort(list, lowIndex, midIndex);
      MergeSort(list, midIndex+1, highIndex);
      Merge(list, lowIndex, highIndex, midIndex);
   }
}
分类: C&&C++, Programming 标签:

Recursion

2011年9月1日 Jarod Lee 没有评论

递归生成某集合的所有序列:

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++ 标签: