您所在位置：主题：[讨论]一道经典的递归题的具体代码
if007
[专家分：650] 发布于 2006-04-05 13:20:00
/********************************************************************
* 文件名： recursion.h
* 文件描述： 一道经典的递归题的具体代码
* 创建人： 陈泽丹, 2006年4月4日 （QQ：82314038）
* 版本号： 1.0
* 修改记录:
********************************************************************/
/*========================================================================
问题描述:
一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A,B和C。有一天，
教授给他们三人出了一道题:教授在每个人脑门上贴了一张纸条并告诉他们，每个人
的纸条上都写了一个正整数,且某两个数的和等于第三个.每个学生都能看见贴在另外两个同学头上的整数，但却看不见自已的数。这时，教授先对学生A发问了：“你能猜出自已的数吗？”A回答：“不能。”教授又转身问学生B：“你能猜出你自已的数吗？”B想了想，也回答：“不能。”教授再问学生C同样的问题，C思考了片刻后，摇了摇头：“不能。”接着，教授又重新问A同样的问题，再问B和C，。。。经过若干轮的提问之后，当教授再问某人时，此人突然露出得意的笑容，把贴在自已头上的那个数准确无误的报了出来。
现在告诉你，教授在第N次提问时，轮到回答问题的那个人猜出了贴在自已头上
的数M，你能推断出另外两个学生的头上的贴的是什么数吗？
提示：总是头上贴着最大的那个数的人最先猜出自已头上的数。
解题思路:
由于自然数是从1开始到无穷大的整数，故若有另两个数相等，则第三个数必为其
和(因为它不可能是他们的差“0”，0不是自然数哦 ^_^ )。而只有最大数才有可能
看见这种情况，故最大数必最先猜出自已头上的数。 -----推理(1)
若我一开始看不到相等的情况呢？
1，若我为他们和的话，那由推理(1)他们猜不到是正常的。不作假设了不去考虑了。
-----推理(2)
2，若我为他们差的话，那由推理(1)他们猜不到就可能有问题了。故假设我为他们
差则他们会看到什么样的情景呢？如可以出现推理(1)的情况，他们能作出凌判断而他
们没作出判断。则说明我必不为他们差。故答案。。。呵呵。。。 ------推理(3)
最后考虑对方也是聪明人哦。假若我为他们差，对方也会用推理(3)来猜测他自已的数
字哦。猜不出时他们也会想他们是差情况时，我的再前前次是怎么判断的。然后大家不断
的用推理(3)来互相猜测对方思路下去，只到有一方在思路上明明出现可判断的推理(1)情
况而无作出判断的情况为止。
以上思路可求出已知三个数，求最大数的那人得知自已头上数的最少次数。但原题是
要求三个数啊？用枚举法解决呗。
总的来说，这是一题枚举法加递归法的经典例题!继汉诺塔后我见过的第二经典递归题。
以下是根据书里讲解的意思打出的代码。
欢迎指教！更欢迎有人贴些其它经典的递归题共享！ ^_^
============================================================================*/
/*--------------------------------------------------------------------------
形成循环数组
Init(int a[], int n): void
求出从start问到end所需的次数
count(int a[], int start, int end): int
求出最大数为t3时，t3猜出自已的数所需的最少次数，i对应t1的值，j对应t2的值
times(int a[], int i, int j, int t1, int t2, int t3): int
求出另两个数的值
answer(int a[], int M, int N): void
最大人数
Max
(注：为便于计算，我使数组下标的开始值从1开始)
--------------------------------------------------------------------------*/
* 文件名： recursion.h
* 文件描述： 一道经典的递归题的具体代码
* 创建人： 陈泽丹, 2006年4月4日 （QQ：82314038）
* 版本号： 1.0
* 修改记录:
********************************************************************/
/*========================================================================
问题描述:
一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A,B和C。有一天，
教授给他们三人出了一道题:教授在每个人脑门上贴了一张纸条并告诉他们，每个人
的纸条上都写了一个正整数,且某两个数的和等于第三个.每个学生都能看见贴在另外两个同学头上的整数，但却看不见自已的数。这时，教授先对学生A发问了：“你能猜出自已的数吗？”A回答：“不能。”教授又转身问学生B：“你能猜出你自已的数吗？”B想了想，也回答：“不能。”教授再问学生C同样的问题，C思考了片刻后，摇了摇头：“不能。”接着，教授又重新问A同样的问题，再问B和C，。。。经过若干轮的提问之后，当教授再问某人时，此人突然露出得意的笑容，把贴在自已头上的那个数准确无误的报了出来。
现在告诉你，教授在第N次提问时，轮到回答问题的那个人猜出了贴在自已头上
的数M，你能推断出另外两个学生的头上的贴的是什么数吗？
提示：总是头上贴着最大的那个数的人最先猜出自已头上的数。
解题思路:
由于自然数是从1开始到无穷大的整数，故若有另两个数相等，则第三个数必为其
和(因为它不可能是他们的差“0”，0不是自然数哦 ^_^ )。而只有最大数才有可能
看见这种情况，故最大数必最先猜出自已头上的数。 -----推理(1)
若我一开始看不到相等的情况呢？
1，若我为他们和的话，那由推理(1)他们猜不到是正常的。不作假设了不去考虑了。
-----推理(2)
2，若我为他们差的话，那由推理(1)他们猜不到就可能有问题了。故假设我为他们
差则他们会看到什么样的情景呢？如可以出现推理(1)的情况，他们能作出凌判断而他
们没作出判断。则说明我必不为他们差。故答案。。。呵呵。。。 ------推理(3)
最后考虑对方也是聪明人哦。假若我为他们差，对方也会用推理(3)来猜测他自已的数
字哦。猜不出时他们也会想他们是差情况时，我的再前前次是怎么判断的。然后大家不断
的用推理(3)来互相猜测对方思路下去，只到有一方在思路上明明出现可判断的推理(1)情
况而无作出判断的情况为止。
以上思路可求出已知三个数，求最大数的那人得知自已头上数的最少次数。但原题是
要求三个数啊？用枚举法解决呗。
总的来说，这是一题枚举法加递归法的经典例题!继汉诺塔后我见过的第二经典递归题。
以下是根据书里讲解的意思打出的代码。
欢迎指教！更欢迎有人贴些其它经典的递归题共享！ ^_^
============================================================================*/
/*--------------------------------------------------------------------------
形成循环数组
Init(int a[], int n): void
求出从start问到end所需的次数
count(int a[], int start, int end): int
求出最大数为t3时，t3猜出自已的数所需的最少次数，i对应t1的值，j对应t2的值
times(int a[], int i, int j, int t1, int t2, int t3): int
求出另两个数的值
answer(int a[], int M, int N): void
最大人数
Max
(注：为便于计算，我使数组下标的开始值从1开始)
--------------------------------------------------------------------------*/
