做题练习--归并排序,穷举
最近比较闲，抽空练练爪子：
多路归并
void MergeLines( int * temp, int * A, int left, int right)
//
其中temp是临时存储空间，A是真正的存放数据空间，left是数组的最左下标，right是数组的最右下标。
  … {
// 先判断些特殊的边界条件
if (right - left < 1 )
return ;
if (right - left == 1 )
  … {
if (A[right] > A[left])
  … {
swap(A[right],A[left]);
 }
return ;
 }
int mid = (right - left) / 2 + left;
MergeLines( & temp[ 0 ], & A[ 0 ],left,mid);
MergeLines( & temp[mid + 1 ], & A[mid + 1 ], 0 ,right - mid -
1 );
// 真正的归并开始（这里可以看做已经做到最后一步）
int k = 0 ;
int i = 0 ,j = mid + 1 ;
while (i <= mid && j <= right)
  … {
if (A[i] > A[j])
  … {
temp[k ++ ] = A[i ++ ];
 }
else
  … {
temp[k ++ ] = A[j ++ ];
 }
 }
if (i > mid)
  … {
while (j <= right)
  … {
temp[k ++ ] = A[j ++ ];
 }
 }
else
  … {
while (i <= mid)
  … {
temp[k ++ ] = A[i ++ ];
 }
 }
// 重新将值赋回A数组
for (i = 0 ; i < k;i ++ )
  … {
A[i] = temp[i];
 }
 }
使用一个串中相同的字母再生成新串，打印所有的串。比如“abc”有“bac”“bca”…等等。
这段代码的想法是{a,b,c},拿到{a}，将{b,c}去递归。如果拿到{b},将{a,c}去递归。
void All( string pre, char * str, int len) //
pre是前缀，str是真正的串，len是串的长度（除去’/ 0’）
//
这里注意str必须是一个new出来的字符串数组，不能是字符串常量数组。
//
开始的调用可以这样写All(“”,str,strlen(str));
  … {
if ( * str == ’ / 0 ’ )
return ;
if (len == 1 )
  … {
cout << pre << str[ 0 ] << endl;
return ;
 }
for ( int i = 0 ; i < len; i ++ )
  … {
if (i == 0 )
All(pre + str[ 0 ], & str[ 1 ],len - 1 );
if (i != 0 )
  … {
swap(str[i],str[ 0 ]);
All(pre + str[ 0 ], & str[ 1 ],len - 1 );
swap(str[i],str[ 0 ]);
 }
 }
 }
上面的函数可以进一步改写:这里的List就是{‘a’,‘b’},currentIndex = 0;k = len -1,len = List的元素个数。
void All( char * List, int currentIndex, int k, int len)
  … {
if (currentIndex == k)
  … {
for ( int i = 0 ; i < len; i ++ )
  … {
cout << List[i];
 }
cout << endl;
 }
else
  … {
for ( int i = currentIndex; i <= k; i ++ )
  … {
swap(List[currentIndex],List[i]);
All(List, currentIndex + 1 , k,len);
swap(List[currentIndex],List[i]);
 }
 }
 }
现在有一张纸币，但是现在有一堆个数无限的硬币（1角，2角，5角），兑换硬币
void past( int i) // 这里的i是最初的钱的价值（兑换成角，1元就是10角…）不过这里还是使用了穷举…:<
  … {
int u = 0 ;
for ( int j = 0 ; j <= i; j += 5 )
for ( int x = 0 ; x <= i; x += 2 )
for ( int c = 0 ; c <= i;c += 1 )
  … {
if (j + x + c == i)
  … {
cout << " <5,2,1> " << endl;
cout << j / 5 << " , " << x / 2 << " , " << c << endl;
u ++ ;
 }
 }
 }
不过写的代码自我感觉变量命名和函数命名不规范。这的确是今后要大大改进的地方。而且效率还很低。
因为硬币的穷举算法效率很低，所以用背包法重写代码：
如果输入的dest是10角，那么这里的srcSet应该含有10/1个1角，10/2个2角，10/5个5角。currentIndex是srcSet的下标，sr
cLen是srcSet的大小，subSet是符合条件的数据,num是subSet的集合中现含的元素个数。
int match( int * srcSet, int currentIndex, int srcLen, int dest,
int * subSet, int num)
  … {
if (currentIndex == srcLen)
return - 1 ;
if(dest-srcSet[currentIndex] < 0)
return -1;
if (dest - srcSet[currentIndex] == 0 )
  … {
subSet[num ++ ] = srcSet[currentIndex];
cout << num << " number match the dest, they are: " << endl;
for ( int i = 0 ; i < num; i ++ )
  … {
cout << subSet[i] << " " ;
 }
cout << endl;
return num;
 }
subSet[num] = srcSet[currentIndex];
int number = match(srcSet,currentIndex + 1 ,srcLen,dest -
srcSet[currentIndex],subSet,num + 1 );
if (number <= 0 )
  … {
return match(srcSet,currentIndex + 1 ,srcLen,dest,subSet,num);
 }
else
  … {
return match(srcSet,currentIndex + 1 ,srcLen,dest,subSet,num);
 }
 }
但是该算法仍然有的缺陷是最后返回的一定是-1。所以只好在程序运行过程中打印出结果。这里要求数组srcSet是从小到大排列的。虽然算法的复杂度没有降低，但是运
行的时间可能会加快。但是在最差情况下，比上面的穷举效率还低。而且多使用了空间。感觉类似于迷宫问题。虽然可以用A*但是最差情况下，比穷举还低。