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

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

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

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

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

@Cyborg Drone · 18.02.2015, 20:18

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

@Magestian · 18.02.2015, 22:27 **[ТС]**

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

Добавлено через 2 часа 5 минут
И да, восьмую по весу, начиная от самой тяжёлой.

@Cyborg Drone · 18.02.2015, 22:35

Многократное применение бинарного поиска к обеим массивам со сравнением результатов. Однако, не понимаю, как с помощью бинарного поиска определить минимальное количество взвешиваний. Всё дело в том, что это количество меньше, чем будет иметь место при применении бинарного поиска.

Не знаю. Сдаюсь.

@Magestian · 18.02.2015, 22:44 **[ТС]**

Есть у меня мысль, как раз хотел написать, но вы меня опередили.
Сравнивать результаты бинарного поиска, таким образом и найти восьмой элемент.

(или же просто не сбивая их в кучу, сравнивать самую тяжёлую(то есть первую) золотую(то есть из первого массива(стопки)), с самой тяжёлой(то есть первой) серебрянной(то есть из второго массива(стопки)), поставить их в порядке убывания, сделать такой же процесс с элементами меньше, опять поставить в порядке убывания, и так до тех пор пока не будет обнаружен восьмой по списку(а значит нужный) элемент(монета). Но это же не тот способ.

ФедосеевПавел · 18.02.2015, 22:54

Может быть, там накладывается условие о 8-ми упорядоченных монетах в итоговой стопке. Поясню. Если 1-ю серебряную монету вставить после 3-й золотой, то из серебряных монет к дальнейшему рассмотрению остаются только 2...5, а из золотых - 4...7.
А сам поиск производить выбирая бинарным поиском монету из серебряной стопки и пытаясь найти её место бинарным поиском в золотой стопке. После нахождения места уменьшаются диапазоны поиска в обоих стопках (или только в одной).
Подозреваю, что число взвешиваний будет стремиться к log₂8=3.

@Cyborg Drone · 18.02.2015, 23:16

ФедосеевПавел, сказано:

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

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

Дело в том, что каждый бинарный поиск в n элементах означает floor(log₂n) взвешиваний, и поисков в стопках будет несколько, а общее количество взвешиваний будет больше, чем не минимальное, не максимальное, а необходимое количество взвешиваний, которое равно 7.

@Magestian · 18.02.2015, 23:35 **[ТС]**

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
Program coins;
uses    crt;
const   n=8;
var     kv,i,Lg,Rg,Ls,Rs:integer;
        a,b:array[1..n] of integer;
 
Begin
writeln('Enter gold coins (a[i]): ');
for i:=1 to n do
Begin
writeln('Enter a[',i,']: ');
readln(a[i]);
End;
for i:=1 to n do
Begin
writeln('Enter silver coins (b[i]): ');
readln(b[i]);
End;
Lg:=1; Rg:=n;
Ls:=1; Rs:=n;
while (Lg<=Rg) and (Ls<=Rs) do
Begin
inc(kv);
i:=(Lg+Rs) div 2;
if a[i]>b[i] then  Lg:=i else if a[i]<b[i] then Rs:=(n-i)+1;
End;
writeln(kv);
readln;
End.

Вот написал, но вылетает с exitcode201(tange check error). Где-то массив вылазит за границу.
Тут я просто нахожу сначала средние элементы обеих массивов, сравниваю их; если первое больше, то из первого массива убрать, те элементы, что стоят выше, а если второе больше, то из второго массива убрать, те элементы, что находятся ниже.

Тут, не то, но это то что, я понял. Как дальше-то - не ясно.

@gazlan · 18.02.2015, 23:41

- До этой высоты ползем зигзугом.
- Не зигзугом, а зигзагом, товарищ майор!
- Как я скажу, так и поползете!

Не очень понял про "бинарный поиск". Фактически, речь идет о сортировке слиянием: необходимо отсортировать первые 8 элементов из двух предварительно отсортированных массивов, то есть ровно 8 взвешиваний (попарных сравнений "серебро-золото"), выбирая на каждом шаге более тяжелый элемент.

@Magestian · 18.02.2015, 23:44 **[ТС]**

Да вот слияние делать нельзя.

ФедосеевПавел · 18.02.2015, 23:48

пусть с: - стопка серебряных монет к рассмотрению, з: - золотых, и: - итоговая.

с: 1 2 3 4 5 6 7 8
з: 1 2 3 4 5 6 7 8
и:
1. 4с < 4з
с: 5 6 7 8
з: 1 2 3 4
и: 1с 2с 3с 4с
2. 6с < 2з
с: 7 8
з: 1 2
и: 1с 2с 3с 4с 5с 6с
3. 7с > 1з
с: 7
з: 2
и: 1с 2с 3с 4с 5с 6с
4. 7с > 2з
с:
з:
и: 1с 2с 3с 4с 5с 6с 2з 7с

4 взвешивания. Т.к. рассматриваемые стопки уменьшаются.

@Magestian · 18.02.2015, 23:57 **[ТС]**

Вот это то и оно, но ещё нужно найти эту восьмую монету.

@gazlan · 18.02.2015, 23:58

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

слияние делать нельзя

Фактически, оно и не делается - просто передвигаем два указателя, пока не достигнем 8-го элемента.

@Cyborg Drone · 19.02.2015, 00:13

А я тоже тормоз Диснейленда... Сколько бинарных поисков будет... Да какая разница!

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

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

А вопрос-то поставлен совсем не так, как мы все его трактуем. Перевожу с русского на русский:

Не взвешивать, други, совершенно не нужно это. Никто не просит определить, какая именно монета находится на 8 месте.

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

Я пришёл к выводу, что минимальное количество взвешиваний при известных массах будет либо 7, либо 8. 8 получится, если нижняя монета в одной из стопок тяжелее верхней в другой стопке.

В такой трактовке уже можно задуматься, как этот бинарный поиск сюда применить...

@Magestian · 19.02.2015, 00:26 **[ТС]**

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

Вот это то и оно, но ещё нужно найти эту восьмую монету.

Нужно. А проходов по контрольному примеру, что дали мне, должно быть судя по всему 4 или 5 всего.

@Cyborg Drone · 19.02.2015, 08:29

Ну да, ну да... Типа, проделать бинарный поиск так: сравнивать монеты из соседних стопок, индексируя их так, чтобы рассматривать (или исключить из рассмотрения, не суть важно) 8 монет... Пример: 1-8, 4-5, 2-7, 3-6 (суммы индексов = 9). Казалось бы, хватит 4 шагов, ну, или 5, чтобы ещё выяснить, в какой стопке верхняя монета тяжелее... Работает, если вес монет при объединении в один массив идёт "вперекрышку", возможно, частично. Да вот беда, возможно такое расположение масс, когда бинарный поиск ошибётся. Например,

16 07 06 05 04 03 02 01
15 14 13 12 11 10 09 08

Дело в том, что монеты не взвешиваются, а сравниваются по весу. Сдаётся мне, что создатели задачи приняли желаемое за действительное...

Добавлено через 6 минут
Что подумал... Бинарный поиск работает, если с обеих стопок можно снять 8 самых тяжёлых монет... Например, 3 из одной и 5 из другой.

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

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

@Magestian · 19.02.2015, 18:23 **[ТС]**

С утра это дошло, но код написать по данному алгоритму не смог.

Добавлено через 13 минут
Перебрал код, что оставлял сверху - нету результата.

@Cyborg Drone · 19.02.2015, 20:24

В принципе, вроде чего-то наклёвывается... Сравнивать те монеты в разных стопках, выше которых в обеих стопках в сумме лежит 7 монет... Можно для простоты рассуждений одну из стопок перевернуть... Пока думаю...

Добавлено через 4 минуты
Вот ведь... Ещё нужно предусмотреть равенство масс двух монет...

@Magestian · 19.02.2015, 20:30 **[ТС]**

Равенство предусматривать ненужно. Все монеты разные.

@Magestian · 22.02.2015, 15:53 **[ТС]**

Итак, подведу рассуждения в кучу:
1)

