Какое минимальное количество взвешиваний необходимо для определения 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

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

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

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

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

@Cyborg Drone Модератор 10451 / 5746 / 3409 Регистрация: 17.08.2012 Сообщений: 17,479
	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 Модератор 10451 / 5746 / 3409 Регистрация: 17.08.2012 Сообщений: 17,479
	18.02.2015, 22:35
	Многократное применение бинарного поиска к обеим массивам со сравнением результатов. Однако, не понимаю, как с помощью бинарного поиска определить минимальное количество взвешиваний. Всё дело в том, что это количество меньше, чем будет иметь место при применении бинарного поиска. Не знаю. Сдаюсь. 0

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

ФедосеевПавел Модератор 8665 / 4502 / 1670 Регистрация: 01.02.2015 Сообщений: 13,931 Записей в блоге: 13
	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

ФедосеевПавел Модератор 8665 / 4502 / 1670 Регистрация: 01.02.2015 Сообщений: 13,931 Записей в блоге: 13
	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 Модератор 10451 / 5746 / 3409 Регистрация: 17.08.2012 Сообщений: 17,479
	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 Модератор 10451 / 5746 / 3409 Регистрация: 17.08.2012 Сообщений: 17,479
	19.02.2015, 20:24
	В принципе, вроде чего-то наклёвывается... Сравнивать те монеты в разных стопках, выше которых в обеих стопках в сумме лежит 7 монет... Можно для простоты рассуждений одну из стопок перевернуть... Пока думаю... Добавлено через 4 минуты Вот ведь... Ещё нужно предусмотреть равенство масс двух монет... 0

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