Какое минимальное количество взвешиваний необходимо для определения 8-ой монеты

@Magestian · Регистрация: 25.09.2014

Студворк — интернет-сервис помощи студентам

Задача выглядит вот так: На столе стоят две стопки монет. В одной стопке 8 золотых монет, а в другой 8 серебряных.
Обе стопки упорядочены по убыванию масс монет. Вопрос: какое минимальное количество взвешиваний необходимо для определения 8-ой монеты. За один раз можно взвешивать только 2 монеты и выбирать какая из них тяжелее.
Нужно использовать бинарный поиск. Слияния массивов применять нельзя.

P.S.: Как работает бинарный поиск я знаю(ранее задачи с ним решал). Знаю как решить задачу при помощи слияния массивов(слить массивы в один, отсортировать, применить бинарный поиск), но этого делать, увы, нельзя.
P.S.S.: Вижу, что есть похожие темы, но ответов на них нет. Помогите и объясните как тут поступать.

ФедосеевПавел · 22.02.2015, 16:53

Magestian, а что собственно нужно - 1) аналитическое доказательство достаточности X взвешиваний или 2) программа, работающая по некоему алгоритму?
Если доказательство, то думаю, нужно по индукции - доказать для 2+2 монет, потом 4+4 (снизить до 2+2), а затем и 8+8 (снизить до 4+4).
Если программа, то определиться с алгоритмом и вперёд.

@Magestian · 22.02.2015, 16:55 **[ТС]**

Алгоритм изложен выше, но программа не выходит.

ФедосеевПавел · 22.02.2015, 16:59

Боюсь выглядеть дураком, но всё же попрошу уточнить пост с описанием алгоритма. Внятным описанием.

@Magestian · 22.02.2015, 17:04 **[ТС]**

Пост #20. Понимаю, там, может быть, не хватает объяснений, но, как говориться: "чем богаты, тем и рады".

ФедосеевПавел · 22.02.2015, 17:10

Царь-Алгоритм:

Добавлено через 1 минуту
Ха, сам себе противоречу...
Добавлено через 41 секунду
Ан нет, не противоречу...

Но повторюсь: что собственно нужно - 1) аналитическое доказательство достаточности X взвешиваний или 2) программа, работающая по некоему алгоритму?
Если доказательство, то думаю, нужно по индукции - доказать для 2+2 монет, потом 4+4 (снизить до 2+2), а затем и 8+8 (снизить до 4+4).
Если программа, то определиться с алгоритмом и вперёд.

но, как говориться: "чем богаты, тем и рады".

Ты как станешь начальником маякни - мы возьмем оборудование твоей фирмы на техобслуживание. Нам будет удобно с невзыскательным заказчиком. Или всё изменится?

@Magestian · 22.02.2015, 17:26 **[ТС]**

Может вы не заметили, но там описано.
1)Проделать бинарный поиск таким образом: сравнивать монеты из стопок, при этом индексирую их так, что бы брать на рассмотрение(или исключать из рассмотрения) 8 монет. К примеру: монеты 1-8, 4-5, 2-7,3-6(заметить то, что суммы индексов равны 9). Таким образом, должно хватить 4 или пять взвешиваний(имеется ввиду сравнивание монет по весу).
2)Бинарный поиск работает, если с обеих стопок можно снять 8 самых тяжёлых монет. К примеру, 3 монеты из одной стопки и 5 монет из другой стопки.
3)Сравнивать те монеты в разных стопках, выше которых в обеих стопках в сумме лежит 7 монет. Можно, для простоты рассуждений, одну из стопок перевернуть.
4)Равенство монет предусматривать не нужно. Монеты изначально все разного веса.
Из комментариев ув. CyborgDrone.

ФедосеевПавел · 23.02.2015, 10:39

