Задача 76254

Темы:    [ Одномерные массивы ] [ Задачи с целыми числами ]

Сложность: 2 Классы:

Условие

(из книги Д. Гриса) Некоторое число содержится в каждом из трёх целочисленных неубывающих массивов 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]);

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	2
Название	Массивы
задача
Номер	1.2.23