名次确定问题(Update:8/10)

2010年7月29日 由 edsionte 留言 »

五位运动员参加比赛,进行结果预测:

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次方 e42

Update:8/10

今天一位同学留言说,判断条件应该再加一条判断a,b,c,d,e互不相等。这个条件在我做这个题的时候就想过,可当时总觉的两个判断条件即可。但是,为什么上面的代码也可以显示处正确的答案?那是因为我加入了break。恰好第一组名词就互不相等。如果把每个break都删除了,就会发现有两组结果,其中一个结果就有重复的名次。

其实这个题目属于一个穷举类的题目,应该在程序中让它列出所有的可能(尽管本题中的答案只有一个),而不是找到一个就立刻停止。

广告位

8 条评论

  1. arvid说道:

    (a+b+c+d+e)==15?
    我理解应该是 not_equal (a,b,c,d,e)&&(a+b+c+d+e==15)?

    [回复一下]

    edsionte 回复:

    你这个对,我那个程序每层循环都有break,我估计我那个刚好是个巧合,正好第一个符合我那个条件的那组名次都互不相同。

    [回复一下]

  2. arvid说道:

    恩,我写了个not_equal,不过时间复杂度较高,不知道有没有更好的算法.
    int not_equal(int p[],int sum)
    {
    int i,j;
    for(i=0;i<sum-1;i++)
    for(j=i;j<sum-1;j++)
    if(p[i]==p[j+1])
    return -1;
    return 0;
    }

    [回复一下]

    edsionte 回复:

    恩,我写了个not_equal,不过时间复杂度较高,不知道有没有更好的算法. int not_equal(int p[],int sum) { int i,j; for(i=0;i<sum-1;i++) for(j=i;j<sum-1;j++。。。。。。。。。
    ——————

    这个挺好阿。至于时间复杂度,n平方还算可以。

    [回复一下]

  3. arvid说道:

    重新写了个,这个效率要高一些,但不是很通用,对数据源有要求..
    int not_equal(int p[],int sum)
    {
    int i,t,*flag;
    t=(sum/32)?(sum/32+(sum%32)?1:0):1;
    flag=calloc(t,4);
    for(i=0;i<sum;i++)
    {
    if(*flag&(1<<p[i])) return -1;
    *flag|=(1<<p[i]);
    }
    return 0;
    }

    [回复一下]

  4. alenChou说道:

    结果为什么是d预测两个都对了呢??不是每个人是对了一半么?

    [回复一下]

    edsionte 回复:

    阿兰同学,结果是31524.

    [回复一下]

    edsionte 回复:

    test new head image

    [回复一下]

发表评论

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key