|
Республиканская олимпиада 1988 г. Теоретический тур
9 класс Задача ¹ 1 Вокруг считающего стоят N человек, один из которых назван первым, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий ведет счет до М, начиная с первого. Человек, на котором остановился счет, выходит из круга. Счет продолжается со следующего человека (при этом выбывшие из круга не считаются) и так до тех пор, пока не останется один человек. Определить начальный номер этого человека.
Задача ¹ 2 Два человека играют в "алгоритмическую игру". Игровое поле - лист бумаги в линейку, содержащий 20 строк. Игроки задают начальные значения переменных А и В из множества {0,1} (Например, А=0, В=0 или А:=1, В:=0), а затем по очереди вписывают по одному из операторов вида
1. А:=1-А 2. В:=1-В 3. ЕСЛИ А=1 ТО В:=1-В ВСЕ 4. ЕСЛИ А=0 ТО В:=1-В ВСЕ 5. ЕСЛИ В=1 ТО А:=1-А ВСЕ 6. ЕСЛИ В=0 ТО А:=1-А ВСЕ
в любую незанятую строку. Когда заполнены все строки, полученная последовательность операторов выполняется при заданных начальных значениях. Если после исполнения алгоритма значения А и В будут различны, побеждает первый игрок, если равны - побеждает второй игрок. Определите при каждом начальном наборе А и В, есть ли у кого-либо из игроков выигрышная стратегия? Если стратегия есть, то в чем она заключается?
Задача ¹ 3 Последовательность 1,0,0,1,0,1,1,0,0,1,1,0,1,0,.. строится так: первый ее элемент равен 1, остальные получаются из элементов с меньшими номерами с помощью операции отрицания: 1, eсли X = 0 NOT (X) = 0, если X = 1 Второй элемент равен отрицанию первого, то есть 0; третий и четвертый равны отрицанию первого и второго соответственно; элементы с пятого по восьмой равны отрицаниям элементов 1-4 соответственно, и т.д.; элементы с номерами 2k +1 ,..., 2 k+1 равны отрицаниям элементов с номерами 1,2,...,2k соответственно. Составить программу, вычисляющую N-й член описанной последовательности по заданному N.
10 класс Задача ¹ 1 В некотором арифметическом выражении удалили все символы, кроме скобок. Составить алгоритм, определяющий по полученной последовательности скобок, правильно ли они были первоначально расставлены.
Задача ¹ 2 Два человека играют в "алгоритмическую игру". Игровое поле - лист бумаги в линейку, содержащий 20 строк. Игроки по очереди вписывают в любую незанятую строку по одному из операторов вида:
1. A:=1-A 2. B:=1-В 3. ЕСЛИ А=1 ТО В:=1-В ВСЕ 4. ЕСЛИ А=0 TO B:=1-B ВСЕ 5. ЕСЛИ В=1 ТО А:=1-А ВСЕ 6. ЕСЛИ В=0 ТО А:=1-А ВСЕ
Когда все строки заполнены, переменным А и В присваиваются значения из множества {0,1} (например, А:=1,В:=1 или А:=0,В:=1) и выполняются все операторы в той последовательности, в которой они записаны. Если в результате значения А и В различны, побеждает первый игрок, если равны - второй игрок. Есть ли у кого- либо из игроков стратегия, гарантирующая выигрыш независимо от начальных значений А и В?
Задача ¹ 3 Возьмем полоску бумаги, согнем ее пополам К раз следующим образом:
и развернем полоску так, чтобы углы на всех сгибах стали равны 90 . Посмотрев на торец полоски, увидим ломаную, которая называется "драконовой ломаной К-го порядка":
К=0 К=1 К=2 К=3
Написать алгоритм, который, получая на входе числа K и L, рисует драконову ломаную К-го порядка с длиной одного звена, равной L.
ПРАКТИЧЕСКИЙ ТУР.
1 вариант
Задача ¹ 1 Дан список всех 64 полей шахматной доски 8 х 8 в виде числовых координат. Написать алгоритм, который определяет, является ли этот список маршрутом ферзя по всем полям доски.
Задача ¹ 2 Дана упорядоченная по возрастанию линейная таблица натуральных чисел А[1] <...< A[N]. Найти наименьшее натуральное число, не представимое в виде суммы некоторых чисел из таблицы. Сумма может состоять и из одного слагаемого; каждый элемент таблицы может входить в нее не более одного раза. Приемлемое решение должно укладываться в С*N действий, где С - постоянная, не зависящая от N.
2 вариант Задача ¹ 1 Составить алгоритм, получающий на входе число K и выдающий на выходе К-тое по порядку четырехзначное число, у которого никакие две цифры не равны между собой. Первым таким числом является 0123.
Задача ¹ 2 Имеются две таблицы натуральных чисел А[1:N] и B[1:N]. Найти перестановку i[1], i[2],..., i[N] чисел 1, 2,...,N, для которой сумма A[1] * B[i[1]] + ... +A[N] * B[i[N]] минимальна. В перестановку каждое число должно входить только один раз. Достаточно эффективным будет считаться алгоритм, требующий выполнения К * N операций, где К - постоянная величина, не зависящая от N. Наилучшее известное решение требует выполнения К*N*Log N операций. |