|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladimir A. Pertzel 2:5020/400 25 Aug 2002 09:20:45
To : Evgeniy Jirnov
Subject : Re: 12 монеток
--------------------------------------------------------------------------------
"Evgeniy Jirnov" <Evgeniy.Jirnov@p13.f1230.n5030.z2.fidonet.org> wrote in
message news:1030057205@p13.f1230.n5030.z2.fidonet.ftn...
> Мир твоему дому, All.
>
> Есть сабж, среди них одна фальшивая(отличается от настоящих весом). С помощью
> трех взвешиваний найти фальшивую монету.
>
> Мне кажется это нерешимо. А вам, уважаемые подписчики?
*Стандартный* подход к задачам со взвешиванием заключается в
кодировании результатов взвешивания (и, естественно, монет)
троичным числом в системе исчисления с цифрами "-1", "0", "+1".
Единственное отличие от стандарта состоит в том, что мы в данной
ситуации не можем отличить положительное число от отрицательного.
Это -- первый пуззель в rec.puzzles (http://rec-puzzles.org)
FAQ (ftp://rtfm.mit.edu/pub/usenet/rec.puzzles/puzzles/faq).
для неимеющих доступа в Сеть, цитирую по
ftp://rtfm.mit.edu/pub/usenet/news.answers/puzzles/archive/logic/part5
==> logic/weighing/balance.p <==
You are given 12 identical-looking coins, one of which is counterfeit
and weighs slightly more or less (you don't know which) than the
others. You are given a balance scale which lets you put the same
number of coins on each side and observe which side (if either) is
heavier. How can you identify the counterfeit and tell whether it
is heavy or light, in 3 weighings?
More generally, you are given N coins, one of which is heavy or light.
==> logic/weighing/balance.s <==
Martin Gardner gave a neat solution to this problem.
Assume that you are allowed W weighings. Write down the 3^W possible
length W strings of the symbols '0', '1', and '2'. Eliminate the three
such strings that consist of only one symbol repeated W times.
For each string, find the first symbol that is different from the symbol
preceeding it. Consider that pair of symbols. If that pair is not 01,
12, or 20, cross out that string. In other words, we only allow strings
of the forms 0*01.*, 1*12.*, or 2*20.* ( using ed(1) regular expressions ).
You will have (3^W-3)/2 strings left. This is how many coins you can
handle in W weighings.
Perform W weighings as follows:
For weighing I, take all the coins that have a 0 in string
position I, and weigh them against all the coins that have
a 2 in string position I.
If the side with the 0's in position I goes down, write down
a 0. If the other side goes down, write down a 2. Otherwise,
write down a 1.
After the W weighings, you have written down an W symbol string. If
your string matches the string on one of the coins, then that is the
odd coin, and it is heavy. If none of them match, than change every
2 to a 0 in your string, and every 0 to a 2. You will then have a
string that matches one of the coins, and that coin is lighter than
the others.
Note that if you only have to identify the odd coin, but don't have to
determine if it is heavy or light, you can handle (3^W-3)/2+1 coins.
Label the extra coin with a string of all 1's, and use the above
method.
Note also that you can handle (3^W-3)/2+1 coins if you *do* have to
determine whether it is heavy or light, provided you have a single reference
coin available, which you know has the correct weight. You do this by
labelling the extra coin with a string of all 2s. This results in it being
placed on the same side of the scales each time, and in that side of the
scales having one more coin than the other each time. So you put the
reference coin on the other side of the scales to the "all 2s" coin on each
weighing.
Proving that this works is straightforward, once you notice that the
method of string construction makes sure that in each position, 1/3
of the strings have 0, 1/3 have 1, and 1/3 have 2, and that if a
string occurs, then the string obtained by replacing each 0 with a
2 and each 2 with a 0 does not occur.
If you already know the odd coin is heavy (or light), you can handle
3^W coins. Given W weighings, there can only be 3^W possible
combinations of balances, left pan heavy, and right pan heavy.
The algorithm in this case:
Divide the coins into three equal groups... A, B, and C. Weigh A
against B. If a pan sinks, it contains the heavy coin, otherwise, the
heavy coin is in group C. If your group size is 1, you've found the coin,
otherwise recurse on the group containing the heavy coin.
--- ifmail v.2.15dev5
* Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
