ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 76248
Темы:    [ Условный оператор ]
[ Знакомство с циклами ]
Сложность: 2
Классы:
В корзину
Прислать комментарий

Условие

Даны два возрастающих массива 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; вторая добавлена для симметрии.

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .