Какое минимальное количество взвешиваний необходимо для определения 8-ой монеты - Pascal
Формулировка задачи:
Задача выглядит вот так: На столе стоят две стопки монет. В одной стопке 8 золотых монет, а в другой 8 серебряных.
Обе стопки упорядочены по убыванию масс монет. Вопрос: какое минимальное количество взвешиваний необходимо для определения 8-ой монеты. За один раз можно взвешивать только 2 монеты и выбирать какая из них тяжелее.
Нужно использовать бинарный поиск. Слияния массивов применять нельзя.
P.S.: Как работает бинарный поиск я знаю(ранее задачи с ним решал). Знаю как решить задачу при помощи слияния массивов(слить массивы в один, отсортировать, применить бинарный поиск), но этого делать, увы, нельзя.
P.S.S.: Вижу, что есть похожие темы, но ответов на них нет. Помогите и объясните как тут поступать.
Решение задачи: «Какое минимальное количество взвешиваний необходимо для определения 8-ой монеты»
textual
Листинг программы
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.
Объяснение кода листинга программы
В данном коде происходит следующее:
- Создается программа
coins
. - Используются библиотеки
crt
, которые необходимы для работы с консольным вводом и выводом. - Задаются константы и переменные: n - количество монет, kv - вес первой монеты, i - текущий индекс, Lg - левая граница диапазона, Rg - правая граница диапазона, Ls - левая граница диапазона для серебра, Rs - правая граница диапазона для серебра, a[i] и b[i] - значения i-ой золотой и серебряной монеты соответственно.
- Выводится запрос на ввод значений золотых монет.
- Для каждого значения золотой монеты (от 1 до n) выводится запрос на ввод соответствующей серебряной монеты.
- Инициализируются переменные Lg, Rg, Ls и Rs.
- Запускается цикл while, который выполняется до тех пор, пока Lg меньше или равно Rg и Ls меньше или равно Rs.
- Внутри цикла увеличивается значение переменной kv.
- Вычисляется средний индекс i, который делит диапазон на две равные части.
- Если значение a[i] больше значения b[i], то Lg обновляется на i.
- Если значение a[i] меньше значения b[i], то Rs обновляется на (n-i)+1.
- После выполнения цикла выводится значение kv.
- Программа завершается и выводится запрос на ввод следующей строки.