Уважаемые посетители!

Iskan Der · 03.05.2012 08:36:24

Iskan Der
Пользователь
Неактивен

Зарегистрирован: 23.02.2010
Сообщений: 650
Репутация : [ 2 | 0 ]

Имеются 9 монет и рычажные весы. Среди монет имеется одна фальшивая, отличающаяся от остальных по весу. Необходимо ее определить за три взвешивания.

Выглядит просто, но у меня меньше четырех взвешиваний не получается никак. Старею

Silencer · 03.05.2012 08:42:19

Silencer
Пользователь
Неактивен

Откуда: Мичуринск
Зарегистрирован: 23.10.2010
Сообщений: 846
Репутация : [ 32 | 1 ]

на 3 кучки разделить надо вначале =)

XELFAER · 03.05.2012 12:06:17

XELFAER
Пользователь
Неактивен

Откуда: ДНР, Донецк
Зарегистрирован: 22.02.2010
Сообщений: 788
Репутация : [ 26 | 0 ]

1) по 4 монеты на каждую чашу весов, и одна в запасе.
1. a) если вес чаш одинаков - монета которая фальшивая в запасе
1. б) если вес чаш разный - берем ту сторону которая легче
2) делим эту сторону 4 монеты по 2 на каждую чашу и выбираем более легкую сторону
3) делим 2 монеты на каждую чашу по одной и находим фальшивую

Верить нельзя никому...

Fat-Zer · 03.05.2012 13:01:14

Fat-Zer
Пользователь
Неактивен

Откуда: Москва
Зарегистрирован: 14.10.2010
Сообщений: 4,977
Репутация : [ 256 | 6 ]

XELFAER, не сказано, что фальшивка легче
Silencer, вроде правильно, но там хитрожопая вторая часть...

+ открыть спойлер

123 V 456 -> s1 ? {
  s1=="=": 789 - одна из фальшивая
  s1=="!=": 15 V 42 -> s2 ? {
    "=" => 36 - фальшивые
    s1==s2 => 14 - фальшивые
    s1!=s2 => 52 - фальшивые
  }
}

95% процентов проблем находятся между клавиатурой и стулом.

Vascom · 03.05.2012 15:26:03

Vascom
Пользователь
Неактивен

Откуда: Moscow
Зарегистрирован: 02.04.2010
Сообщений: 4,535
Репутация : [ 189 | 2 ]

Подразумевается, что фальшивая монета легче. Изначально монеты были золотые и серебряные (только их подделывать есть смысл), а это тяжёлые металлы. Фальшивка же должна быть из недорогого и лёгкого металла.

Iskan Der · 03.05.2012 15:29:26

Iskan Der
Пользователь
Неактивен

Зарегистрирован: 23.02.2010
Сообщений: 650
Репутация : [ 2 | 0 ]

Vascom пишет:

Подразумевается, что фальшивая монета легче. Изначально монеты были золотые и серебряные (только их подделывать есть смысл), а это тяжёлые металлы. Фальшивка же должна быть из недорогого и лёгкого металла.

Вообще-то, весь цимес задачи в том, что неизвестно, в какую сторону фальшивка от настоящей монеты отличается, иначе бы она вообще в два действия решалась.

Ranyar · 03.05.2012 15:30:43

Ranyar
Пользователь
Неактивен

Откуда: Улан-Батор
Зарегистрирован: 19.05.2010
Сообщений: 885
Репутация : [ 38 | 1 ]

Vascom пишет:

Подразумевается, что фальшивая монета легче.

Но прямо этого не сказано. В любом случае, делением на три кучки, как предложил Silencer, фальшивую монету можно найти, будь она легче или тяжелее настоящей.

Time flies like an arrow. Fruit flies like a banana.
Eats, shoots and leaves.

Vascom · 03.05.2012 15:31:39

Vascom
Пользователь
Неактивен

Откуда: Moscow
Зарегистрирован: 02.04.2010
Сообщений: 4,535
Репутация : [ 189 | 2 ]

Но если неизвестно легче или тяжелее, то делением на 3 кучки не найдёшь ведь.