Пусть имеется по восемь серебряных и золотых монет. Обозначим текущее состояние тремя строками — серебряные монеты, оставшиеся на рассмотрение (строка, начинающаяся с «с:»), золотые монеты, оставшиеся на рассмотрение (строка, начинающаяся с «з:»), строка с монетами, попавшими в итоговую стопку (строка, начинающаяся с «и:»). Т.к. рассматриваться будут не все монеты, то для упрощения обозначим индексы диапазонов как Ls, Rs (для серебряных монет) и Lg, Rg (для золотых монет).
Согласно условию, монеты в стопках упорядочены по убыванию веса, т.е. монеты с меньшими индексами (ближе к столу) имеют больший вес. И соответственно монеты в результирующей стопке будут расположены также. Начальное состояние описывается так:
с: 1с 2с 3с 4с 5с 6с 7с 8с (Ls=1, Rs=8)
з: 1з 2з 3з 4з 5з 6з 7з 8з (Lg=1, Rg=8)
и:
Попробуем определить монеты, которые попадут в итоговую стопку из восьми монет.
1. Первое взвешивание делаем для монет, находящихся посредине каждой стопки. Т.е. взвешиваем S[(Ls+Rs)/2] и G[(Lg+Rg)/2]. Из-за того, что стопки монет равноценны, то предположим, что S[(Ls+Rs)/2] < G[(Lg+Rg)/2]. Ясно что в итоговую стопку попадут монеты с большим весом, т.е. G[Lg]...G[(Lg+Rg)/2].
Получим
с: 1с 2с 3с 4с
з: 5з 6з 7з 8з
и: 1з 2з 3з 4з
В стопке золотых монет остались G[((Lg+Rg)/2)+1]...G[Rg] — то есть всё, что осталось.
В стопке серебряных монет остались пригодными к дальнейшему рассмотрению S[Ls]...S[(Ls+Rs)/2]. Это следует из соображения, что в итоговой стопке будет 8 монет, из которых 4 уже определены, и из серебряных туда попадут лишь наиболее тяжелые.
2. В итоговой стопке имеется 4 монеты, при дальнейшем решении в стопку будут добавляться другие монеты и, возможно, что при сортировке эти монеты бы расположились между монетами первой партии.
Итак, получаем условие

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
if S[(Ls+Rs) div 2] < G[(Lg+Rg) div 2] then
begin
  Ls:=Ls;
  Rs:=(Ls+Rs) div 2;
  Lg:=((Lg+Rg) div 2)+1;
  Rg:=Rg;
end
else
begin
  Ls:=((Ls+Rs) div 2)+1;
  Rs:=Rs;
  Lg:=Lg;
  Rg:=(Lg+Rg) div 2;
end;

2. Повторим аналогичную процедуру взвешивания для оставшихся частей стопок. Получим
с: 1с 2с <--- условно, но останется два
з: 5з 6з <--- условно, но останется два
и: 1з 2з 3з 4з 5x 6x <---- новая партия обозначена индексом x
3. Повторим аналогичную процедуру взвешивания для оставшихся частей стопок. Получим
с: 1с <--- условно, но останется один
з: 5з <--- условно, но останется один
и: 1з 2з 3з 4з 5x 6x 7y <---- новая партия обозначена индексом y
4. Повторим аналогичную процедуру взвешивания для оставшихся частей стопок. Получим
с:
з:
и: 1з 2з 3з 4з 5x 6x 7y 8z <---- новая партия обозначена индексом z
5. У нас теперь есть перечень монет, которые будут присутствовать в итоговой стопке в числе первых восьми. Осталось определить из четырёх кандидатов (4з 6x 7y 8z), который из них меньше — он и будет восьмым по порядку в новой стопке. Это реализуется тремя взвешиваниями: Result:=min(min(4з, 6x), min(7y, 8z)).
Итого, получается семь взвешиваний.

Пример программы.
Она убогая:
1. Плохо определено условие прекращения взвешиваний (цикл while).
2. Перечень индексов для заключительных взвешиваний из итогового массива задан жёстко.

Pascal
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
program Coins;
 
const
  N = 8;
type
  TArray = array[1..N] of integer;
 
  function min(a, b: integer): integer;
  begin
    if a < b then
      min := a
    else
      min := b;
  end;
 
const
  s: TArray = (290, 280, 270, 260, 250, 240, 230, 220);
  g: TArray = (291, 242, 233, 232, 231, 223, 222, 221);
var
  r:  TArray;  {итоговая стопка}
  Rr: integer; {текущая "высота" итоговой стопки}
  Ls, Rs, Lg, Rg: integer;
  Count: integer; {подсчёт взвешиваний}
  i:  integer;
begin
  Count := 0;
  Rr := 0;
  Ls := 1;
  Rs := N;
  Lg := 1;
  Rg := N;
  while Rr < N do
  begin
    Inc(Count);
    if s[(Ls + Rs) div 2] < g[(Lg + Rg) div 2] then
    begin
      for i := Lg to (Lg + Rg) div 2 do
      begin
        Inc(Rr);
        r[Rr] := g[i];
      end;
      Ls := Ls;
      Rs := (Ls + Rs) div 2;
      Lg := ((Lg + Rg) div 2) + 1;
      Rg := Rg;
 
    end
    else
    begin
      for i := Ls to (Ls + Rs) div 2 do
      begin
        Inc(Rr);
        r[Rr] := s[i];
      end;
      Ls := ((Ls + Rs) div 2) + 1;
      Rs := Rs;
      Lg := Lg;
      Rg := (Lg + Rg) div 2;
    end;
  end;
  writeln('The 8th coin is ', min(min(r[4], r[6]), min(r[7], r[8])));
  writeln(Count + 3);
end.

Добавлено через 13 минут
-------------------------------
Это алгоритм решения задачи о поиске 8-й монеты в итоговой стопке без сортировки слиянием.
Это не обязательно оптимальный, он просто такой, каким я его вижу.
Magestian, программа здесь вторична, главное - описание действий. Будет другое - изменится и программа. Может я глупый, но описание из твоего поста не наводит меня на какие-либо мысли.

