算法设计与分析-第五章作业

这一周要交的作业是:
1、编程作业:5.10练习题9、10、12题。每道题编程调试成功后将程序和运行结果分别截图,保存到同一个word文档中,用学号+姓名命名后提交到第五章作业文件夹。
作业提交截止时间:3月18日23:00。



第12题. 采用递归回溯法设计一个算法求1~n的n个整数中取出m个元素的排列,要求每个元素最多只能取一次。例如,n=3,m=2的输出结果是(1,2)(1,3)(2,1)(2,3)(3,1)(3,2)。


main函数里面的mn可以换成其它数。

#include <iostream>
using namespace std;
constexpr auto MAXN = 15;
constexpr auto MAXM = 10;
int m, n;
int x[MAXM]; 
bool already[MAXN];
void array1(int i)
{
	if (i > m)
	{
		for (int j = 1; j <= m; j++)
			cout << x[j]<<" ";
		cout << endl;	
	}
	else
	{
		for (int j = 1; j <= n; j++)
		{
			if (!already[j])
			{
				already[j] = true;
				x[i] = j; 
				array1(i + 1);
				already[j] = false;
			}
		}
	}
}
void main()
{
	n = 4, m = 2;
	array1(1);
}


第9题. 设计一个算法求解简单装载问题,设有一批集装箱要装上一艘载重量为 W 的轮船,其中编号为 i(0≤i≤n-1)的集装箱的重量为 wi。现要从 n 个集装箱中选出若干装上轮船,使它们的重量之和正好为 W。如果找到任一种解返回true,否则返回 false。


第10题. 给定若干个正整数a0、a0 、…、an-1 ,从中选出若干数,使它们的和恰好为k,要求找选择元素个数最少的解。

上一篇 下一篇
---内容结束---