一个农夫带着一只狼、一只山羊和一篮蔬菜要过河,但只有一条小船PPT名师课件
- 格式：ppt
- 大小：1.67 MB
- 文档页数：41
下载文档原格式
合集下载
农夫过河
}
else
{
graph->Edge[i][j] = graph->Edge[j][i] = false;
}
}
}
return;
}
// 判断在河的那一边
char* judgement(int state)
{
return ( (0 == state) ? "左岸" : "右岸" );
// 查找顶点（F，W，S，V）在顶点向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)
{
// 从0开始查找
for (int i = 0; i < graph->vertexNum; i++)
{
graph->vertex[i].farmer = farmer;
graph->vertex[i].wolf = wolf;
graph->vertex[i].sheep = sheep;
}
void enQueue_seq( PSeqQueue paqu, DataType x ) {
if ( (paqu->r + 1) % MAXNUM == paqu->f )
printf( "Full queue.\n" );
else {
paqu->q[paqu->r] = x;
{
return i; //返回当前位置
}
}
return -1; //没有找到此顶点
else
{
graph->Edge[i][j] = graph->Edge[j][i] = false;
}
}
}
return;
}
// 判断在河的那一边
char* judgement(int state)
{
return ( (0 == state) ? "左岸" : "右岸" );
// 查找顶点（F，W，S，V）在顶点向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)
{
// 从0开始查找
for (int i = 0; i < graph->vertexNum; i++)
{
graph->vertex[i].farmer = farmer;
graph->vertex[i].wolf = wolf;
graph->vertex[i].sheep = sheep;
}
void enQueue_seq( PSeqQueue paqu, DataType x ) {
if ( (paqu->r + 1) % MAXNUM == paqu->f )
printf( "Full queue.\n" );
else {
paqu->q[paqu->r] = x;
{
return i; //返回当前位置
}
}
return -1; //没有找到此顶点
狼羊过河
用简单的查表代替switch…case语句。映射表内容如下：
截图3
表中的处理函数非常简单，就是根据当前状态以及过河动作，得到一个新状态，如果过河动作与当前状态矛盾，
则返回失败，以FARMER_GO_TAKE_WOLF动作对应的处理函数ProcessFarmerGoTakeWolf()为例，看看ProcessFarmerGoTakeWolf()函数
本题算法的核心就是对这个状态树进行深度优先遍历，当某个状态满足结束状态时就输出一组结果。
需要注意的是，并不是每个动作都可以得到一个新状态，比如“农夫带狼过河”这个动作，
对于那些狼已经在河对岸的状态就是无效的，无法得到新状态，因此这个八叉树并不是满树。除此之外，
题目要求的合法性判断也可以砍掉很多无效的状态。最后一点需要注意的是，即使是有效的状态，也会有重复，
Farmer go back, item states is : 0 0 1 0
Farmer take vegetable go over river, item states is : 1 0 1 1
Farmer take sheep go back, item states is : 0 0 0 1
这个检查由IsProcessedState()函数完成，IsProcessedState()函数的实现也很简单，就是遍历states，
与新状态比较是否有相同状态，代码如下：
截图5
运行程序，最终得到的结果是：
Find Result 1:
Unknown action, item states is : 0 0 0 0
终状态，如果是则说明这个搜索路径可以得到一个解，于是调用PrintResult()函数打印结果，随后的return表示终止设个搜索路
截图3
表中的处理函数非常简单，就是根据当前状态以及过河动作，得到一个新状态，如果过河动作与当前状态矛盾，
则返回失败，以FARMER_GO_TAKE_WOLF动作对应的处理函数ProcessFarmerGoTakeWolf()为例，看看ProcessFarmerGoTakeWolf()函数
本题算法的核心就是对这个状态树进行深度优先遍历，当某个状态满足结束状态时就输出一组结果。
需要注意的是，并不是每个动作都可以得到一个新状态，比如“农夫带狼过河”这个动作，
对于那些狼已经在河对岸的状态就是无效的，无法得到新状态，因此这个八叉树并不是满树。除此之外，
题目要求的合法性判断也可以砍掉很多无效的状态。最后一点需要注意的是，即使是有效的状态，也会有重复，
Farmer go back, item states is : 0 0 1 0
Farmer take vegetable go over river, item states is : 1 0 1 1
Farmer take sheep go back, item states is : 0 0 0 1
这个检查由IsProcessedState()函数完成，IsProcessedState()函数的实现也很简单，就是遍历states，
与新状态比较是否有相同状态，代码如下：
截图5
运行程序，最终得到的结果是：
Find Result 1:
Unknown action, item states is : 0 0 0 0
终状态，如果是则说明这个搜索路径可以得到一个解，于是调用PrintResult()函数打印结果，随后的return表示终止设个搜索路
狼羊草过河-图论
狼羊草过河问题描述•一位农夫带了狼、羊、草，准备过河。
可是小船每次只能容下农夫和一件物品。
渔民不在时，狼会吃羊、羊会吃草。
而且，我们假设，狼或羊在农夫不在时不会自己跑掉或被人牵走且农夫会划船。
要求我们设计一个方案，使人、狼、羊、草都能安全过河。
问题分析及假设过河问题相当于状态的转移。
初状态是人，狼，羊，草均在此岸，目标终状态是人，狼，羊，草均在对岸。
定义以下两种向量表示状态的转移：•状态向量：用四维向量(人，狼，羊，草)表示人，狼，羊，草各自的状态，记“在此岸”时各分量为“1”，否则为“0”。
例如：(1，1，1，1)表示人，狼，羊，草均在此岸，(0，0，0，0)表示人，狼，羊，草均在对岸。
•运载向量：用四维向量(人，狼，羊，草)表示他们各自被运载的情况，记“被运载”时各分量为“1”，否则记为“0”。
例如：(1，1，0，0)表示被运载的是人和狼，又如(1，0，1，0)表示被运载的是人和羊。
模型定义根据题设要求，在满足系统限定条件下，可得以下状态向量和运载向量集合：•用S表示所有允许状态向量的集合，则S={(1，1，1，1)，(1，1，1，0)，(1，1，0，1)，(1，0，1，1)，(1，0，1，0)，(0，1，0，1)，(0，0，0，1)，(0，0，1，0)，(0，1，0，0)，(0，0，0，0)}•用D表示所有允许运载向量的集合，则D={(1，0，0，0)，(1，1，0，0)，(1，0，1，0)，(1，0，0，1)}状态转移方程：原状态⊕运载=现状态运算规则：1+1=0，1+0=1，0+1=1，0+0=0可取状态向量允许运载方式：可取状态向量+ 可取运载向量=模型求解(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)1.(1，1，1，1) += (0，0，1，1)×= (0，1，0，1)√= (0，1，1，0)×= (0，1，1，1)×(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)2.(0，1，0，1) += (1，0，0，1)×= (1，1，1，1) ×= (1，1，0，0)×= (1，1，0，1)√解法一：初始状态（1，1，1，1）经多次运载状态变化成最终状态（0，0，0，0）(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)3.(1，1，0，1) += (0，0，0，1)√= (0，1，1，1) ×= (0，1，0，0)√= (0，1，0，1)√(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)4.1. (0，0，0，1) += (1，1，0，1)√= (1，0，1，1) √= (1，0，0，0)×= (1，0，0，1)×(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)4.2.(0，1，0，0) += (1，0，0，0)×= (1，1，1，0) √= (1，1，0，1)√= (1，1，0，0)×4.3. (0，1，0，1)与上述第二步重复，必定不是最优解，故不用进行下去。
农夫过河
数据结构课程设计《农夫过河》学院：软件学院班级：12软工移动2班姓名：学号：12151156711 问题描述农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸, 需要安全运到北岸。
一条小船只能容下他和一件物品, 只有农夫能撑船，问农夫怎么能安全过河？狼吃羊, 羊吃白菜, 农夫不能将这两种或三种物品同时放在河的一侧, 因为没有农夫的照看, 狼就要吃羊, 而羊可能要吃白菜。
这类问题的实质是系统的状态问题, 要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。
2概要设计2.1 数据结构的设计农夫过河问题的模型化有一组状态( 如农夫和羊在南, 狼和白菜在北) ; 从一个状态可合法地转到另外几个状态( 如农夫自己过河或农夫带着羊过河) ; 有些状态不安全( 如农夫在北, 其他东西在南) ; 有一个初始状态( 都在南) ; 结束状态( 这里只有一个, 都在北) 。
问题表示: 需要表示问题中的状态, 农夫等位于南和北( 每个有两种可能) 。
可以采用位向量, 4 个二进制位的情况表示状态, 显而易见, 共24= 16种可能状态。
从高位到低位分别表示农夫、狼、白菜和羊。
0000( 整数0) 表示都在南岸, 目标状态1111( 即整数15) 表示都到了北岸。
有些状态0011,0101, 0111, 0001, 1100, 1001 是不允许出现的, 因为这些状态是不安全状态。
f( farmer) , w(wolf) , g(goat) , c( cabbage) 分别表示农夫自己、农夫携带狼、农夫携带羊、农夫携带菜过河。
现在的问题转化为: 找一条合法路径( 相邻状态之间的转移合法) , 从开始状态到某个结束状态, 途中不经过不安全状态。
2.2算法的设计求农夫、狼、白菜和羊的当前状态的函数为每一种状态做测试, 状态安全则返回0, 否则返回1。
安全性判断函数, 若状态安全则返回0int farmer(int location) //判断农夫位置对0做与运算，还是原来的数字，用来判断位置{return 0 != (location & 0x08);}int wolf(int location) //判断狼位置{return 0 != (location & 0x04);}int cabbage(int location) //判断白菜位置{return 0 != (location & 0x02);}int goat(int location) //判断羊的位置{return 0 !=(location & 0x01);}int safe(int location) // 若状态安全则返回 true{if ((goat(location) == cabbage(location)) && (goat(location) != farmer(location)) )return 0;if ((goat(location) == wolf(location)) && (goat(location) != farmer(location)))return 0;return 1; //其他状态是安全的借助于位向量和按位运算符, 很容易描述过河动作, 这种问题表示的设计使得程序的实现比较容易。
3.2算法及其描述课件
问题二
❖ 有一个年级的同学，每9人一排多5人， 每7人一排多1人，每5 人一排多2人， 这个年级至少有多少人 ？
问题二：280 ×5+225 ×1+126 ×2－315 ×5＝302人 （9） （7） （5）
创新型例题
一位商人有9枚金币，其中有一枚 略轻的是假币，你能用天平（无砝码） 将假币找出来吗？写出解决这一问题 的算法。
羊回来 第三步:运狼过河,回来 第四步:运羊过河
开始 运羊过河,回来
运菜过河, 并运羊回来 运狼过河,回来
运羊过河 结束
韩信点兵
❖ 我国汉代有一位大将，名叫韩信。刘邦去一 次去查看部队，问韩信部队的人数，韩信说， 如果3个3个的数，最后剩2个；如果5个5个 的数，最后剩3个；如果7个7个的数，最后剩 2个。最少有多少人？这样可把刘邦给难住了。 他的这种巧妙算法，人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。
导入一
假设要喝一杯茶有以下几个步骤：
a.烧水
b.洗刷水壶
c.找茶叶 d.洗刷茶具
e.沏茶
请问你怎样安排？
烧水泡茶问题：
解：烧水泡茶可分下面四步完成： 第一步：洗好开水壶； 第二步：灌好凉水，放在火上，等待水开； 第三步：等待时洗好茶杯，茶杯里放好茶叶； 第四步：水开后再冲水泡茶 。
一个农夫带着一条狼、一头山羊和一篮蔬菜 要过河,但只有一条小船.乘船时,农夫只能带一 样东西.当农夫在场的时候,这三样东西相安无事. 一旦农夫不在,狼会吃羊,羊会吃菜.请设计一个 算法,使农夫能安全地将这三样东西带过河.
设备
A
B
C
D
产品
甲
2
1
4
0
乙
2
一个农夫带着一只狼、一只山羊和一篮蔬菜要过河,但只有一条小船PPT完美课件
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
例2.写出用“二分法”求方程 x2-2=0（x>0）的 近似解的算法.
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
解方程组
3x-2y=3
2x+y=4
① ②
第一步, 取 a1=3,b1=-2,c1=3,
a2=2,b2=1,c2=4.
第二步,计算
x= b1c2 -b2c1 , y= a 2c1 -a1c 2 .
a 2b1-a1b2
a 2b1 -a1b 2
第三步,给出运算结果.
x= b1c2 -b2c1 a 2b1 -a1b2
【提升总结】
1.算法定义的理解 在数学中，现代意义上的“算法”通常是指可以用 计算机来解决的某一类问题的程序或步骤，这些程 序或步骤必须是明确和有效的，而且能够在有限步 之内完成.
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
第一步,把9枚金币平均分成三组，每组三枚. 第二步,先将其中的两组放在天平的两边，如果天平 不平衡，那么假金币就在轻的那一组；如果天平左 右平衡，则假金币就在未称量的那一组里. 第三步,取出含假币的那一组，从中任取两枚金币放 在天平两边进行称量，如果天平不平衡，则假金币 在轻的那一边；若平衡，则未称的那一枚就是假币.
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
例2.写出用“二分法”求方程 x2-2=0（x>0）的 近似解的算法.
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
解方程组
3x-2y=3
2x+y=4
① ②
第一步, 取 a1=3,b1=-2,c1=3,
a2=2,b2=1,c2=4.
第二步,计算
x= b1c2 -b2c1 , y= a 2c1 -a1c 2 .
a 2b1-a1b2
a 2b1 -a1b 2
第三步,给出运算结果.
x= b1c2 -b2c1 a 2b1 -a1b2
【提升总结】
1.算法定义的理解 在数学中，现代意义上的“算法”通常是指可以用 计算机来解决的某一类问题的程序或步骤，这些程 序或步骤必须是明确和有效的，而且能够在有限步 之内完成.
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
一个农夫 带着一 只狼、 一只山 羊和一 篮蔬菜 要过河 ，但只 有一条 小船P PT 完美课件
第一步,把9枚金币平均分成三组，每组三枚. 第二步,先将其中的两组放在天平的两边，如果天平 不平衡，那么假金币就在轻的那一组；如果天平左 右平衡，则假金币就在未称量的那一组里. 第三步,取出含假币的那一组，从中任取两枚金币放 在天平两边进行称量，如果天平不平衡，则假金币 在轻的那一边；若平衡，则未称的那一枚就是假币.
农夫过河
程序设计报告题目：农夫过河专业：计算机科学与技术小组成员：班级:指导教师：日期：2014年12月25日成员分工：农夫过河【摘要】农夫问题即一个农民带着一只狼、一只羊和一棵白菜，身处河的南岸,他需要把这些东西全部运到河的北岸。
而他只有一条小船，且这只小船小到只能容下他和一件物品,另外只有农民能撑船。
农夫不能留下狼和羊自己离开，也不能留下白菜和羊自己离开,更不能留下狼，羊和白菜而独自离开，因为没有农夫的照看,狼就要吃掉羊,而羊又要吃掉白菜。
好在狼是是肉动物，它不吃白菜，问农夫应该采取什么方案才能将所有的东西安全地从河的南岸运到北岸？这类农夫问题是一个传统的数据结构问题,利用基于队列的图的广度优先搜索求解农夫过河问题是一个易于理解、切实可行的方案,具有一定的推广价值。
关键字：农夫过河问题;队列;广度优先搜索一、实验内容概述(设计任务与技术要求)农民过河问题是指农民需要带一只狼、一只羊和一棵白菜到河的南岸去,需要安全运到北岸。
而一条小船只能容下他和一件物品,只有农民能撑船。
问农民怎么能安全过河,问题中需要涉及到狼会吃羊,羊会吃白菜,所以农民不能将这两种或三种物品单独放在河的一侧,因为没有农民的照看,狼就要吃掉羊,而羊可能又要吃掉白菜。
这类问题的实质是系统的状态问题,要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。
根据实际情况，对此问题分析可以得到不同的特征：1,是农民和羊在河的南岸，狼和白菜在河的北岸；2,是从一个状态可转到另外一个状态，而不违反狼吃羊，羊吃草的规则（例如农民自己过河或者农民带着羊过河）；3,是有些状态是不安全的（例如农民一人在北岸，而其他的东西都在南岸）；4,是初始状态是农民，羊，狼，白菜都在河的南岸和结束状态是农民，羊，狼，白菜都在河的北岸。
实现农夫过河问题，则需要找到一条合法的路径（相邻状态之间的转移合法），从开始状态到某个结束状态，路途中不能经过不安全的状态。
算法的概念及描述课件学年浙教版(2019)高中信息技术必修1(22张PPT)
2.1 算法的概念及描述
农夫如何安全带这三样东西过河？
一个农夫带着一条狼、一头山羊 和一篮蔬菜要过河，但只有一条船。 乘船时，农夫在场的时候，这三样东 西相安无事。一旦农夫不在，狼会吃 羊，羊会吃菜。船很小，只够农夫带 一样东西过河。农夫该如何解此难题？
农夫如何安全带这三样东西过河？
方法一： 1、农夫带羊过河,农夫回来；
功能
开始/结束框 表示算法的开始或结束
输入/输出框 表示算法中数据的输入或输出
处理框
表示算法中数据的运算处理
判断框
表示算法中的条件判断
流程线
表示算法中的流向
连接框
表示算法中的转接
尝试画出求根公式的流程图
2. 流程图描述算法
开始
输入二项系数a， 一项系数b，常数c
计算判别式
b2 4ac
0？
x1=((-b)+math.sqrt(ref))/(2*a) x2=((-b)-math.sqrt(ref))/(2*a) printf(“方程有实数解”) printf(“x1=”,x1) printf(“x2=”,x2) else: printf(“方程无实数解”)
体验算法多样性
求两个正整数的最大公约数问题
2. 流程图描述算法
流程图用一些图形符号表示规定的操作，并用带箭头的流程线连接这些 图形符号，表示操作进行方向。
自然语言描述如下： （1）输入变量flag的值。 （2）若flag的值为1, 则设置指示灯为 绿色，输出“空车位”；否则，设置 指示灯为红色，输出“非空车位。
2. 流程图描述算法
图形
名称
过程方法具体描述： ax²+bx+c=0
（1）输入一般形式下的二次项系数a，一次项系数b，常数项c； （2）计算判别式 b2 4ac 的值；
农夫如何安全带这三样东西过河？
一个农夫带着一条狼、一头山羊 和一篮蔬菜要过河，但只有一条船。 乘船时，农夫在场的时候，这三样东 西相安无事。一旦农夫不在，狼会吃 羊，羊会吃菜。船很小，只够农夫带 一样东西过河。农夫该如何解此难题？
农夫如何安全带这三样东西过河？
方法一： 1、农夫带羊过河,农夫回来；
功能
开始/结束框 表示算法的开始或结束
输入/输出框 表示算法中数据的输入或输出
处理框
表示算法中数据的运算处理
判断框
表示算法中的条件判断
流程线
表示算法中的流向
连接框
表示算法中的转接
尝试画出求根公式的流程图
2. 流程图描述算法
开始
输入二项系数a， 一项系数b，常数c
计算判别式
b2 4ac
0？
x1=((-b)+math.sqrt(ref))/(2*a) x2=((-b)-math.sqrt(ref))/(2*a) printf(“方程有实数解”) printf(“x1=”,x1) printf(“x2=”,x2) else: printf(“方程无实数解”)
体验算法多样性
求两个正整数的最大公约数问题
2. 流程图描述算法
流程图用一些图形符号表示规定的操作，并用带箭头的流程线连接这些 图形符号，表示操作进行方向。
自然语言描述如下： （1）输入变量flag的值。 （2）若flag的值为1, 则设置指示灯为 绿色，输出“空车位”；否则，设置 指示灯为红色，输出“非空车位。
2. 流程图描述算法
图形
名称
过程方法具体描述： ax²+bx+c=0
（1）输入一般形式下的二次项系数a，一次项系数b，常数项c； （2）计算判别式 b2 4ac 的值；
趣味奥数PPT教学文稿
将下面的T字图用剪刀剪成4块，猜一猜，你能用 多长时间将它拼回原状？和爸爸妈妈一起试一试吧！
动物园比赛
森林里举行比赛，要派出猴子、狐狸、兔子和松 鼠中的两个动物去参加。如果派猴子去，那么也要 派狐狸去；如果不派兔子去，那么也不能派狐狸去； 要是兔子参加的话，松鼠可不愿意去。那么，最后 能参加比赛的是哪两个动物？
8个头
20条腿
鸡兔同笼
方法一：砍腿法
鸡兔同笼 其他方法：
小鸡合体法 兔子分身法 加腿法 假设法 列表法 ······
此课件下载可自行编辑修改，仅供参考！ 感谢您的支持，我们努力做得更好！谢谢
趣味奥数PPT
农夫过河 Game TIME
A组
B组
① ②③
②
①
③
农夫过河
一个农夫带着一头狼，一只羊和一个白菜过 河，小船只能一次装载农夫和一样货物，狼会吃 羊，羊会吃白菜，只有农夫在时才安全。农夫怎 么做才能让所有货物安全的过河？
第一步：载羊过河； 第二步：载狼过河，然后把羊载回去； 第三步：放下羊，载白菜过河； 第四步：载羊过河。
七环问题 Game TIME
A组
B组
七环问题
第一天 第二天 第三天 第四天 第五天 第六天 第七天
趣味奥数（二）
前 提
数学基础
奥数思维
促 进
低段（一二年级） 直观形象思维
中段（三四年级） 形象抽象思维 高段（五六年级） 本质抽象思维
囚犯分汤
我分汤 囚犯A
我选汤 囚犯B
囚犯分汤
你能想一个办法来分汤， 让所有人都觉得公平吗？
囚犯A
囚犯B 囚犯C
提示： 分得是否平均不重要， 重要的是，
让每个人都觉得公平！
动物园比赛
森林里举行比赛，要派出猴子、狐狸、兔子和松 鼠中的两个动物去参加。如果派猴子去，那么也要 派狐狸去；如果不派兔子去，那么也不能派狐狸去； 要是兔子参加的话，松鼠可不愿意去。那么，最后 能参加比赛的是哪两个动物？
8个头
20条腿
鸡兔同笼
方法一：砍腿法
鸡兔同笼 其他方法：
小鸡合体法 兔子分身法 加腿法 假设法 列表法 ······
此课件下载可自行编辑修改，仅供参考！ 感谢您的支持，我们努力做得更好！谢谢
趣味奥数PPT
农夫过河 Game TIME
A组
B组
① ②③
②
①
③
农夫过河
一个农夫带着一头狼，一只羊和一个白菜过 河，小船只能一次装载农夫和一样货物，狼会吃 羊，羊会吃白菜，只有农夫在时才安全。农夫怎 么做才能让所有货物安全的过河？
第一步：载羊过河； 第二步：载狼过河，然后把羊载回去； 第三步：放下羊，载白菜过河； 第四步：载羊过河。
七环问题 Game TIME
A组
B组
七环问题
第一天 第二天 第三天 第四天 第五天 第六天 第七天
趣味奥数（二）
前 提
数学基础
奥数思维
促 进
低段（一二年级） 直观形象思维
中段（三四年级） 形象抽象思维 高段（五六年级） 本质抽象思维
囚犯分汤
我分汤 囚犯A
我选汤 囚犯B
囚犯分汤
你能想一个办法来分汤， 让所有人都觉得公平吗？
囚犯A
囚犯B 囚犯C
提示： 分得是否平均不重要， 重要的是，
让每个人都觉得公平！
过河ppt
在一个漆黑的夜晚，小明一家在野外要过一座桥，过桥有以下要求： １必须有灯。 ２每次此桥最多可过两人， ３走得快的要等走得慢的， ４而且灯在点燃后３０分就会熄灭。 问小明一家如何过桥？
１２分
８分
６分
３分
１分
答案： 第一步:小明与弟弟过桥，小明回来，耗时４分； 第二步:小明与爸爸过河，弟弟回来，耗时９分； 第三步:妈妈与爷爷过河，小明回来，耗时１３分； 最后,小明与弟弟过河，耗时3秒，总共耗时29分，多么惊险！
巧妙渡河 猎人要把一只狼，一头羊和一篮白菜从河的左岸带到右岸， 但他的渡船太小，一次只能带一样。因为狼要吃羊，羊会吃白菜， 所以狼和羊，羊和白菜不能在无人监视的情况下相处。 问猎人怎样才能达如下： 第一次：猎人把羊带至右岸； 第二次：猎人单身回左岸，把白菜带至右岸，此时右岸有猎人，羊和白菜； 第三次：猎人再把羊带回左岸，放下羊把狼带至右岸，此时右岸有猎人，狼和白菜； 第四次：猎人单身回左岸，最后把羊带至右岸，便可完成渡河的任务。
小学奥数专题趣味奥数PPT课件
小学奥数专题趣味奥数
宣讲人：某某某 时间：20XX.XX
小学奥数专题趣味奥数
一个农夫带着一头狼，狼会吃 羊，羊会吃白菜，只 有农夫在时才安全。农夫怎 么做才能让所有货物安 全的过河
农夫过河
小学奥数专题趣味奥数
一个农夫带着一头狼，一只羊和一个白菜过 河，小船只能一次 装载农夫和一样货物，狼会吃 羊，羊会吃白菜 只有农夫在时才安全。农夫怎 么做才能让所有货物安全的过河？ 载羊过河。
那么也要 派狐狸去；那么，最后 能参加比赛的是哪两 个动物？
小学奥数专题趣味奥数
有6个小朋友，每个小朋 友都要互相赠送一张
卡片。请问赠送了多少张 卡片?
有6个小朋友，每个小朋 友都要互相握一次手问 好
请问一共需要:握 多少次手
小学奥数专题趣味奥数
赠送卡片
赠送卡片：每个人轮流送给另外5个人 卡片。6 x 5 = 30 （张）握手：第一个 人另外5个人握手，第二个人和后面的 4个人握手，依次类推。5 + 4 + 3 + 2 + 1 = 15 （次）
小学奥数专题趣味奥数
趣味奥数
3
一个大和尚喝三碗粥，三个小和尚喝一 碗粥。 寺庙里有100个和尚刚好喝了 100 碗粥。请问有多少 个大和尚？
小学奥数专题趣味奥数
趣味奥数
4个和尚4碗粥 25个4个和尚4碗粥 100个和尚 100碗粥
小学奥数专题趣味奥数
倒油问题
卖油郎有一个10斤油，装在10 斤的缸子里，还有一个可以装7 斤和3斤的油桶。
焊接一个金环也是花 费5元。
小学奥数专题趣味奥数
数学基础
直观形象思维 形象抽象思维 本质抽象思维
小学奥数专题趣味奥数
趣味奥数
宣讲人：某某某 时间：20XX.XX
小学奥数专题趣味奥数
一个农夫带着一头狼，狼会吃 羊，羊会吃白菜，只 有农夫在时才安全。农夫怎 么做才能让所有货物安 全的过河
农夫过河
小学奥数专题趣味奥数
一个农夫带着一头狼，一只羊和一个白菜过 河，小船只能一次 装载农夫和一样货物，狼会吃 羊，羊会吃白菜 只有农夫在时才安全。农夫怎 么做才能让所有货物安全的过河？ 载羊过河。
那么也要 派狐狸去；那么，最后 能参加比赛的是哪两 个动物？
小学奥数专题趣味奥数
有6个小朋友，每个小朋 友都要互相赠送一张
卡片。请问赠送了多少张 卡片?
有6个小朋友，每个小朋 友都要互相握一次手问 好
请问一共需要:握 多少次手
小学奥数专题趣味奥数
赠送卡片
赠送卡片：每个人轮流送给另外5个人 卡片。6 x 5 = 30 （张）握手：第一个 人另外5个人握手，第二个人和后面的 4个人握手，依次类推。5 + 4 + 3 + 2 + 1 = 15 （次）
小学奥数专题趣味奥数
趣味奥数
3
一个大和尚喝三碗粥，三个小和尚喝一 碗粥。 寺庙里有100个和尚刚好喝了 100 碗粥。请问有多少 个大和尚？
小学奥数专题趣味奥数
趣味奥数
4个和尚4碗粥 25个4个和尚4碗粥 100个和尚 100碗粥
小学奥数专题趣味奥数
倒油问题
卖油郎有一个10斤油，装在10 斤的缸子里，还有一个可以装7 斤和3斤的油桶。
焊接一个金环也是花 费5元。
小学奥数专题趣味奥数
数学基础
直观形象思维 形象抽象思维 本质抽象思维
小学奥数专题趣味奥数
趣味奥数
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
根据以上分析，可写出如下算法： 第一步,用2除7，得到余数1,因为余数不为0，所以2不 能整除7. 第二步,用3除7，得到余数1,因为余数不为0，所以3不 能整除7. 第三步,用4除7，得到余数3,因为余数不为0，所以4不 能整除7. 第四步,用5除7，得到余数2,因为余数不为0，所以5不 能整除7. 第五步,用6除7，得到余数1,因为余数不为0，所以6不 能整除7. 因此，7是质数.
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
第一章 算法初步
1.1 算法与程序框图 1.1.1 算法的概念
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
想一想：什么是二分法？ 对于区间[a,b ]上连续不断且f(a)·f(b)<0的函数 y=f(x),通过不断地把函数f(x)的零点所在的区间 一分为二，使区间的两个端点逐步逼近零点，进 而得到零点近似值的方法叫做二分法. 【思考】：如何应用二分法求解实际问题呢？
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
问题4:有人对歌德巴赫猜想“任何大于4的偶数 都能写成两个奇质数之和”设计了如下操作步 骤： 第一步,检验6=3+3. 第二步,检验8=3+5. 第三步,检验10=5+5. …… 利用计算机无穷地进行下去！
思考2
假设家中生火泡茶有以下几个步骤：
到底什么是算 法呢？
a.生火 b.将水倒入壶中 c.找茶叶
d.洗茶壶、茶碗
e.用开水冲茶
请选出一个最优方案（ B ）（注意：有些工作可以同
时进行）
A.abcde B.bacde C.cadbe D.dcabe
广义的算法是指完成某项工作的方法和步骤，那 么我们可以说洗衣机的使用说明书是操作洗衣机的算 法，菜谱是做菜的算法等.
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
Ø有效性:算法从初始步骤开始,分为若干明确的步骤, 每一步都只能有一个确定的继任者,只有执行完前一 步才能进入到后一步,并且每一步都确定无误后,才能 解决问题. Ø不惟一性:求解某一个问题的算法不一定是惟一的, 对于同一个问题可以有不同的算法.
x= b1c2 -b 2c1 . a 2b1 -a1b 2
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
问题1：这两个解方程组算法的比较.
3x-2y=3 2x+y=4
① ②
a1x+b1y=c1 a2x+b2y=c2
① ②
(a1b2-a2b10)
--------------------------------------------------
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
写出解方程组
3x-2y=3 2x+y=4
第一步,（消元）
① 的步骤 ②
①+②×2，得 7x=11.
③
第二步,（解一元一次方程）
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
注意事项：①农夫一次只能运一样东西，②如果 农夫不在旁边的话，狼会吃羊，羊会吃菜，我们 该怎样帮帮农夫呢？
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
探究点1 算法的概念
思考1
6+5×(4-2)的计算步骤是什么? 【提示】先进行括号里的运算； 再算乘法； 最后算加法.
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
解③得 x= 11. 7
第三步,（代入求解）
将 x= 1代1入①,得 7
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
y= 6 . 7
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
3x-2y= 3
2xBiblioteka +y=
4
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
2.算法的基本特征 Ø明确性:算法的每一个步骤都是确切的,能有效执行 且得到确定结果,不能模棱两可. Ø有限性:算法应由有限步组成,至少对某些输入,算法 应在有限多步内结束,并给出计算结果．
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
第一步,
第一步, ①×a2- ②×a1得(a2b1
①+②×2，得7x=11.③ 第二步,解③得
x= 11. 7
第三步,将 x = 1代1 入
1.理解算法的概念,体会算法的思想.（重点） 2.掌握简单问题算法的表述.(重点、难点) 3.会写出解线性方程（组）的算法. 4.通过实例,提高对解决具体问题的步骤进行分析的 能力,体会算法的基本思想.
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
例1．设计一个算法，判断7是否为质数. 算法分析： 根据质数的定义，可以这样判断：依次用2～6除7， 如果它们中有一个能整除7，则7不是质数，否则7 是质数.
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
请问，利用这种程序能够证明猜想的正确性吗？ 不能
这是一种算法吗？ 不是
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
（1）一个农夫带着一只狼、一只山羊和一篮蔬菜要 过河，但只有一条小船.乘船时,农夫只能带一样东西. 当农夫在场的时候,这三样东西相安无事，一旦农夫 不在，狼会吃羊，羊会吃菜.请设计一个方案，使农 夫能安全地将这三样东西带过河.
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
a1x+b1y=c1 a2x+b2y=c2
①
② (a1b2-a2b10)
写出解第二个方程组的算法： 第一步,①×a2- ②×a1 得 (a2b1-a1b2)y=a2c1-a1c2. ③
推广
第二步,解③，得 y=a2c1-a1c2 . a2b1-a1b2
④
第三步,将④代入①得
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
问题3:一位商人有9枚金币，其中有一枚略轻的 假币，你能用天平（无砝码）将假币找出来吗？ 写出解决这一问题的算法.
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
解方程组
3x-2y=3
2x+y=4
① ②
第一步, 取 a1=3,b1=-2,c1=3,
a2=2,b2=1,c2=4.
第二步,计算
x= b1c2 -b2c1 , y= a 2c1 -a1c 2 .
a 2b1-a1b2
a 2b1 -a1b 2
第三步,给出运算结果.
x= b1c2 -b2c1 a 2b1 -a1b2
y= a 2c1 -a1c2 a 2b1 -a1b2
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件
问题2：请你说出登录腾讯QQ的步骤. （电脑已经打开）
第一步：打开QQ程序. 第二步：输入QQ号码. 第三步：输入密码. 第四步：点击登录.
一个农夫带着一只狼、一只山羊和一 篮蔬菜 要过河 ，但只 有一条 小船P P T 名师课件