当前位置：文档之家 › 算法设计第四章部分作业

算法设计第四章部分作业

  • 格式：doc
  • 大小：109.50 KB
  • 文档页数：23

下载文档原格式

  / 23

合集下载

算法设计与分析知到章节答案智慧树2023年天津大学

算法设计与分析知到章节答案智慧树2023年天津大学

算法设计与分析知到章节测试答案智慧树2023年最新天津大学第一章测试1.下列关于效率的说法正确的是（）。

参考答案:提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法;效率主要指处理机时间和存储器容量两个方面;效率是一个性能要求，其目标应该在需求分析时给出2.算法的时间复杂度取决于（）。

参考答案:问题的规模;待处理数据的初态3.计算机算法指的是（）。

参考答案:解决问题的有限运算序列4.归并排序法的时间复杂度和空间复杂度分别是（）。

参考答案:O(nlog2n);O(n)5.将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。

（）参考答案:错6.用渐进表示法分析算法复杂度的增长趋势。

（）参考答案:对7.算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

（）参考答案:对8.某算法所需时间由以下方程表示，求出该算法时间复杂度（）。

参考答案:O(nlog2n)9.下列代码的时间复杂度是（）。

参考答案:O(log2N)10.下列算法为在数组A[0,...,n-1]中找出最大值和最小值的元素，其平均比较次数为（）。

参考答案:3n/2-3/2第二章测试1.可用Master方法求解的递归方程的形式为（）。

参考答案:T(n)=aT(n/b)+f(n) , a≥1, b＞1, 为整数, f(n)＞0.2.参考答案:对3.假定，, 递归方程的解是. ( )参考答案:对4.假设数组A包含n个不同的元素，需要从数组A中找出n/2个元素，要求所找的n/2个元素的中点元素也是数组A的中点元素。

针对该问题的任何算法需要的时间复杂度的下限必为。

( )参考答案:错5.使用Master方法求解递归方程的解为（）.参考答案:6.考虑包含n个二维坐标点的集合S，其中n为偶数，且所有坐标点中的均不相同。

一条竖直的直线若能把S集合分成左右两部分坐标点个数相同的子集合，则称直线L为集合S的一条分界线。

若给定集合S，则可在时间内找到这条分界线L。

C语言程序设计(第三版)谭浩强著 各章习题答疑

C语言程序设计(第三版)谭浩强著 各章习题答疑

以八、 /* 以八、十六进制输出 */
} ???? 是对应的带符号短整数。 输出结果是八进制整数 十六进制整数
2
3.9 计算某个表达式的值。 通用程序清单如下： stdio.h” #include ”stdio.h stdio.h void main() { ?????? x; 计算表达式值存入x x=( 表达式 )；/* 计算表达式值存入x */ printf(”% printf( %？\n”,x); ,x); } ?????? 表达式对应的数据类型符(需事先判断) ？ 表达式为整型，则为d 表达式为实型，则为f 3
第七章习题答疑（二）
折半查找法在排序数组中查找某个数。 上课时已有提示。 7.13 字符串连接(b[]中字符串连接到a[]中字符串后) 设：a[10]=”12 ,b[]=”abc 12”, abc” 12 abc (1)找到a串的’\0’的下标（i=2） ’ (2)j=0; 当型循环（b[j]!=’\0’） ’\ ’ a[i]=b[j],i++,j++ (3)a[i]=’\0’ \ 7.15 字符串复制(b[]中字符串复制到a[]中) 设：a[10]=”12”,b[]=”abc” (1)i=0; 当型循环（b[i]!=’\0’） a[i]=b[i],i++ (2)a[i]=’\0’ 7.9
18
第十章习题答疑（一）
输入3个整数，按照由小到大顺序输出。 int x,y,z,*px=&x,*py=&y,*pz=&x; 用以前的程序，其中的x、y、z换成*px、*py、*pz 10.3 输入10个整数存入一维数组a[10]，将其中最小数与第1 个数交换，最大数与最后一个数交换。 要求编3个函数： 10 10 输入10个整数、交换、输出交换后的10个整数。 输入函数： void in(int *p,int n) 输出函数： void out(int *p,int n) 交换函数： void change(int *p,int n) 其中寻找最大最小数的方法： int *q,*max,*min; for (max=min=p,q=p+1;q<p+n;q++) { if(*max<*q) max=q; if(*min>*q) min=q; } 19 交换的方法：*p和*min，*(p+n-1)和*max 10.1

第四章习题1

第四章习题1

2017/10/10
14
填空
1.在采用请求分页式存储管理的系统中，地址变换过程可能会因为 地址长度越界 、 缺页 和 访问权限错误 _________________ _______等原因而产生中断。 2.在分区分配算法中，首次适应算法倾向于优先利用内存中 低地址 部分 空闲区，从而保留了 高地址 ___部分的大空闲区。 3.虚拟存储通常由主存 和 辅存 _两级存储系统组成。为了在一台特定的机 物理地址 器上执行程序，必须把 逻辑地址 ____映射到这台机器主存储器的 _______ 空间上，这个过程称为地址映射 。 4.在段式存储管理中，段的保护通常有 越界保护 ____和 存取控制 ____两种。 5.设有8页的逻辑空间，每页有1024字节，它们被映射到32块的物理存储区 13 位，物理地址至少是 15 位。 中。那么逻辑地址的有效位是______
2017/10/10 13
21、在动态分区分配的算法中,首次适应算法倾向于优先利用 内存中的( 低地址 )部分的空闲分区,从而保留了( 高地址 ) 部分的空闲分区。 22、地址变换机构的最基本任务是将(用户地址空间)中的( 逻辑地址(或相对地址) )变换为( 内存空间 )中的( 物理地址(或绝对地址) )。在分页系统中为实现地址变换而 设置了页表寄存器,其中存放了( 页表始址 )和( 页表长度 ), 在进程未运行时,他们存放在( PCB(或进程控制块) )中。在 分页系统中进行地址变换时,应将页表寄存器中的(页表始址) 和( 页号 )进行相加,得到该页的在页表中的位置,从中可得 到( 物理块号 )。 23、为实现请求分页管理,应在页表中增加( 状态位 )、( 访问字段 )、( 修改位 )、( 外存地址 )几项。
2017/10/10
18

DS第四章 数组

DS第四章 数组

起始位置，亦称为基地址。
1
2
i 1
k i 1

练习1：


数组A[0..5,0..6]，每个元素占5个字节，首地 址为1000，按列优先存储，则A[5,5]的存储地 址是 （ ）。 分析： 因为是按列优先，所以在A[5,5] 前已经 存储了0～4列共5列，每列有6个元素，所以共 5×6＝30个元素。在第5列上， A[5,5]之前有 5个元素，则A[5,5]之前共有30+5=35个元素， 所以其地址为： 1000+35*5=1175

矩阵中元素已经按行和按列排好序，要求查找的时间复杂度为 O(m+n)，因此不能采用常规的二层循环的查找。 方法：从B的右上角元素开始比较，每次比较有3种可能的结果： 1) B[i,j]=x ，查找成功； 2) B[i,j]>x，则向j小的方向（即向左）继续查找（减少一列）； 3) B[i,j]<x，则向i大的方向（即向下）继续查找（减少一行）； 这样：每次比较可以使得搜索范围减少一行或一列，最多经过 m+n次比较就可以找到。 若下标超出范围，则查找失败。
(i 1) * (2n i 2) (n p 1) 2 p 1
i 1
个元素，而在第i行上aij之前有j-i个元素，它是所 在行的第（j-i+1）个元素，所以，它是数组a的第 (i-1)*(2n-i+2)/2+(j-i+1)个元素。 注意到B的 下标从0开始：

