关于鬼谷子问徒 - C语言论坛

问题点数：0 回复次数：31

关于鬼谷子问徒

昨天simpley找我说的，说原经典答案不对，记录如下：

simpley 20:06:53
   你知道答案吗
simpley 20:07:42
   通常的答案是4和13
simpley 20:08:09
   但我可以证明别的数也可以

尐嚥籹 20:45:34
   然后呢，你还找到什么解？
simpley 20:46:24
   13,16
simpley 20:47:52
   共4个,有的推理把它们排除了,其逻辑是很荒谬的

我觉得有点奇怪，昨天做完我的作业后，玩完我的游戏后，在无聊之际决定写一下解题，
结果10分钟写好后，意外发现这个直接写比构造状态机好写得多
刚刚又修改了一下，运行以后发现。。。。Orz
我的代码如下：

/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **
*****************************************************************/
/*
鬼谷子问徒[经典]
孙膑，庞涓都是鬼谷子的徒弟。一天鬼谷子出了这道题目：
他从2到99中选出两个不同的整数，把积告诉孙膑，把和告诉庞涓；
庞涓说：我虽然不能确定这两个数是什么，但是我肯定你也不知道这两个数是什么。
孙膑说：我本来的确不知道，但是听你这么一说，我现在能够确定这两个数字了。
庞涓说：既然你这么说，我现在也知道这两个数字是什么了。
请问这两个数字是什么？为什么？
*/
/*
以下代码，条件1-3分别对应两人依次说的三句话
算法采用最直接最容易理解的穷举验证法
*/

//是否唯一分解（附加条件：分解出的数小于100)
int isOneSolve(int n, int nMax = 100)
{
    int nRet=0; //记录满足本条件数
    for (int nd=2; nd*nd<n; ++nd)
    {
        if ( n%nd==0 && n/nd<nMax)
            if (++nRet>1) return 0;
    }
    return nRet;
}
//条件1，sum的任意和的分拆之积不可能有唯一分解，否则对方可能猜出
int p1(int sum)
{
    if(sum<6) return 0;
    for (int t=(sum-1)/2; t>1; --t)
    {
        if ( isOneSolve(t*(sum-t)) ) return 0;
    }
    return 1;
}
//条件2，只有一种积的分拆满足条件1
int p2(int times2)
{
    int nRet=0; //记录满足本条件数
    for (int nd=2; nd*nd<times2; ++nd)
    {
        if ( times2%nd==0 && p1(nd+times2/nd) )
            if (++nRet>1) return 0;
    }
    return nRet;
}
//条件3，只有一种和的分拆满足条件2
int p3(int sum)
{
    int nRet=0; //记录满足本条件数
    for (int t=(sum-1)/2; t>1; --t)
    {
        if ( p2(t*(sum-t)) )
            if (++nRet>1) return 0;
    }
    return nRet;
}

#include <stdio.h>
//作者：雨中飞燕
int main(int argc, char *argv[])
{
    for (int n=6; n<200; ++n) //穷举和的可能，最大不超过200
    {
        // 其和能同时满足条件1和3者即为结果
        if (p1(n) && p3(n))
        {
            //找出对应解
            for (int t=2; t*2<n; ++t)
            {
                if ( p2(t*(n-t)) ) //分拆结果符合条件2就输出
                    printf("%d %d\n", t, n-t);
            }
        }
    }
    puts("Finish");getchar();return 0;
}

运行结果是什么自己运行看看吧，结果没找到13,16
不太清楚simpley所说的另外还有哪三个解？