文档库 最新最全的文档下载
当前位置:文档库 › 伪造硬币问题+找零钱问题

伪造硬币问题+找零钱问题

伪造硬币问题+找零钱问题
伪造硬币问题+找零钱问题

1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法,并计算其时间复杂度。

(1)源程序:

#include

#include

#include

int findTheCoin(int q[],int a,int b);

int quantity(int q[],int a,int b);

void main()

{

time_t ts;

srand((unsigned) time(&ts));

const int Max=70;

int n,k;

while(true)

{

cout << "请输入硬币的个数"<< endl;

cin >> n;

int q[Max];

int i;

for( i=1;i<=n;i++)

{

q[i]=2;

}

k=rand()%n;

if(k==0)

k=n;

q[k]=1;

cout<<"随机产生的硬币排列顺序"<

for(i=1;i<=n;i++)

{

cout<

if(i%5==0)

cout<

}

cout<

int p=findTheCoin(q,1,n);

cout<<"伪造硬币的位置:"<

cout<<"======================="<

}

}

int quantity(int q[],int a,int b)

{

int total=0;

int i;

for( i=a;i<=b;i++)

total+=q[i];

return total;

}

int findTheCoin(int q[],int a,int b)

{

if(a==b)

return a;

int n=b-a+1;

int c=n%3;

int m=a+n/3-1;

int d;

switch(c)

{

case 0:

if (quantity(q,a,m)==quantity(q,m+1,m+n/3))

{

d=findTheCoin(q,m+n/3+1,m+2*(n/3));

return d;

}

else if (quantity(q,a,m)==quantity(q,m+n/3+1,m+2*(n/3)))

{

d=findTheCoin(q,m+1,m+n/3);

return d;

}

else

{

d=findTheCoin(q,a,m);

return d;

}

//break;

case 1:

if( (quantity(q,a,m)==quantity(q,m+1,m+n/3)) && (quantity(q,m+n/3+1,m+2*(n/3))==quantity(q,m+1,m+n/3)) )

return m+2*(n/3)+1;

else

{

if (quantity(q,a,m)==quantity(q,m+1,m+n/3))

{

d=findTheCoin(q,m+n/3+1,m+2*(n/3));

}

else if (quantity(q,a,m)==quantity(q,m+n/3+1,m+2*(n/3)))

{

d=findTheCoin(q,m+1,m+n/3);

return d;

}

else

{

d=findTheCoin(q,a,m);

return d;

}

}

//break;

case 2:

if(q[m+2*(n/3)+1]==q[m+2*(n/3)+2])

{

if (quantity(q,a,m)==quantity(q,m+1,m+n/3))

{

d=findTheCoin(q,m+n/3+1,m+2*(n/3));

return d;

}

else if (quantity(q,a,m)==quantity(q,m+n/3+1,m+2*(n/3)))

{

d=findTheCoin(q,m+1,m+n/3);

return d;

}

else

{

d=findTheCoin(q,a,m);

}

}

else

{

if(q[m+2*(n/3)+2]==q[1])

return m+2*(n/3)+1;

//cout<<"伪造硬币的号码是"<<3*m+1<

else

return m+2*(n/3)+2;

//cout<<"伪造硬币的号码是"<<3*m+2<

}

}

//return true;

}

(2)运行结果

2.【找零钱问题】一个小孩买了价值为33美分的糖,并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。

(1)源程序:

#include

#include

int makeChange(int money,int coin25,int coin10,int coin5,int coin1)