因此aij和B[k]之间的对应关系为：
i (i 1) j 1 2 k j ( j 1) i 1 2
当i j j
= LOC(B[0])+K*L=LOC(B[0])+[I*(I-1)/2+J-1]*L

算法设计与分析第三版第四章课后习题答案

算法设计与分析第三版第四章课后习题答案

算法设计与分析第三版第四章课后习题答案4.1 线性时间选择问题习题4.1问题描述：给定一个长度为n的无序数组A和一个整数k，设计一个算法，找出数组A中第k小的元素。

算法思路：本题可以使用快速选择算法来解决。

快速选择算法是基于快速排序算法的思想，通过递归地划分数组来找到第k小的元素。

具体步骤如下： 1. 选择数组A的一个随机元素x作为枢纽元。

2. 使用x将数组划分为两个子数组A1和A2，其中A1中的元素小于等于x，A2中的元素大于x。

3. 如果k等于A1的长度，那么x就是第k小的元素，返回x。

4. 如果k小于A1的长度，那么第k小的元素在A1中，递归地在A1中寻找第k小的元素。

5. 如果k大于A1的长度，那么第k小的元素在A2中，递归地在A2中寻找第k-A1的长度小的元素。

6. 递归地重复上述步骤，直到找到第k小的元素。

算法实现：public class LinearTimeSelection {public static int select(int[] A, int k) { return selectHelper(A, 0, A.length - 1, k);}private static int selectHelper(int[] A, int left, int right, int k) {if (left == right) {return A[left];}int pivotIndex = partition(A, left, righ t);int length = pivotIndex - left + 1;if (k == length) {return A[pivotIndex];} else if (k < length) {return selectHelper(A, left, pivotInd ex - 1, k);} else {return selectHelper(A, pivotIndex + 1, right, k - length);}}private static int partition(int[] A, int lef t, int right) {int pivotIndex = left + (right - left) / 2;int pivotValue = A[pivotIndex];int i = left;int j = right;while (i <= j) {while (A[i] < pivotValue) {i++;}while (A[j] > pivotValue) {j--;}if (i <= j) {swap(A, i, j);i++;j--;}}return i - 1;}private static void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}}算法分析：快速选择算法的平均复杂度为O(n)，最坏情况下的复杂度为O(n^2)。

《C程序设计》作业参考答案(1-4章)

《C程序设计》作业参考答案(1-4章)

第1章C语言概述习题（P13）：1.3 写出一个C程序的构成。

答：C程序由一个main函数和0个或多个自定义函数构成，每个函数的构成如下：函数类型函数名（函数参数列表）{说明部分执行部分}1.4 C语言以函数为程序的基本单位，有什么好处？答：一个函数实现一个相对独立的功能，便于实现程序的模块化。

1.5 请参照本章例题，编写一个C程序，输出以下信息：*************************************************Very good!*************************************************答：参照例1.1编程如下# include <stdio.h>void main(){printf("********************************************\n");printf(" Very good!\n");printf("********************************************\n");}1.6 编写一个C程序，输入a、b、c 3个值，输出其中最大者。

答：参照例1.3编程如下法一：修改例1.3的主函数，自定义max函数不变。

# include <stdio.h>void main(){int max(int x,int y); /*函数声明*/int a,b,c,m; /*定义4个变量，m用于存放最大值*/scanf("%d%d%d",&a,&b,&c);/*从键盘上输入3个整数*/m=max(a,b); /*第一次调用max函数求出前两个数的最大值放在m中*/m=max(m,c); /*再调max函数求出m和第三个数的最大数*/printf("max is %d\n",m); /*输出结果*/}int max(int x,int y) /*定义求两个数的最大数的函数max */{int z;if(x>y) z=x;else z=y;return(z);}法二：修改例1.3的主函数和max函数，将max函数改为求3个数的最大数。

『嗨威说』算法设计与分析-PTA程序存储问题删数问题最优合并问题（第四章上机实践报告）

