suanfafenxi.txt

算法设计与分析的实验指导

	int m,n,i,j,l[100][100];
	m=strlen(x);
	n=strlen(y);
	for(i=0;i<m+1;i++)
		l[i][0]=0;
	for(j=0;j<n+1;j++)
		l[0][j]=0;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(x[i-1]==y[j-1])     //i,j从1开始，但字符串是从0开始
				l[i][j]=l[i-1][j-1]+1;
			else if(l[i][j-1]>l[i-1][j])
				l[i][j]=l[i][j-1];
			else
				l[i][j]=l[i-1][j];
	return l[m][n];
}
由于每个数组单元的计算耗费Ο(1)时间，算法lcs_length耗时Ο(mn)。
思考：空间能节约吗？
2．	计算矩阵连乘积
在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：
 
现在的问题是，给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求计算出这n个矩阵的连乘积A1A2…An。
递归公式：  
程序如下：
#include<stdio.h>
int main()
{
	int p[101],i,j,k,r,t,n;
	int m[101][101];            //为了跟讲解时保持一致数组从1开始
	int s[101][101];            //记录从第i到第j个矩阵连乘的断开位置
	scanf("%d",&n);
	for(i=0;i<=n;i++) 
		scanf("%d",&p[i]);      //读入p[i]的值(注意：p[0]到p[n]共n+1项)
	for(i=1;i<=n;i++)           //初始化m[i][i]=0
		m[i][i]=0;
	for(r=1;r<n;r++)            //r为i、j相差的值
		for(i=1;i<n;i++)        //i为行
		{
			j=i+r;              //j为列
			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];    //给m[i][j]赋初值
			s[i][j]=i;
			for(k=i+1;k<j;k++)
			{
				t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
				if(t<m[i][j])
				{
					m[i][j]=t;                //m[i][j]取最小值
					s[i][j]=k;
				}
			}
		}
	printf("%d",m[1][n]);
}
3．	凸多边形的最优三角剖分
多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。
    通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P=<v0 ,v1 ,… ,vn-1>表示具有n条边v0v1，v1v2，… ,vn-1vn的一个凸多边形，其中，约定v0=vn 。
    若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦 将多边形分割成凸的两个子多边形<vi ,vi+1 ,… ,vj>和<vj ,vj+1 ,… ,vi>。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。如图是一个凸多边形的两个不同的三角剖分。
  
