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