Добавлено через 14 минут
-------------------------
Я добавил сообщение. Потом заметил опечатку в раннем тексте, нажал правку, подредактировал, но исчез поздний текст. Может что-то нажал неправильно или глюки браузера.
Поэтому восстановлю сообщения.
-------------------------
Заметил, что по результатам работы r[8] - и есть искомая 8-я монета. Решил доказать, что дополнительные взвешивания не нужны.

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

Итог, достаточно 4-х взвешиваний в цикле, дополнительный поиск минимума min(min(), min()) - не требуется.
Исправление программы (удаление лишних строк, массива r, функции min и прочего) оставлю для ТС.

@Magestian · 24.02.2015, 00:21 **[ТС]**

Вот, посидел пару часиков и решил(может кому пригодиться).

Pascal
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
Program coins;
const   n=8;
var     a,b:array [1..n] of integer;
        i,ii,lg,rg,ls,rs,kv,cn:integer;
 
Begin
for i:=1 to n do
Begin
 write('Enter gold coin a[',i,']: ');
 readln(a[i]);
End;
for i:=1 to n do
Begin
 write('Enter silver coin b[',i,']: ');
 readln(b[i]);
End;
lg:=1;
ls:=1;
rg:=n;
rs:=n;
kv:=0;
while (lg<>rg) and (ls<>rs) do
Begin
i:=(lg+rg) div 2;
ii:=(ls+rs) div 2;
if a[i]<b[ii] then
Begin
rg:=i;
ls:=ii+1;
End else
Begin
lg:=i+1;
rs:=ii;
End;
inc(kv);
End;
if a[lg]<b[ls] then cn:=b[ls]
else cn:=a[lg];
inc(kv);
writeln('Coin is: ',cn,'. Weighings: ',kv);
readln;
End.

ФедосеевПавел · 24.02.2015, 00:48

Сообщение от Magestian

Вот, посидел пару часиков и решил(может кому пригодиться).

Ай да молодец!

Новые блоги и статьи Все статьи Все блоги /
Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125

	Какое минимальное количество взвешиваний необходимо для определения 8-ой монеты 18.02.2015, 18:53. Показов 4148. Ответов 28 Метки нет (Все метки) Задача выглядит вот так: На столе стоят две стопки монет. В одной стопке 8 золотых монет, а в другой 8 серебряных. Обе стопки упорядочены по убыванию масс монет. Вопрос: какое минимальное количество взвешиваний необходимо для определения 8-ой монеты. За один раз можно взвешивать только 2 монеты и выбирать какая из них тяжелее. Нужно использовать бинарный поиск. Слияния массивов применять нельзя. P.S.: Как работает бинарный поиск я знаю(ранее задачи с ним решал). Знаю как решить задачу при помощи слияния массивов(слить массивы в один, отсортировать, применить бинарный поиск), но этого делать, увы, нельзя. P.S.S.: Вижу, что есть похожие темы, но ответов на них нет. Помогите и объясните как тут поступать. 0

ФедосеевПавел Модератор 8675 / 4512 / 1670 Регистрация: 01.02.2015 Сообщений: 13,949 Записей в блоге: 14
	22.02.2015, 16:53
	Magestian, а что собственно нужно - 1) аналитическое доказательство достаточности X взвешиваний или 2) программа, работающая по некоему алгоритму? Если доказательство, то думаю, нужно по индукции - доказать для 2+2 монет, потом 4+4 (снизить до 2+2), а затем и 8+8 (снизить до 4+4). Если программа, то определиться с алгоритмом и вперёд. 0

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125
	22.02.2015, 16:55 [ТС]
	Алгоритм изложен выше, но программа не выходит. 0

ФедосеевПавел Модератор 8675 / 4512 / 1670 Регистрация: 01.02.2015 Сообщений: 13,949 Записей в блоге: 14
	22.02.2015, 16:59
	Боюсь выглядеть дураком, но всё же попрошу уточнить пост с описанием алгоритма. Внятным описанием. 0

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125
	22.02.2015, 17:04 [ТС]
	Пост #20. Понимаю, там, может быть, не хватает объяснений, но, как говориться: "чем богаты, тем и рады". 0

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125
	22.02.2015, 17:26 [ТС]
	Может вы не заметили, но там описано. 1)Проделать бинарный поиск таким образом: сравнивать монеты из стопок, при этом индексирую их так, что бы брать на рассмотрение(или исключать из рассмотрения) 8 монет. К примеру: монеты 1-8, 4-5, 2-7,3-6(заметить то, что суммы индексов равны 9). Таким образом, должно хватить 4 или пять взвешиваний(имеется ввиду сравнивание монет по весу). 2)Бинарный поиск работает, если с обеих стопок можно снять 8 самых тяжёлых монет. К примеру, 3 монеты из одной стопки и 5 монет из другой стопки. 3)Сравнивать те монеты в разных стопках, выше которых в обеих стопках в сумме лежит 7 монет. Можно, для простоты рассуждений, одну из стопок перевернуть. 4)Равенство монет предусматривать не нужно. Монеты изначально все разного веса. Из комментариев ув. CyborgDrone. 0