『嗨威说』算法设计与分析-PTA程序存储问题删数问题最优合并问题（第四章上机实践报告）本⽂索引⽬录：⼀、PTA实验报告题1 ：程序存储问题 1.1 实践题⽬ 1.2 问题描述 1.3 算法描述 1.4 算法时间及空间复杂度分析⼆、PTA实验报告题2 ：删数问题 2.1 实践题⽬ 2.2 问题描述 2.3 算法描述 2.4 算法时间及空间复杂度分析三、PTA实验报告题3 ：最优合并问题 3.1 实践题⽬ 3.2 问题描述 3.3 算法描述 3.4 算法时间及空间复杂度分析四、实验⼼得体会（实践收获及疑惑）⼀、PTA实验报告题1 ：程序存储问题 1.1 实践题⽬： 1.2 问题描述： 题意是，题⼲给定磁盘总容量和各个⽂件的占⽤空间，询问该磁盘最多能装⼏个⽂件。

1.3 算法描述： 签到题，只需要将各个⽂件从⼩到⼤排序，并拿⼀个变量存储已占⽤的容量总和，进⾏对⽐即可得到结果。

#include<bits/stdc++.h>#include<algorithm>using namespace std;#define MAXLENGTH 1000int interger[MAXLENGTH];int main(){int num,length;int sum = 0;int counter = 0;int m = 0;cin>>num>>length;for(int i=0;i<num;i++){cin>>interger[i];}sort(interger,interger+num);while(true){if(sum+interger[m]>length||counter==num)break;sum+=interger[m];counter++;m++;}cout<<counter<<endl;return0;} 1.4 算法时间及空间复杂度分析： 整体算法上看，输⼊需要O（n）的时间进⾏输⼊，最快⽤O（nlogn）的时间复杂度进⾏排序，使⽤O（n）的时间进⾏结果叠加，总时间复杂度为O（nlogn），时间复杂度花费在排序上。

《第四章5用计算器开方》作业设计方案-初中数学鲁教版五四制12七年级上册

《用计算器开方》作业设计方案（第一课时）一、作业目标本作业设计旨在通过使用计算器进行开方运算的实践，使学生熟练掌握用计算器进行开方的方法和技巧，加深对开方概念的理解，并能够灵活运用开方知识解决实际问题。

二、作业内容（一）基本操作练习1. 让学生使用计算器进行简单的开方运算，如：√4、√9、√16等，以熟悉计算器的操作界面和开方功能。

2. 让学生尝试使用计算器进行带小数点的数开方，如：√2.56、√3.14等，以增强学生的实际操作能力。

（二）进阶应用练习1. 结合实际问题，设计开方运算的应用题，如：计算一个矩形的对角线长度等。

2. 让学生根据所学的开方知识，自行设计一些实际问题，并使用计算器进行求解。

（三）综合理解题通过题目解析的方式，引导学生分析复杂的开方问题，例如利用平方根性质解决问题，理解正负数的平方根概念等。

三、作业要求1. 学生需在完成基本操作练习的基础上，尝试完成进阶应用练习和综合理解题。

2. 作业中应注明每道题的答案及解题过程，对于应用题需详细描述问题背景和解题思路。

3. 作业中需体现出学生对开方知识的理解和运用能力，特别是在实际问题中的运用。

4. 要求学生保持作业整洁，字迹清晰，答题规范。

四、作业评价1. 教师将根据学生的作业完成情况，评价其掌握用计算器进行开方运算的程度及运用知识解决实际问题的能力。

2. 评价将综合考虑学生的答案准确性、解题过程是否清晰、是否能够灵活运用所学知识等方面。

3. 对于表现优秀的学生，教师将给予表扬和鼓励；对于存在问题的学生，教师将给予指导和帮助。

五、作业反馈1. 教师将对学生的作业进行批改，并及时反馈批改结果给学生。

2. 针对学生在作业中出现的错误和不足，教师将提供详细的指导和建议，帮助学生改正错误并提高解题能力。