Fat-Zer · 03.05.2012 15:44:32

Fat-Zer
Пользователь
Неактивен

Откуда: Москва
Зарегистрирован: 14.10.2010
Сообщений: 4,977
Репутация : [ 256 | 6 ]

Vascom пишет:

Но если неизвестно легче или тяжелее, то делением на 3 кучки не найдёшь ведь.

решается... смотри у меня под спойлером, если невтерпёж... [очевидные действия я опустил]

ЗЫ: я вас ненавижу... уже три часа на braingames.ru с этой подачи зависаю...

95% процентов проблем находятся между клавиатурой и стулом.

Vascom · 03.05.2012 15:48:25

Vascom
Пользователь
Неактивен

Откуда: Moscow
Зарегистрирован: 02.04.2010
Сообщений: 4,535
Репутация : [ 189 | 2 ]

Fat-Zer, всё равно за три взвешивания у тебя не получается определить одну фальшивую монету.

voral · 03.05.2012 16:09:00

voral
Пользователь
Неактивен

Откуда: Иваново
Зарегистрирован: 23.02.2010
Сообщений: 1,993
Репутация : [ 53 | 6 ]

Vascom пишет:

Fat-Zer, всё равно за три взвешивания у тебя не получается определить одну фальшивую монету.

Почему. Имхо в худшем случае 3

То что не убивает нас, делает нас сильнее! © Ницше.
When life puts you in tough situations, don’t say "why me". Just say "try me".
GNU/Linux Debian

Vascom · 03.05.2012 16:23:11

Vascom
Пользователь
Неактивен

Откуда: Moscow
Зарегистрирован: 02.04.2010
Сообщений: 4,535
Репутация : [ 189 | 2 ]

Может тогда распишите алгоритм Fat-Zer на пальцах и с пояснением каждой строки? Если не сложно.

Я согласен, что это можно сделать, но не алгоритмом Fat-Zer.

voral · 03.05.2012 16:59:19

voral
Пользователь
Неактивен

Откуда: Иваново
Зарегистрирован: 23.02.2010
Сообщений: 1,993
Репутация : [ 53 | 6 ]

Vascom пишет:

Может тогда распишите алгоритм Fat-Zer на пальцах и с пояснением каждой строки? Если не сложно.
Я согласен, что это можно сделать, но не алгоритмом Fat-Zer.

Делим монеты на три стопки по три.
1. 1ое Взвешивание. 123 и 456. Если веса равны то фальшивка в стопке 789 (переход на пункт 2) Иначе на п. 3.

2. Если по п.1 фальшивка в 789. 2ое взвешивание 7 против 8. Если веса равны то фальшивка 9. Больше взвешиваний не нужно. Иначе переходим на 2.1
2.1 3е взвешивание Взвешиваем 7 и 9. Если веса равны то фальшивка 8, если веса не равны фальшивка 7. Больше взвешиваний не нужно в обоих случаях

3. Перераспределяем монеты и взвешиваем (2-ое) 14 и 25. Если равны то переходим на 3.1 иначе на 3.2
3.1 Если 14 и 25 равны. То фальшивка в 3 или 6. Взвешиваем (3-е) 34 и 25. Если равны, то фальшивка 6 иначе 3. Больше взвешиваний не нужно
3.2. (Если 14 тяжелее 25 и 123 тяжелее 456 (по 1ому взвешиванию) ) или (Если 14 легче 25 и 123 легче 456 (по 1ому взвешиванию) ) то фальшивка 1 или 5 (переход на 3.2.1) иначе 4 или 2 (переход на 3.2.2)
3.2.1 Взвешиваем (3-е) 64 и 25 если равны фальшивка 1 иначе 5
3.2.2 Взвешиваем (3-е) 16 и 25 если равны фальшивка 4 иначе 2

Т.е ходы взвешиваний

1 - 2 (рез 9)
1 - 2 - 2.1 (рез 8 или 7)
1 - 3 - 3.1 (рез 6 или 3)
1 - 3 - 3.2.1 (рез 1 или 5)
1 - 3 - 3.2.2 (рез 2 или 4)

