当前位置：文档库 › 算法分析与设计程序操作实现 2大作业

算法分析与设计程序操作实现 2大作业

实现操作者：08网本

分组：6组每组1道大作业。

所占分值：30分（百分制）

实现内容：

1 循环赛日程表

问题描述：设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：

①每个选手必须与其他n-1个选手各赛一次。

②每个选手一天只能参赛一次。

③循环赛在n-1天内结束。

请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行、第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n一1。

3-4个算法解决以上问题。

2 求3个数的最小公倍数

问题描述：对任给的3个正整数，求它们的最小公倍数。

看完题目，读者一定会回忆起：最小公倍数的定义以及用短除法求这3个数的最小公倍数，甚至想到了最大公约数与最小公倍数的换算公式……。其实，与问题相关的每一个经验和思路，都可能是解决这个问题的一种方法，下面就给出用这3种思路进行算法设计的过程。

3个算法解决以上问题。

3 猴子选大王

问题描述：不同于自然界猴子选大王的方式，这里的猴子是这样选举它们的大王的：17只猴子围成一圈，从某只开始报数1—2—3—1—2—3—…，报“3”的猴子就被淘汰，游戏一直进行到圈内只剩一只猴子，它就是猴大王了。

通过解决这个问题将使我们进一步认识算法与数据结构的紧密关系。

3-4个算法解决以上问题。

4 最大子段和问题

问题描述：给定n个整数(可能为负整数)a1,a2,a3,a4,a5，求形如：

A i,a i+1,……,a j, i、j=1,…,n, i<=j

的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。

例如，当(a1,a2,a3,a4,a5 ,a6)＝(-2，11，-4，13，-5，-2)时，最大子段和为：

∑==

i k

a20j＝2，j＝4(下标从1开始)

3-4个算法解决以上问题。

5 与利润无关的背包问题1

背包问题1：在9件物品中选出3件使其质量和与500克之差的绝对值最小。数据由键盘输入。

背包问题2：小明有一只能装10kg的背包，现有白菜一棵5kg，猪肉一块2kg，一条鱼3．5kg，白糖一袋1kg，菜油一桶5．1kg。请编写一个算法，使小明的背包所装东西的总质量最重。

背包问题3。

设有一个背包可以放人的物品质量为s，现有n件物品，质量分别为w1,w2,...,w n.

问：能否从这n件物品中选择若干件放人此背包，使得放人的质量之和正好为s?如果存在一种符合上述要求的选择，则称此背包问题有解(或称解为“真”)，否则此问题无解(或称解为“假”)。

6 与利润有关的背包问题

复杂一些的背包问题除了要考虑背包的总容量，还要考虑所装物品的最高利润，这样的问题可能更符合实际，但解决起来也就更复杂一些。当然题目中的背包可以理解为汽车等装运工具。

背包问题4：一个商人带着一个能装m kg的背包去乡下收购货物，准备将这些货物卖到城里获利。现有n种货源，且知第i种货物有w i kg，可获利p i元。请编写算法帮助商人收购货物，以获取最高的利润。

背包向题5：0／1背包问题：题目同例6-4，只是约定物品不允许拆零。

回溯搜索解0/1背包问题。

上一个算法只给出了最大利润的值，而没有给出最大利润下背包所装物品的方案。下面除了通过回溯算法改进上一个算法的效率，还实现了给出背包所装物品方案的功能。

7 资源分配问

算法设计与分析(作业三)

算法设计与分析实验报告学院信息科学与技术学院专业班级软件工程3班学号 20122668 姓名王建君指导教师尹治本 2014年10月

实验四矩阵相乘次序一、问题提出用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。（3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。二、求解思路本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况：（1）只有一个矩阵，则只需打印出A1；（2）有两个矩阵，则需打印出（A1A2）；（3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。三、算法复杂度该算法时间复杂度最高为）（n 3 O 。四、实验源代码

《C程序设计》作业内容

