编程中的基本数据结构与算法思想( 四 ) _算法

每个人的阅读兴趣用一个二维数组like描述：
Like[i][j] = true i喜欢书j
Like[i][j] = false i不喜欢书j

文章插图

设计一个函数trynext(int i)给第i个人分书。
用一个一维数组take表示某本书分给了某人。take[j]=i+1;//把第j本书分配给第i个人
依次尝试把书j分给人i 。
如果第i个人不喜欢第j本书，则尝试下一本书，如果喜欢，并且第j本书尚未分配，则把书j分配给i 。
如果i是最后一个人，则方案数加1 ，输出该方案。否则调用trynext(i+1)为第i+1个人分书。
如果对第i个人枚举了他喜欢的所有的书，都没有找到可行的方案，那就回到前一个状态i-1 ，让i-1把分到的书退回去，重新找喜欢的书，再递归调用函数，寻找可行的方案。

#include <IOStream>
#include <conio.h>
using namespace std;
int like[5][5]={
{0,0,1,1,0},
{1,1,0,0,1},
{0,1,1,0,1},
{0,0,0,1,0},
{0,1,0,0,1}};
int take[5]={0,0,0,0,0};//记录每一本书的分配情况
int n;//n表示分书方案数
void trynext(int i);
int main()
{
n=0;
trynext(0);
getch();
return 0;
}
//对第 i 个人进行分配
void trynext(int i)
{
int j,k;
for(j=0;j<5;j++)
{
if(like[i][j]&&take[j]==0)
{
take[j]=i+1;//把第j本书分配给第i个人
if(i==4)//第5个人分配结束，也即所有的书已经分配完毕，可以将方案进行输出
{
n++;
cout<<"第"<<n<<"种分配方案"<<endl;
for(k=0;k<5;k++)
cout<<"第"<<k<<"本书分配给"<<(char)(take[k]+'A'-1)<<endl;
cout<<endl;
}
else
trynext(i+1);//递归，对下一个人进行分配
take[j]=0;//回溯，寻找下一种方案
}
}
}

当like矩阵的值为

文章插图

附归并排序的代码：
#include <stdio.h>#include <stdlib.h>#include <limits.h>// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(nlogn)// 最优时间复杂度 ---- O(nlogn)// 平均时间复杂度 ---- O(nlogn)// 所需辅助空间 ------ O(n)// 稳定性 ------------ 稳定// 合并两个已排好序的数组A[left...mid]和A[mid+1...right]void Merge(int A[], int left, int mid, int right){ int len = right - left + 1; int *temp = new int[len]; // 辅助空间O(n) int index = 0; int i = left; // 前一数组的起始元素 int j = mid + 1; // 后一数组的起始元素 while (i <= mid && j <= right) {temp[index++] = A[i] <= A[j] ? A[i++] : A[j++]; // 带等号保证归并排序的稳定性 } while (i <= mid) {temp[index++] = A[i++]; } while (j <= right) {temp[index++] = A[j++]; } for (int k = 0; k < len; k++) {A[left++] = temp[k]; }}// 递归实现的归并排序(自顶向下)void MergeSortRecursion(int A[], int left, int right) { if (left == right) // 当待排序的序列长度为1时，递归开始回溯，进行merge操作return; int mid = (left + right) / 2; MergeSortRecursion(A, left, mid); //左半部分排好序 MergeSortRecursion(A, mid + 1, right); //右半部分排好序 Merge(A, left, mid, right); //合并左右部分}// 非递归(迭代)实现的归并排序(自底向上)void MergeSortIteration(int A[], int len) { int left, mid, right;// 子数组索引,前一个为A[left...mid] ，后一个子数组为A[mid+1...right] for (int i = 1; i < len; i *= 2) // 子数组的大小i初始为1 ，每轮翻倍 {left = 0;while (left + i < len) // 后一个子数组存在(需要归并){mid = left + i - 1;right = mid + i < len ? mid + i : len - 1;// 后一个子数组大小可能不够Merge(A, left, mid, right);left = right + 1; // 前一个子数组索引向后移动} }}int main(){ int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 从小到大归并排序 int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; int n1 = sizeof(A1) / sizeof(int); int n2 = sizeof(A2) / sizeof(int); MergeSortRecursion(A1, 0, n1 - 1); // 递归实现 MergeSortIteration(A2, n2); // 非递归实现 printf("递归实现的归并排序结果："); for (int i = 0; i < n1; i++) {printf("%d ", A1[i]); } printf("");printf("非递归实现的归并排序结果："); for (i = 0; i < n2; i++) {printf("%d ", A2[i]); } printf("");system("pause"); return 0;}