证明人民币找零问题贪心算法正确性范文模版修改版.docx
- 文档编号:10320145
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:14
- 大小:21.68KB
证明人民币找零问题贪心算法正确性范文模版修改版.docx
《证明人民币找零问题贪心算法正确性范文模版修改版.docx》由会员分享,可在线阅读,更多相关《证明人民币找零问题贪心算法正确性范文模版修改版.docx(14页珍藏版)》请在冰点文库上搜索。
证明人民币找零问题贪心算法正确性范文模版修改版
第一篇:
证明人民币找零问题贪心算法正确性(范文模版)
证明人民币找零问题贪心算法的正确性
问题提出:
根据人们生活常识,我们到商店里买东西需要找零钱时,收银员总是先给我们最大面值的,要是不够再找面值小一点的,直到找完为止。
这就是一个典型的贪心选择问题。
问题描述:
当前有面值分别为100元、50元、20元、10元、5元、1元,5角,2角、1角的人民币。
证明人民币在找零时(1-99元)符合贪心算法,即证明此问题满足贪心算法的两个基本要素:
即最优子结构性质和贪心选择性质。
问题证明:
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。
在人民币找零问题中,其最优子结构性质表现为:
设c[i]是各面额人民币使用的数量,S[i]是商品价格为n时的最优解,数量为K。
现在设某面值的人民币数量减一:
S[j]=S[j]-1,则新的S[i]为n-c[j]的最优解,纸币数K-1.否则,设T[i]是n-c[j]的最优解,纸币数为m,即m
设纸币面额100,50,20,10,5,2,1元的数量依次为A,B,C,D,E,F,G,则根据贪心算法思想得到的解应依次保证max(A),max(B),max(C),max(D),max(E),max(F),max(G)。
假设存在更优的算法,使得所用的纸币数更少,即数量至少小于或等于A+B+C+D+E+F+G-1。
那么在纸币总数减少的情况下保证总额不变只能增大相对大面额纸币的数量并减少小面额纸币数量。
而由贪心算法知max(A)已经是最大的了,以此类推,max(B),max(C),max(D),max(E),max(F)均应为最大数量了,所以贪心算法得到的解是最优解,即满足贪心选择性质。
综上所述,人民币找零问题满足贪心算法。
第二篇:
贪心算法实验报告
实验报告题目实验四贪心算法
开课实验室:
数学实验室
指导老师:
韩逢庆
时间:
2011.12学院:
理学院
专业:
信息与计算科学
班级:
2009级2班姓名:
古月
学号:
09180230
一、实验目的
1.加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握;
2.提高学生利用课堂所学知识解决实际问题的能力;
3.提高学生综合应用所学知识解决实际问题的能力。
二、实验内容
题目见P143:
4-16,4-23.
三、实验要求
(1)用分治法求解最少加油次数和最少硬币个数问题;
(2)再选择自己熟悉的其它方法求解本问题;
(3)上机实现所设计的所有算法;
四、实验过程设计(算法设计过程)
(1)最少加油次数实验题目
一辆汽车加满油以后可以行使n公里,旅途中有若干个加油站,设计一个有效算法,指出应在哪些加油站停靠加油,使沿路加油次数最少。
并证明算法能产生一个最优解。
过程设计
贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。
当然,希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。
比如说最少加油次数的问题。
在这个算法中,我采用的贪心算法的策略。
首先人机互动的设定加满油以后最长能够行使的距离,然后输入了各个站点之间的距离,在程序的设计中,首先检查了程序的可行性。
要是遇到当某两个站点之间的距离大于汽车一次加油以后所能够行使的最大距离时,我们认为此问题是不可行的。
这个在实际情况中也是很容易理解的。
然后在满足可行性条件下,依次采用贪心算法对问题得以实现。
采用s这个来保存现在车里面留下的油,当此时留下的有能够行驶完这一站点到下一站点之间的距离是,在这一站点的时候就不加油。
但是若不能行使完这一段路程的时候,就加满油。
核心算法如下:
for(i=0,s=0;i
{
s=s+a[i];
if(s>n)
{
sum++;
s=a[i];
}
}
(2)最少硬币个数问题实验题目
考虑下面的用最少硬币个数找出n分钱的问题:
当使用2角5分,1角,5分和1分四种硬币面值时,设计一个找n分钱的贪心算法,并证明算法能产生最优解。
过程设计
贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。
当然,希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。
比如说找最少硬币个数的问题。
在算法的实现过程中,当剩余的钱数大于2角5分时,我们在记录找2角5分硬币的个数的变量里面加一,同时把剩余所找的钱的总数目也减2角5分。
不断重复这个过程,直到剩余所需找的钱的数目小于2角5分时,在记录找1角硬币的个数的变量里面加一,同时把剩余所找的钱的总数目也减1角,不断重复这个过程,直到剩余所需找的钱的数目小于1角。
5分和1分的硬币实现过程同上述过程一样,一直执行到所剩的钱的数目为0,此时停止计算,得到最优解。
五、实验结果分析
(1)最少加油次数
当加油后行驶的最大距离小于相邻站点的最小值时,此时,可行,求解结果如下:
当加油后行驶的最大距离大于相邻站点的最小值时,此时,没用可行性,为边沿情况,求解结果如下:
(分析时空复杂性,设计测试用例及测试结果)时间复杂性:
该算法的时间复杂度为O(n)空间复杂性分析:
该算法的空间复杂度为O
(1)
(2)最少硬币问题当输入的找零钱数为正常的时候的运行情况如下:
当输入的找零钱数为不正常的时候(为负)的运行情况如下:
(分析时空复杂性,设计测试用例及测试结果)时间复杂性:
该算法的时间复杂性为O(n)空间复杂性分析:
该算法的空间复杂性为O
(1)
六、实验体会
贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。
当然,希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。
如单源最短路经问题,最小生成树问题,相容活动安排问题等。
这样和采用动态规划的算法相比,算法的思想更加的简单,实现起来更加的容易。
但是也要明确贪心算法和动态规划的主要区别。
及0-1背包问题可以用动态规划算法求解,但是贪心选择算法却不能用动态规划算法求解。
因为贪心算法无法最终将背包装满,部分闲置的背包空间使得每公斤背包空间的价值降低了。
七、附录:
(源代码)
(1)最少加油次数具体算法的实现如下:
#includevoidmain(){intn,m,a[100],i,s,sum=0,j;cout>n;cin>>m;cout
cin>>a[i];}for(i=0;i
cout
if(a[j]>m)
{
sum=-1;
break;
}if(sum!
=-1){
}for(i=0,s=0;i
s=s+a[i];
if(s>n)
{
sum++;
s=a[i];
}}}if(sum==-1)cout
#includemain(){doublen,m,a,b,c,d,f;a=b=c=d=0;cout>n;if(n
cout=2.5){
a++;
m=m-2.5;}while(m>=1){
b++;
m=m-1;}while(m>=0.5){
c++;
m=m-0.5;}while(m>=0.1){
d++;
m=m-0.1;}f=a+b+c+d;cout
第三篇:
实验3贪心算法(定稿)
《算法设计与分析》实验报告
实验3贪心算法
姓名学号班级实验日期实验地点
一、实验目的
1、掌握贪心算法的设计思想。
2、理解最小生成树的相关概念。
二、实验环境
1、硬件环境CPU:
酷睿i5内存:
4GB硬盘:
1T
2、软件环境
操作系统:
Windows10编程环境:
jdk编程语言:
Java
三、实验内容:
在Prim算法与Kruskal算法中任选一种求解最小生成树问题。
1、你选择的是:
Prim算法
2、数据结构
(1)图的数据结构——图结构是研究数据元素之间的多对多的关系。
在这种结构中,任意两个元素之间可能存在关系,即结点之间的关系可以是任意的,图中任意元素之间都可能相关。
图形结构——多个对多个,如
(2)树的数据结构——树结构是研究数据元素之间的一对多的关系。
在这种结构中,每个元素对下(层)可以有0个或多个元素相联系,对上(层)只有唯一的一个元素相关,数据元素之间有明显的层次关系。
树形结构——一个对多个,如
3、算法伪代码Prim(G,E,W)输入:
连通图G输出:
G的最小生成树T1.S←{1};T=∅2.WhileV-S≠∅do
3.从V-S中选择j使得j到S中顶点的边e的权最小;T←T∪{e}4.S←S∪{j}
3、算法分析时间复杂度:
O(n)空间复杂度:
O(n^2)
4、关键代码(含注释)
packagePrim;
importjava.util.*;publicclassMain{staticintMAXCOST=Integer.MAX_VALUE;
staticintPrim(intgraph[][],intn){/*lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树*/
intlowcost[]=newint[n+1];
/*mst[i]记录对应lowcost[i]的起点,当mst[i]=0时表示起点i加入生成树*/intmst[]=newint[n+1];
intmin,minid,sum=0;
/*默认选择1号节点加入生成树,从2号节点开始初始化*/for(inti=2;i
/*标记1号节点加入生成树*/mst[1]=0;
/*n个节点至少需要n-1条边构成最小生成树*/for(inti=2;i
/*找满足条件的最小权值边的节点minid*/for(intj=2;j
/*输出生成树边的信息:
起点,终点,权值*/
System.out.printf("%c1,minid+'A''A'+1;intj=chy-'A'+1;graph[i][j]=cost;graph[j][i]=cost;for(intj=1;j
5、实验结果
(1)输入
(2)输出
最小生成树的权值为:
生成过程:
(a)
(b)
(d)
(e)
(c)
四、实验总结(心得体会、需要注意的问题等)
这次实验,使我受益匪浅。
这次实验我选择了Prim算法来求出树的最小生成树,在编写代码的过程中,我对Prim算法有了更深的了解,也使我对算法设计与分析更有兴趣,今后一定要更努力的学习这门课。
第四篇:
用贪心算法求解Prim算法上机实验报告书
算法分析与设计
实验报告
班级:
学号:
姓名:
上机时间:
一、实验目的与要求:
1、熟悉贪心算法的基本原理和适用范围;
2、使用贪心算法编程,求解最小生成树问题。
二、实验题目:
用贪心算法求解Prim算法
三、实验内容:
任选一种贪心算法(prim或Kruskal),求解最小生成树。
对算法进行
描述和复杂性分析。
编程实现。
四、问题描述:
设G=(V,E)是连通带权图,V={1,2,…,n}。
构造G的最小生成树的Prim
算法的基本思想是:
首先置S={1},然后,只要S是V的真子集,就作如
下的贪心选择:
选取满足条件i∈s,j∈V-S,且c[i][j]最小的边,将顶
点j添加到S中。
这个过程一直进行到S=V时为止。
在这个过程中选取到
的所有边恰好构成G的一棵最小生成树。
五、问题分析与算法设计
六、实验结果及分析
七、实验总结
八、程序代码
#include
#include
#include
#include
#include
#definemaxint20
#defineinf700
intAllSelected(intn,ints[])
{
inti;
for(i=1;i
{
if(s[i]==0)
return0;
}
return1;
}
voidPrim(intn,int**c)
{
intlowcost[maxint];
intclosest[maxint];
bools[maxint];s[1]=true;
for(inti=2;i
{
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=false;
}
for(i=1;i
{
intmin=inf;
intj=1;
for(intk=2;k
{
if((lowcost[k]
{
min=lowcost[k];
j=k;
}
s[j]=true;
for(intk=2;k
if((c[j][k]
{
lowcost[k]=c[j][k];closest[k]=j;
}
}
}
}
voidmain()
{
intn,i,j;
int**k;
printf("请输入顶点个数:
");
scanf("%d",&n);
k=(int**)malloc(sizeof(int*)*(n+1));
for(i=1;i
k[i]=(int*)malloc(sizeof(int)*(n+1));
printf("输入顶点间的权值(自己到自己为0,没有路的为大于其他任何值的数):
\n");for(i=1;i
for(j=i;j
{
printf("k[%d][%d]=k[%d][%d]=",i,j,j,i);
scanf("%d",&k[i][j]);
k[j][i]=k[i][j];
}
printf("\n");
printf("顶点\t");
for(i=1;i
{
printf("%d\t",i);
}
printf("\n");
for(i=1;i
{
printf("%d\t",i);
for(j=1;j
{
printf("%d\t",k[i][j]);
}
printf("\n");
}
printf("\n");
Prim(n,k);
}
第五篇:
数学教案《找找人民币》
数学教案《认识人民币》
一活动目标
1认识人民币的不同面值和基本单位。
2知道并熟练掌握货币间的兑换关系。
3尝试在生活中运用人民币,体验数学与生活之间的关系。
二活动准备
1教具:
仿真人民币(100元50元20元10元5元1元5角1角)2学具:
仿真人民币;模拟商店、商品(标好价格)3PPT课件制作
三活动过程1课堂导入
提问
(1):
人民币是什么?
在生活中的用途?
重要性?
提问
(2):
人民币的基本单位?
有哪些面值?
提问(3):
知道人民币之间的兑换关系吗?
如:
10元等于几个1
元、1元等于几个1角„„2感知人民币兑换关系
出示教具人民币,取出100元50元20元10元5元1元5角1
角等面值的人民币,摆成一排,同时引导幼儿读出面值。
提问
(1):
100元可以换成几个50元,几个20元,几个10元?
请你用学具摆出来。
小结:
100元可以换成2个50元,5个20元,10个10元。
提问
(2):
10元可以换成几个5元,几个1元?
1元可以换成几个
5角,几个1角?
请你用学具摆出来。
小结:
10元可以换成2个5元,10个1元。
1元可以换成2个5
角,10个1角。
3预备游戏
游戏《人民币宝宝抱成团》:
幼儿把自己看做面值为“1元”的人
民币宝宝,教师ppt放出“10元”数目的人民币。
播放音乐,幼儿
随着教师放的音乐走圆圈并思考,当音乐停止时,幼儿做出反应,
自由结伴,凑成与出示人民币相同的数目,10个人抱成一团。
(可
采用淘汰制,并变换幼儿充当的面值和出示面值,增加游戏的多变
性和趣味性。
)4分组操作
二人一组(可交换操作),一人拿出面值较大的人民币(如50元),
另一人找出几个小面值的人民币凑成50元。
可以用5张10元,也
可以用2张20元和1张10元的组合,还可以用3张10元和1张
20元的组合。
让幼儿在操作中感知不同的人民币组合。
5集体活动(也可作为回家后的亲子活动)
角色游戏《小卖场》:
将幼儿分成两组,一组扮演售货员,一组扮演顾客。
注意陈列物品的价格,让幼儿模拟购买东西时该给多少钱,算清找回多少钱。
教师可以在一旁适当引导幼儿正确付钱、找零。
四总结
根据幼小衔接这一特殊的过渡阶段,我设计了这次数学活动。
活动中让幼儿认识了日常生活中的人民币面值和基本单位,以及掌握人民币之间的兑换关系。
以生活这条主线,让幼儿在熟悉的大环境下锻炼逻辑思维能力,体会等量代换的概念。
此外,从幼儿园升入小学,幼儿的上课时间有所延长,为了保证幼儿课堂上的注意力,我穿插了小游戏和小组活动,让幼儿能够不知不觉间适应小学课堂的课时。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 证明 人民币 找零 问题 贪心 算法 正确性 范文 模版 修改