实验一C语言的运行环境的使用一、目的与要求 1. 了解Windows系统下C语言的运行环境，熟悉C程序调试、运行的基本操作方法。 2. 熟练掌握编辑、编译、连接和运行C程序的方法。 3. 通过运行简单的C程序，初步了解C源程序的特点。 4. 初步理解C语言的数据类型，了解变量定义、变量赋值以及简单运算方法，了解程序运行结果的基本输出方法。二、实验例题在C语言运行环境下，按以下例题要求完成程序的编辑、编译、连接和运行，直至取得正确的运行结果。【例1】编程实现在屏幕上显示如下三行文字 Hello, world ! Wolcome to the C language world! Everyone has been waiting for. （1）输入如下程序： #include int main() { printf("Hello,World!\n"); printf("Wolcome to the C language world!\n"); printf("Everyone has been waiting for.\n"); return 0; } （2）将输入的程序以文件名example.c存盘。（3）编译：通过“组建”(Build) 下拉菜单中的“编译”（compile）命令，编译example.c，若出现编译错误，则修改程序，重新编译，直至编译成功，系统自动生成目标文件example.obj。（4）连接：通过“组建”（Build）下拉菜单中的“组建”（Build）命令，生成以.exe为扩展名的可执行文件example.exe。（5）运行：通过“组建”菜单下的“执行”（Excute）命令运行程序并观察运行结果。【例2】编写程序，将两个整数相加，并输出结果。 #include int main() { int a,b,sum; a=123;b=456; sum=a+b; printf(“sum is %d\n”,sum); return 0;}

C语言程序设计大作业报告模板

《C语言程序设计》大作业报告 1.目的掌握所学C语言程序设计的方法，熟悉所学语言的开发环境及调试过程，熟悉所学C语言中的数据类型，数据结构、语句结构、运算方法，巩固和加深对理论课中知识的理解，提高学生对所学知识的综合运用能力。通过综合设计要求达到下列基本技能： 1．培养查阅参考资料、手册的自学能力，通过独立思考深入钻研问题，学会自己分析、解决问题。 2．通过对所选题目方案分析比较，确立方案，编制与调试程序，初步掌握程序设计的方法，能熟练调试程序。 2.作业内容

熟练掌握所学语言的基本知识：数据类型（整形、实型、字符型、指针、数组、结构等）；运算类型（算术运算、逻辑运算、自增自减运算、赋值运算等）；程序结构（顺序结构、判断选择结构、循环结构）；大程序的功能分解方法（即函数的使用）等。进一步掌握各种函数的应用等。 3.要求： 1.要求每个同学都要认真对待，积极参与。 2.独立完成，不能抄袭。 3.课程设计结束时每位同学必须完成《大作业报告册》，其中包含设计源代码和设计思路。 4.不符合要求的程序、设计报告、抄袭的设计报告或源程序代码、在设计中完全未参与的将作不及格处理。 5.统一格式，A4打印，按时提交。 4.题目：设计要求：编写一个程序，求3x4数组的转置矩阵。要求在main函数里面读数，在change函数里面把矩阵转置。 5.程序设计设计思路：1是先定义两个数组，一个是a[3][4],另一个是b[4][3]。2是将随便输入的12个数输入到a[3][4]。3是在change函数中将a[3][4]中值通过for循环的镶嵌将数组a[3][4]的值赋值给数组b[4][3]。4在主函数中将数组b[4][3]通过for循环的嵌套输出。代码

算法分析与设计作业及参考答案样本

《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成绩记入课程总成绩。客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A )

A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法

C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:

算法分析与设计实验报告

算法设计与分析学院：计算机科学与技术学号：129074106 姓名：张淼淼 2014 11 14