3. 教师将根据学生的作业情况，调整后续的教学计划和教学方法，以更好地满足学生的学习需求。

作业设计方案（第二课时）一、作业目标1. 熟练掌握使用计算器进行开方运算；2. 了解并掌握平方根、算术平方根的算法及操作过程；3. 增强学生的动手操作能力及解决问题的能力，通过实际操作学会开方的方法和技巧。

第四章 程序设计基础 同步练习-粤教版(2019) 必修1数据与计算

第四章程序设计基础一、选择题1．分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决问题，最后将子问题的解组合起来形成原问题的解。

这要求原问题和子问题的（）A．规模相同，性质相同B．规模相同，性质不同C．规模不同，性质相同D．规模不同，性质不同2．某算法的部分流程图如下图所示，执行该流程图，则输出s的值以及k的值是( )A．25 ，9B．36 ，11C．36 ，13D．49 ，153．以下流程图符号是输入输出框的是（）A．B．C．D．4．如图所示的流程图，当输入16、80时，输出16；当输入20、18时，输出18，则虚线框中应填入的是()。

A．c=a,c=b B．c=b, c=a C．c=max(a,b)D．c=min(a,b) 5．观察流程图，下列关于算法特征表述错误．．的是（）A．算法可以没有数据输入B．算法必须至少有一个输出C．该流程图符合算法的有穷性特征D．该流程图中s＝s＋1体现了算法的确定性6．下面四个选项中，全部是C语言关键字的选项是（）A．auto enum includeB．switch type def continueC．signed union scanfD．if struct type7．某算法的部分流程图如图所示。

执行这部分流程，则输出a的值为（）A．1B．4C．8D．128．计算机能够直接识别和执行的语言是( )A．机器语言B．汇编语言C．Python 语言D．C语言二、简答题9．程序设计语言有哪些，分别具备什么特点。

10．思考高楼的自动电梯在运行时需要考虑哪些方面（例如方便乘客，节约能源等），请为自动电梯设计一个适宜的算法。

三、操作题11．某数据解密算法描述如下：（1）在输入的数字字符串中依次提取有效的密文，有效的密文的特点：①是一组连续的，都小于5的三位数字串；②每个位置上的数字不能被重复提取；（2）对有效密文进行解密的过程：将密文作为一个五进制数转换为对应的十进制数值，根据ASCII字符的十进制编码表，得出对应的明文字符（提示：空格符所对应的ASCII码值为十进制数32，小写字母“z”所对应的ASCII码值为十进制数122）.例如，密文242转换成十进制数为72，对应的明文字符为大写字母“H”。

第4章 算法与程序设计-大学计算机—计算思维视角-刘添华-清华大学出版社


