Задача 76254
|
|
 |
Условие
(из книги Д. Гриса) Некоторое число содержится в каждом из
трёх целочисленных неубывающих массивов
x[1]≤...≤x[p],
y[1]≤...≤y[q],
z[1]≤...≤z[r]. Найти одно из таких чисел.
Число действий должно быть порядка
p + q + r.
Решение
p1:=1; q1=1; r1:=1;
{инвариант: x[p1]..x[p], y[q1]..y[q], z[r1]..z[r]
содержат общий элемент}
while not ((x[p1]=y[q1]) and (y[q1]=z[r1])) do begin
| if x[p1]<y[q1] then begin
| | p1:=p1+1;
| end else if y[q1]<z[r1] then begin
| | q1:=q1+1;
| end else if z[r1]<x[p1] then begin
| | r1:=r1+1;
| end else begin
| | { так не бывает }
| end;
end;
{x[p1] = y[q1] = z[r1]}
writeln (x[p1]);