1、当问题规模100 N 时，快速排序和插入排序各需多少时间？写清机器配置，列出五种快速排序所需时间(ms) 插入排序所需时间（ms ）两者相差多少 N=100 0.00600 0.019000 -0.013000 N=1000 0.074000 0.724000 -0.650000 N=10000 0.032000 64.657000 -64.625000 N=100000 13.300000 50.900000 -37.600000 N=1000000 53.500000 117.700000 -64.200000 Window 7 32位 Cpu ：Inter(R) Core(TM) i3-2120 cpu@3.30GHz AMD Radeon HD 6450 Graphics

程序： #include #include #include #include int a[1000000];

int b[1000000]; void QuickSort(int low ,int high) { long i,j; int x; i=low; j=high; x=a[i]; while(i=x&&i(j+1)) QuickSort(j+1,high); } void BinaryInsertSort(int length) { int low,high,mid; int i,j,m;//m为保存待插入的元素 for(i=1;i=b[mid]) low=mid+1; else high=mid-1; } for(j=i-1;j>=high+1;j--)//high为插入位置 b[j+1]=b[j];//后移元素，留出插入的空位b[high+1]=m;//将元素插入正确的位置 }

C语言程序设计作业参考答案

《C语言程序设计》作业参考答案作业一 C语言概述一、选择题： 1-5 ACDCB 二、编程题： main() { printf(“****************************************\n”); printf(“ Hello,world! \n”); printf(“****************************************\n”); } 作业二程序的灵魂——算法一、填空题： 1.确定性有效性有零个或多个输入有一个或多个输出 2.顺序结构选择结构循环结构 3.函数作业三数据类型、运算符与表达式一、选择题： 1-5 BDDAB 6-10 BCAAB 11-15 BCADC 16-20 DACCA 21-25 ADDBA 26-30 DDDDD 作业四顺序结构一、选择题： 1-5 BCDDD 6-10 BDADD 二、填空题： 1.【31.415920,3.14159e+01】 2.【c=k】 3.【a=1,b=空格,c=2】 4.【a=12,b=345】 5.【c=A】作业五选择结构一、选择题：1-5 ADCBC 6-10 BBBBA 11-15 DBAAC 16-17 CB 二、填空题： 1.【-1】 2.【3】 3.【4】 4.【11】 5.【97或'a'】作业六循环结构一、选择题： 1-5 CBAAC 6-10 CBCCB 11-15 DBDDB 16-20 BCAAC 21-25 CDBBB

作业七数组一、选择题： 1-5 CDDAC 6-10 CCDBC 11-15 DDBCA 16-20 DCBDD 21-23 BDB 二、填空题： 1. LBLMNP 2. SW* 3. mo 4. a=2，b=1 作业八函数一、选择题： 1-5 AAACA 二、填空题： 1.【编程中的main( )函数】 2.【函数说明部分】和【函数体】 3.【–125= –5*5*5】 4.【void add (float a, float b)】【float add (float a, float b)】 5.【i=7; j=6; x=7 i=2; j=7; x=5】 6.【111】三、编程题： 1.参考代码 main() { int score,temp,log; char grade; log=1; while (log) { printf(“enter score:”); scanf(“%d”,&score); if ((score>100)||(score<0)) printf(“\n error,try again! \n”); else log=0; } if (score==100)temp=9; else temp=(score-score%10)/10; switch(temp) { case 0:case 1:case2: case 3:case 4:case 5:grade=’E’;break; case 6:grade=’D’;break; case 7:grade=’C’;break; case 8:grade=’B’;break; case 9:grade=’A’; } printf(“score=%d,grade=%c\n”,score,grade); } 2.解：设计以高度n为参数的函数trangle(int n),打印等边三角形。参考程序如下： #include

计算机算法设计与分析

算法设计与分析实验报告班级：姓名：学号： (备注：共给出5个参考实验案例，根据学号尾数做对应的实验，即如尾号为1，则模仿案例实验123；尾号2，则模仿案例实验234；尾号3，即345；尾号4，同1.)

目录实验一分治与递归 (1) 1、基本递归算法 (1) 2、棋盘覆盖问题 (2) 3、二分搜索 (3) 4、实验小结 (5) 实验二动态规划算法 (5) 1、最长公共子序列问题 (5) 2、最大子段和问题 (7) 3、实验小结 (8) 实验三贪心算法 (8) 1、多机调度问题 (8) 2、用贪心算法求解最小生成树 (10) 3、实验小结 (12) 实验四回溯算法和分支限界法 (12) 1、符号三角形问题 (12) 2、0—1背包问题 (14) 3、实验小结 (18) 实验五多种排序算法效率比较 1、算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等 (19) 2、实验小结 (18)

P art1：课程设计过程设计选题--→题目分析---→系统设计--→系统实现--→结果分析---→撰写报告 P art2：课程设计撰写的主要规范 1.题目分析：主要阐述学生对题目的分析结果，包括题目描述、分析得出的有关模型、相关定义及假设； 2.总体设计：系统的基本组成部分，各部分所完成的功能及相互关系； 3.数据结构设计：主要功能模块所需的数据结构，集中在逻辑设计上； 4.算法设计：在数据结构基础上，完成算法设计； 5.物理实现：主要有数据结构的物理存储，算法的物理实现，系统相关的实现。具体在重要结果的截图，测试案例的结果数据，核心算法的实现结果等； 6.结果分析：对第五步的分析，包括定性分析和定量分析，正确性分析，功能结构分析，复杂性分析等； 7.结论：学生需对自己的课程设计进行总结，给出评价，并写出设计体会； 8.附录：带有注释的源代码，系统使用说明等； 9.参考文献：列出在撰写过程中所需要用到的参考文献。

C程序设计作业样本

第一章作业答案：一，59，14.4，28.e 二1小题，59 2，15 一、将数89、20.25、40.875用十六进制表达二、填空 1.在C语言中，数值常量0x3b十进制值是。 2.字母f ASCII码为十进制数___________。第三章作业一、选取题： 1、下列变量名中， B 是非法。 A) Tom B) 3n C) little_boy D) c10 2、若有如下类型阐明 char a; int b; float c; double d;则表达式a*b+d-c成果类型是（A ） A）float B）char C）int D）double 3、若x为整型，则逗号表达式(x=4*5,x*5),x+25成果及x值分别是（C ）对的答案是100，45 A）45 20 B）125 20 C）125 45 D）100 100 4、假设所有变量均为整型，则表达式(a=3,b=2,b++,a+b)值是 C 。 A) 5 B) 8 C) 6 D)7 5、已知c2为字符型，则执行语句c2=’E’+’8’-‘A’后，c2值为 C 。 A) 12 B) 11 C)不拟定值D) 10

