Написать алгоритм определения 1 фальшивой монеты, если неизвестно больше или меньше она...

Question

Написать алгоритм определения 1 фальшивой монеты, если неизвестно больше или меньше она весит в сравнении с настоящими монетами, на 4 взвешивание. Общее количество монет 22

Answer 1

?  - фальшивая
+  - настоящая
dif  - знание о весе фальшивой (больше или меньше)
vs  - взвешивание
=>  - итог взвешивания

1 откладываем

1) 7? vs 7?
if == => 14+ 7? goto 2)
if <> => 7+ 14? goto

2) 4? vs 4+
if == => 18+ 3? goto 3)
if <> => 10+ 4? goto

3) 2? vs 2+
if == => 20+ 1? goto 4)
if <> => 19+ 2? goto

4) 1? vs 1+
if == => фальшивая та что отложена вначале
if <> => нашли

Comments

допишу позже, а то надо убегать

---

1 откладываем

1) 7? vs 7? (№1)
if == => 14+ 7? goto 2)
if <> => 7+ 14? goto 7)

2) 4? vs 4+ (№2)
if == => 18+ 3? goto 3)
if <> => 17+ 4? dif goto 6)

3) 2? vs 2+ (№3)
if == => 20+ 1? goto 4)
if <> => 19+ 2? dif goto 5)

4) 1? vs 1+ (№4)
if == => фальшивая та что отложена вначале
if <> => нашли

5) 1? vs 1? (dif) (№4)=> нашли

---

6) 2? vs 2? (dif) (№3)=> 19+ 2? goto 5)

7) 7? vs 7+ (№2)
if == => 14+ 7? dif(из предыдушего взвешивания) goto 8)
if <> => 14+ 7? dif goto 8)

8) 2? vs 2? (dif) (№3)
if == => 18+ 3? dif goto 9)
if <> => 19+ 2? dif goto 5)

9) 1? vs 1? (dif) (№4)
if == => нашли, это та что не взвешивалась из трех сомнительных
if <> => нашли

---

? не фальшивая а сомнительная

---

Я не знаю почему, но я думал, что нет такого варианта, как поровну, вот и не нашел решения. Извиняюсь, был не прав.

---

поровну взвешивать не оптимально, оптимальнее взвешивать тройками

---

выбери лучшим плиз

Answer 2

За четыре взвешивания невозможно определить, где фальшивая монета, если количество монет не является степенем двойки (2, 4, 8, 16, 32) и т.д.

Допустим, взвешиваем поровну:
11 на 11, а дальше как? 5 на 6? Там уже можно вычислить только множеством операций, и далеко не за 4 взвешивания.

Comments

можно, нечего человека обманывать

---

жду вашего решения

---

та писала его пол часа а потом сайт гллюкнул и все затерлось((( влом опять набирать

---

и как быть с неравным количеством монет на разных чашах весов?

---

И совет, не набирайте большие программы на сайте, себе дороже выйдет :). Уже на набирался. Теперь только маленькие пишу здесь и то не всегда.