[讨论]一道经典的递归题的具体代码

主题：[讨论]一道经典的递归题的具体代码

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开始)
--------------------------------------------------------------------------*/

#include <iostream.h>

const int Max=3;

void Init(int a[], int n)
{
    for (int i=1; i<n; i++)
        a[i]=i+1;
    a[i]=1;
}

int count(int a[], int start, int end)
{
    int c=0;
    for (int i=start; a[i]!=a[end]; i=a[i])
        c++;
    return c;
}

int times(int a[], int i, int j, int t1, int t2, int t3)
{
    if ( i<j )     return times(a, i, j-i, t1, t3, t2)+count(a,t2,t3);
    else if (i>j)  return times(a, i-j, j, t3, t2, t1)+count(a,t1,t3);
    else return t3;
}

void answer(int a[], int M, int N)
{
    int k=1;
    int t[Max+1];
    int i;
    for (i=1; i<=Max; i++)
        t[i]=i;
    if (N%Max != 0)
    {
        int temp=t[N%Max];
        t[N%Max]=t[3];
        t[3]=temp;
    }
    for (i=1; i<M; i++)
    {
        if ( times(a,i,M-i,t[1],t[2],t[3]) == N )
        {
            cout<<i<<" "<<M-i<<endl;
            k=0;
            cout<<endl;
        }
    }
    if (k) cout<<"该条件无解."<<endl;
}

void main()
{

    int a[Max+1];
    Init(a,3);
    int M,N;
    cout<<"请输入提问次数:";
    cin>>N;
    cout<<"请输入最大数:";
    cin>>M;
    answer(a,M,N);
}