6、设a为double变量，b为int型变量，c为字符型变量，则a+b+c为( C )型 A) int B) float C) double D) char 7、Ｃ语言中不可用作标记符字符有( C ) A下划线 B % C数字 D字母 8、下面四个选项中，均是合法整型常量是（D ） A）160 B）- 0xcdf C）- 01 D）0x - 0xffff 01a 0668 2e5 9、设a为字符变量，b为int型变量，c为double型变量，则a*b+c为( C )型 A. int B. float C. double D. char 10.若a是int型变量，则表达式(a=4*5,a*2),a+4值为（ C ） A. 20 B.22 C. 24 D. 44 第四章作业一、选取题 1、若x为int型变量，则执行如下语句后x= C 。 x=5; x-=x-=x+x; A. -10 B. -5 C.0 D.10 2、在printf()函数格式阐明符中，字符型数输出格式阐明符是 D 。

C语言课程设计大作业62994

郑州大学课程报告课程名称：C语言程序设计专业班级：（15）班学生姓名：谢* 学号： 20127611*** 任课教师：赵** 学期： 2012-2013-2 课程报告任务书

开发一个通讯录管理系统，基本信息包括：编号、姓名、性别、出生年月、固定电话、手机号、电子邮件等基本信息（也可以根据自己情况进行扩充）。使之能提供以下基本功能：（1）通讯录等信息录入功能(注：数据等要求用文件保存)－－输入（2）通讯录信息的浏览功能－－输出（3）查询功能(至少一种查询方式)、排序功能(至少一种排序方式)： ①按电话号码进行查询②按姓名查询等③按照年龄排序④按姓名排序等（4）通讯录条目的删除与修改等扩展功能：可以按照自己的程度进行扩展。比如（1）简单的权限处理（2）报表打印功能（3）模糊查询，如姓张的人员等；或者给定电子邮件的部分进行查询等（4）给定指定年龄范围之内的查询等等。总之，可以根据自己需求进行分析功能，成绩评定按照难度进行区分。成绩评定教师：

