First give several lemmas here:
1. If we know the broken ball is heavy or light, we can find the broken ball from 3^t balls in t steps. And we cannot find it from over 3^t balls in t steps.
2. We can find the broken ball from less that (3^t -1)/2 balls in t steps, and know whether it’s heavy or light. And we cannot determine the broken ball is heavy or light for (3^t -1)/2 or more balls in t steps.
3. We can find the broken ball from (3^t +1)/2 balls with another good ball, however may not know whether the ball is heavy or light.
4. We can find the broken ball from (3^t -1)/2 balls in t steps, however, may not know whether it’s heavy or light.
5. Given a good ball, we can find the broken ball from (3^t -1)/2 balls in t steps, and know whether it’s heavy or light.
Proof:
1) Lemma 1 is obvious, pass it.
2) We then try to prove first part of lemma 2. The following proof only apply to t >= 3; for t = 1, 2, you can verify it easily.
We pick (3^t -3)/2 as example, if we can make for it, obvious we can make for numbers less than it. We first split the balls into three piles, exactly (3^(t-1) -1)/2 balls for each pile. We name them A, B and C. Then, we put A and B in the scales, three results are possible here:
a) Balance. We need determine the broken ball from C in t-1 steps. This is what lemma 5 tells.
b) A is heavy. We now know C is already good balls. We then split A to A1 and A2, B to B1 and B2. A1 and B1 with size, A2 and B2 with size (3^(t-2) -1)/2. We then put A1 and B2 in left side of scales, A2 and other 3^(t-2) good balls from C in right side. Three results here also:
Balance. We know bad ball is in B1, and it’s light. From lemma 1, we can find it out in t-2 steps
Left is heavy. We know bad ball is in A1, and it’s heavy. From lemma 1, we can find it out in t-2 steps.
Right is heavy, we know that bad ball is a heavy ball in A2 or a light ball in B2. Notice A2 and B2 both have (3^(t-2) -1)/2 balls, so we got a recursive situation here. And for t=3, the most simple situation, it’s apparently true. Done.
c) A is light, similar with b). Done.
3) Now come to second part of lemma 2. From information theory, we can easy know we cannot find the broken ball from more than (3^t -1)/2 balls in t steps. We now need prove it also impossible to find the broken ball in t steps for exact (3^t -1)/2 balls. If we can, think we about the decision tree, we must average divide among the three child nodes (balance, left heavy and right heavy) for each node, it impossible since (3^t -1)/2 is not a multiplier of 3.
4) We then prove lemma 3. For t = 1, it’s obvious. For t > 1, we divide the balls to three piles, respectively, A with (3^t -1)/2 balls, B with (3^(t-1) +1)/2 balls and C with (3^(t-1) +1)/2 balls. We first put A and the good ball, namely G in left, and B in right. If balance, bad ball in C, and we get a recursive situation. If not balance, suppose left heavy. We then divide A to A1 and A2, B to B1 and B2, A1 and B1 have 3^(t-2) balls, A2 with (3^(t-2) -1)/2 balls, B2 with (3^(t-2) +1)/2 balls. We put A1 and B2 in left, A2 and 3^(t-2) +1 good balls in right. There are tree situations here:
a) Left heavy, then bad ball in A1 and heavy, from lemma 1 we can find it in t-2 steps.
b) Balance, then bad ball in B1 and light, from lemma 1 we can find it in t-2 steps.
c) Right heavy, bad balls in A2 or B2. We get a recursive situation here. Consider the simplest situation, A have 1 ball(named 1) and B have 2 ball(named 2 and 3). We put 1 and 2 in left, and another two good balls in right:
i. balance, we know 3 is the bad ball, and light
ii. left heavy, 1 is the bad ball, and heavy
iii. right heavy, 2 is the bad ball and light
The situation when right is heavy is similar.
5) Now to prove lemma 4. We divide the (3^t -1)/2 balls into three piles, respectively, A and B with (3^(t-1) -1)/2 balls, C with (3^(t-1) +1)/2 balls. Then we put A and B in the scale. If not balance, from 2) we know we can find the bad ball out. If balance, from lemma 3 we know we can find the bad ball, however, may not know whether it’s heavy or light.
6) At the end, we come to lemma 4. We divide the balls into A with (3^t -1)/2 balls, B with (3^(t-1) +1)/2 balls and C with (3^t -1)/2 balls. And put A and the good ball in left, B in right:
a) Balance, bad ball in C, we get a recursive situation here. And for t = 1, it apparently right.
b) Not balance, we get the exact same situation as in 4).
这是代码：
#include
#include
#include
using namespace std;
#include
DEFINE_bool(random, true, "");
DEFINE_int32(count, 13, "");
DEFINE_bool(has_good, false, "");
DEFINE_bool(is_heavy, false, "");
DEFINE_bool(is_light, false, "");
unsigned int three_power[20];
enum SCALE_STATUS {
SCALE_INVLIAD_STATUS = -1,
SCALE_LEFT_HEAVY = 0,
SCALE_RIGHT_HEAVY = 1,
SCALE_BALANCE = 2,
};
SCALE_STATUS GetScaleStatus(bool no_balance) {
static size_t count = 0;
cout << "The " << ++count;
switch (count % 10) {
case 1:
cout << "st test:\n";
break;
case 2:
cout << "nd test:\n";
break;
case 3:
cout << "rd test:\n";
break;
default:
cout << "th test:\n";
break;
}
SCALE_STATUS status = SCALE_INVLIAD_STATUS;
if (FLAGS_random) {
if (no_balance) {
status = static_cast
} else {
status = static_cast
}
} else {
do {
if (no_balance) {
cout << "Input scale status(L or R): ";
} else {
cout << "Input scale status(B, L or R): ";
}
char ch = '\0';
cin >> ch;
if (!no_balance && (ch == 'B' || ch == 'b')) {
status = SCALE_BALANCE;
} else if (ch == 'L' || ch == 'l') {
status = SCALE_LEFT_HEAVY;
} else if (ch == 'R' || ch == 'r') {
status = SCALE_RIGHT_HEAVY;
}
} while (status == SCALE_INVLIAD_STATUS);
}
return status;
}
void FindBadBallKnowHeavyOrLight(unsigned int count, int start_number,
bool heavy) {
assert(count > 0);
if (count == 3) {
cout << "\nPut " << start_number << " in left and "
<< start_number + 1 << " in right:\n";
SCALE_STATUS status = GetScaleStatus(false);
if (status == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is " << start_number + 2 << " and is ";
if (heavy) {
cout << "heavy.\n";
} else {
cout << "light.\n";
}
} else if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. ";
if (heavy) {
cout << "Bad ball is " << start_number << " and is heavy.\n";
} else {
cout << "Bad ball is " << start_number + 1 << " and is light.\n";
}
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight heavy. ";
if (heavy) {
cout << "Bad ball is " << start_number + 1 << " and is heavy.\n";
} else {
cout << "Bad ball is " << start_number << " and is light.\n";
}
}
return;
} else if (count == 2) {
cout << "\nPut " << start_number << " in left and "
<< start_number + 1 << " in right:\n";
SCALE_STATUS status = GetScaleStatus(true);
if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. ";
if (heavy) {
cout << "Bad ball is " << start_number << " and is heavy.\n";
} else {
cout << "Bad ball is " << start_number + 1 << " and is light.\n";
}
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight heavy. ";
if (heavy) {
cout << "Bad ball is " << start_number + 1 << " and is heavy.\n";
} else {
cout << "Bad ball is " << start_number << " and is light.\n";
}
}
return;
} else if (count == 1) {
cout << "\tBad ball is " << start_number << " and is ";
if (heavy) {
cout << "heavy.\n";
} else {
cout << "light.\n";
}
}
cout << "\nDivide the " << count << " balls into 3 piles:\n";
cout << "\tA of";
int next_count = (count - count / 3) / 2;
int i = 0;
for (; i < next_count; ++i) {
cout << " " << start_number + i;
}
cout << "\n\tB of";
for (; i < next_count * 2; ++i) {
cout << " " << start_number + i;
}
cout << "\n\tC of";
for (; i < count; ++i) {
cout << " " << start_number + i;
}
cout << "\nThen put A in left and B in right:\n";
SCALE_STATUS status = GetScaleStatus(false);
if (status == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is ";
start_number += next_count * 2;
count -= next_count * 2;
if (count == 1) {
cout << start_number;
} else {
cout << "in C";
}
} else {
if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft Heavy. Bad ball is ";
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight Heavy. Bad balk is ";
}
count = next_count;
if (status == SCALE_LEFT_HEAVY && heavy ||
status == SCALE_RIGHT_HEAVY && !heavy) {
if (count == 1) {
cout << start_number;
} else {
cout << "in A";
}
} else {
start_number += count;
if (count == 1) {
cout << start_number;
} else {
cout << "in B";
}
}
}
if (heavy) {
cout << " and is heavy.\n";
} else {
cout << " and is light.\n";
}
if (count > 1) {
FindBadBallKnowHeavyOrLight(count, start_number, heavy);
}
}
void FindBadBallInternal1(unsigned int count, int start1, int start2,
bool left_heavy) {
assert(count > 0);
if (count == 1) {
cout << "\nPut " << start1 << " in left and a good ball in right:";
SCALE_STATUS status = GetScaleStatus(false);
if (status == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is " << start2 << " and is ";
if (left_heavy) {
cout << "light.\n";
} else {
cout << "heavy.\n";
}
} else {
if (left_heavy) {
cout << "\tLeft heavy. Bad ball is " << start1 << " and is light.\n";
} else {
cout << "\tRight heavy. Bad ball is " << start1 << " and is heavy.\n";
}
}
return;
} else if (count == 2) {
cout << "\nPut " << start1 << " in left and " << start1 + 1 << " in right:";
SCALE_STATUS status = GetScaleStatus(false);
if (status == SCALE_BALANCE) {
cout << "\tBalance.\n";
status = GetScaleStatus(true);
if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. ";
if (left_heavy) {
cout << "Bad ball is " << start2 + 1 << " and is light.\n";
} else {
cout << "Bad ball is " << start2 << " and is heavy.\n";
}
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tLeft heavy. ";
if (left_heavy) {
cout << "Bad ball is " << start2 << " and is light.\n";
} else {
cout << "Bad ball is " << start2 + 1 << " and is heavy.\n";
}
}
} else if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. ";
if (left_heavy) {
cout << "Bad ball is " << start1 << " and is heavy.\n";
} else {
cout << "Bad ball is " << start1 + 1 << " and is light.\n";
}
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight heavy. ";
if (left_heavy) {
cout << "Bad ball is " << start1 + 1 << " and is heavy.\n";
} else {
cout << "Bad ball is " << start1 << " and is light.\n";
}
}
return;
}
int next_count = count / 3;
cout << "\nDivide A into A1 of";
int i = 0;
for (; i < count - next_count; ++i) {
cout << " " << start1 + i;
}
cout << " and A2 of";
for (; i < count; ++i) {
cout << " " << start1 + i;
}
cout << "\nDivide B into B1 of";
for (i = 0; i < count - next_count; ++i) {
cout << " " << start2 + i;
}
cout << " and B2 of";
for (; i < count; ++i) {
cout << " " << start2 + i;
}
cout << "\nThen put A1 and B2 in Left, put A2 and "
<< count - next_count << " good balls in right:\n";
SCALE_STATUS status = GetScaleStatus(false);
if (status == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is in B1 and is ";
if (left_heavy) {
cout << "light.\n";
FindBadBallKnowHeavyOrLight(count - next_count, start2, false);
} else {
cout << "heavy.\n";
FindBadBallKnowHeavyOrLight(count - next_count, start2, true);
}
} else if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. Bad ball is in A1 and is ";
if (left_heavy) {
cout << "heavy.\n";
FindBadBallKnowHeavyOrLight(count - next_count, start1, true);
} else {
cout << "light.\n";
FindBadBallKnowHeavyOrLight(count - next_count, start1, false);
}
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight heavy. Bad ball is in ";
if (left_heavy) {
cout << "A2(heavy) or B2(light). ";
} else {
cout << "A2(light) or B2(heavy). ";
}
cout << "\nNow assume A2 as A and B2 as B.\n";
FindBadBallInternal1(next_count, start1 + count - next_count,
start2 + count - next_count, left_heavy);
}
}
void FindBadBallInternal2(unsigned int count, int start1, int start2,
bool left_heavy) {
assert(count > 1);
if (count == 2) {
cout << "\n\nPut " << start2 << " in left and "
<< start2 + 1 << " in right:\n";
SCALE_STATUS status = GetScaleStatus(false);
if (status == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is " << start1 << " and is ";
if (left_heavy) {
cout << "heavy.\n";
} else {
cout << "light.\n";
}
} else if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. Bad ball is ";
if (left_heavy) {
cout << start2 + 1 << " and is light.\n";
} else {
cout << start2 << " and is heavy.\n";
}
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight heavy. Bad ball is ";
if (left_heavy) {
cout << start2 << " and is light.\n";
} else {
cout << start2 + 1 << " and is heavy.\n";
}
}
return;
}
int next_count = count / 3 + 1;
cout << "\nDivide A into A1 of";
int i = 0;
for (; i < count - next_count; ++i) {
cout << " " << start1 + i;
}
cout << " and A2 of";
for (; i < count - 1; ++i) {
cout << " " << start1 + i;
}
cout << "\nDivide B into B1 of";
for (i = 0; i < count - next_count; ++i) {
cout << " " << start2 + i;
}
cout << " and B2 of";
for (; i < count; ++i) {
cout << " " << start2 + i;
}
cout << "\nPut A1 and B2 in Left, put A2 and "
<< count - next_count + 1 << " good balls in right:\n";
SCALE_STATUS status = GetScaleStatus(false);
if (status == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is in B1 and is ";
if (left_heavy) {
cout << "light.\n";
FindBadBallKnowHeavyOrLight(count - next_count, start2, false);
} else {
cout << "heavy.\n";
FindBadBallKnowHeavyOrLight(count - next_count, start2, true);
}
} else if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. Bad ball is in A1 and is ";
if (left_heavy) {
cout << "heavy.\n";
FindBadBallKnowHeavyOrLight(count - next_count, start1, true);
} else {
cout << "left.\n";
FindBadBallKnowHeavyOrLight(count - next_count, start1, false);
}
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight heavy. Bad ball is in ";
if (left_heavy) {
cout << "A2(heavy) or B2(light). ";
} else {
cout << "A2(light) or B2(heavy). ";
}
cout << "\nNow assume A2 as A and B2 as B.\n";
FindBadBallInternal2(next_count, start1 + count - next_count,
start2 + count - next_count, left_heavy);
}
}
void FindBadBallWithGood(unsigned int count, int start_number) {
assert(count > 0);
if (count == 3) {
cout << "\nPut " << start_number << " in left and "
<< start_number + 1 << " in right:\n";
SCALE_STATUS status1 = GetScaleStatus(false);
if (status1 == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is " << start_number + 2 << ".\n";
cout << "\nPut " << start_number + 2
<< " in left and a good ball in right:\n";
SCALE_STATUS status2 = GetScaleStatus(true);
if (status2 == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. Bad ball is " << start_number + 2
<< " and is heavy.\n";
} else if (status2 == SCALE_RIGHT_HEAVY) {
cout << "\tRight heavy. Bad ball is " << start_number + 2
<< " and is light.\n";
} else {
assert(false);
}
} else {
if (status1 == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy.\n";
} else if (status1 == SCALE_RIGHT_HEAVY) {
cout << "\tRight heavy.\n";
} else {
assert(false);
}
cout << "\nPut " << start_number
<< " in left and a good ball in right:\n";
SCALE_STATUS status2 = GetScaleStatus(false);
if (status2 == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is " << start_number + 1 << " and is ";
if (status1 == SCALE_LEFT_HEAVY) {
cout << "light.\n";
} else {
cout << "heavy.\n";
}
} else {
status2 = status1;
if (status2 == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. Bad ball is " << start_number
<< " and is heavy.\n";
} else {
cout << "\tRight heavy. Bad ball is " << start_number
<< " and is light.\n";
}
}
}
return;
} else if (count == 2) {
cout << "\nPut " << start_number << " in left and "
<< start_number + 1 << " in right:\n";
SCALE_STATUS status1 = GetScaleStatus(true);
if (status1 == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy.\n";
} else {
assert(status1 == SCALE_RIGHT_HEAVY);
cout << "\tRight heavy.\n";
}
cout << "\nPut " << start_number << " in left and a good ball in right:\n";
SCALE_STATUS status2 = GetScaleStatus(false);
if (status2 == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is " << start_number + 1 << " and is ";
if (status1 == SCALE_LEFT_HEAVY) {
cout << "light.\n";
} else {
cout << "heavy.\n";
}
} else {
status2 = status1;
if (status2 == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy. Bad ball is " << start_number
<< " and is heavy.\n";
} else {
cout << "\tRight heavy. Bad ball is " << start_number
<< " and is light.\n";
}
}
return;
} else if (count == 1) {
cout << "\nPut " << start_number << " in left and a good ball in right:\n";
SCALE_STATUS status = GetScaleStatus(true);
if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft heavy.";
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight heavy.";
}
cout << " Bad ball is " << start_number << " and is ";
if (status == SCALE_LEFT_HEAVY) {
cout << "heavy.\n";
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "light.\n";
}
return;
}
int next_count = count / 3 + 1;
cout << "\nDivide the " << count << " balls into 3 piles:\n";
cout << "\tA of";
int i = 0;
for (; i < next_count - 1; ++i) {
cout << " " << start_number + i;
}
cout << "\n\tB of";
for (; i < next_count * 2 - 1; ++i) {
cout << " " << start_number + i;
}
cout << "\n\tC of";
for (; i < count; ++i) {
cout << " " << start_number + i;
}
cout << "\nThen put A and a good ball in left and B in right:\n";
SCALE_STATUS status = GetScaleStatus(false);
if (status == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is in C.\n";
FindBadBallWithGood(count - next_count * 2 + 1,
start_number + next_count * 2 - 1);
} else {
if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft Heavy. Bad ball is in A(heavy) or B(light)\n";
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight Heavy. Bad ball is in A(light) or B(heavy)\n";
}
FindBadBallInternal2(next_count, start_number,
start_number + next_count - 1,
(status == SCALE_LEFT_HEAVY));
}
}
void FindBadBallNormal(unsigned int count, int start_number) {
assert(count > 2);
int next_count = (count - count / 3) / 2;
cout << "\nDivide the " << count << " balls into 3 piles:\n";
cout << "\tA of";
int i = 0;
for (; i < next_count; ++i) {
cout << " " << start_number + i;
}
cout << "\n\tB of";
for (; i < next_count * 2; ++i) {
cout << " " << start_number + i;
}
cout << "\n\tC of";
for (; i < count; ++i) {
cout << " " << start_number + i;
}
cout << "\nThen put A in left and B in right:\n";
SCALE_STATUS status = GetScaleStatus(false);
if (status == SCALE_BALANCE) {
cout << "\tBalance. Bad ball is in pile C.\n";
FindBadBallWithGood(count - 2 * next_count, start_number + next_count * 2);
} else {
if (status == SCALE_LEFT_HEAVY) {
cout << "\tLeft Heavy. Bad ball is in A(heavy) or B(light)\n";
} else {
assert(status == SCALE_RIGHT_HEAVY);
cout << "\tRight Heavy. Bad ball is in A(light) or B(heavy)\n";
}
FindBadBallInternal1(next_count, start_number, start_number + next_count,
(status == SCALE_LEFT_HEAVY));
}
}
bool FindBadBall(unsigned int count) {
if (FLAGS_is_heavy || FLAGS_is_light) {
if (FLAGS_count > three_power[19]) {
cout << "Please input a valid number!\n";
return false;
}
int i = 0;
for (; i < sizeof(three_power) / sizeof(three_power[0]); ++i) {
if (FLAGS_count <= three_power[i]) break;
}
cout << "I can find the bad ball in at most " << i << " steps!\n";
FindBadBallKnowHeavyOrLight(FLAGS_count, 1, FLAGS_is_heavy);
} else if (!FLAGS_has_good) {
if (FLAGS_count < 3 || FLAGS_count >= (three_power[19] - 1) / 2) {
cout << "Please input a valid number!\n";
return false;
}
int i = 0;
for (; i < sizeof(three_power) / sizeof(three_power[0]); ++i) {
if (FLAGS_count < (three_power[i] - 1) / 2) break;
}
cout << "I can find the bad ball in at most " << i << " steps!\n";
FindBadBallNormal(FLAGS_count, 1);
} else {
if (FLAGS_count > (three_power[19] - 1) / 2) {
cout << "Please input a valid number!\n";
return false;
}
int i = 0;
for (; i < sizeof(three_power) / sizeof(three_power[0]); ++i) {
if (FLAGS_count <= (three_power[i] - 1) / 2) break;
}
cout << "I can find the bad ball in at most " << i << " steps!\n";
FindBadBallWithGood(FLAGS_count, 1);
}
return true;
}
int main(int argc, char** argv) {
if (!InitFlags(argc, argv)) {
cout << Usage(argv[0]) << endl;
return -1;
}
if (FLAGS_count < 1) {
cout << "Please input a valid number!\n";
return -1;
}
unsigned int current = 1;
for (int t = 0; t < sizeof(three_power) / sizeof(three_power[0]); ++t) {
three_power[t] = current;
current *= 3;
}
if (FLAGS_random) {
srand(time(NULL));
}
FindBadBall(FLAGS_count);
return 0;
}
No comments:
Post a Comment