|
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. |
