II РЕСПУБЛИКАНСКАЯ ОЛИМПИАДА ЮНЫХ ПРОГРАММИСТОВ.

г. Винница 1989 г.

9 класс

Теоретический тур

Т.9.1.

Есть N контактов. Проводами соединены контакты: 1-й со 2-м, 2-й с 3-м, 3-й с 4-м,...,N-1-й с N-м.

._______._____._____. . . . .________.

1 2 3 4 N-1 N

В нескольких проводах случился обрыв. Составить алгоритм, выясняющий за наименьшее количество проб, в каких проводах случился обрыв. Одна проба проверяет, идет ли ток между i-м и k-м контактами. Алгоритм при пробе может пользоваться вспомогательным литерным алгоритмом - функцией ЕСТЬТОК(i,k),принимающей значения "Да" или "Нет".

Т.9.2.

Дана функция, аргументы которой - произвольные натуральные числа

f(M-N,N), при М>N

f(M,N)= N, при М=N

f(N-M,M), при N>M

Составить алгоритм, вычисляющий значение функции без помощи рекурсии.

Т.9.3.

Есть N селений. Некоторые селения попарно соединены тропинками, вне селений никакие две тропинки общих точек не имеют. В целочисленной таблице ТРОПЫ[1:N, 1:N] задана информация о тропинках; количество тропинок между i-тым и j-тым селениями равно значению элемента таблицы ТРОПЫ[i,j]=ТРОПЫ[j,i] (в том числе для i=j) Написать алгоритм, определяющий, можно ли нарисовать карту тропинок, не отрывая карандаша от бумаги и не рисуя ни одну тропу дважды.

10 класс

Теоретический тур

Т.10.1.

Написать алгоритм, отгадывающий число N, задуманное человеком, задавая ему "да-нет" вопросы. N может быть любым конечным натуральным числом. Алгоритм должен использовать как можно меньше вопросов при больших N.

Для диалога с человеком используются вспомогательные алгоритмы ВВОД и ВЫВОД с любым количеством параметров любых типов.

Т.10.2.

Данa функция, аргументы которой - неотрицательные целые числа M и N (M £ N)

1, при М=0

f(M,N)=f(M-1,N-1)+f(M,N-1), при 0 < М < N

1, при M=N

Составить алгоритм, вычисляющий значение функции без помощи рекурсии.

Т.10.3.

Набор обобщенного домино состоит из М костей, на каждой кости нанесены два целых числа от 0 до N; любая пара чисел может встречаться в наборе 0, 1 или несколько раз. Значения костей заданы в таблице ДОМИНО[1:M,1:2].

Составить алгоритм, определяющий, можно ли построить из всех костей набора цепь по правилам домино.

П р а к т и ч е с к и й т у р .

Два человека играют в такую игру: есть электрическая схема, в которую входят батарейка, лампочки и контакты, к которым можно присоединять любое количество проводов.

Игроки ходят по очереди: при каждом ходе игрок соединяет проводом любую пару различных контактов, которая ранее не была соединена напрямую каким-либо игроком.

Игрок, после хода которого будут гореть все лампочки, считается выигравшим.

Написать программу, выступающую за одного из игроков и стремящуюся к выигрышу.

Сопротивление всех проводов считать равным 0.