一. 需求分析 1,具有数据的插入、修改、删除、显示和查询功能的电话簿管理程序。 2,数据包括：人名、工作单位、电话号码和E-MAIL地址。 3,可对记录中的姓名和电话号码进行修改。 4,可增加和删除记录。 5,可显示所有的保存记录。 6,可按人名或电话号码进行查询。分析建议采用结构体数组和文件系统实现。结构体成员包括人名、工作单位、电话号码和E-MAIL地址。根据题目的要求程序应该采用结构体数组和文件系统实现。应该有文件的操作功能；在程序中应该包括输入、显示、删除、查询、添加、修改、保存、加载和退出的功能。二、概要设计 (1)．程序的模块组成及各个函数的功能：程序的模块组成：主函数：main(); 输出数据函数：printf(); 读取数据函数：scanf(); 显示记录函数：Display(); 删除记录函数：shanchu(); 查找记录函数：chaxun(); 自定义清屏函数：system(“cls”); 自定义输入函数：input(); 字符输入函数：getchar(); 修改数据函数：xiugai(); 保存数据函数：baocun(); 排序数据函数：paixu(); 各函数的主要功能：

c程序设计作业

1、分析下面程序： # include int main() { char c1,c2； c1=97; c2=98; printf("c1=%c,c2=%c\n"c1,c2); printf("c1=%d,c2=%d\n",c1,c2); return 0; } （1）运行时会输出什么信息？为什么？（2）如果将程序第4,5行改为 c1=197; c2=198; 运行时会输出什么信息？为什么？（3）如果将程序第3行改为 int c1,c2; 运行时会输出什么信息？为什么？答：（1）程序运行不了，因为程序存在错误。正确的程序为：#include int main() { char c1,c2; c1=97; c2=98; printf("c1=%c,c2=%c\n",c1,c2); printf("c1=%d,c2=%d\n",c1,c2); return 0; } （2）如果将程序第4,5行改为 c1=197; c2=198; 运行时会输出：（3）如果将程序第3行改为 int c1,c2; 运行时会输出：

因为int表示整型，%c是输出字符，a的ASCLL代码是97，b的是98，所以输出 c1=a,c2=b.%d是表示输出十进制整型，所以输出c1=97,c2=98 2、用下面的scanf函数输入数据，使a=3，b=7，x=8.5，y=71.82，c1=’A’,c2=’a’。问在键盘上如何输入？ #include int main() { int a,b; float x,y; char c1,c2; scanf("a=%db=%d",&a,&b); scanf("%f%e",&a,&y); scanf("%c%c",&c1,&c2); return 0; } 答：输入如图：输出如图：（此文档部分内容来源于网络，如有侵权请告知删除，文档可自行编辑修改内容，供参考，感谢您的配合和支持）

《算法分析与设计》作业参考答案

《算法分析与设计》作业参考答案作业一一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。二、简答题： 1.算法需要满足哪些性质？简述之。答：算法是若干指令的有穷序列，满足性质：（1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令清晰、无歧义。（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。答：将递归算法转化为非递归算法的方法主要有：（1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。（3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j]

《算法分析与设计》实验指导书

《计算机算法设计与分析》实验指导书（第一版）