{

int i=0,j=0;

while(money)

{

if(money>=25)

{

i=money/25;

if(i<=coin25)

{

money=money-25*i;

j+=i;

cout<<"需要25美分"<

}

else

{

money=money-25*coin25;

j+=coin25;

cout<<"需要25美分"<

}

}

if(money>=10)

{

i=money/10;

if(i<=coin10)

{

money=money-10*i;

j+=i;

cout<<"需要10美分"<

}

else

{

money=money-10*coin10;

j+=coin10;

cout<<"需要10美分"<

}

}

if(money>=5)

{

i=money/5;

if(i<=coin5)

{

money=money-5*i;

j+=i;

cout<<"需要5美分"<

}

else

{

money=money-5*coin5;

j+=coin5;

cout<<"需要5美分"<

}

}

if(money>=1)

{

i=money/1;

if(i<=coin1)

{

money=money-1*i;

j+=i;

cout<<"需要1美分"<

}

else

{

cout<<"!!!!!!!!!!!!!!!!!!!!!!!"<

cout<<"! 零钱不够,无法找零! !"<

cout<<"! 请退出后重新操作! !"<

cout<<"!!!!!!!!!!!!!!!!!!!!!!!"<

return 0;

}

}

}

cout<<"共需要"<

return 1;

}

void main()

{

int money,smoney,ymoney;

int coin25,coin10,coin5,coin1;

cout<<"欢迎使用,按0可退出!"<

cout<<"请输入各面值硬币的个数:"<

cout<<"25美分个数:";

cin>>coin25;

cout<<"10美分个数:";

cin>>coin10;

cout<<"5美分个数:";

cin>>coin5;

cout<<"1美分个数:";

cin>>coin1;

while(true)

{

cout<<"应收:";

cin>>ymoney;

if(ymoney==0)

break;

cout<<"实收:";

cin>>smoney;

money=smoney-ymoney;

cout<<"您要找"<

if(money==0)

continue;

makeChange(money,coin25,coin10,coin5,coin1);

cout<<"==========================="<

}

}

(2)运行结果

贪心算法经典例题