То что не убивает нас, делает нас сильнее! © Ницше.
When life puts you in tough situations, don’t say "why me". Just say "try me".
GNU/Linux Debian

Vascom · 03.05.2012 17:04:43

Vascom
Пользователь
Неактивен

Откуда: Moscow
Зарегистрирован: 02.04.2010
Сообщений: 4,535
Репутация : [ 189 | 2 ]

Не знаю как вам, а мне сложно было об этом догадаться по этому алгоритму:

123 V 456 -> s1 ? {
  s1=="=": 789 - одна из фальшивая
  s1=="!=": 15 V 42 -> s2 ? {
    "=" => 36 - фальшивые
    s1==s2 => 14 - фальшивые
    s1!=s2 => 52 - фальшивые
  }
}

voral · 03.05.2012 17:26:02

voral
Пользователь
Неактивен

Откуда: Иваново
Зарегистрирован: 23.02.2010
Сообщений: 1,993
Репутация : [ 53 | 6 ]

Vascom пишет:

Не знаю как вам, а мне сложно было об этом догадаться по этому алгоритму:

я сам не смог решить задачу пока не увидел этот алгоритм

То что не убивает нас, делает нас сильнее! © Ницше.
When life puts you in tough situations, don’t say "why me". Just say "try me".
GNU/Linux Debian

Fat-Zer · 03.05.2012 19:07:53

Fat-Zer
Пользователь
Неактивен

Откуда: Москва
Зарегистрирован: 14.10.2010
Сообщений: 4,977
Репутация : [ 256 | 6 ]

Vascom, кто захотел тот понял... =)
+ рассчитывал, что алгоритм за одно/два взвешивания определить фальшивку из 2/3 монет вы можете...
ЗЫ: я конечно мастер изобретать псевдокоды, но пару не однозначностей синтаксиса допустил... поправлюсь от греха подальше...

+ открыть спойлер

123 V 456 -> s1 ? {
  s1=="=": 789 - фальшивые
  s1=="!=": 15 V 42 -> s2 ? {
    s2=="=" : 36 - фальшивые
    s1==s2 : 14 - фальшивые
    s1!=s2 : 52 - фальшивые
  }
}

95% процентов проблем находятся между клавиатурой и стулом.

XELFAER · 03.05.2012 21:18:45

XELFAER
Пользователь
Неактивен

Откуда: ДНР, Донецк
Зарегистрирован: 22.02.2010
Сообщений: 788
Репутация : [ 26 | 0 ]

Fat-Zer пишет:

XELFAER, не сказано, что фальшивка легче

или легче или тяжелее - разница в весе, последовательность действий не меняется.

Верить нельзя никому...

Lupo Alberto · 03.05.2012 21:30:51

Lupo Alberto
Пользователь
Неактивен

Откуда: Беларусь, Гомель
Зарегистрирован: 04.07.2010
Сообщений: 11,183
Репутация : [ 571 | 8 ]

XELFAER пишет:

или легче или тяжелее - разница в весе, последовательность действий не меняется.

Меняется. Как вы определите кучку, где находится фальшивая монета, не зная, легче или тяжелее она должна быть?

Был, был и весь вышел...

XELFAER · 03.05.2012 22:30:22

XELFAER
Пользователь
Неактивен

Откуда: ДНР, Донецк
Зарегистрирован: 22.02.2010
Сообщений: 788
Репутация : [ 26 | 0 ]

Lupo Alberto пишет:

Меняется. Как вы определите кучку, где находится фальшивая монета, не зная, легче или тяжелее она должна быть?

точно, верно замечено.

Верить нельзя никому...

Vascom · 03.05.2012 22:33:26

Vascom
Пользователь
Неактивен

Откуда: Moscow
Зарегистрирован: 02.04.2010
Сообщений: 4,535
Репутация : [ 189 | 2 ]

Ну тут понятно, достаточно определить каких больше: тяжёлых или лёгких. И вроде в алгоритм это входит.

Chars67 · 03.05.2012 23:51:05

Chars67
Пользователь
Неактивен

