算法设计与分析C++语言描述(陈慧南版)课后答案

算法设计与分析C语⾔描述（陈慧南版）课后答案第⼀章15P1-3. 最⼤公约数为1。

快1414倍。

主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环）若考虑其他语句，则没有这么多，可能就601倍。

第⼆章32P2-8.（1）画线语句的执⾏次数为log n 。

(log )n O 。

划线语句的执⾏次数应该理解为⼀格整体。

（2）画线语句的执⾏次数为111(1)(2)16jnii j k n n n ===++=∑∑∑。

3()n O 。

（3）画线语句的执⾏次数为。

O 。

（4）当n 为奇数时画线语句的执⾏次数为(1)(3)4n n ++，当n 为偶数时画线语句的执⾏次数为 2(2)4n +。

2()n O 。

2-10.（1）当 1n ≥ 时，225825n n n -+≤，所以，可选 5c =，01n =。

对于0n n ≥，22()5825f n n n n =-+≤，所以，22582()n n n -+=O 。

（2）当 8n ≥ 时，2222582524n n n n n -+≥-+≥，所以，可选 4c =，08n =。

对于0n n ≥，22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。

（3）由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以22582()n n n -+=Θ。

2-11. (1) 当3n ≥时，3log log n n n <<，所以()20log 21f n n n n =+<，3()log 2g n n n n =+>。

可选 212c =，03n =。

对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。

注意：是f (n )和g (n )的关系。

算法设计与分析基础习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (―lazy deletion ‖)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。

算法设计与分析习题答案算法设计与分析是计算机科学中一个重要的领域，它涉及到算法的创建、优化以及评估。

以下是一些典型的算法设计与分析习题及其答案。

习题1：二分查找算法问题描述：给定一个已排序的整数数组，编写一个函数来查找一个目标值是否存在于数组中。

答案：二分查找算法的基本思想是将数组分成两半，比较中间元素与目标值的大小，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。

这个过程会不断重复，直到找到目标值或搜索范围为空。

```pythondef binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return Trueelif arr[mid] < target:low = mid + 1else:high = mid - 1return False```习题2：归并排序算法问题描述：给定一个无序数组，使用归并排序算法对其进行排序。

答案：归并排序是一种分治算法，它将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并成一个有序数组。

```pythondef merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1arr = [38, 27, 43, 3, 9, 82, 10]merge_sort(arr)print("Sorted array is:", arr)```习题3：动态规划求解最长公共子序列问题问题描述：给定两个序列，找到它们的最长公共子序列。

C语言课后习题标准答案第1章C语言概述一、简答题1．(1)语言简洁、紧凑,使用方便、灵活;（２）运算符丰富；(3)具有丰富的数据类型;（４)具有结构化的控制语句;(5）语法限制不太严格，程序设计自由度大；（6)C语言允许直接访问物理地址,能进行位（bit)操作，能实现汇编语言的大部分功能，可以直接访问硬件；(7）生成目标代码质量高,程序执行效率高;（8)用C语言写的程序可移植性好，基本上不作修改就能用于各种型号的计算机和各种操作系统。

2.顺序结构，分支结构,循环结构3.所谓算法就是为解决一个问题而采取的方法和步骤。

算法的特性：有穷性、确定性、输入、输出、可行性。