贪心算法经典例题 发布日期:2009-1-8 浏览次数:1180 本资料需要注册并登录后才能下载! ·用户名密码验证码找回密码·您还未注册?请注册 您的账户余额为元,余额已不足,请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。 从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌(NOIP2002tg) [问题描述] 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为: ①9 ②8 ③17 ④ 6 移动3次可达到目的: 从③取 4 张牌放到④(9 8 13 10) -> 从③取 3 张牌放到②(9 11 10 10)-> 从②取 1 张牌放到①(10 10 10 10)。 [输入]:键盘输入文件名。 文件格式:N(N 堆纸牌,1 <= N <= 100) A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输出]:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in: 4 9 8 17 6 屏慕显示:3 算法分析:设a[i]为第i堆纸牌的张数(0<=i<=n),v为均分后每堆纸牌的张数,s为最小移到次数。 我们用贪心法,按照从左到右的顺序移动纸牌。如第i堆(0

软件测试实验报告

桂林航天工业学院课程设计报告 课程名称:软件测试 姓名: 专业: 学号:2011025201

实验一黑盒测试 一.实验目的 (1)能熟练应用黑盒测试技术进行测试用例设计; (2)对测试用例进行优化设计; 二.实验要求与内容 运用等价类划分和边界值分析测试技术设计测试用例。 1.三角形问题的边界值分析测试用例 在三角形问题描述中,除了要求边长是整数外,没有给出其它的限制条件。在此,我们将三角形每边边长的取范围值设值为[1, 100] 。在三角形问题中,有四种可能的输出:等边三角形、等腰三角形、一般三角形和非三角形。利用这些信息能够确定下列输出(值域)等价类。 R1 = { : 边为a,b,c的等边三角形 } R2 = { : 边为a,b,c的等腰三角形 } R3 = { : 边为a,b,c的一般三角形 } R4 = { : 边为a,b,c不能组成三角形 } 程序代码: #include"iostream" using namespace std; void main() { int a,b,c; cout<<"请输入三个整数:"<>a>>b>>c; if((a>=1&&a<=100)&&(b>=1&&b<=100)&&(c>=1&&c<=100)) { if((a+b-c<=0)||(a+c-b<=0)||(b+c-a<=0)||(a==0)||(b==0)||(c==0)) cout<<"不是三角形"<

人教统编版四年级上学期语文第27课《故事二则》同步练习C卷

人教统编版四年级上学期语文第27课《故事二则》同步练习C卷 姓名:________ 班级:________ 成绩:________ 小朋友,带上你一段时间的学习成果,一起来做个自我检测吧,相信你一定是最棒的! 一、基础达标 (共7题;共50分) 1. (8分)选词填空 A.关心 B.热心 C.耐心D、专心 (1)老师布置的事情,陈华总是十分________地去做。 (2)张小军把班级当成了自己的家,被评为________集体的“好少年”。 (3)他对同学很________,谁有了困难,他都尽力去帮助。 (4)同学有不懂的问题向他请教,他总是________地讲解。 2. (10分)按要求填一填。 (1)“山”的笔顺是________,共________笔,第二笔是________。 (2)“火”的笔顺是________,共________笔,第二笔是________。 (3)“耳”的笔顺是________,共________笔,第二笔是________。 (4)“里”共有________笔,第五笔是________。 (5)照样子,写出反义词。 例:多——少 上——________ 小——________ 男——________ 关——________ (6)写出带有下面笔画的字。

________________________________(7)比一比,再组词。 了________ 日________ 田________ 人________ 子________ 目________ 口________ 大________ 3. (2分)加偏旁组字再组词(至少有一个字是本课出现的) 昔 ________ ________ ________ ________ 甬 ________ ________ ________ ________ 责 ________ ________ ________ ________ 采 ________ ________ ________ ________ 4. (3分)认真填写,再仔细读一读。 “横七竖八”指的是________,带有“七、八”的成语有________。 5. (10分)比一比,组词语。 汤________ 争________ 轮________ 邦________烫________ 睁________ 抡________ 绑________扬________ 挣________ 伦________ 帮________ 6. (2分)比一比,再组词。 冒________ 荆________ 挤________ 采________ 昌________ 刺________ 剂________ 睬________ 察________ 邦________ 汤________ 场________ 蔡________ 绑________ 烫________ 肠________

算法设计实验_贪心算法背包问题

《算法分析与设计》 课程实验 专业年级:信息与计算科学 学生学号: 学生姓名: 实验题目:用贪婪法求解背包问题 指导老师: 实验时间:20xx年xx月x日 一、实验内容 用贪婪法求解背包问题 要求:用非递归实现 二、实验步骤 2.1、理解算法思想和问题要求; 2.2、写出每个操作的算法 非递归算法: greedbag() { int N; int c;

int[] w; int[] v; Scanner scan=new Scanner(System.in); System.out.print("输入背包的容量:"); c=scan.nextInt(); System.out.print("输入物品的数量:"); N=scan.nextInt(); System.out.print("分别输入物品的价值:"); v=new int[N]; for(int i=0;i

贪心算法0-1背包问题(算法实验代码)

实验三、0-1背包问题(贪心算法) 实验代码: #include int max(int a,int b) { if(a>b) return a; else return b; } void Knapsack(int *v,int *w,int *x,int c,int n, int m[8][100]) { int i,j; for(j=0;j=1;i--) { for(j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } for(i=1;i

printf("物品总数为:7\n"); printf("物品重量和价值分别为:\n"); printf("\n重量价值\n"); for (i=1;i<=n;i++) printf("%d %d \n",w[i],v[i]); int m=15; int array[8][100]={0}; Knapsack(v,w,x,m,7,array); printf("背包能装的最大价值为: %d\n",array[1][m]); printf("贪心算法的解为: "); for(i=1;i<=n;i++) { if(i==1) printf("%d",x[i]); else printf(" %d",x[i]); } printf("\n"); return 0; } 测试截图为:

贪心算法 找零钱问题

学号 《算法设计与分析》 实验报告三 学生姓名 专业、班级 指导教师 成绩 电子与信息工程系

实验三:贪心算法运用练习 一、实验目的 本次实验是针对贪心算法运用的算法设计及应用练习,旨在加深学生对该部分知识点的理解,提高学生运用该部分知识解决问题的能力。 二、实验步骤与要求 1.实验前复习课程所学知识以及阅读和理解指定的课外阅读材料; 2.学生独自完成实验指定内容; 3.实验结束后,用统一的实验报告模板编写实验报告。 4.提交说明: (1)电子版提交说明: a 需要提交Winrar压缩包,文件名为“《算法设计与分析》实验二_学号_姓名”, 如“《算法设计与分析》实验二_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验二_学号_姓名”命名的顶层文件夹, 其下为两个文件夹,一个文件夹命名为“源程序”,另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 (2)打印版提交说明: a 不可随意更改模板样式。 b 字体:中文为宋体,大小为10号字,英文为Time New Roman,大小为10号 字。 c 行间距:单倍行距。 (3)提交截止时间:2012年12月7日16:00。 三、实验项目 1.传统的找零钱问题的算法及程序实现。 2.特殊的0-1背包问题的求解:本次求解的0-1背包问题的特点为每种物品各有M件,已知每个物品的单位价值,求使得所获价值最大的装包方案。 四、实验过程 找零钱问题: #include using namespace std; void Zl(double num) { int leave=0; int a[8]; leave = (int)(num*10)%10; a[1] = leave/5;

找零钱最佳组合

找零钱最佳组合 假设商店货品价格(R)都不大于100元(且为整数),若顾客付款(P)在100元内,现有一个程序能在每位顾客付款后给出找零钱的最佳组合(找给顾客货币张数最少)。假定此商店的货币面值只包括:50元(N50)、10元(N10)、5元(N5)、1元(N1)四种。 请结合等价类划分法和边界值分析法为上述程序设计出相应的测试用例。 一、分析输入的情形。RR>100 0=N1>=1 N1=0 N50=14>=N10>=1N5=1 N50=0N10=0N5=0P P>100 R<=P<=100 P100 R<=0 P>100 P=50 RR2>=10 RR3>=5 四、由上述之输入/输出条件组合出可能的情形。(RR=P-R)

R>100 R<=0 0100 0

动态规划解找零钱问题实验报告

一、实验目的 (1)熟练掌握动态规划思想及教材中相关经典算法。 (2)掌握用动态规划解题的基本步骤,能够用动态规划解决一些问题。二、实验内容与实验步骤 (1)仔细阅读备选实验的题目,选择一个(可选多个)作为此次实验题目,设计的程序要满足正确性,代码中有关键的注释,书写格式清晰,简洁易懂,效率较高,利用C++的模板,设计的程序通用性好,适合各种合理输入,并能对不合理输入做出正确的提示。 (2)可供选择的题目有以下2个: (i)找零钱问题(难度系数为3) ★问题描述 设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱,可以实用的各种面值的硬币个数不限。当只 用硬币面值T[1],T[2],…,T[i]时,可找出钱数j的最少硬币个数记为 C(i,j)。若只用这些硬币面值,找不出钱数j时,记C(i,j)=∞。 ★编程任务 设计一个动态规划算法,对1≤j≤L,计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的 计算时间复杂性 ★数据输入 由文件input.txt提供输入数据。文件的第1行中有1个正整数n (n<=13),表示有n种硬币可选。接下来的一行是每种硬币的面值。由 用户输入待找钱数j。 ★结果输出 程序运行结束时,将计算出的所需最少硬币个数输出到文件output.txt中。 输入文件示例输出文件示例 input.txt output.txt 3 3 1 2 5 9

三、实验环境 操作系统 Windows 7 调试软件 VC++6.0 上机地点 综合楼211 四、问题分析 (1) 分析要解决的问题,给出你的思路,可以借助图表等辅助表达。 答:这个问题用动态规划来解,归结到动态规划上面就变成了无限背包问题(因为收银台的硬币默认是无穷的,但一种改进版本可以考察有限硬币的情况)。区别在于,现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的,即每次选择都可以选择任何一种硬币。 首先,找零钱问题具有最优子结构性质: 兑换零钱问题的最优子结构表述:对于任意需要找的钱数j ,一个利用T[n]中的n 个不同面值钱币进行兑换零钱的最佳方案为P(T(1),j),P(T(2),j),...,P(T(n),j),即此时的最少钱币个数 ∑==n 1j) P(T (k),),(k j n C ,则 P(T(2),j),...,P(T(n),j)一定是利用T[n]中n 个不同的面值钱币对钱数 j=j-P(T(1),j)* T(1)进行兑换零钱的最佳方案。 其次,找零钱问题具有重叠于问题性质: a)当n=1时,即只能用一种钱币兑换零钱,钱币的面值为T[0],有 b)当n>1时, 若j>T[n],即第n 种钱币面值比所兑换零钱数小,因此有} 1])[,({),(m in 1+-=≤≤k T j n C j n C n k 。当k 为n)i (1k 0≤≤时,C(n,j)达到最小 值,有P(T(k0),j)=P(T(0k ),j-T(0k ))+1 若j=T[n],即用n 种钱币兑换零钱,第n 种钱币面值与兑换零钱数j 相等,此时有C(n,j)=C(n,T[n])=1; { ] [,1] [,0])[,(),(n T i n T i n T i P j i P =≠= = 若j

软件测试实验报告

桂林航天工业学院 课程设计报告 课程名称:软件测试 专业:软件技术 学号:201102520xxx 姓名: 指导教师:

实验一黑盒测试 一.实验目的 (1)能熟练应用黑盒测试技术进行测试用例设计; (2)对测试用例进行优化设计; 二.实验内容 1.三角形问题的边界值分析测试用例 在三角形问题描述中,除了要求边长是整数外,没有给出其它的限制条件。在此,我们将三角形每边边长的取范围值设值为[1, 100] 。在三角形问题中,有四种可能的输出:等边三角形、等腰三角形、一般三角形和非三角形。利用这些信息能够确定下列输出(值域)等价类。 R1 = { : 边为a,b,c的等边三角形} R2 = { : 边为a,b,c的等腰三角形} R3 = { : 边为a,b,c的一般三角形} R4 = { : 边为a,b,c不能组成三角形} 2. 找零钱最佳组合 假设商店货品价格(R) 都不大于100元(且为整数),若顾客付款(P)在100元内,现有一个程序能在每位顾客付款后给出找零钱的最佳组合(找给顾客货币张数最少)。假定此商店的货币面值只包括:50元(N50)、10元(N10)、5元(N5)、1元(N1) 四种。请结合等价类划分法和边界值分析法为上述程序设计出相应的测试用例。 三、程序代码

1.三角形问题程序。 #include int main(void){ int a,b,c;//定义三个整数a,b,c printf("请输入1到100的三个整数:"); scanf("%d%d%d",&a,&b,&c); if((a>=1&&a<=100)&&(b>=1&&b<=100)&&(b>=1&&b<=100))//判断取值范围 { if((a+b>c)&&(a+c>b)&&(b+c>a))//判断是否构成三角形 { if(a==b&&b==c) printf("等边三角形\n"); else if(a==b||a==c||b==c) printf("等腰三角形\n"); else printf("一般三角形\n"); } else printf("不能组成三角形\n"); } else

0023算法笔记——【贪心算法】哈夫曼编码问题

0023算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。一个包含100,000个字符的文件,各字符出现频率不同,如下表所示。 有多种方式表示文件中的信息,若用0,1码表示字符的方法,即每个字符用唯一的一个0,1串表示。若采用定长编码表示,则需要3位表示一个字符,整个文件编码需要300,000位;若采用变长编码表示,给频率高的字符较短的编码;频率低的字符较长的编码,达到整体编码减少的目的,则整个文件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224,000位,由此可见,变长码比定长码方案好,总码长减小约25%。 前缀码:对每一个字符规定一个0,1串作为其代码,并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单;例如001011101可以唯一的分解为0,0,101,1101,因而其译码为aabe。

译码过程需要方便的取出编码的前缀,因此需要表示前缀码的合适的数据结构。为此,可以用二叉树作为前缀码的数据结构:树叶表示给定字符;从树根到树叶的路径当作该字符的前缀码;代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出,表示最优前缀码的二叉树总是一棵完全二叉树,即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的,其编码的二叉树不是一棵完全二叉树。在一般情况下,若C是编码字符集,表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符,该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为d T(c)。d T(c)也是字符c的前缀码长。则平均码长定义为:

C语言版贪心算法背包问题

#include<> #define N 100 typedef struct bao{ int num; float w; float v; }; typedef struct avg{ int num; ( float val; float w; float v; }; struct bao b[N]; struct avg d[N]; int n; float c; ^ void Sort() { int i,j,k; struct avg temp[N]; for(i=0;i

float x[N],sum = 0; for(i=0;ic) break; x[d[i].num] = 1; sum += d[i].v; c -= d[i].w; } if(i

实验二(贪心算法)

华东师范大学计算机科学技术系上机实践报告 课程名称:算法设计与分析年级:05上机实践成绩: 指导教师:柳银萍姓名:张翡翡 上机实践名称:贪心算法学号:10052130119上机实践日期:2007-4-10 上机实践编号:NO.2组号:上机实践时间:10:00-11:30 一、目的 了解熟悉掌握贪心算法实质并学会灵活运用,从而解决生活中一些实际问题。 二、内容与设计思想 1.超市的自动柜员机(POS)要找给顾客各种数值的现金,表面上看,这是一个很简单的任务,但交给机器办就不简单了。你作为一个计算机专家,要求写一个程序来对付这个“简单”的问题。 你的自动柜员机有以下的币种:100元,50元,20元,10元,5元,2元,1元。你可以假设每种钱币的数量是无限的。现在有一笔交易,需要找个客户m元,请你设计一个算法,使得找给顾客的钱币张数最少。 要求: 输入:第一行仅有一个整数n(0

背包问题(贪心算法)

算法分析与设计实验报告 第 4 次实验

}

附录:完整代码 #include #include #include struct node{ float value; float weight; }; float Value,curvalue=0; float Weight,curweight=0; //按价重比冒泡排序 void sort(node Node[],int M){ int i,j; node temp; for(i=0;i

软件测试技术实验报告册

. 精选范本 河南工程学院 计算机学院 软件测试技术实验报告册 适用专业: 学期: 专业: 班级: 学号: 姓名: 指导教师: 2014年9月

. 精选范本目录 实验一 (1) 实验二 (5) 实验三 (10) 实验四 (13) 实验五 (16) 实验六 (19) 附录 (22)

. 精选范本实验一、黑盒测试 一、实验目的 1、熟练掌握黑盒测试方法的相关知识和方法; 2、熟练等价类划分方法、边界值分析法、判定表方法和因果图法; 3、掌握基本的测试用例的设计。 二、实验内容 1.题目一:电话号码问题 某城市电话号码由三部分组成。它们的名称和内容分别是: (1)地区码:空白或三位数字; (2)前缀:非'0'或'1'的三位数字; (3)后缀:4位数字。 假定被测程序能接受一切符合上述规定的电话号码,拒绝所有不符合规定的电话号码。根据该程序的规格说明,作等价类的划分,并设计测试方案。 2.题目二:三角形问题 根据下面给出的规格说明,利用等价类划分的方法,给出足够的测试用例。 “一个程序读入三个整数。把此三个数值看成是一个三角形的三个边。这个程序要打印出信息,说明这个三角形是三边不等的、是等腰的、还是等边的。” 3.题目三:日期问题 用决策表测试法测试以下程序:该程序有三个输入变量month、day、year(month 、day和year均为整数值,并且满足:1≤month≤12和1≤day≤31),分别作为输入日期的月份、日、年份,通过程序可以输出该输入日期在日历上隔一天的日期。例如,输入为2004 年11月29日,则该程序的输出为2004年12月1日。 (1) 分析各种输入情况,列出为输入变量month 、day 、year 划分的有效等价类。 (2) 分析程序的规格说明,并结合以上等价类划分的情况,给出问题规定的可能采取的操作(即列出所有的动作桩)。

贪心算法详解分析

贪心算法详解 贪心算法思想: 顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。 贪心算法的基本要素: 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路: 从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时,算法停止。 该算法存在问题: 1. 不能保证求得的最后解是最佳的; 2. 不能用来求最大或最小解问题; 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程: 从问题的某一初始解出发; while 能朝给定总目标前进一步do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解; 用背包问题来介绍贪心算法: 背包问题:有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大,但不能超过总容量。

0021算法笔记——【贪心算法】贪心算法与活动安排问题

0021算法笔记——【贪心算法】贪心算法与活动安排问题 1、贪心算法 (1)原理:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 (2)特性:贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性:贪心选择性质和最优子结构性质。 1)贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局 部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为:

首先考察问题的一个整体最优解,并证明可修改这个最优解,使其以贪心选择开始。做了贪心选择后,原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择,最终可得到问题的整体最优解。其中,证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。 2)最优子结构性质 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。 (3)贪心算法与动态规划算法的差异: 动态规划和贪心算法都是一种递推算法,均有最优子结构性质,通过局部最优解来推导全局最优解。两者之间的区别在于:贪心算法中作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解则不作保留,贪心算法每一步的最优解一定包含上一步的最优解。动态规划算法中全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解。 (4)基本思路: 1)建立数学模型来描述问题。 2)把求解的问题分成若干个子问题。 3)对每一子问题求解,得到子问题的局部最优解。 4)把子问题的解局部最优解合成原来解问题的一个解。 2、活动安排问题