凸多边形最优三角剖分的问题是：给定一个凸多边形P=<v0 ,v1 ,… ,vn-1>以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。
可以定义三角形上各种各样的权函数W。例如：定义ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。(注意：解决此问题的算法必须适用于任意的权函数)
4．	防卫导弹
一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：
a)它是该次测试中第一个被防卫导弹截击的导弹；
b)它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。
输入数据：第一行是一个整数n，以后的n各有一个整数表示导弹的高度。
输出数据：截击导弹的最大数目。
分析：定义l[i]为选择截击第i个导弹，从这个导弹开始最多能截击的导弹数目。
由于选择了第i枚导弹，所以下一个要截击的导弹j的高度要小于等于它的高度，所以l[i]应该等于从i＋1到n的每一个j，满足h[j]<=h[i]的j中l[j]的最大值。
程序如下：
#include<stdio.h>
int main()
{
	int i,j,n,max,h[100],l[100];
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&h[i]);
	l[n-1]=1;
	for(i=n-2;i>=0;i--)
	{
		max=0;
		for(j=i+1;j<n;j++)
			if(h[i]>h[j]&&max<l[j])
				max=l[j];
		l[i]=max+1;
	}
	printf("%d",l[0]);
}
5．	石子合并
在一个圆形操场的四周摆放着n堆石子(n<= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，由文件读入堆栈数n及每堆栈的石子数(<=20)。
选择一种合并石子的方案,使得做n－1次合并,得分的总和最小；
输入数据：
第一行为石子堆数n；
第二行为每堆的石子数,每两个数之间用一个空格分隔。
输出数据：
从第一至第n行为得分最小的合并方案。第n+1行是空行.从第n+2行到第2n+1行是得分最大合并方案。每种合并方案用n行表示，其中第i行(1<=i<=n)表示第i次合并前各堆的石子数(依顺时针次序输出，哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。
Sample Input
4
4 5 9 4
Sample Output
－4 5 9 －4
－8 －5 9
－13 －9
22 4 －5 －9 4
4 －14 －4
－4 －18
22

6．	最小代价子母树
设有一排数，共ｎ个，例如：22 14 7 13 26 15 11。任意2个相邻的数可以进行归并，归并的代价为该两个数的和,经过不断的归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使总代价为最小。
输入、输出数据格式与“石子合并”相同。
Sample Input
4
12 5 16 4
Sample Output
－１２ －５ １６ ４
１７ －１６ －４
－１７ －２０
３７
7．	商店购物
某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）；一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如：3朵花的价格不是6而是5 ICU；2个花瓶加1朵花是10 ICU不是12 ICU。
编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为：3朵花和2个花瓶。那么顾客应付款为14 ICU因为：
1朵花加2个花瓶优惠价：10 ICU
2朵花正常价：4 ICU
输入数据：第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。 两个文件中都只用整数。
第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。
第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然， 优惠价要低于该组合中商品正常价之总和。
输出数据：在输出文件OUTPUT．TXT中写 一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。
8．	旅游预算
一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则：
若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。
输入数据：从当前目录下的文本文件“route.dat”读入数据。按以下格式输入若干旅行路线的情况：
第一行为起点到终点的距离（实数）
第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用，第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。
输出数据：答案输出到当前目录下的文本文件“route.out”中。该文件包括两行。第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，此外没有多余的空格。
Sample Input
516.3 38.09 1
15.7 22.1 20.87 3 2 
125.4 1.259 
297.9 1.129 
345.2 0.999
Sample Output
38.09 1
2
9．	皇宫看守
太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
请你编程计算帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
输入数据：输入数据由文件名为intput.txt的文本文件提供。输入文件中数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0<i<=n），在该宫殿安置侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，...，rm。
对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。
输出数据：输出到output.txt文件中。输出文件仅包含一个数，为所求的最少的经费。
如右图的输入数据示例：
Sample Input
6 
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0
Sample Output
25
10．	游戏室问题
有一个游戏室里有多个游戏室，并且这每个游戏室里还有多个游戏室，每个游戏室里面还有游戏室，依此类推。进入每个游戏室都可得到一定的快乐，每个游戏室的门票价格都大于等于0，都有一个快乐值，并且只有进入了一个游戏室，才可以进入它内部的游戏室，小明现在有n元钱，问最大能得到多少的快乐。
11．	*基因问题
已知两个基因序列如s：AGTAGT；t：ATTAG。现要你给序列中增加一些空格后，首先使得两个序列的长度相等，其次两个串对应符号匹配得到的值最大。基因只有四种分别用A、G、C、T表示，匹配中不允许两个空格相对应，任意两符号的匹配值由下表给出：
	A	G	C	T	︺
A	5	-2	-1	-2	-4
G	-2	5	-4	-3	-2
C	-1	-4	5	-5	-1
T	-2	-3	-5	5	-2
︺	-4	-2	-1	-2	
提示：定义问题l[i][j]为取第一个序列的前i项，和第二个序列的前j项，这两个序列加空格匹配的最大值。它的最优值与三个子问题有关，l[i-1][j-1]、l[i][j-1]、l[i-1][j]。
建立递归公式如下：
 
其中m[0][t[j]表示表中空格和t[j]匹配的对应值。
思考：本问题的初始化。
12．	*田忌赛马
田忌与齐王赛马，双方各有n匹马参赛（n<=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。
分析：先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手：
若田忌的马快，就让这两匹马比赛；
若田忌的马慢，干脆就让他对付齐王最快的马；
若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。
定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。
则： 
程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。
程序如下：
#include<stdio.h>
void readdata();
void init();
int n,a[100],b[100],l[100][100];
int main()
{
	int i,j;
	readdata();
	init();
	for(i=n-2;i>=0;i--)
		for(j=1;j<n-i;j++)
			if(a[i+j]<b[j])
				l[i][j]=l[i][j-1]+1;
			else if(a[i+j]>b[j])
				l[i][j]=l[i+1][j-1]-1;
			else if(l[i+1][j-1]-1>l[i][j-1])
				l[i][j]=l[i+1][j-1]-1;
			else
				l[i][j]=l[i][j-1];
	printf("%d",l[0][n-1]);
}
void readdata()
{
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(i=0;i<n;i++)
		scanf("%d",&b[i]);
}
void init()
{
	int i;
//	qsort(a,n);          //略
	for(i=0;i<n;i++)
	{
		if(a[i]<b[0])
			l[i][0]=1;
		else if(a[i]==b[0])
			l[i][0]=0;
		else
			l[i][0]=-1;
	}
}
 
实验五：贪心算法和随机算法
1.	背包问题
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品	A	B	C	D	E	F	G
重量	35	30	60	50	40	10	25
价值	10	40	30	50	35	40	30

2.	照亮的山景
在一片山的上空，高度为T处有N个处于不同位置的灯泡，如图。如果山的边界上某一点于某灯i的连线不经过山的其它点，我们称灯i可以照亮该点。开尽量少的灯，使得整个山景都被照亮。山被表示成有m个转折点的折线。
提示：照亮整个山景相当于照亮每一个转折点。
 

3.	搬桌子问题
某教学大楼一层有n个教室，从左到右依次编号为1、2、…、n。现在要把一些课桌从某些教室搬到另外一些教室，每张桌子都是从编号较小的教室搬到编号较大的教室，每一趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或往右走搬另一张桌子。输入数据：先输入n、m，然后紧接着m行输入这m张要搬课桌的起始教室和目标教室。输出数据：最少需要跑几趟。
Sample Input
10  5
1  3
3  9
4  6
6  10
7  8
Sample Output
3
分析：贪心算法，把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。
程序如下：
#include<stdio.h>
int main()
{
	struct
	{
		int start;
		int end;
	}a[100];
	int i,j;
	int n,m,min,num,temp,used[100]={0};
	scanf("%d%d",&m,&n);
	for(i=0;i<n;i++)
		scanf("%d%d",&a[i].start,&a[i].end);
//	sort(a,n);         //按start从小到大对数组a排序
	min=0;
	num=0;
	while(num<n)
	{
		temp=0;
		for(i=0;i<n;i++)
			if(used[i]==0&&a[i].start>=temp)
			{
				temp=a[i].end;
				used[i]=1;
				num++;
			}
		min++;
	}
	printf("%d",min);
}
4.	用随即算法求解8皇后问题
5.	素数测试



附录：逻辑推理问题

对于较难的逻辑推理问题，看上去难于解决，不知道该从哪里下手时，认真的读题从最简单最特殊的情况入手
1．	月薪30K的面试题
小明和小强都是张老师的学生，张老师的生日是m月n日，2人都知道张老师的生日是下列10组中的一天，张老师把m值告诉了小明，把n值告诉了小强，张老师问他们知道他的生日是那一天吗？
3月4日 3月5日 3月8日 
6月4日 6月7日 
9月1日 9月5日 
12月1日 12月2日 12月8日 
小明说：如果我不知道的话，小强肯定也不知道 
小强说：本来我也不知道，但是现在我知道了 
小明说：哦，那我也知道了
提示：做西服有的需要几分钟，有的需要几百道工序。只要认真就能做好。
此题做对的人很少，不是因为题目太难，而是因为不够认真。
2．	微软面试题
一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。然而所有主人和他们的狗都不能够离开自己的房子，主人与主人之间也不能通过任何方式进行沟通，他们能做的只是通过窗户观察别人家的狗是否生病从而判断自己的狗病否。（就是说，每个主人只能看出其他 49家的狗是不是生病，单独看自己的狗是看不出来的）第一天没有枪声，第二天还是没有枪声，第三天传出一阵枪声，问有多少条狗被枪杀。
提示：上面的大字
3．	海盗分金块问题
海盗，大家听说过吧。这是一帮亡命之徒，在海上抢人钱财，夺人性 命，干的是刀头上舔血的营生。在我们的印象中，他们一般都瞎一只 眼，用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地 下埋宝的好习惯，而且总要画上一张藏宝图，以方便后人掘取。不过 大家是否知道，他们是世界上最民主的团体。参加海盗的都是桀骜不 驯的汉子，是不愿听人命令的，船上平时一切事都由投票解决。船长 的唯一特权，是有自己的一套餐具--可是在他不用时，其他海盗是 可以借来用的。船上的唯一惩罚，就是被丢到海里去喂鱼。
现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题 他们是由投票来解决的。投票的规则如下：先由最凶猛的海盗来提出 分配方案，然后大家一人一票表决，如果有50%或以上的海盗同意这个 方案，那么就以此方案分配，如果少于50%的海盗同意，那么这个提出 方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那 个海盗提出方案，依此类推。
我们先要对海盗们作一些假设。
1)每个海盗的凶猛性都不同，而且所有海盗都知道别人的凶猛性，也就是说，每个海盗都知道自己和别人在这个提出方案的序列中的位置。另外，每个海盗的数学和逻辑都很好，而且很理智。最后，海盗间私底下的交易是不存在的，因为海盗除了自己谁都不相信。
2)一枚金币是不能被分割的，不可以你半枚我半枚。
3)每个海盗当然不愿意自己被丢到海里去喂鱼，这是最重要的。
4)每个海盗当然希望自己能得到尽可能多的金币。
5)每个海盗都是现实主义者，如果在一个方案中他得到了1枚金币，而下一个方案中，他有两种可能，一种得到许多金币，一种得不到金币，他会同意目前这个方案，而不会有侥幸心理。总而言之，他们相信二 鸟在林，不如一鸟在手。
6)最后，每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自己利益的前提下，他会尽可能投票让自己的同伴喂鱼。
现在，如果有10个海盗要分100枚金币，将会怎样？
提示：同上
4．	囚犯放风问题
有100个无期徒刑囚徒，被关在100个独立的小房间，互相无法通信。每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次，也可能一次抽不到。
放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每个人除非出来放风，是看不到这个灯的。一天，全体囚徒大会，国王大赦，给大家一个机会：
如果某一天，某个囚徒能够明确表示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未被放过风，那么所有的囚徒一起处死！囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？除了那个灯以外，囚徒们不能以其他方式联系 
提示：说过了
5．	天盟笔试的最后一道题目
一段文章，中有逗号若干，现求一算法，搜寻某一逗号位置。要求：
1、只搜索文章一遍
2、搜索过程中只能存储一个逗号的位置
3、对于每个逗号，被搜寻到的几率是相等的
提示：书读百遍其意自见
6．	现有100个黑球和100个白球，每次从中任意取出两个球，若颜色相同，则给这堆球中放入一个黑球，若颜色不同，则给这堆球中放入一个白球，这样当这堆球中只剩下一个球时这个球是什么颜色，请证明你的结论。
    提示：多读仔细分析就能抓住关键。