Зарегистрирован: 21.02.2010
Сообщений: 2,429
Репутация : [ 29 | 6 ]

Фиксируем три раза по три монеты - нумеруем эти тройки - 1 2 3
\/ и /\ - cуть лоханка с этой тройкой выше или ниже
Весы - рычажные, результаты первых двух взвешиваний возможны такие:
2 3
1 == /\ 3, фальшивка легче
1 == \/ 3, тяжелее
1 \/ == 2, легче
1 /\ == 2, тяжелее
1 \/ \/ 1, тяжелее
1 /\ /\ 1, легче
Теперь известно, в какой из троек присутствует фальшивка, и легче или тяжелее она прочих монет.
И осталось ещё одно взвешивание - любых двух монет из выделенной тройки.

Давно уже не забавно наблюдать торжество отрицательного отбора.

yars · 04.05.2012 00:24:51

yars
Slacker
Неактивен

Откуда: Тамбовская область
Зарегистрирован: 23.03.2012
Сообщений: 10,043
Репутация : [ 309 | 1 ]

Задачка на перестановки, так? Тогда есть еще задачка похожая: есть три штыря: один с "блинами" и два свободных. Задача: за минимальное количество перемещений переместить "блины" с одного штыря на другой:

Как-то так:
<=> I I
<===> I I
<=====> I I
|+++++++++++++++++++++++++++|

Истинный hotplug - это обычная электрическая розетка: воткнул - работает, и никаких драйверов.
Arch Linux/Xfce/Xiaomi Mi Notebook Pro 15.6 | Slackware64-current/Xfce/Lenovo G580

Chars67 · 04.05.2012 00:32:41

Chars67
Пользователь
Неактивен

Зарегистрирован: 21.02.2010
Сообщений: 2,429
Репутация : [ 29 | 6 ]

В.Е.Кузнецов
Представление в ЭВМ неформальных процедур, с.35

Там и задача на Ханойские башни корректнее сформулирована, и решение есть,
и можно внезапно открыть для себя продукционные системы...

Давно уже не забавно наблюдать торжество отрицательного отбора.

NoXi0uZ · 04.05.2012 01:13:55

NoXi0uZ
Пользователь
Неактивен

Откуда: Москва
Зарегистрирован: 07.08.2010
Сообщений: 135
Репутация : [ 5 | 0 ]

Vascom пишет:

Но если неизвестно легче или тяжелее, то делением на 3 кучки не найдёшь ведь.

Делим на 3 по 3.
Шаг 1) взвешиваем кучку 1 и 2. Если 1 > 2, то тогда взвешиваем 1 и 3. Если 1 = 3, то фальшивая во второй куче, если 1 > 3, то в 1. Отсюда ксати делается вывод тяжелее или легче фальш монета. Ситуация 2>1обратно симметрична. Итог: на первом взвешивании неравенство, то вторым определяется в какой ( 1 или 2 ) кучке фальшивая и легче она или тяжелее.
Шаг 2) В кучке с фальш монетой берем 2 наугад и взвешиваем, если одинаковые, то фальшивая последняя. Если не равны, то та что тяжелее или лечге в зависимости от шага 1 ( там определились)

Если на шаге 1) 1 = 2, то фальшивая в 3 кучке. Тогда, берем из 3 кучки наугад две:
если 3.1 = 3.1, то фальшивая 3.3
если 3.1 <> 3.2, то 3 взывешивание: 3.1 и 3.3 - если 3.1 = 3.3, то фальшивая 3.2, если 3.1<>3.3, то 3.1 - фальшивая.

PS походу у Chars67 такое же решение)

github.com/cocaine

Termo · 04.05.2012 01:44:52

Termo
Злобный фигурант
Неактивен

Зарегистрирован: 22.03.2010
Сообщений: 5,930

Vascom пишет:

Фальшивка же должна быть из недорогого и лёгкого металла.

угу
из чугуна

ПатреГ не любит Gnome...

NoXi0uZ · 04.05.2012 08:49:10

NoXi0uZ
Пользователь
Неактивен

Откуда: Москва
Зарегистрирован: 07.08.2010
Сообщений: 135
Репутация : [ 5 | 0 ]

