Задача 76248
|
|
 |
Условие
Даны два возрастающих массива x: array[1..k] of integer и y: array[1..l] of integer. Найти количество общих элементов в этих массивах, то есть количество тех целых t, для которых t = x[i] = y[j] для некоторых i и j. (Число действий порядка k + l.)Решение
k1:=0; l1:=0; n:=0;
{инвариант: 0<=k1<=k; 0<=l1<=l;
искомый ответ = n + количество общих
элементов в x[k1+1]...x[k] и y[l1+1]...y[l]}
while (k1 <> k) and (l1 <> l) do begin
| if x[k1+1] < y[l1+1] then begin
| | k1 := k1 + 1;
| end else if x[k1+1] > y[l1+1] then begin
| | l1 := l1 + 1;
| end else begin {x[k1+1] = y[l1+1]}
| | k1 := k1 + 1;
| | l1 := l1 + 1;
| | n := n + 1;
| end;
end;
{k1 = k или l1 = l, поэтому одно из множеств, упомянутых
в инварианте, пусто, а n равно искомому ответу}
Замечание. В третьей альтернативе достаточно было бы увеличивать одну из переменных k1, l1; вторая добавлена для симметрии.
