-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathfind_a_fake_coin_form_12.cpp
256 lines (232 loc) · 7.09 KB
/
find_a_fake_coin_form_12.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
//---------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <cstdio>
#include <conio.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <limits.h>
using namespace std;
/**
** 源文件： find_a_fake_coin_form_12.cpp
** 功能说明：
** 测试程序，假币问题：12枚金币中存有一假币，且不知假币较轻或较重，给一天枰限称3次找出其中的假币并知其轻重。
程序罗列出所有不同的解法，共2*12种。
** 作者：junkun huang e-mail：[email protected]
** 创建日期：2008-11 前 /
*/
int sum_coins(const int A[], int from, int to )
{
int sum = 0;
for (int i=from; i<=to; i++)
sum += A[i];
return sum;
}
void print_comp_tips(const char* format, ...)
{
va_list arg_ptr;
va_start(arg_ptr, format);
vector<int> args;
while (true)
{
int para = va_arg(arg_ptr, int);
if (-1 == para)
break;
args.push_back(para);
}
cout << " 天枰比较：{";
assert (0 == args.size() % 2);
const size_t comp_num = args.size()/2;
for (size_t i = 0; i < comp_num; ++i)
cout << args[i] << " ";
cout << "} VS {";
for (size_t i = comp_num; i < args.size(); ++i)
cout << args[i] << " ";
cout << "}" << endl;
va_end(arg_ptr);
}
bool find_a_fake_coin(const int A[], int& fake_coin, int& fake_state)
{
if (print_comp_tips("%d%d%d%d%d%d%d%d%d", 1, 2, 3, 4, 5, 6, 7, 8, -1),
sum_coins(A, 1, 4)==sum_coins(A, 5, 8) )
{
//假货币重量未知
if ( print_comp_tips("%d%d%d%d%d", 1, 9, 10, 11, -1),
(A[1]+A[9])==sum_coins(A, 10, 11) )
{
//A[12]是假币
if (print_comp_tips("%d%d%d", 1, 12, -1),
A[1] < A[12])//假币较重
fake_state = 1;
else//假币较轻
fake_state = 0;
fake_coin = 12;
}
else if ( (A[1]+A[9])>sum_coins(A, 10, 11) )
{
if (print_comp_tips("%d%d%d", 10, 11, -1),
A[10]==A[11])
{
//A[9]假币，较重
fake_state = 1;
fake_coin = 9;
}
else if (A[10]>A[11])
{
//A[11]假币，较轻
fake_state = 0;
fake_coin = 11;
}
else//if (A[10]<A[11])
{
//A[10]假币，较轻
fake_state = 0;
fake_coin = 10;
}
}
else if (print_comp_tips("%d%d%d", 10, 11, -1),
A[10]==A[11])
{
//A[9]假币，较轻
fake_state = 0;
fake_coin = 9;
}
else if (A[10]>A[11])
{
//A[10]假币，较重
fake_state = 1;
fake_coin = 10;
}
else//if (A[10]<A[11])
{
//A[11]假币，较重
fake_state = 1;
fake_coin = 11;
}
}
else if ( sum_coins(A, 1, 4)>sum_coins(A, 5, 8) )
{
if ( print_comp_tips("%d%d%d%d%d%d%d%d%d", 1, 6, 7, 8, 5, 9, 10, 11, -1),
(A[1]+sum_coins(A, 6, 8))==(A[5]+sum_coins(A, 9, 11)) )
{
//假货币重量较重
if ( print_comp_tips("%d%d%d", 2, 3, -1),
A[2]==A[3] )
fake_coin = 4;
else
fake_coin = A[2]>A[3] ? 2:3;
fake_state = 1;
}
else if ( (A[1]+sum_coins(A, 6, 8)) > (A[5]+sum_coins(A, 9, 11)) )
{
if (print_comp_tips("%d%d%d", 1, 9, -1),
A[1]==A[9])
{
fake_coin = 5;//假货币重量较轻
fake_state = 0;
}
else
{
fake_coin = 1;//假货币重量较重
fake_state = 1;
}
}
else//if ( (A[1]+Sum_Coin(A, 6, 8)) < (A[5]+Sum_Coin(A, 9, 11)) )
{
//假货币重量较轻
if (print_comp_tips("%d%d%d", 6, 7, -1),
A[6]==A[7])
fake_coin = 8;
else
fake_coin = A[6]<A[7] ? 6:7;
fake_state = 0;
}
}
//( Sum_Coin(A, 1, 4) < Sum_Coin(A, 5, 8) )
else if (print_comp_tips("%d%d%d%d%d%d%d%d%d", 1, 6, 7, 8, 5, 9, 10, 11, -1),
(A[1]+sum_coins(A, 6, 8))==(A[5]+sum_coins(A, 9, 11)) )
{
//假货币重量较轻
if (print_comp_tips("%d%d%d", 2, 3, -1),
A[2]==A[3] )
fake_coin = 4;
else
fake_coin = A[2]<A[3] ? 2:3;
fake_state = 0;
}
else if ( (A[1]+sum_coins(A, 6, 8)) > (A[5]+sum_coins(A, 9, 11)) )
{
//假货币重量较重
if (print_comp_tips("%d%d%d", 6, 7, -1),
A[6]==A[7])
fake_coin = 8;
else
fake_coin = A[6]>A[7] ? 6:7;
fake_state = 1;
}
else if (print_comp_tips("%d%d%d", 1, 9, -1),
A[1]==A[9])
{
fake_coin = 5;//假货币重量较重
fake_state = 1;
}
else
{
fake_coin = 1;//假货币重量较轻
fake_state = 0;
}
return true;
}
void print_coins(const int pCoins[], int count)
{
cout << "[编号]轻重";
for (int i=1; i<=count; ++i)
{
cout << " [" << i << "]"<< pCoins[i];
}
cout << endl;
}
int main()
{
time_t t;
srand((unsigned) time(&t));
char c;
const int COINS_COUNT = 12;
int pCoins[COINS_COUNT+1] = {0};
do
{
system("cls");
cout << " 假币问题：12枚金币中存有一假币，且不知假币较轻或较重，给一天枰限称3次找出其中的假币并知其轻重。演示如下：\n";
// int fake_s = rand()%2;//1 ，假币较重； 0 ，假币较轻
// int fake_pos = (rand()%COINS_COUNT)+1;
for (int fake_s = 0; fake_s < 2; ++fake_s)
for (int fake_pos = 1; fake_pos <= COINS_COUNT; ++ fake_pos)
{
cout << " NO." << (fake_s)*COINS_COUNT + fake_pos << " --- --- --- --- --- --- --- --- --- --- --- ---\n";
int fake_coin = -1; //假币位置
int fake_state = -1; //1 ，假币较重； 0 ，假币较轻
for (int i=1; i<=COINS_COUNT; ++i)
pCoins[i] = 1;
if (fake_s==0)
pCoins[fake_pos] = 0;
else
pCoins[fake_pos] = 2;
print_coins(pCoins, COINS_COUNT);
find_a_fake_coin(pCoins, fake_coin, fake_state);
assert (-1 != fake_state && -1 != fake_coin);
cout << " 假币位置：" << fake_coin;
if ( fake_state==0 )
cout << " 假币较轻！\n";
else //if (1 ==fake_state)
cout << " 假币较重！\n";
cout << " --- end ---\n";
}
cout << "\n\n !!!按任意键继续，Esc退出程序!!!" << endl;
}
while( (c=getch())!=27 );
return 0;
}