电子教案C 语言案例教程第五章8_第1页
电子教案C 语言案例教程第五章8_第2页
电子教案C 语言案例教程第五章8_第3页
电子教案C 语言案例教程第五章8_第4页
电子教案C 语言案例教程第五章8_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、第八节 贪婪法本节任务 学会用贪婪法解决复杂的问题 学习要点 掌握贪婪法的一般步骤和注意事项 【引例】5_8_1 顾客到超市购物，收银员怎么给顾客找钱最快？想一想：当收银员运算量最小、取的纸币张数最少时找钱最快。比如，给顾客找97元钱，应该找1张50元的、2张20元的，1张5元的，1张2元的。 人们平时购物结帐时，总希望收银员找回零钱的张数越少越好，这样才便于携带。而收银员总是满足了人们的要求。其实收银员根本没有考虑找钱的所有方案，而是从最大面额的纸币开始，按递减的顺序找各种纸币，即先尽量用大面值的纸币，当不足大面值纸币的金额时才去考虑下一种较小面值的纸币！这就是贪婪法，它又称水果法，主妇买水

2、果，总是先拣大的拿；大的拿完了，再拣次大的拿；次大的拿完了，才拣小的拿。贪婪法，确实“贪婪”！ 定义：贪婪法，指从问题的初始解出发，一步一步接近给定目标，并尽可能快地去逼近更好的解。贪婪法追求最快最优解，但只能求某个解，不能求全部解。#include conio.h# define N 20 /* 限制找回给顾客纸币的最大张数 */* find()产生p数组，并统计找零纸币的张数 */int find ( int n, int *d, int c, int *pd ) int r ; if (n=0) return 0 ; if (c=0) return -1 ; if (n=0) retur

3、n r+1 ; return -1 ; void main ( ) int n , k , i, pN,d7=100,50,20,10,5,2,1 ; clrscr(); printf (Please input moneny n: ) ; scanf(%d,&n) ; for(i=0; i=di) break ; k=find(n, &di , 7-i , p ) ; /* 7-i代表找零的币种数 */ if (k=0) printf(Error, Sorry! n) ; else /* 输出pk数组 */ printf(%d=%d,n,p0) ; /* 处理只找1张纸币的情况 */ for

4、 (i=1 ; i100），用10吨、5吨、3吨的货车运输，怎样调度用车最少？ 本章导读 学习本书的目的是学会用C语言编程。本章我们由浅入深，教读者学会排序、检索、尝试、贪婪、迭代、递推、递归、回朔等8种常用的算法。为了学好上述这些技能和知识，我们只能在计算机上边学边练。强化机上的编程训练是学好编程的唯一途径。复习与测验4花朵幼儿园414个小朋友春游。大型客车54座，中型客车36座，问怎样安排车辆才能保证车辆最少、每个小朋友均有座位，并且每个车上无空座？要求：分别用穷举法、贪婪法求解；列变量表，源程序关键语句注释。5植树节时，有一小组学生分得一批树苗，每人种5棵，还剩下4棵；如果有2人各种4棵，其余每人各种6棵

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论