贪心算法背包问题

算法设计与分析实验报告 题目:贪心算法背包问题 专业:JA V A技术xx——xxx班 学号: 姓名: 指导老师:

实验三:贪心算法背包问题 一、实验目的与要求 1、掌握背包问题的算法 2、初步掌握贪心算法 二、实验题: 问题描述:与0-1背包问题相似,给定n种物品和一个背包。物品i的重量是wi,其价值为vi,背包的容量为c。与0-1背包问题不同的是,在选择物品i装入背包时,背包问题的解决可以选择物品i的一部分,而不一定要全部装入背包,1< i < n。 三、实验代码 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class er extends JFrame { private static final long serialVersionUID = -1508220487443708466L; private static final int width = 360;// 面板的宽度 private static final int height = 300;// 面板的高度 public int M; public int[] w; public int[] p; public int length; er() { // 初始Frame参数设置 this.setTitle("贪心算法"); setDefaultCloseOperation(EXIT_ON_CLOSE); setSize(width, height); Container c = getContentPane(); c.setLayout(new BoxLayout(c, BoxLayout.Y_AXIS)); setLocation(350, 150); // 声明一些字体样式 Font topF1 = new Font("宋体", Font.BOLD, 28); Font black15 = new Font("宋体", Font.PLAIN, 20); Font bold10 = new Font("宋体", Font.BOLD, 15); // 声明工具栏及属性设置 JPanel barPanel = new JPanel(); JMenuBar topBar = new JMenuBar(); topBar.setLocation(1, 1); barPanel.add(topBar); // 面板1和顶部标签属性设置 JPanel p1 = new JPanel(); JLabel topLabel = new JLabel("背包问题");

贪心算法-找零问题 实验报告

实验三 课程名称:算法设计与实现实验名称:贪心算法-找零问题 实验日期:2019年5月2日仪器编号:007 班级:数媒0000班姓名:郝仁学号0000000000 实验内容 假设零钱系统的币值是{1,p,p^2,……,p^n},p>1,且每个钱币的重量都等于1,设计一个最坏情况下时间复杂度最低的算法,使得对任何钱数y,该算法得到的零钱个数最少,说明算法的主要设计思想,证明它的正确性,并给出最坏情况下的时间复杂度。 实验分析 引理1(离散数学其及应用3.1.4):若n是正整数,则用25美分、10美分、5美分和1美分等尽可能少的硬币找出的n美分零钱中,至多有2个10美分、至多有1个5美分、至多有4个1美分硬币,而不能有2个10美分和1个5美分硬币。用10美分、5美分和1美分硬币找出的零钱不能超过24美分。 证明如果有超过规定数目的各种类型的硬币,就可以用等值的数目更少的硬币来替换。注意,如果有3个10美分硬币,就可以换成1个25美分和1个5美分硬币;如果有2个5美分硬币,就可以换成1个10美分硬币;如果有5个1美分硬币,就可以换成1个5美分硬币;如果有2个10美分和1个5美分硬币,就可以换成1个25美分硬币。由于至多可以有2个10美分、1个5美分和4个1美分硬币,而不能有2个10美分和1个5美分硬币,所以当用尽可能少的硬币找n美分零钱时,24美分就是用10美分、5美分和1美分硬币能找出的最大值。 假设存在正整数n,使得有办法将25美分、10美分、5美分和1美分硬币用少于贪心算法所求出的硬币去找n美分零钱。首先注意,在这种找n美分零钱的最优方式中使用25美分硬币的个数q′,一定等于贪心算法所用25美分硬币的个数。为说明这一点,注意贪心算法使用尽可能多的25美分硬币,所以q′≤q。但是q′也不能小于q。假如q′小于q,需要在这种最优方式中用10美分、5美分和1美分硬币至少找出25美分零钱。而根据引理1,这是不可能的。由于在找零钱的这两种方式中一定有同样多的25美分硬币,所以在这两种方式中10美分、5美分和1美分硬币的总值一定相等,并且这些硬币的总值不超过24美分。10美分硬币的个数一定相等,因为贪心算法使用尽可能多的10美分硬币。而根据引理1,当使用尽可能少的硬币找零钱时,至多使用1个5分硬币和4个1分硬币,所以在找零钱的最优方式中也使用尽可能多的10美分硬币。类似地,5美分硬币的个数相等;最终,1美分的个数相等。 同上,由于1+p1+p2+p3+...pk-1=pk - 1

2015下半年软件评测师考试真题及答案-下午卷

2015下半年软件评测师考试真题及答案-下午卷 试题一 阅读下列java程序,回答问题1至问题3,将解答填入答题纸内对应栏内。 【Java程序】 public int addAppTask(Acitivity activity,Intent intent,TaskDescription description,Bitmap thumbnail){ Point size=getSize();//1 final int tw=thumbnail.getWidth(); final int th=thumbmail.getHeight(); if(tw!=size.x||th!=size.y){ //2,3 Bitmap bm=Bitmap.createBitmap(size.x,size.y,thumbmail .getConfig()); //4 float scale; float dx=0,dy=0; if(tw*size.x>size.y*th){ //5 scale=(float)size.x/(float)th; //6 dx=(size.y-tw*scale)*0.5f; }else{ //7 scale=(float)size.y/(float)tw; dy=(size.x-th*scale)*0.5f; } Matrix matrix=new Matrix(); matrix.setScale(scale, scale); matrix.postTranslate((int)(dx+0.5f),0); Canvas canvas=new Canvas(bm); canvas.drawBitmap(thumbmail,matrix,null); canvase.serBitmap(null); thumbnail=bm; }

相关文档