名次确定问题

五位运动员参加比赛，进行结果预测：

A说：B第一，我第三
B说：我第二，E第四
C说：我第一，D第三
D说：C最后，我第三
E说：我第四，A第一

比赛结束，每位选手只说对了一半，编程确定比赛名次。

拿到这道题，我首先想到的是，ABCDE五人有5！个排列次序，对于每个次序都验证题目要求，满足即可break各个循环。于是代码如下：

#include 

int main()
{
        int i,sum=0;
        int a,b,c,d,e;
        int flag=0;

        for(a=1;a<\6;a++)
        {
                for(b=1;b<\6;b++)
                {
                        for(c=1;c<\6;c++)
                        {
                                for(d=1;d<\6;d++)
                                {
                                        for(e=1;e<\6;e++)
                                        {

                                                sum=0;
                                                sum=(b==1||a==3)+(b==2||e==4)+(c==1||d==2)+(c==5||d==3)+(e==4||a==1);
                                                if(sum==5)
                                                {
                                                        flag=1;
                                                        printf("e=%d ",e);
                                                        break;
                                                }
                                        }

                                        if(flag)
                                        {
                                                printf("d=%d ",d);
                                                break;
                                        }
                                }
                                if(flag)
                                {
                                        printf("c=%d ",c);
                                        break;
                                }
                        }
                        if(flag)
                        {
                                printf("b=%d ",b);
                                break;
                        }
                }
                if(flag)
                {
                        printf("a=%d ",a);
                        break;
                }
        }
        printf("\n");
        return 0;
}

编译运行。结果错误：11134。原因是这样的：满足上述条件的序列很多，但是遇到第一个满足条件的序列（此时a，b，c都是1，可见没跑几下就break了）时，因为多个break的原因就跳出了所有循环。看来还得加一个筛选条件。既然名字是1～5的任意排序，那么五位选手名次之和肯定是固定的，因此加入此条件即可筛选处最终名次。如下：

                                            sum=0;
                                                sum=(b==1||a==3)+(b==2||e==4)+(c==1||d==2)+(c==5||d==3)+(e==4||a==1);
                                                if(sum==5)
                                                {
                                                        if((a+b+c+d+e)==15)
                                                        {
                                                        flag=1;
                                                        printf("e=%d ",e);
                                                        break;
                                                        }
                                                }

这样就OK了。看来除了得到题目表面的信息后，还得学会抓住隐含条件。其实第一个条件也可以有下面的几种表达方式：

                                                //方法1
                                                sum=0;
                                                sum+=(b==1&&a!=3)||(b!=1&&a==3);
                                                sum+=(b==2&&e!=4)||(b!=2&&e==4);
                                                sum+=(c==1&&d!=2)||(c!=1&&d==2);
                                                sum+=(c==5&&d!=3)||(c!=5&&d==3);
                                                sum+=(e==4&&a!=1)||(e!=4&&a==1);
                                                //方法2
                                                sum=0;
                                                sum=(a==3||a==1)+(b==1||b==2)+(c==1||c==5)+(d==2||d==3)+(e==4);

这里还有一个更简单的方法。在我作完后，我觉得这个题目用5重循环是否太多余，就想看看牛人是如何完成的，所以就咨询牛涛，它发过来一个链接，果然很简便。虽然意思是一样的但是时间复杂度只有N平方而已。我这个N的5次方。