|
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. |
© Всеукраинский виртуальный центр олимпиад школьников "ОЛІМП"