前言计算机算法分析与设计是面向设计的，它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。开发环境不限，本书采用C/C++语言的集成开发环境等。实验完成后书写实验报告，包含实验问题、基本思想、关键算法流程图、测试数据及运行结果（截图）、调试心得和源程序。总实验学时为16学时。

目录预备实验验证算法的方法 (4) 实验目的： (4) 实验课时： (4) 实验原理： (4) 实验题目： (6) 基本题： (6) 提高题： (6) 实验一递归与分治 (7) 实验目的： (7) 实验课时： (7) 实验原理： (7) 实验题目： (7) 基本题： (7) 提高题： (8) 思考问题： (8) 实验二动态规划算法 (9) 实验目的： (9) 实验课时： (9) 实验原理： (9) 实验题目： (9) 基本题： (9) 提高题： (10) 思考问题： (10) 实验三贪心选择算法 (11) 实验目的： (11) 实验课时： (11) 实验原理： (11) 实验题目： (11) 基本题： (11) 提高题： (12) 思考问题： (12) 实验四回溯算法 (13) 实验目的： (13) 实验课时： (13) 实验原理： (13) 实验题目： (14) 基本题： (14) 提高题： (14) 思考问题： (14)

C语言程序设计-作业与答案

《C 语言程序设计》课程作业适用层次：专升本培养类型：理工科专业专业班级：姓名：学号：作业要求：题目可打印，答案要求手写，考试时交作业。第1次： 1．编写程序，分别计算1到100之间的奇数之和及偶数之和，并输出。 2．输入三角形的三条边a 、b 、c ，如果能构成一个三角形，则计算并输出三角形的周长和面积（结果保留两位小数）；否则输出“无效的边长！”。三角形面积计算公式为： s=))()((c x b x a x x ---，其中，x=(a+b+c)/2。 3．输入一个整数，求它的各位数字之和。例如，123的各位数字之和为6，-63的各位数字之和为9。 4．使用格里高利公式求π的近似值，精确到最后一项的绝对值小于10-6 。 +-+-=71 513114π …… 5．中国古代数学史上著名的“百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问翁、母、雏各几何？ 6．编写程序，键盘输入正整数n （0= 2 2. 编写一个函数prime(int n)，判断一个整数是否是素数，若是素数，函数值返回1，否则返回0。利用该函数找出100-200之间的所有素数。素数是只能被1和自身整除的正整数，2是最小的素数。 3．写一函数int strlength(char *s)求一个字符串的长度。主函数中输入一个字符串，调用函数strlength 求其长度并输出。

算法分析与设计(线下作业二)

《算法分析与设计》学习中心：专业：学号：姓名：

作业练习二一、名词解释 1、MST性质 2、子问题的重叠性质递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。二、简答题 1、简述动态规划算法求解的基本要素。答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。

3、贪心算法求解的问题主要具有哪些性质简述之。答：贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个基本要素；另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。

算法分析与设计实验报告

实验一、归并排序及各种排序算法性能比较一、实验实习目的及要求了解归并排序等各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证。二、实验实习设备（环境）及要求（软硬件条件）计算机eclipse软件，执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明) 项目：对10 4 6 3 8 2 5 7进行从小到大排序，采用几种排序方法，并统计这几种方法的运行时间，与归并排序比较。内容及步骤： (1)归并排序：将序列每次分成两组，再进行合并，直到递归完成； 1、递归调用mergeSort对数组排序 2、merge将两个有序数组合并为一个有序数组

3、主函数调用mergeSort对数组排序 4、统计时间 (2) 选择排序：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后只有一个元素时结束；也可选择当前最大的并与当前的相对的最后一个元素交换，直到最后只有一个元素时结束。

1、数组长度为n，需要选择n-1次；每次选择完成后，将数组中的最大值与最后一个元素互换，调用java.util包中Arrays类。 2、主函数调用ChooseSort对数组排序。 3、统计运行时间。 (3)插入排序：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当所有的元素插入完毕时，就排好序了； 1、从第二个元素开始，与之前序列比较，插入到合适的位置。

2、主函数调用sort对数组排序。 3、统计运行时间 (4) 快速排序：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右边比它大，然后对左右两边进行递归； 1、选取一个基准位，从右边向左边看，找比基准位小的元素，再从左边向右边看，找比基准位大的元素，若两者均存在则交换；若两者相遇，则相遇元素与基准位元素交换，然后递归排序左右半数组。

C语言大作业学生信息管理系统

《程序设计综合课程设计》报告学生姓名： ______ ______ ______ ______________________ 学生班级： ______________________ ____________ ____________ 学生学号： ____________ 指导教师： ______ 2014年6 月 22 日

目录前言 (2) 第1章Visual C++6.0简介及其优点 (3) 第2章课程设计的目的和要求 (4) (4) 2.2课程设计的要求 (5) 第3章课程设计任务内容 (6) 3.1 需求分析 (6) 3.2可行性分析 (6) 第4章软件使用说明 (7) 第5章总结 .................................................. 错误!未指定书签。附录源程序学生信息管理系统前言学生信息档案的管理对于学校的管理者来说至关重要，学生信息是高等学校非常重要的一项数据资源，是一个教育单位不可缺少一部分。特别是近几年来，国家政策的调整，我国高等院校大规模的扩招，给高等院校的教学管理、学生管理、后勤管理等方面都带来不少的冲击。其包含的数据量大，涉及的人员面广，而且需要及时更新，故较为复杂，难以单纯地依靠人工管理，而且传统的人工管理方式既不易于规范化，管理效率也不高，目前我国各类高等院校中还有相当一部分学生档案管理还停留在纸介质的基础上，尤其是中、小学对学生档案的管理更是落后，这样的管理机制已经不能适应时代发展的要求，其管理方法将浪费许多人力和物力。随着科学技术的不断提高，计算机科学与技术日渐成熟，计算机应用的普及已进入人类社会生活的各个领域，并发挥着越来越重要的作用。这种传统的手工管理模式必然被以计算机为物质基础的信息管理方法所取代。作为计算机应用的一部分，使用计算机对学生档案进行管理，有着手工管理所无法比拟的优点，如：检索迅速、查找方便、可靠性高、存储量大、保密性好、寿命长、成本低等。这些优点能够极大地提高学生档案管理的效率，也是学校向科学化、正规化管理发展的必要条件，更是各个高等院校与世界接轨的重要条件。

算法分析与设计实验二哈夫曼编码

昆明理工大学信息工程与自动化学院学生实验报告（201 —201 学年第一学期）课程名称：算法设计与分析开课实验室：年月日一、上机目的及内容 1.上机内容设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）证明哈夫曼树满足最优子结构性质；（2）设计贪心算法求解哈夫曼编码方案；（3）设计测试数据，写出程序文档。数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树

程序流程图：

三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件四、实验方法、步骤（或：程序代码或操作过程）程序代码： #include #include #include typedef struct { unsigned int weight; unsigned int parent,LChild,RChild; } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0 && i!=(*s1)) { min=i; break; }

算法分析与设计程序操作实现 2大作业

算法设计与分析(作业三)

《C程序设计》作业内容

C语言程序设计大作业报告模板

算法分析与设计作业及参考答案样本

算法分析与设计实验报告

C语言程序设计作业参考答案

最新算法分析与设计作业(一)及参考答案讲课讲稿

计算机算法设计与分析

C程序设计作业样本

C语言课程设计大作业62994

c程序设计作业

《算法分析与设计》作业参考答案

《算法分析与设计》实验指导书

C语言程序设计-作业与答案

算法分析与设计(线下作业二)

算法分析与设计实验报告

C语言大作业学生信息管理系统

算法分析与设计 实验二 哈夫曼编码

算法分析与设计实验二哈夫曼编码