习题1
1.
图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler,1707—1783)提出并解决了该问题。七桥问题是这样描述的:北区 一个人是否能在一次步行中穿越哥尼斯堡(现
东区 在叫加里宁格勒,在波罗的海南岸)城中全部岛区 的七座桥后回到起点,且每座桥只经过一次,
南区 图是这条河以及河上的两个岛和七座桥的草
图 七桥问题
图。请将该问题的数据模型抽象出来,并判断此问题是否有解。
七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1, 一次步行
2, 经过七座桥,且每次只经历过一次 3, 回到起点
该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。
2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n
2.循环直到r=0 m=n n=r r=m-n 3 输出m
3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C++描述。
编写程序,求n至少为多大时,n个“1”组成的整数能被2013整除。
#include
int main() {
double value=0;
for(int n=1;n<=10000 ;++n) {
value=value*10+1; if(value 13==0) {
cout<<\至少为:\ break; }
}计算π值的问题能精确求解吗?编写程序,求解满足给定精度要求的π值
#include
int main () {
double a,b;
double arctan(double x);圣经上说:神6天创造天地万有,第7日安歇。为什么是6天呢?任何一个自然数的因数中都有1和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。例如,6=1+2+3,因此6是完美数。神6天创造世界,暗示着该创造是完美的。设计算法,判断给定的自然数是否是完美数
#include
int main() {
int value, k=1; cin>>value;
for (int i = 2;i!=value;++i) {
while (value % i == 0 ) {
k+=i;有4个人打算过桥,这个桥每次最多只能有两个人同时通过。他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的:甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间?
由于甲过桥时间最短,那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如:
第一趟:甲,乙过桥且甲回来
第二趟:甲,丙过桥且甲回来 第一趟:甲,丁过桥 一共用时19小时
9.欧几里德游戏:开始的时候,白板上有两个不相等的正整数,两个玩家交替行动,每次行动时,当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差,而且这个数字必须是新的,也就是说,和白板上的任何一个已有的数字都不相同,当一方再也写不出新数字时,他就输了。请问,你是选择先行动还是后行动?为什么?
设最初两个数较大的为a, 较小的为b,两个数的最大公约数为factor。
则最终能出现的数包括: factor, factor*2, factor*3, ..., factor*(a/factor)=a. 一共a/factor个。
如果a/factor 是奇数,就选择先行动;否则就后行动。
习题4
1. 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关,试说明这几个参数与分治法时间复杂性之间的关系。
2. 证明:如果分治法的合并可以在线性时间内完成,则当子问题的规模之和小于原问题的规模时,算法的时间复杂性可达到O(n)。
O(N)=2*O(N/2)+x O(N)+x=2*O(N/2)+2*x
a*O(N)+x=a*(2*O(N/2)+x)+x=2*a *O(N/2)+(a+1)*x 由此可知,时间复杂度可达到O(n);
3.分治策略一定导致递归吗?如果是,请解释原因。如果不是,给出一个不包含递归的分治例子,并阐述这种分治和包含递归的分治的主要不同。
不一定导致递归。
如非递归的二叉树中序遍历。
这种分治方法与递归的二叉树中序遍历主要区别是:应用了栈这个数据结构。
4. 对于待排序序列(5, 3, 1, 9),分别画出归并排序和快速排序的递归运行轨迹。
归并排序:
第一趟:(5,3)(1,9); 第二趟:(3,5,1,9);
第三趟:(1,3,5,9);
快速排序:
第一趟:5( ,3,1,9);设计分治算法求一个数组中的最大元素,并分析时间性能。
设计分治算法,实现将数组A[n]中所有元素循环左移k个位置, 要求时间复杂性为O(n),空间复杂性为O(1)。例如,对abcdefgh循环左移3位得到defghabc。
设计递归算法生成n个元素的所有排列对象。 #include
int data[100];
设计分治算法求解一维空间上n个点的最近对问题。
参见4.4.1最近对问题的算法分析及算法实现
9. 在有序序列(r1, r2, …, rn)中,存在序号i(1≤i≤n),使得ri=i。请设计一个分治算法找到这个元素,要求算法在最坏情况下的时间性能为O(log2n)。
在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。
设M是一个n×n的整数矩阵,其中每一行(从左到右)和每一列(从上到下)的元素都按升序排列。设计分治算法确定一个给定的整数x是否在M中,并分析算法的时间复杂性。
12. 设S是n(n为偶数)个不等的正整数的集合,要求将集合S划分为子集S1和S2,使得| S1|=| S2|=n/2,且两个子集元素之和的差达到最大。
设a1, a2,…, an是集合{1, 2, …, n}的一个排列,如果i
k循环赛日程安排问题。设有n=2个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其他n-1个选手各赛一次; (2)每个选手一天只能赛一次。
采用分治方法。
将2^k选手分为2^k-1两组,采用递归方法,继续进行分组,直到只剩下2个选手时,然后进行比赛,回溯就可以指定比赛日程表了
n15. 格雷码是一个长度为2的序列,序列中无相同元素,且每个元素都是长度为n的
3
二进制位串,相邻元素恰好只有1位不同。例如长度为2的格雷码为(000, 001, 011, 010,