《算法竞赛入门经典》习题及反思 -<2>

数组

Master-Mind Hints，Uva 340

题目：给定答案序列和用户猜的序列，统计有多少数字对应正确(A),有多少数字在两个序列都出现过但位置不对。

输入包括多组数据。每组输入第一行为序列长度n，第二行是答案序列，接下来是若干猜测序列。猜测序列为0时改组数据结束。n=0时输入结束。

样例输入：

4

1 3 5 5

4 3 3 5

6 5 5 1

6 1 3 5

1 3 5 5

0 0 0 0

10

1 2 2 2 4 5 6 6 6 9

1 2 3 4 5 6 7 8 9 1

1 1 2 2 3 3 4 4 5 5

1 2 1 3 1 5 1 6 1 9

1 2 2 5 5 5 6 6 6 7

0 0 0 0 0 0 0 0 0 0

0

样例输出：

Game 1：

(1,1)

(2,0)

(1,2)

(1,2)

(4,0)

Game 2:

(2,4)

(3,2)

(5,0)

(7,0)

我的思路：

这里贴一段错误的代码;思路看起来是对的，但是实现和Debug过程过于麻烦，远远不及书上的思路。不必细究。

#include<stdio.h>

int main()

{

	struct p

	{

		int a;

		int b;//b stand for status used/unused

	}b[105];

	int n,i,j,t=0,m=0,a[105],k=0;

	while(scanf("%d",&n)!=EOF && n!=0)

	{

		for(i=1;i<=n;i++)

		b[i].b=0;//setstatus "0"

		for(i=1;i<=n;i++)

		scanf("%d",&a[i]);

		for(k=1;;k++)

		{

			scanf("%d",&b[1].a);

		    if(b[1].a==0)break;//scanf 0

		    else

		    {

			    for(i=2;i<=n;i++)

			    scanf("%d",&b[i].a);

		    }

		    for(i=1;i<=n;i++)//comparing a[i] and b[j].a

		    {

		    	for(j=1;j<=n;j++)

		    	{

		    		if(a[i]==b[j].a && j==i)

		    		{

		    			t++;

		    			if(b[j].b==1)m--;

		    			/*for(k=1;k<=j;k++)

		    			{

		    				if(b[k].a==a[i] && b[k].b==1)

		    				{

		    					m--;

		    					b[k].b=0;

		    				}

		    			}*/

						b[j].b=1;

						break;

		    		}

		    		if(a[i]==b[j].a && i!=j && b[j].b==0)

		    		{

		    			//if(b[j-1].b==2)break;

		    			m++;

		    			b[j].b=1;

		    			break;

		    		}

		    	}

		    }

		    printf("Game %d: (%d,%d)\n",k,t,m);

		    t=0;

		    m=0;

		    for(i=1;i<=n;i++)

		    b[i].b=0;

		}

	}

	return 0;

}//6 5 5 3

//1 2 2 5 5 5 6 6 6 7

这大概是我至今最失败的几次编程之一了，我定义一个结构体数组b，b[i].a存储用户输入的数，b[i].b存储这个数的状态，如果它被调用则置1，如果被错误调用(即本来是与答案序列正确对应的，但被程序视作不对应从而使m++)置0，同时t++，m--。读者大概也能够猜出我的想法：用循环嵌套循环来寻找位置相同和不相同的数从而获取A和B的个数。

在经过几个小时的不断重复的过程中，我发现耗费在这上面的时间过多，而每一次尝试都无功而返。

不禁让我反思自己的问题，在我之前的编程中，解决问题的算法经常出现一些严重的漏洞，使我不得不去重新思考这个方法的框架，耗费的时间以小时计。别人十几分钟就可以解决的问题我会花上两三个小时。

重新思索其他的解题方法也许是一个不错的解决方法，但是我能不能找到它，并且效率是否会高，这还需我自己用时间来检验。

回到此题，可能是最简单的算法：直接统计A，为了计算B，对每个数字(0-9)，统计二者出现的次数c1，c2，那么min(c1,c2)就是该数字对B的贡献。最后要减去A的部分。

代码(大体部分)：

#include<stdio.h>

int main()

{

	int n,i,j,c1=0,c2=0,m=0,t=0;

	int a[1005],b[1005];

	scanf("%d",&n);

	for(i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

	}

	for(i=1;i<=n;i++)

	{

		scanf("%d",&b[i]);

		if(b[i]==a[i])t++;//查找正确的位

	}

	for(i=1;i<=9;i++)//遍历1-9

	{

		for(j=1;j<=n;j++)

		{

			if(a[j]==i)c1++;//出现在a[i]中的个数

			if(b[j]==i)c2++;//出现在b[i]中的个数

		}

		if(c1>c2)m+=c2;

		else m+=c1;//m+=min(c1,c2)

		c1=0;

		c2=0;

	}

	printf("Game:(%d,%d)",t,m-t);//计算错位：m-t

	return 0;

}

                                                                                                2016/3/9

巴特西

《算法竞赛入门经典》习题及反思 -<2>

数组

Master-Mind Hints，Uva 340

最新文章

热门文章