Сообщение от Cyborg Drone

Ну да, ну да... Типа, проделать бинарный поиск так: сравнивать монеты из соседних стопок, индексируя их так, чтобы рассматривать (или исключить из рассмотрения, не суть важно) 8 монет... Пример: 1-8, 4-5, 2-7, 3-6 (суммы индексов = 9). Казалось бы, хватит 4 шагов, ну, или 5, чтобы ещё выяснить, в какой стопке верхняя монета тяжелее... Работает, если вес монет при объединении в один массив идёт "вперекрышку", возможно, частично. Да вот беда, возможно такое расположение масс, когда бинарный поиск ошибётся. Например,
16 07 06 05 04 03 02 01
15 14 13 12 11 10 09 08
Дело в том, что монеты не взвешиваются, а сравниваются по весу. Сдаётся мне, что создатели задачи приняли желаемое за действительное...
Добавлено через 6 минут
Что подумал... Бинарный поиск работает, если с обеих стопок можно снять 8 самых тяжёлых монет... Например, 3 из одной и 5 из другой.
Добавлено через 1 минуту
Ха, сам себе противоречу...
Добавлено через 41 секунду
Ан нет, не противоречу...

2)

Сообщение от Cyborg Drone

В принципе, вроде чего-то наклёвывается... Сравнивать те монеты в разных стопках, выше которых в обеих стопках в сумме лежит 7 монет... Можно для простоты рассуждений одну из стопок перевернуть... Пока думаю...
Добавлено через 4 минуты
Вот ведь... Ещё нужно предусмотреть равенство масс двух монет...

