五位运动员参加比赛,进行结果预测:
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次方 。
Update:8/10
今天一位同学留言说,判断条件应该再加一条判断a,b,c,d,e互不相等。这个条件在我做这个题的时候就想过,可当时总觉的两个判断条件即可。但是,为什么上面的代码也可以显示处正确的答案?那是因为我加入了break。恰好第一组名词就互不相等。如果把每个break都删除了,就会发现有两组结果,其中一个结果就有重复的名次。
其实这个题目属于一个穷举类的题目,应该在程序中让它列出所有的可能(尽管本题中的答案只有一个),而不是找到一个就立刻停止。