问题描述: Sally有12枚银币,其中有11枚是真的,1枚是假的。假的这枚在外形、色泽上与真的无异,但是质量上有差距。可能比真的重,也可能比真的轻。幸运的是Sally借到了一个天平,有3次机会来称量决出其中的假币。规定每次放到天平两端的银币数目是一样的,最终还需要找出假币的质量是轻,还是重。
分析:
这道题其实是很简单的,没有什么算法的东西在里面,就是个模拟题。但是有几点是需要注意的:
(1)不要被样例输入所影响,每次放到天平上的物品数最多有6个,最少有1个,不一定是4个。
(2)3次称量,每次放上去的数目也不一定是相同的。
我的思路是:
开辟一个数组来存放已经确定为真币的银币,初始化为0,然后逐行读取数据,根据称得的结果来确定真币。对于天平平衡的情况来说,比较简单,两边的银币肯定都是真的,数组中对应的数值为1,表示确定是真币了。但是对于左边重或者右边重的就不好说了,要分两种情况,一种是假币比真币轻,一种是假币比真币重,根据情况修改数组元素,2表示可能比真币重,3表示可能比真币轻。但是里面其实还有一些小细节需要考虑。具体看代码。
1
#include<stdio.h>
2
#include<string.h>
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
int i=0,j=0;
5![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int rec[12]={0};
6![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int doubt[12]={0};//加上怀疑次数
7
char left[3][7]; //左边的数组
8
char right[3][7]; //右边的数组
9
char were[3][5];//比较结果
10
//寻找轻球
11
int light()
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
13
for(i=0;i<3;i++)
14![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
15
switch(were[i][0])
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
17
case 'e':
18
for(j=0;j<strlen(left[i]);j++)
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
20
int l=left[i][j]-65;int r=right[i][j]-65;
21
rec[l]=1;//表示它是确定了真的
22
rec[r]=1;//表示它是确定了真的
23
}
24
break;
25
case 'u':
26
for(j=0;j<strlen(left[i]);j++)
27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
28
int l=left[i][j]-65;int r=right[i][j]-65;
29
rec[l]=1;//表示它是真的
30
if(rec[r]!=1)//表示对它进行的两次判断是矛盾的
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ rec[r]=3; doubt[r]++;}
32
}
33
break;
34
case 'd':
35
for(j=0;j<strlen(left[i]);j++)
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
37
int l=left[i][j]-65;int r=right[i][j]-65;
38
rec[r]=1;//表示它是真的
39
if(rec[l]!=1)//就表示这个地方已经被确定过了,有矛盾了
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{rec[l]=3;doubt[l]++;}
41
}
42
break;
43
}
44
}
45
int maxdoubt0=-1,k=-1,num=0;
46
for(i=0;i<12;i++)
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
48
switch(rec[i])
49![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
50
case 3:if(doubt[i]>maxdoubt0)
51![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ num=0;maxdoubt0=doubt[i];k=i;}
52
if(doubt[i]==maxdoubt0&&i!=k)
53
num++;
54
break;
55
case 1:break;
56
case 0:break;
57
}
58
}
59
if(num==0) return k;
60
else return -1;
61
}
62
//寻找重球
63
int heavy()
64![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
65
for(i=0;i<3;i++)
66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
67
switch(were[i][0])
68![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
69
case 'e': for(j=0;j<strlen(left[i]);j++)
70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
71
int l=left[i][j]-65;int r=right[i][j]-65;
72
rec[l]=1;//表示它是确定了真的
73
rec[r]=1;//表示它是确定了真的
74
}
75
break;
76
case 'u': for(j=0;j<strlen(left[i]);j++)
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
78
int l=left[i][j]-65;int r=right[i][j]-65;
79
rec[r]=1;//表示它是真的
80
if(rec[l]!=1)
81![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{rec[l]=2;doubt[l]++;}
82
}
83
break;
84
case 'd': for(j=0;j<strlen(left[i]);j++)
85![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
86
int l=left[i][j]-65;int r=right[i][j]-65;
87
rec[l]=1;//表示它是真的
88
if(rec[r]!=1)
89![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{rec[r]=2;doubt[r]++;}
90
}
91
break;
92
}
93
}
94
int maxdoubt0=-1,k=-1;
95
for(i=0;i<12;i++)
96![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
97
switch(rec[i])
98![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
99
case 2:if(doubt[i]>maxdoubt0)
100![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ maxdoubt0=doubt[i];k=i;}
101
break;
102
case 1: break;
103
case 0: break;
104
}
105
}
106
return k;
107
}
108
int main()
109![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
110
int n;
111
char c;
112
freopen("1013test.txt","r",stdin);
113
scanf("%d",&n);
114
c=getchar();
115
while(n--)
116![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
117
//3表示它被怀疑是轻的,1表示确定了是真的,2表示它被怀疑是重的,0表示不确定。
118
memset(rec,0,12*sizeof(int));
119
memset(doubt,0,12*sizeof(int));
120
//初始化
121
for(i=0;i<3;i++)
122![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
123
memset(left+i,'\0',7*sizeof(char));
124
memset(right+i,'\0',7*sizeof(char));
125
memset(were+i,'\0',4*sizeof(char));
126
}
127![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
128
for(i=0;i<3;i++)
129![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
130
for(j=0;j<7;j++)
131![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
132
scanf("%c",&c);
133
if(c==' ') break;
134
else left[i][j]=c;}
135
for(j=0;j<7;j++)
136![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
137
scanf("%c",&c);
138
if(c==' ') break;
139
else right[i][j]=c;}
140
for(j=0;j<5;j++)
141![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
142
scanf("%c",&c);
143
if(c=='\n') break;
144
else were[i][j]=c;}
145
}
146
//测试思路是这样的:这个要分成两种情况,假设里面有个轻球和假设里面有个重球
147
int k=light();//假设里面有个轻球
148
if(k==-1)//轻球失败
149![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
150
memset(rec,0,12*sizeof(int));
151
memset(doubt,0,12*sizeof(int));
152
k=heavy();//假设里面是个重球
153
k=k+65;
154
printf("%c is the counterfeit coin and it is heavy.\n",k);
155
}
156
else
157![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
158
k=k+65;
159
printf("%c is the counterfeit coin and it is light.\n",k);
160
}
161
}
162
return 0;
163
}
164![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
汗!!代码好长啊,关键是自己对字符输入方面有点不精通。