7．	下面用数学归纳法证明“所有的马的颜色都相同”的证明是否正确，如不正确指出错误的原因。
（1）基础：当n=1时显然正确。
（2）归纳：假设n=k时命题成立，当n=k+1时，从中间取出一匹马，这是只有k匹马，根据假设，这k匹马的颜色是相同的，再从中取出一匹马，把刚才这匹马放回，这是又是k匹马，根据假设，这k匹马的颜色是相同的，所以这k+1匹马的颜色是相同的。
由以上两步可知，所有的马的颜色都是相同的。
提示：不需要什么，除了知识。
8．	现在小明一家过一座桥，过桥时候是黑夜，所以必须有灯。现在小明过桥要１秒，小明的弟弟要３秒，小明的爸爸要６秒，小明的妈妈要８秒，小明的爷爷要１２秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后３０秒就会熄灭。问小明一家如何过桥？（再加一点，如果是5个人，6个人呢？）
9．	小明早晨6：00从山脚下开始爬山，中午12：00到达山顶；第二天早晨6：00从山顶开始下山，中午12：00到达山脚下。上山的路只有一条没有任何岔路，你能否证明：小明在同一个时间经过了同一个点。
10．	一男孩和一女孩分别在离家2千米和1千米且方向相反的两所学校上学每天同时以4千米/时和2千米/时的速度步行上学一小狗以6千米/时的速度从男孩奔向女孩又从女孩处奔向男孩，如此往返当两人到达学校时小狗在何处？

然后一步一步分析