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

Объяснение кода листинга программы

В данном коде происходит следующее:

  1. Создается программа coins.
  2. Используются библиотеки crt, которые необходимы для работы с консольным вводом и выводом.
  3. Задаются константы и переменные: n - количество монет, kv - вес первой монеты, i - текущий индекс, Lg - левая граница диапазона, Rg - правая граница диапазона, Ls - левая граница диапазона для серебра, Rs - правая граница диапазона для серебра, a[i] и b[i] - значения i-ой золотой и серебряной монеты соответственно.
  4. Выводится запрос на ввод значений золотых монет.
  5. Для каждого значения золотой монеты (от 1 до n) выводится запрос на ввод соответствующей серебряной монеты.
  6. Инициализируются переменные Lg, Rg, Ls и Rs.
  7. Запускается цикл while, который выполняется до тех пор, пока Lg меньше или равно Rg и Ls меньше или равно Rs.
  8. Внутри цикла увеличивается значение переменной kv.
  9. Вычисляется средний индекс i, который делит диапазон на две равные части.
  10. Если значение a[i] больше значения b[i], то Lg обновляется на i.
  11. Если значение a[i] меньше значения b[i], то Rs обновляется на (n-i)+1.
  12. После выполнения цикла выводится значение kv.
  13. Программа завершается и выводится запрос на ввод следующей строки.

Оцени полезность:

6   голосов , оценка 4 из 5
Похожие ответы