Два человека играют в "алгоритмическую игру". Игровое поле - лист бумаги в линейку, содержащий 20 строк. Игроки задают начальные значения переменных А и В из множества {0,1} (Например, А=0, В=0 или А:=1, В:=0), а затем по очереди вписывают по одному из операторов вида

1. А:=1-А

2. В:=1-В

3. ЕСЛИ А=1 ТО В:=1-В ВСЕ

4. ЕСЛИ А=0 ТО В:=1-В ВСЕ

5. ЕСЛИ В=1 ТО А:=1-А ВСЕ

6. ЕСЛИ В=0 ТО А:=1-А ВСЕ

в любую незанятую строку. Когда заполнены все строки, полученная последовательность операторов выполняется при заданных начальных значениях. Если после исполнения алгоритма значения А и В будут различны, побеждает первый игрок, если равны - побеждает второй игрок. Определите при каждом начальном наборе А и В, есть ли у кого-либо из игроков выигрышная стратегия? Если стратегия есть, то в чем она заключается?

Последовательность 1,0,0,1,0,1,1,0,0,1,1,0,1,0,.. строится так: первый ее элемент равен 1, остальные получаются из элементов с меньшими номерами с помощью операции отрицания:

NOT (X) =

0, если X = 1

В некотором арифметическом выражении удалили все символы, кроме скобок. Составить алгоритм, определяющий по полученной последовательности скобок, правильно ли они были первоначально расставлены.

Два человека играют в "алгоритмическую игру". Игровое поле - лист бумаги в линейку, содержащий 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) и выполняются все операторы в той последовательности, в которой они записаны. Если в результате значения А и В различны, побеждает первый игрок, если равны - второй игрок. Есть ли у кого- либо из игроков стратегия, гарантирующая выигрыш независимо от начальных значений А и В?

Возьмем полоску бумаги, согнем ее пополам К раз следующим образом:

и развернем полоску так, чтобы углы на всех сгибах стали равны 90 . Посмотрев на торец полоски, увидим ломаную, которая называется "драконовой ломаной К-го порядка":

К=0 К=1 К=2 К=3

Написать алгоритм, который, получая на входе числа K и L, рисует драконову ломаную К-го порядка с длиной одного звена, равной L.

Дан список всех 64 полей шахматной доски 8 х 8 в виде числовых координат. Написать алгоритм, который определяет, является ли этот список маршрутом ферзя по всем полям доски.

Дана упорядоченная по возрастанию линейная таблица натуральных чисел А[1] <...< A[N]. Найти наименьшее натуральное число, не представимое в виде суммы некоторых чисел из таблицы. Сумма может состоять и из одного слагаемого; каждый элемент таблицы может входить в нее не более одного раза.

Приемлемое решение должно укладываться в С*N действий, где С - постоянная, не зависящая от N.

Составить алгоритм, получающий на входе число K и выдающий на выходе К-тое по порядку четырехзначное число, у которого никакие две цифры не равны между собой. Первым таким числом является 0123.

Имеются две таблицы натуральных чисел А[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 операций.