Поиск фальшивой монеты - Free Pascal

Формулировка задачи:

Имеется 11 монет. Золотые все. Николаевские червонцы. Среди них одна фальшивая, позолоченная. А внутри свинец. Из химии известно, что свинец легче золота. Есть аптекарские весы, точные. С двумя чашками. Программа определяет, какое минимальное число взвешиваний необходимо для определения фальшивой монеты. К тому же она указывает номер фальшивой монеты, полученный путем взвешиваний. Указание: использовать массив из 11 элементов для хранения весов монет. Вес фальшивой монеты располагать в массиве произвольно.

Решение задачи: «Поиск фальшивой монеты»

Листинг программы

{$mode objfpc}
const n = 11;
type ar=array[1..n] of integer;
var
  a:ar;
  i,j,k,p:integer;
function s(t:ar;ts,te:integer):integer;
begin
  Result:=0;
  for ts:=ts to te do Result:=Result+t[ts];
end;
begin
  randomize;
  for i:=1 to n do a[i]:=1;
  a[random(n)+1]:=0;
  for i:=1 to n do write(i,':',a[i],'  ');writeln;
  i:=1;j:=n;p:=0;
  repeat
    k:=i+(j-i) div 2;
    p:=p+1;
    if j-i=1 then begin
      if a[i]<a[j] then begin k:=i;break;end else begin k:=j;break;end;
    end;
    if s(a,i,k-1)=s(a,k,j-1) then begin k:=j;break;end;
    if s(a,i,k-1)<s(a,k,j-1) then j:=k-1 else begin i:=k;j:=j-1;end;
  until false;
  writeln('взвешиваний',p:3,' номер монеты',k:3);
end.

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

Объявлены константы и переменные:
- n = 11 (количество монет)
- ar = array[1..n] of integer (тип массива для хранения количества монет)
- i, j, k, p = integer (переменные для циклов)
- a[i] = 1 (изначально все монеты считаются настоящими)
- a[random(n)+1] = 0 (одна монета выбирается как фальшивая)
- i = 1, j = n (переменные для цикла по монетам)
- p = 0 (переменная для подсчета количества весов)
Выполняется функция s(t; ts, te): integer
- Результат функции равен сумме элементов массива t с ts до te
Выполняется цикл по монетам:
- Для каждой монеты выводится ее номер и количество
Начинается поиск фальшивой монеты с помощью вложенных циклов:
- Переменные i и j используются для определения текущего диапазона для сравнения
- Переменная p используется для подсчета количества весов
В каждой итерации находится серединная монета k
- Если разница между i и j равна 1, то сравниваются значения a[i] и a[j]
- Если значения равны, то фальшивая монета находится в диапазоне от i до j-1
- Если a[i] меньше a[j], то фальшивая монета находится в диапазоне от i+1 до j-1
- Если a[i] больше или равно a[j], то фальшивая монета находится в диапазоне от i до j-2
- Если a[i] меньше a[j] и a[i+1] меньше a[j-1], то фальшивая монета находится в диапазоне от i+1 до j-1
- Если a[i] меньше a[j] и a[i+1] больше или равно a[j-1], то фальшивая монета находится в диапазоне от i до j-2
- Если a[i] больше или равно a[j] и a[i+1] меньше a[j-1], то фальшивая монета находится в диапазоне от i+1 до j-1
- Если a[i] больше или равно a[j] и a[i+1] больше или равно a[j-1], то фальшивая монета находится в диапазоне от i до j-2
После нахождения фальшивой монеты выводится сообщение с номером этой монеты и количеством весов.