对于一道题目的深入分析.ppt

《对于一道题目的深入分析.ppt》由会员分享，可在线阅读，更多相关《对于一道题目的深入分析.ppt（20页珍藏版）》请在三一办公上搜索。

1、对于一道题目的深入分析,对猴子分桃问题的延伸,当我们写论文时，往往需要对一类题目进行较深入地分析。本文就猴子分桃问题，举例说明对于一道问题的分析方法。,引言,有N只猴子分M个桃子，却怎么也不能分匀，于是约定第二天再分。当天晚上，一只猴子来到桃子堆前，把桃子均匀分成N堆，发现多了一个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，把桃子均匀分成N堆，发现又多了一个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前每个猴子都进行了相同的运动。已知N,求M的最小值。,问题1,对于这道问题，我们发现直接

2、做很困难，但是记得曾经有一道很简单但与此题很相似的问题，所以我们要将问题化为我们所熟悉的问题。,分析,有N只猴子分M个桃子，约定第二天分。当天晚上，一只猴子来到桃子堆前，并把桃子均匀分成N堆，取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，并把剩下的桃子均匀分成N堆，取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前每个猴子都进行了相同的运动。已知N,求M的最小值。,问题2,设第一个猴子离开后还剩A1个桃子，第二个猴子离开后还剩A2个桃子第N个猴子离开后还剩AN个桃子，则有：,这道题的解法很简单，下面给出做法：,A1=M/N*(N-1)A2=A1

3、/N*(N-1)A3=A2/N*(N-1),Ai=Ai-1/N*(N-1)AN=AN-1/N*(N-1),将上式合并:AN=(N-1)/N)N*M由于N-1与N互质，且AN为正整数，所以M为NN的倍数，M的最小值为NN。,下面回到问题1，我们试图将问题已化为和问题2相同的形式。下面给出初步分析：,回到题目1,设第一个猴子离开后还剩A1个桃子，第二个猴子离开后还剩A2个桃子第N个猴子离开后还剩AN个桃子，则有：,A1=(M-1)/N*(N-1)A2=(A1-1)/N*(N-1)A3=(A2-1)/N*(N-1)Ai=(Ai-1-1)/N*(N-1)AN=(AN-1-1)/N*(N-1),为了使上

4、式与问题2的格式相符，将每个等式的左右两边分别加上N-1。,A1+N-1=(M+N-1)/N*(N-1)A2+N-1=(A1+N-1)/N*(N-1)A3+N-1=(A2+N-1)/N*(N-1)Ai+N-1=(Ai-1+N-1)/N*(N-1)AN+N-1=(AN-1+N-1)/N*(N-1),对于上式,设Bi=Ai+N-1。,B1=(M+N-1)/N*(N-1)B2=B1/N*(N-1)B3=B2/N*(N-1)Bi=Bi-1/N*(N-1)BN=BN-1/N*(N-1),这就回到了我们所熟悉的形式，由问题2的结论，M+N-1的最小值为NN，于是推得M的最小值为NN N+1,问题3,让我们

5、看一道更一般的题目：,有N只猴子分M个桃子，却怎么也不能分匀，于是约定第二天再分。当天晚上，一只猴子来到桃子堆前，把桃子均匀分成N堆，发现多了K个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，把桃子均匀分成N堆，发现又多了K个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前每个猴子都进行了相同的运动。已知N,求M的最小值。,同问题2，有下列等式：,A1=(M-K)/N*(N-1)A2=(A1-K)/N*(N-1)A3=(A2-K)/N*(N-1)Ai=(Ai-1-K)/N*(N-1)AN=(

6、AN-1-K)/N*(N-1),我们希望上式也能变形成同样的格式：Ai+kk=(Ai-1+kk)/N*(N-1)由 Ai=(Ai-1-K)/N*(N-1)解得 kk=(N-1)*K由问题2，M的最小值为 NN kk=NN(N-1)*K,问题3看起来好像是猴子分桃子类问题发展的极限了，但是事实真的是这样吗?请看下面一道题。,问题4：,有N只猴子分M个桃子，却怎么也不能分匀，于是约定第二天再分。当天晚上，一只猴子来到桃子堆前，把桃子均匀分成N堆，发现多了1个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，把桃子均匀分成N堆，发现又多了2个，于是

7、他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前每个猴子都进行了相同的运动。已知N,求M的最小值。,由上文，所有的等式可表示为：Ai=(Ai-1-i)/N*(N-1)可是，由于每一项的常数项中都与I有关。所以，简单的把左右的常数项配成一致，是不能解决问题的。我们考虑把每一等式配成如下格式：Ai+k*(i+1)+kk=(Ai-1+k*i+kk)/N*(N-1),由问题3类似，解得：k=N-1 kk=-N*k于是M的最小值为NN-k-kk=NN-N+1+N*k,以上对于一道问题，进行了深入地研究，并由此引伸出许多更具普遍性的问题，这种深入探讨有助于增加对单一问题及算法的理解并有可能提出一些新的问题，以提高自身的水平。,总结,谢谢,北京市清华附中 高逸涵,