3)

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

Равенство предусматривать ненужно. Все монеты разные.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

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

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

@Cyborg Drone Модератор 10422 / 5710 / 3401 Регистрация: 17.08.2012 Сообщений: 17,367
	18.02.2015, 20:18
	Не вполне понятно условие... Выяснить, какая монета в обеих стопках на 8 месте по весу от самой тяжёлой? И где в каждой стопке расположена тяжелейшая монета: сверху или снизу? 0

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125
	18.02.2015, 22:27 [ТС]
	Тяжелейшая монета в самом верху, так как упорядочено по убыванию массы монет. А найти надо восьмую монету с учётом того, что обе кучи как бы "вместе"(то слияние массивов, которое делать нельзя). Добавлено через 2 часа 5 минут И да, восьмую по весу, начиная от самой тяжёлой. 0

@Cyborg Drone Модератор 10422 / 5710 / 3401 Регистрация: 17.08.2012 Сообщений: 17,367
	18.02.2015, 22:35
	Многократное применение бинарного поиска к обеим массивам со сравнением результатов. Однако, не понимаю, как с помощью бинарного поиска определить минимальное количество взвешиваний. Всё дело в том, что это количество меньше, чем будет иметь место при применении бинарного поиска. Не знаю. Сдаюсь. 0

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125
	18.02.2015, 22:44 [ТС]
	Есть у меня мысль, как раз хотел написать, но вы меня опередили. Сравнивать результаты бинарного поиска, таким образом и найти восьмой элемент. (или же просто не сбивая их в кучу, сравнивать самую тяжёлую(то есть первую) золотую(то есть из первого массива(стопки)), с самой тяжёлой(то есть первой) серебрянной(то есть из второго массива(стопки)), поставить их в порядке убывания, сделать такой же процесс с элементами меньше, опять поставить в порядке убывания, и так до тех пор пока не будет обнаружен восьмой по списку(а значит нужный) элемент(монета). Но это же не тот способ. 0

ФедосеевПавел Модератор 8655 / 4490 / 1669 Регистрация: 01.02.2015 Сообщений: 13,898 Записей в блоге: 12
	18.02.2015, 22:54
	Может быть, там накладывается условие о 8-ми упорядоченных монетах в итоговой стопке. Поясню. Если 1-ю серебряную монету вставить после 3-й золотой, то из серебряных монет к дальнейшему рассмотрению остаются только 2...5, а из золотых - 4...7. А сам поиск производить выбирая бинарным поиском монету из серебряной стопки и пытаясь найти её место бинарным поиском в золотой стопке. После нахождения места уменьшаются диапазоны поиска в обоих стопках (или только в одной). Подозреваю, что число взвешиваний будет стремиться к log₂8=3. 0

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125
	18.02.2015, 23:44 [ТС]
	Да вот слияние делать нельзя. 0

ФедосеевПавел Модератор 8655 / 4490 / 1669 Регистрация: 01.02.2015 Сообщений: 13,898 Записей в блоге: 12
	18.02.2015, 23:48
	пусть с: - стопка серебряных монет к рассмотрению, з: - золотых, и: - итоговая. с: 1 2 3 4 5 6 7 8 з: 1 2 3 4 5 6 7 8 и: 1. 4с < 4з с: 5 6 7 8 з: 1 2 3 4 и: 1с 2с 3с 4с 2. 6с < 2з с: 7 8 з: 1 2 и: 1с 2с 3с 4с 5с 6с 3. 7с > 1з с: 7 з: 2 и: 1с 2с 3с 4с 5с 6с 4. 7с > 2з с: з: и: 1с 2с 3с 4с 5с 6с 2з 7с 4 взвешивания. Т.к. рассматриваемые стопки уменьшаются. 0

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125
	18.02.2015, 23:57 [ТС]
	Вот это то и оно, но ещё нужно найти эту восьмую монету. 0

@Cyborg Drone Модератор 10422 / 5710 / 3401 Регистрация: 17.08.2012 Сообщений: 17,367
	19.02.2015, 08:29
	Ну да, ну да... Типа, проделать бинарный поиск так: сравнивать монеты из соседних стопок, индексируя их так, чтобы рассматривать (или исключить из рассмотрения, не суть важно) 8 монет... Пример: 1-8, 4-5, 2-7, 3-6 (суммы индексов = 9). Казалось бы, хватит 4 шагов, ну, или 5, чтобы ещё выяснить, в какой стопке верхняя монета тяжелее... Работает, если вес монет при объединении в один массив идёт "вперекрышку", возможно, частично. Да вот беда, возможно такое расположение масс, когда бинарный поиск ошибётся. Например, 16 07 06 05 04 03 02 01 15 14 13 12 11 10 09 08 Дело в том, что монеты не взвешиваются, а сравниваются по весу. Сдаётся мне, что создатели задачи приняли желаемое за действительное... Добавлено через 6 минут Что подумал... Бинарный поиск работает, если с обеих стопок можно снять 8 самых тяжёлых монет... Например, 3 из одной и 5 из другой. Добавлено через 1 минуту Ха, сам себе противоречу... Добавлено через 41 секунду Ан нет, не противоречу... 0

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125
	19.02.2015, 18:23 [ТС]
	С утра это дошло, но код написать по данному алгоритму не смог. Добавлено через 13 минут Перебрал код, что оставлял сверху - нету результата. 0

@Cyborg Drone Модератор 10422 / 5710 / 3401 Регистрация: 17.08.2012 Сообщений: 17,367
	19.02.2015, 20:24
	В принципе, вроде чего-то наклёвывается... Сравнивать те монеты в разных стопках, выше которых в обеих стопках в сумме лежит 7 монет... Можно для простоты рассуждений одну из стопок перевернуть... Пока думаю... Добавлено через 4 минуты Вот ведь... Ещё нужно предусмотреть равенство масс двух монет... 0

@Magestian 1 / 1 / 0 Регистрация: 25.09.2014 Сообщений: 125
	19.02.2015, 20:30 [ТС]
	Равенство предусматривать ненужно. Все монеты разные. 0