算法的描述-流程图
• 流程图从开始符开始，以结束符结束。 顾名思义，就是用来直观地描述一个过程、 算法的具体步骤。 • 同一个算法可以用不同的表示方法描述。 例4-2的算法用流程图方法表示，如图所示。
算法的描述-N-S图
1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图，并以他们的 姓名的第一个字母命名为N-S图。
算法的描述-伪代码
例4-2求最大数的算法用伪代码表示如下所示。
“伪代码”是用介于自然语言和计算机
Begin /*算法开始*/
语言之间的文字和符号来描述算法。“伪”
N=1 Input A Max=A 当 N<=10 则
意味着假，因此用伪代码写的算法不能被计 算机所理解，但便于转换成某种语言编写的 计算机程序。
第5步：输出计数器的值。
例4-1的算法满足算法的五个特征。
算法的评价
评价算法，是为了提高程序的效率、不断优化算法。 (1)时间复杂度
时间复杂度是指计算机执行一个算法在时间上的消耗度量。 (2)空间复杂度
空间复杂度是指在—个算法的运行过程中，对临时耗费的存储空间的度量。
时间复杂度和空间复杂度往往是相互矛盾的，通常要降低算法的执行时间就要 以使用更多的空间作为代价，而要节省空间则往往要以增加算法的执行时间作为成本， 二者很难兼顾。
算法的描述-流程图
美国国家标准化协会ANSI(American National Standard Institute) 规定了一些 常用的流程图符号：
起止框
判断框
处理框
输入/输出框
注释框
流向线
连接点
流程图表示的算法形象、直观，易于理解，能够清楚地显示出各个框之间的逻 辑关系和执行流程，便于交流，因此被广泛使用，成为程序员们交流的重要手段。 当然，这种表示法也存在着占用篇幅大、画图费时、不易修改等缺点。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
算法：
输入：火柴的数量和第二个让人拿的火柴数量
输出：第一个拿的火柴数量
1.构造fun()函数，让A拿的火柴数是第二个人拿完后的数量模5的值
2.判断n%5的值
3.如果模值不等于0，调用fun()函数
4.进行递归调用fun知道火柴拿完为止
程序：
//火柴问题，如果火柴根数是5的倍数，那么只要B不是傻瓜A就输定了！反之如果不是5的倍数，那么A每次只要拿n%5的模值就一定能赢
r[m]=r[n-1];
r[n-1]=temp;
}
HeapSort(r, n-1);
for( i=0;i<7;i++)
cout<<r[i]<<" ";
return 0;
}
void SiftHeap(int r[ ], int k, int n)
{
int i, j, temp;
i = k; j = 2 * i +1; //置i为要筛的结点，j为i的左孩子
cout<<r[i]<<" ";
cout<<endl;
cout<<"大根堆中要删除的元素的下标为:";
cin>>m;//输入大根堆中要删除的元素的下标
if(m<0||m>=n)
cout<<"要删除的元素的不存在"<<endl;
else
{
int temp;
temp=r[m];//将该元素的下标与大根堆最后一个元素交换，然后将前n-1个元素进行大根堆排序即可
{
if(i<=(m+k)/2)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
void xun(char a[],int k,int n)//（函数2）第二个调用函数，调用函数1
{
fun(a,0,k-1);//第一次调用函数1，将(abc)对称交换得到(cba),最后a[]为(cbadefgh)
b=b*2;
}
}
count=a*b+s;
return count;
}
int main()
{
int m,n;
int sum;
cout<<"请输入两个乘数:";
cin>>n>>m;
sum=fun(n,m);
cout<<"计算结果为:";
cout<<sum<<endl;
return 0;
}
第8题：
想法：
对于火柴游戏，如果起初所有火柴的数量是5的倍数，那么第一个人是不能赢的，如果要第一个人赢得游戏，那么，要在火柴数量不是5的倍数的情况下进行，不管第二个人拿几根火柴，只要第一个人拿的数量是n%5的模值即可赢得游戏！
else fun(n);
return 0;
}
第10题：
想法：
这个想法是基于已知假币的轻重的情况下进行的，我假设假币比真币轻来进行试验，也可以假设假币比真币重，只需要稍微改写一下程序即可。首先，我将硬币分成3堆，用数组来存放硬币的重量，随便假设一个数组元素为假，用累加判断大小的方式来判断假币出现在哪一堆分组中，对可能出现的三种情况进行递归调用Coin（）函数来进行循环判断，直到找到假币为止
cout<<a<<"和"<<b<<"的最大公倍数是："<<s<<endl;
return 0;
}
int CommFactor2(int m, int n)//返回两个数的最大公约数
{
int r = m % n;
while (r != 0)
{
m = n;
n = r;
r = m % n;
}
return n;
算法：
1.输入：一个数组和左移位数
2.编写两个函数，一个是对称交换函数1，另一个是调用函数2，用函数2三次调用函数1，完成整个对称交换过程。
3.调用函数2
4.输出：左移后的数组
程序：
/*(升级版2)这个是用分治法将一个字符串(abcdefgh)左移3位(defghabc)，具体用到的方法是对称交换和调用函数*/
3.建立初始大根堆
4.输入要删除的元素的下标
5.将要删除的元素与最后一个一个元素交换
6.建立前n-1个元素的大根堆
程序：
//想法：先将已知序列排列成一个大根堆，删除某个元素后，将最后一个元素赋值给删除节点，然后再进行堆排序（堆排序只是有序排序中的一部分）
#include <iostream.h>
void HeapSort(int r[ ], int n);//建立堆以及堆中元素整体排序
const int N = 12; //假设求解12枚硬币问题
int a[N] = {2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2};
int Coin(int low, int high, int n);
int main()
{
int i=Coin(0,11,12);
cout<<"假币是第"<<i<<"个"<<endl;
return 0;
}//真币的重量是2，假币的重量是1
int Coin(int low, int high, int n) //在a[low]~a[high]中查找假币
{
int i, num1, num2, num3; // num1、num2和num3存储3组硬币的个数
int add1 = 0, add2 = 0; //add1和add2存储前两组硬币的重量和
算法：
输入：一个数组用来存放硬币的重量
输出：假币的位置
1.构造Coin()函数，将硬币分成三堆，如果硬币数量是3的倍数则均分成3组，如果不是则前两组分成n/3+1
2.累加比较重量来判断假币出现的地方
3.递归循环调用Coin()函数
4.返回假币的下标
5.在主函数中调用Coin()函数，输出结果
程序：
#include <iostream.h>
i = j; j = 2 * i+1; //被筛结点位于原来结点j的位置
}
}
}
void HeapSort(int r[ ], int n)
{
int i;
for (i = (n-1)/2; i >= 0; i--) //初始建堆，从最后一个分支结点至根结点
SiftHeap(r, i, n) ;
}
第7题：
算法第4-7章部分答案
第四章
第4题：
想法：
求两个正整数m和n的最小公倍数，由题目给出的提示可以知道，m和n的最小公倍数等于两个数的积除以它们的最大公约数。在第一张的事后要我们就已经用欧几里德算法求过两个数的最大公约数，所以对于题目4，我们就可以直接引用欧几里德算法辅助求最小公倍数。
算法：
输入：两个自然数m和n
else //在第3组查找，下标范围low+num1+num2~high
Coin(low + num1 + num2, high, num3);
}
第五章
第6题：
想法：
对于第6题，用分治法进行求解的话，若是采用循环赋值的方式，如果字符的个数和左移的位数成倍数关系，那么算法就比较容易实现，但是如果不成比例关系，算法写起来就比较麻烦，所以，我用了另一种方式，进行三次对称交换就可以完成算法。
if (n == 1) //递归结束的条件
return low + 1; //返回的是序号，即下标加1
if (n % 3 == 0) //3组硬币的个数相同
num1 = num2 = n / 3;
else
num1 = num2 = n / 3 + 1; //前两组有n / 3 + 1枚硬币
num3 = n - num1 - num2;
想法：
求两个数的乘积，根据已知提示可以采用俄式乘法，即是采用减治法将被乘数一直减小到1，同时将乘数以2倍的方式增大，同时将减去过程中产生的数累加最后一个求和
算法：
输入：两个正整数
输出:l两个数的乘积
1.构造一个俄式乘法函数fun（）
2.输入两个数，对两个数比较大小，将较小的数作为被乘数
3.判断被乘数的奇偶性，若是偶数则减半，若是技术则减1再减半
cout<<"出错了!您只能拿1—4根火柴:"<<endl;
else
{
n=n-j;
return fun(n);//递归调用函数
}
}
}
}
int main()
{
cout<<"请输入火柴根数:";
int n;
cin>>n;
if(n%5==0)
cout<<"放弃吧!在B不是傻瓜的情况下A输定了!"<<endl;
4.进行while循环做递归处理
5.返回最后的值
6.调用函数输出结果
程序：
//俄式乘法算法
#include<iostream>
using namespace std;
int fun(int a,int b)