|
II РЕСПУБЛIКАНСЬКА ОЛIМПIАДА ЮНИХ ПРОГРАМIСТIВ.
м. Вiнниця 1989 г.
9 клас
Теоретичний тур
Т.9.1.
Є N контактiв. Проводами з'єднанi контакти: 1-й з 2-м, 2-й з 3-м, 3-й з 4-м,...,N-1-й з N-м.
._______._____._____. . . . .________.
1 2 3 4 N-1 N
В декiлькох проводах трапився обрив. Скласти алгоритм, який з'ясовує за найменшу кiлькiсть спроб, в яких проводах трапився обрив. Одна спроба перевiряє, чи тече струм мiж i-м i k-м контактами. Алгоритм при спробi може користуваитсь допомiжним лiтерним алгоритмом - функцiєю ЄТРУМ(i,k), яка приймає значення "Так" або "Нi".
Т.9.2.
Данa функцiя, аргументи якої - довiльнi натуральнi числа
f(M-N,N), при М>N
f(M,N)= N, при М=N
f(N-M,M), при N>M
Скласти алгоритм, що знаходить значення функцiї без допомоги рекурсiї.
Т.9.3.
Есть N сiл. Деякi села попарно з'єднанi стежками, зовнi сiл жоднi двi стежки спiльних точок не мають. В целочисельнiй таблицi СТЕЖКИ[1:N, 1:N] задана iнформацiя щодо стежок; кiлькiсть стежок мiж i-м та j-м селами дорiвнює значенню елемента таблицi СТЕЖКИ[i,j]=СТЕЖКИ[j,i] (в тому числi для i=j). Написати алгоритм, який визначає, чи можна намалювати карту стежок, не вiдриваючи олвiця вiд паперу i не малюючи жодну стежку двiчi.
10 клас
Теоретичний тур
Т.10.1.
Написати алгоритм, який вiгадує число N, що задумане людиною. Алгоритм повинен задавати людинi питання, на якi можна вiдповiдати "так" або "нi" . N може бути будь-яким кiнцевим натуральним числом. Алгоритм повинен використовувати якомога менше питань при великих N.
Для дiалога з людиною виковистовуються допомiжнi алгоритми ВВIД и ВИВIД с довiльною кiлькiстю параметрiв будь-яких типiв.
Т.10.2.
Данa функцiя, аргументи якої - невiд'ємнi цiлi числа M i N (M£
N)
1, при М=0
f(M,N)= f(M-1,N-1)+f(M,N-1), при 0 < М < N
1, при M=N
Скласти алгоритм, що знаходить значення функцiї без допомоги рекурсiї.
Т.10.3.
Набiр узагальненого домiно мiстить М кiсток, на кожнiй кiстцi нанесено два цiлих числа вiд 0 до N; будь-яка пара чисел може зустрiчатися в наборi 0, 1 або декiлька разiв. Значеняя кiсток задано в таблицi ДОМIНО[1:M,1:2].
Скласти алгоритм, який визначає, чи можна побудувати з усiх кiсток набору ланцюг за правилами домiно.
П р а к т и ч н и й т у р .
Двоє грають в таку гру: є електрична схема, в яку входять батарейка, лампочки и контакти, до якої можна приєдинати будь-яку кiлькiсть проводiв.
Гравцi ходять по черзi: при кожному ходi гравець з'єднує проводом будь-яку пару рiзних контактiв, що ранiше не були з'єднанi напряму деяким гравцем.
Гравець, пiсля ходу якого будуть горiти всi лампочки, вважається переможцем.
Написати пограму, яка виступає за одного з гравцiв i прагне до виграшу.
Опiр усiх проводiв вважати рiвним 0. |