Termo пишет:

из чугуна

это не металл, а сплав ) И кстати, высокопрочный достаточно дорог. (Хотя ни фига он не прочный)

github.com/cocaine

ormorph · 05.05.2012 21:05:00

ormorph
Пользователь
Неактивен

Зарегистрирован: 21.02.2010
Сообщений: 1,575
Репутация : [ 64 | 0 ]

Termo пишет:

угу
из чугуна

Чугун тоже легче золота)
таблица плотности металлов тыц
m=P*V
P-плотность
V-объем
m-масса

Тока в начальном условии я не видел, что бы монеты были золотые.

Termo · 07.05.2012 15:40:19

Termo
Злобный фигурант
Неактивен

Зарегистрирован: 22.03.2010
Сообщений: 5,930

ичо?

ПатреГ не любит Gnome...

ormorph · 08.05.2012 00:17:25

ormorph
Пользователь
Неактивен

Зарегистрирован: 21.02.2010
Сообщений: 1,575
Репутация : [ 64 | 0 ]

Termo пишет:

ичо?

То что, фальшивые могут быть сделаны из того же материала, и по весу не отличаться.
Просто сделаны не тем кто имеет право на производство таких монет.

Termo · 09.05.2012 19:08:28

Termo
Злобный фигурант
Неактивен

Зарегистрирован: 22.03.2010
Сообщений: 5,930

ormorph пишет:

То что, фальшивые могут быть сделаны из того же материала, и по весу не отличаться.
Просто сделаны не тем кто имеет право на производство таких монет.

ни разу такого не видел

ПатреГ не любит Gnome...

Уважаемые посетители!

9 монет (логическая задачка) (Страница 1 из 2)

Сообщений с 1 по 30 из 36

1 Тема от Iskan Der 03.05.2012 08:36:24

2 Ответ от Silencer 03.05.2012 08:42:19 (03.05.2012 08:45:26 отредактировано Silencer)

3 Ответ от XELFAER 03.05.2012 12:06:17

4 Ответ от Fat-Zer 03.05.2012 13:01:14 (03.05.2012 13:22:39 отредактировано Fat-Zer)

5 Ответ от Vascom 03.05.2012 15:26:03

6 Ответ от Iskan Der 03.05.2012 15:29:26

7 Ответ от Ranyar 03.05.2012 15:30:43

8 Ответ от Vascom 03.05.2012 15:31:39

9 Ответ от Fat-Zer 03.05.2012 15:44:32

10 Ответ от Vascom 03.05.2012 15:48:25

11 Ответ от voral 03.05.2012 16:09:00

12 Ответ от Vascom 03.05.2012 16:23:11

13 Ответ от voral 03.05.2012 16:59:19

14 Ответ от Vascom 03.05.2012 17:04:43

15 Ответ от voral 03.05.2012 17:26:02

16 Ответ от Fat-Zer 03.05.2012 19:07:53

17 Ответ от XELFAER 03.05.2012 21:18:45

18 Ответ от Lupo Alberto 03.05.2012 21:30:51

19 Ответ от XELFAER 03.05.2012 22:30:22

20 Ответ от Vascom 03.05.2012 22:33:26

21 Ответ от Chars67 03.05.2012 23:51:05 (04.05.2012 00:06:01 отредактировано Chars67)

22 Ответ от yars 04.05.2012 00:24:51

23 Ответ от Chars67 04.05.2012 00:32:41

24 Ответ от NoXi0uZ 04.05.2012 01:13:55 (04.05.2012 01:32:55 отредактировано NoXi0uZ)

25 Ответ от Termo 04.05.2012 01:44:52

26 Ответ от NoXi0uZ 04.05.2012 08:49:10

27 Ответ от ormorph 05.05.2012 21:05:00

28 Ответ от Termo 07.05.2012 15:40:19

29 Ответ от ormorph 08.05.2012 00:17:25

30 Ответ от Termo 09.05.2012 19:08:28

Сообщений с 1 по 30 из 36

Просматривают тему: 1 гость, 0 пользователей