算法设计与分析实验报告
实验名称统计数字问题评分
实验日期年月日指导教师
姓名专业班级学号
一.实验要求
1、掌握算法的计算复杂性概念。
2、掌握算法渐近复杂性的数学表述。
3、掌握用C++语言描述算法的方法。
4．实现具体的编程与上机实验，验证算法的时间复杂性函数。
二.实验内容
统计数字问题
1、问题描述
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9)
2、编程任务
给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9)
三.程序算法
将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。
四.程序代码
#include
int s[10]; //记录0~9出现的次数
int a[10]; //a[i]记录n位数的规律
void sum(int n,int l,int m)
{
if(m==1)
{
int zero=1;
for(int i=0;i<=l;i++) //去除前缀0
{
s[0]-=zero;
zero*=10;
}
}
if(n<10)
{
for(int i=0;i<=n;i++)
{
s[i]+=1;
}
return;
}//位数为1位时,出现次数加1
//位数大于1时的出现次数
for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1)
{
m=1;int i;
for(i=1;i m=m*10; a[t]=t*m; } int zero=1; for(int i=0;i { zero*= 10; } //求出输入数为10的n次方 int yushu=n%zero; //求出最高位以后的数 int zuigao=n/zero; //求出最高位zuigao for(i=0;i { s[i]+=zero; } //求出0~zuigao-1位的数的出现次数 for(i=0;i<10;i++) { s[i]+=zuigao*a[l]; } //求出与余数位数相同的0~zuigao-1位中0~9出现的次数 //如果余数是0,则程序可结束,不为0则补上所缺的0数,和最高位对应所缺的数 if(yushu==0) //补上所缺的0数,并且最高位加1 { s[zuigao]++; s[0]+=l; } else { i=0; while((zero/=10)>yushu) { i++; } s[0]+=i*(yushu+1);//补回因作模操作丢失的0 s[zuigao]+=(yushu+1);//补回最高位丢失的数目 sum(yushu,l-i-1,m+1);//处理余位数 } } void main() { int i,m,n,N,l; cout<<"输入数字要查询的数字:"; cin>>N; cout<<'\n'; n = N; for(i=0;n>=10;i++) { n/=10; } //求出N的位数n-1 l=i; sum(N,l,1); for(i=0; i<10;i++) { cout<< "数字"< } } 五.程序调试中的问题 调试过程中总是有这样那样的问题，通过一步步的修改，最终得以实现。 六.实验结果 盛年不重来，一日难再晨。及时宜自勉，岁月不待人。 算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程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 。 四、实验源代码 算法设计与分析（第二版）主编：吕国英 习题答案 第四章 1. #include for(i=1;i<=9;i++) { n=(n+2)*2; } printf("%d\n",n); return 0; } 3. #include 实验三分治算法（2） 一、实验目的与要求 1、熟悉合并排序算法（掌握分治算法） 二、实验题 1、问题陈述: 对所给元素存储于数组中和存储于链表中两中情况，写出自然合并排序算法. 2、解题思路: 将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序. 三、实验步骤 程序代码: #include int target[N],head[N],tail[N]; int i=0,n,m; for(; i 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号： 05 学生姓名：俞梦真 指导教师：郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 归式，就是如何将原问题划分成子问题。 2.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。 3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢（2）递归与非递归之间如何实现程序的转换？ （3）分析二分查找和快速排序中使用的分治思想。 答： 1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。 2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。 （4）分析二次取中法和锦标赛算法中的分治思想。 二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r 专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日 48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n 第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn) 证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1] 专业：J信息1101 学号：4111118002 姓名：彭倩 社会调查实验报告 在这次社会调查实验中，我了解到CATI,即计算机辅助电话访问（Computer Assisted Telephone Interview），是将近年高速发展的通讯技术及计算机信息处理技术应用于传统的电话访问所得到的产物,问世以来得到越来越广泛的应用。它是在加深对中国调查业的理解和对国外同类软件研究的基础上，自主开发了这套符合中国国情的系统。 CATI是具有高技术含量、高专业性和高实用性的电话调研产品。自20世纪70年代诞生以来，计算机辅助电话调查以其可控性高、时效性强等特点越来越为研究者所接受。在信息挂帅的今天，CATI系统更被视为收集资料、分析数据的利器，在商业、学术以及政府调研行为中得到了广泛应用。 从社会调查实验中，我们也可以了解到CATI项目整体业务流程如下： 通过利用CATI系统，我知道了计算机辅助电话访问就是用计算机为媒介设计问卷，用电话向被调查者进行访问。从而让计算机代替了问卷、答案纸和铅笔。通过计算机拨打所要的号码，电话接通之后，调查员就读出计算机屏幕上显示出的问答题并直接将被调查者的回答（用号码表示）用键盘记入计算机的记忆库之中。计算机会系统地指引整个业务流程。问卷可以直接在计算机中设计、调试，抽样过程可以大大简化，配额也完全由计算机系统自动控制，问卷执行时所有的问卷内部的流程和逻辑都有计算机内部控制，并且计算机会检查答案的适当性和一致性。 从中我感受到计算机收集数据的过程是自然的、平稳的，而且访问时间大大缩减，数据质量得到了加强，数据的录入等过程也不再需要，编码也可以统一的自动实现。由于回答是直接输入计算机的，关于数据收集和结果的阶段性的和最新的报告几乎可以立刻就得到。同时CATI可以提供更高效更全面透明的监控方式，所有的话务监控、通话录音、监听、监看都在一个独立的计算机上执行，大大减低了对访问过程的产生干扰的可能性。采用这种访问调查方式，具有调查内容客观真实、保密性强、访问效率高等特点。 在这次社会调查中，我深刻的感受到CATI在社会调查访问中具有强大的功能。 1、实效快。省去了传统调查所必须的印刷问卷、上门入户或邮寄问卷、审核问卷、数据录入等环节，在短时间内即可完成调查，访问结束后几十分钟内即可汇总数据，周期较短。 第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环） 若考虑其他语句，则没有这么多，可能就601倍。 第二章 32P 2-8.（1）画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 （3 ）画线语句的执行次数为 。O 。 （4）当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++， 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.（1）当1n ≥时，225825n n n -+≤，所以，可选5c =，01n =。 对于0n n ≥，22 ()5825f n n n n =-+≤，所以，22 582()n n n -+=O 。 （2）当8n ≥时，2222 582524n 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 ≥时，3 log log n n n <<，所以()20log 21f n n n n =+<，3 ()log 2g n n n n =+>。可选21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。 （2）当4n ≥时，2 log log n n n <<，所以2 2 ()/log f n n n n =<，2 2 ()log g n n n n =≥。可选1c =，04n =。对于0n n ≥，2 ()()f n n cg n <≤，即()(())f n g n =O 。 （3）因为log log(log )()(log ) n n f n n n ==，()/log log 2n g n n n n ==。当4n ≥时，log(log )()n f n n n =≥， 学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日 实验一：递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2018年10月10日16:00。 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： 【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 实验报告 实验思考题： 1、某调查员欲从某大学所有学生中抽样调查学生平均生活费支出情况，假设该调查员已经 完成了抽样，并获得样本情况（见样本文件），请根据此样本分别按性别、家庭所在地分层，并计算各层的样本量、平均生活费支出、生活费支出的方差及标准差。 （1）先对数据按照家庭所在地进行排序：【数据】→【排序】，选择“家庭所在地”（2）再对数据进行分类汇总：【数据】→【分类汇总】，“分类字段”选择“家庭所在地”，“汇总方式”选择“平均值”，“选定汇总项”选择“平均月生活费”，在对话框下方选择“汇总结果显示在数据下方”；再做两次分类汇总，“汇总方式”分别选择“计数”和“标准偏差”。最后得到表1-1所示结果： 表1-1 家庭所在地平均月生活费 大型城市平均值614.5348837 大型城市计数86 大型城市标准偏差300.0849173 乡镇地区平均值529.4117647 乡镇地区计数68 乡镇地区标准偏差219.0950339 中小城市平均值618.6440678 中小城市计数118 中小城市标准偏差202.5264159 总计平均值595.0367647 总计数272 总计标准偏差243.4439223 （3）在SPSS软件中得出的计算结果： 选择————，然后在出现的对话框中 分别在“Dependent list”框中选入“家庭所在地”，在“Independent List”框中选入“平均月生活费”，得到如表1-2所示结果： 表1-2 Report 平均月生活费 家庭所在地Mean N Std. Deviation 大型城市614.5386300.085 乡镇地区529.4168219.095 中小城市618.64118202.526 Total595.04272243.444 选择——，在出现的对话框中选择“function”选择估计量，得到如图1-2所示结果： 图1-1 图1-2 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; 3.3 3.3 经调查研究发现，家庭书刊消费受家庭收入及户主受教育年数的影响，表3.6为对某地区部分家庭抽样调查得到的样本数据。 表3.6 家庭书刊消费、家庭收入及户主受教育年数数据 （1）作家庭书刊消费（Y ）对家庭月平均收入（X ）和户主受教育年数（T ）的多元线性回归： 1 2 3 i i i i u Y X T βββ=+++ 利用样本数据估计模型的参数，对模型加以检验，分析所估计模型的经济意义和作用。 步骤： 1.打开EViews6，点“File ”→“New ”→“Workfile ”。选择 “Unstructured/Unda=ted ”在Observations 后输入18，点击ok 。 2. 在命令行输入：DATA Y X T，回车。将数据复制粘贴到Group中的表格中。 3. 建立数据关系图为初步观察数据的关系，在命令行输入命令：sort Y，从而实现数据Y的递增排序。 4. 在数据表“group”中点“view/graph/line”，最后点击确定，出现序列Y、X、T 的线性图。 5. OLS 估计参数,点击主界面菜单Quick\Estimate Equation ，弹出对话框，如下图。在其中输入Y c X T ，点确定即可得到回归结果。 ()()()()()() 2 2 50.01620.0864552.3703 49.46026 0.02936 5.20217 t= 1.011244 2.944186 10.067020.951235 =0.944732 F=146.2974 ?i i i X T Y R R =-++-= 经济意义：家庭月平均收入每增加1元，家庭书刊消费将增加0.08645 元。户主受教育年数每 算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序代码如下： #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 统计学实验报告 一、实验主题:大学生专业与实习工作的关系 二、实验背景: 二十一世纪的今天大学生已是一个普遍的社会群体，高校毕业人数日益增加，社会、企业所提供的职位日益紧张，大学生就业问题是当今社会关注的焦点。面对日益沉重的就业压力，越来越多的大学毕业生选择了企业需求的职业，而这种职业与自己在校所学专业根本“无关”或相去甚远，大学毕业生就业专业不对口的现象非常严重。专业对口是个广义的概念，就是说你所学的专业与你所作的工作相关，比如你专业是会计，工作后你到了一个企业做会计，或者到银行做柜员，这都是与经济相关的，这就是对口。如果你学机械设计，但工作后却做了统计员，业务员等于你所学专业无关的工作，这就叫专业不对口。专业不对口导致毕业生所学知识没有用武之地，所以这是一种人力资源的浪费。 三、实验目的: 大学生就业专业不对口是客观存在的问题，我们研究此问题有这几点目的:①了解当代大学生实习工作与专业是否对口的情况，当代大学生对工作与专业不对口现象的态度。②分析大学生就业结构和 专业对口问题，了解当今大学生专业对口情况，为以后大学生选择专业、选择工作岗位提供有效的信息和借鉴。③寻找导致专业不对口的原因，以减少社会普遍存在的人力资源的浪费。 四、实验要求:就相关问题收集一定数量的数据，用EXCEL进行如下 分析:1进行数据筛选、排序、分组;2、制作饼图并进行简要解释;3、制作频数分布图，直方图等并进行简要解释。 五、实验设备及材料:计算机，手机，EXCEL软件，WORD软件。 六、实验过程: (一)制作并发放调查问卷。 (二)收回并统计原始数据:收回了102名大学生填写的调查问卷，并对相关数据进行统计。 (三)筛选与实验相关问题: 1.您的性别( ): A. 男B.女 西安电子科技大学网络教育 2010学年上学期期末考试模拟试题一 一、 填空题（每小题4分，共计40分） 1. 通常只考虑三种情况下的时间复杂度，即 情况、 情况和 情况 下的时间复杂度，分别记为T max (N)、T min (N) 和T avg (N)，实践表明可操作性最好且最有实 际价值的是 情况下的时间复杂度。 2. n n 1032 的渐近表达式是 ， )log(3n 的渐近表达式是 。 3. 根据符号O 的定义易知O(1)=O(2)，用O(1)和O(2)表示同一个方法时，差别仅在于其中 的 。 4. 递归算法是指 的算法， 递归函数是指 的函数。 5. 贪心算法总是做出在当前看来_____________的选择，也就是说，贪心算法并不从整体最优考虑它 所做出的选择只是在某种意义上的________________。 6. 如果某问题具有________________________和___________________________两个重要性质，该问题可以用贪心算法求解。 7. 单源最短路径问题适合用_______________算法来求解、0-1背包问题适合用_____________算法来 求解。 8. 分治法是将一个规模为n 的问题分解为k 个规模________的子问题，这些子问题___________且与 原问题__________。递归地求解这些子问题，然后将各个子问题的解_________得到原问题的解。 9. 动态规划算法的两个基本要素是____________________和____________________。 10.___ 算法可以有效地解凸多边形最优三角剖分问题，而____________算法是求解最优 装载问题的有效方法。 二、简答题（每小题10分，共计40分） 1. 如果只需要求解问题的最优值，动态规划算法步骤是什么？如果需要构造最优解，则还需要加上什么步骤？ 2. 请简述什么是贪心选择性质 3. 请简述什么是最小生成树。 4. 请简述贪心算法比动态规划算法效率高的原因。 算法设计与分析实验报告 教师： 学号： 姓名： 实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 算法设计与分析(作业三)
算法设计与分析 吕国英 习题答案第四章
算法设计与分析实验三
算法设计与分析实验报告
算法分析与设计
算法设计与分析习题解答
社会调查实验报告
算法设计与分析C++语言描述(陈慧南版)课后答案
《算法设计与分析》实验一
抽样调查-分层抽样实验报告
《算法设计与分析》递归算法典型例题
最新版计量经济学实验报告
《算法设计与分析》实验报告
算法设计与分析实验报告 统计数字问题
南京邮电大学算法设计实验报告——动态规划法
统计学实验报告【最新】
算法设计与分析试题(三合一).(优选)
算法设计与分析实验报告
相关主题
文本预览