表示算法的方式:（1）用自然语言表示;(２）用流程图表示；(3)用N—Ｓ流程图表示；(4)用伪代码表示；（5）用计算机语言表示。

二、算法1．瓶子A里盛有醋瓶子B里盛有酱油那一个空瓶C将A中的醋倒入Ｃ将B中的酱油倒入Ａ将C中的醋倒入B2．输入一个数放在ａ中max＝a以下步骤重复9次:输入一个数放在a中如果a＞mａx，max=b打印mａx的值3．如果ﻩﻩa＜ｂtemp=aﻩa=bﻩﻩb＝teｍｐ如果ｃ＞aﻩtemｐ1=aﻩﻩｔｅmp2=ba=ｃﻩb＝tｅmp1ﻩｃ=temｐ2否则ﻩ如果ﻩｃ＞bﻩｔｅmp=bﻩb=cﻩc=ｔemp打印a，b，c的值4．i＝1sum=0以下程序循环１00遍：sum＝sum＋iﻩi＝ｉ+1打印sｕm的值5．如果（n除以3的余数为0并且n除以5的余数为０）n能够同时被3和5整除否则ﻩｎ不能够同时被3和5整除6．i=101以下语句循环５０遍：ﻩj=2ﻩflag=1ﻩ当j<(ｉ除以2的整数部分)时循环以下语句：ﻩﻩ如果i除以j的余数为零ﻩﻩﻩfｌaｇ=０ﻩﻩﻩ退出该循环如果flaｇ＝1ﻩﻩﻩ打印ｉ的值ﻩｉ=i+17．如果m<ｎﻩﻩtemp＝mﻩﻩm=nｎ=temｐi＝nj＝1做以下循环,直到m能够被i/j整除：如果i能够被j整除并且m能够被i／j整除i/j即是ｍ和n的最大公约数ﻩ跳出循环否则ﻩj=j+1打印ｉ/j的值8．ｄａta=b＊b—4*a＊c如果ｄata>０否则如果data=０ﻩx1=x2=—ｂ／2否则无实数解三、编程题1．mａin(){ﻩpｒintf（“########＃＃#########＃######＃＃##\n”）;ﻩｐrinｔf(“How do yoｕdo?\n”）;ﻩprintf(“＃###＃####＃###＃###＃######＃＃##＃#\n”)；}2．mａin(）｛adata b x2)(1+-=a data b x2)(2--=。

《算法分析与设计C》复习总成绩=平时成绩（30%）+考试成绩（70%）考试时间：2015年06月28日(16:00-17:50)试卷题型：一、 选择题（每空2分，共20分）二、 填空题（每空2分，共20分）三、 证明题（每题5分，共10分）四、 问答题（每题10分，共50分）第一章 算法求解基础算法的概念算法特征（输入、输出、确定性、可行性、有穷性）——掌握每种特征的含义、算法和程序的区别描述算法的方法（自然语言、流程图、伪代码、程序设计语言）欧几里德算法（辗转相除法）——递归/迭代程序实现及其变形常见算法种类——精确算法、启发式算法、近似算法、概率算法第二章 算法分析基础算法复杂度——运行一个算法所需的时间和空间。

好算法的四个特征（正确性、简明性、效率、最优性）正确性vs健壮性vs可靠性最优性——算法（最坏情况下）的执行时间已达到求解该类问题所需时间的下界。

影响程序运行时间的因素（程序所依赖的算法、问题规模和输入数据、计算机系统性能）算法的渐近时间复杂度 ——数量级上估计（Ο、Ω、Θ）最好、最坏、平均时间复杂度——定义——课后习题2-8（通过考察关键操作的执行次数）时间复杂度证明——课后习题2-10，2-13，2-17算法按时间复杂度分类：多项式时间算法、指数时间算法多项式时间算法：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3) 指数时间算法：O(2n)<O(n!)<O(n n)第五章 分治法分治法——求解的基本要素：将一个难以直接求解的复杂问题分解成若干个规模较小、相互独立但类型相同的子问题，然后求解这些子问题；如果这些子问题还比较复杂而不能直接求解，还可以继续细分，直到子问题足够小，能够直接求解为止；最后将子问题的解组合成原始问题的解。

这种问题求解策略称为分治法。

分治法很自然的导致一个递归算法。

平衡子问题思想递归算法的时间复杂度分析:递推式T(n)=aT(n/b)+cn k，T(1)=c——递推式中每部分的含义——求解得到算法的渐近时间复杂度（分三种情况）——改进思路求最大最小元二分搜索算法框架对半搜索——程序实现——对半搜索二叉判定树（树的构成）——对半搜索二叉判定树性质（左右子树结点数、树高等）——对半搜索的时间复杂度分析（搜索成功/失败、最好/最坏/平均）。