Задача 76249
|
|
 |
Условие
Решить предыдущую задачу, если про массивы известно лишь, что x[1]≤...≤x[k] и y[1]≤...≤y[l] (возрастание заменено неубыванием).Решение
Условие возрастания было использовано в третьей альтернативе выбора: сдвинув k1 и l1 на 1, мы тем самым уменьшали на 1 количество общих элементов в x[k1+1]...x[k] и x[l1+1]...x[l]. Теперь это придётся делать сложнее. ...
end else begin {x[k1+1] = y[l1+1]}
| t := x [k1+1];
| while (k1<k) and (x[k1+1]=t) do begin
| | k1 := k1 + 1;
| end;
| while (l1<l) and (x[l1+1]=t) do begin
| | l1 := l1 + 1;
| end;
| n := n + 1;
end;
Замечание. Эта программа имеет дефект: при проверке условия
(k1 < k) and (x[k1+1]=t)
(или второго, аналогичного) при ложной первой скобке вторая
окажется бессмысленной (индекс выйдет за границы массива)
и возникнет ошибка.
Некоторые версии паскаля, вычисляя A and B, сначала
вычисляют A и при ложном A не вычисляют B. (Так
ведёт себя, например, система Turbo Pascal версии 5.0 — но
не 3.0.)
Тогда описанная ошибка не возникнет. Но если мы не хотим полагаться на такое свойство используемой нами реализации паскаля (не предусмотренное его автором Н. Виртом), то можно поступить так. Введём дополнительную переменную b: boolean и напишем:
if k1 < k then b := (x[k1+1]=t) else b:=false;
{b = (k1<k) and (x[k1+1] = t)}
while b do begin
| k1:=k1+1;
| if k1 < k then b := (x[k1+1]=t) else b:=false;
end;
Можно также сделать иначе:
end else begin {x[k1+1] = y[l1+1]}
| if k1 + 1 = k then begin
| | k1 := k1 + 1;
| | n := n + 1;
| end else if x[k1+1] = x [k1+2] then begin
| | k1 := k1 + 1;
| end else begin
| | k1 := k1 + 1;
| | n := n + 1;
| end;
end;
Так будет короче, хотя менее симметрично.
Наконец, можно увеличить размер массива в его описании,
включив в него фиктивные элементы.
