Задача 1.
Пусть программа на языке BASIC состоит из последовательностей операторов. Каждая последовательность состоит из ненулевого числа операторов. Операторы отделяются друг от друга символом двоеточие (:), который для других целей в программе не используется. Последовательность может располагаться на нескольких строках, при этом разбивка оператора на 2 строки не допускается; если последовательность продолжается на следующей строке, в конце текущей строки стоит двоеточие. Последовательности операторов в тексте программы имеют уникальные номера. Таким образом, структура последовательности операторов следующая:
-каждая новая последовательность начинается с новой строки;
- в начале последовательности, до ее номера, состоящего не более чем из 8-ми десятичных цифр, могут присутствовать пробелы;
- после номера последовательности также могут присутствовать пробелы;
- оператор всегда начинается не с цифры;
- оператор нельзя разрывать на несколько строк, если оператор не последний, за ним (возможно через пробелы) следует двоеточие.
Переходы в программе осуществляются посредством операторов goto или gosub (эти ключевые слова могут быть записаны как с использованием заглавных, так и прописных букв, например GoSUb).
Вид операторов
goto номер последовательности
gosub номер последовательности
(между ключевыми словами и номером последовательности могут присутствовать пробелы).
Написать программу, которая читает из файла имя файла (имя файла вводится с клавиатуры), текст BASIC программы и перенумеровывает последовательности операторов так, чтобы
- в выходном файле порядок последовательностей совпадал с порядком последовательностей исходного файла, отсортированного по возрастанию номеров последовательностей;
- первая последовательность выходного файла имела номер f, а каждая следующая последовательность имела номер на d больше, чем предыдущая (f и d - натуральные числа, вводимые с клавиатуры).
Текст программы состоит не более чем из 100 строк, длина строки не превышает 80 символов.
Преобразованную BASIC-программу выводить в файл
имя_файла.OUT.
Входные данные корректны.
Задача 2.
Пусть грамматика языка описывается следующим образом:
<выражение>::=<операнд> <on> <операнд> | <операнд>
<on>::=+|-|*
<операнд>::=<переменная> | <целое без знака>
<переменная>::= A | B | C | D | ... | Z
<целое без знака>::= 1 | 2 | 3 | 4 | ... | 9 | 0
<оператор>::=<IF-оператор> | <WHILE-оператор> | <присвоить>
<присвоить>::=<переменная>:=<выражение>
<IF-оператор>::= IF <условие> THEN <оператор> ELSE <оператор>
<WHILE-оператор>::= WHILE <условие> DO BEGIN <оператор> END
<условие>=<выражение> > <выражение>
<программа P>=<оператор> | <программа P><оператор>
Задается текст программы P. Каждый оператор программы Р начинается с новой строки. Оператор может быть записан в нескольких строках. Ввод программы осуществляется из файла. Имя файла вводится с клавиатуры. В программе все переменные и ключевые слова записываются заглавными буквами латинского алфавита. Текст вводимой программы Р синтаксически правильный.
Написать программу, оптимизирующую введенный текст программы Р по следующим правилам:
Если в операторе IF условие всегда истинно (ложно) (например 2>1 (1>2)), то в текст преобразованной программы включается только оператор, стоящий за THEN ( за ELSE, если он есть).
Если в операторе WHILE условие всегда ложно, то WHILE- оператор из текста программы исключается.
Если в операторах IF, WHILE в <условие> или в операторе присваивания в правой части стоит выражение, численное значение операндов которого известно, то это значение вычисляется и записывается вместо <выражения> в условие или вместо правой части оператора присваивания соответственно.
Если в двух операторах присваивания (обозначим их А и В) в программе Р в левой части оператора стоит одна переменная, и эта переменная не используется ни в правой части операторов присваивания, ни в условиях IF- или WHILE-операторов, встречающихся в тексте программы между операторами А и В, то в программе Р остается только оператор В.
Если внутри тела цикла оператора WHILE стоит оператор присваивания, и переменная из левой части этого оператора не встречается в <условии>, то этот оператор выносится из цикла и ставится перед ним.
Если в ветках THEN и ELSE оператора IF стоит один и тот же оператор присваивания (переменные в левых частях этих двух операторов совпадают, а значения правых частей одинаковы, например,
IF A>B THEN L:=A+B ELSE L:=B+A),
то этот оператор присваивания записывается вместо IF-оператора.
Вывод программы оптимизатора направляется в файл с именем код.OUT.
Задача 3.
На шашечной доске размера n x n её верхний правый угол имеет номер (1,1). В позиции (i,j) стоит фишка, которая может двигаться по правилу, показанному на рисунке (допустимые ходы обозначены х, шашка - О). Фишка не может дважды ставиться на одно и то же поле.
Играют двое, по очереди двигая фишку. Выигрывает поставивший фишку в позицию (1,1).
Для введённых i,j определить, может ли выиграть первый игрок при наилучших ходах второго.
Написать программу, где первый игрок - компьютер.
Задача 4.1.
Есть две обезьяны и куча из L бананов. Обезьяны по очереди, начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может при каждом очередном ходе взять из кучи либо a1, либо a2, либо ... aS бананов (а1 <a2 <...<aS), а 2-ая при каждом очередном
ходе --либо b1, либо b2, либо ... bK бананов (b1 <b2 <...<bK ). Нумерация индексов при a и b не имеет никакого отношения к номерам ходов обезьян Выигрывает та обезьяна, которая на своем ходе не может взять банан(ы) (либо потому, что их не осталось, либо потому что бананов осталось меньше чем a1 (при ходе первой обезьяны) либо b1 (при ходе второй обезьяны)).
Определить может ли выиграть первая обезьяна при наилучших ходах соперницы, которая также стремится выиграть. Все входные данные - натуральные числа.
Задача 4.2.
Вводится целое число K>=1. Бумажная полоса разбита на N клеток (K <= N <= 40).Играют двое, по очереди выбирая и зачеркивая K пустых смежных клетки. Выигрывает сделавший последний ход.
1)Ввести N и определить, имеет ли игрок 1 выигрышную стратегию ( т.е. может ли игрок 1 выиграть при наилучших последующих ходах игрока 2). Сообщение вида 'У игрока 1 (не) существует выигрышная стратегия'.
2)Для N определить, имеет ли игрок 1,сделав заданный первый ход, выигрышную стратегию.
3)Провести игру для N и первого хода игрока 1. За второго игрока играет программа. Ходы первого вводятся с клавиатуры. Цель второго игрока -победа. Ход задается индекcoм ячейки L (1<=L<=N-K+1).При этом вычеркиваются клетки с индексами от L до L+K-1.После каждого хода выводится текущая позиция в виде
1
2
3
...
n
*
*
Сверху печатается номер позиции. Зачеркнутые клетки помечаются символом '*'. В конце игры выдать сообщение 'Победа игрока 1(2)'. При вводе N и K выдать подсказывающие сообщения 'N>'и 'K>', при вводе хода - 'Ход игрока 1>'.Предусмотреть контроль корректности входных данных.
Задача 5.
Пусть слово - это последовательность от 1 до 8 символов, не включающая пробелов.
Вводится n слов A1,...,An. Можно ли их переупорядочить так, чтобы получилась "цепочка", т.е. для каждого слова Aj его первая буква должна совпадать с последней буквой предыдущего слова, а последняя буква в Aj - с первой буквой последующего слова; соответственно последняя буква последнего слова должна совпадать с первой буквой первого слова. В цепочку входят все n слов без повторений.
Дать ответ в виде "Можно"\"Нельзя".
Если такое упорядочение возможно, то вывести какую-нибудь цепочку слов. Слова при выводе разделяются пробелами.
Задача 6.
На линейке из m клеток в разных концах стоят две фишки, которые ходят по очереди. Каждая из фишек может ходить влево или вправо не более чем на К клеток (m<=80;К<=m-2). При этом нельзя перешагивать через фишку и нельзя оставаться на месте. Фишка проигрывает, если она не может сделать ход. Написать программу, реализующую выигрышную стратегию для одной из фишек. При этом разрешается передача хода в самом начале игры. Предусмотреть контроль входных данных.
Задача 7.
Составить программу, которая по введенному N выдает последовательность длины N, состоящую из цифр 0 и 1 такую, что ни один фрагмент этой подпоследовательности не повторяется подряд трижды.
Задача 8.
Ввести три числа а,b,с.
1). Представить a в виде суммы минимального числа целых слагаемых x[i], каждое из которых лежит на отрезке [b,c].
2). Можно ли представить число а таким образом, чтобы
,
где b<=x[i]<=c, х[i], а, в, с - целые. Лучшим считается алгоритм находящий такое представление с наименьшим числом множителей. Предусмотреть вариант, когда такого представления не существует.
Задача 9.
Даны три слова X,Y,Z. Определить, существует ли слово V такое, что X,Y,Z являются повторениями слова V. Если V существует, то напечатать его. Слова имеют длину не более 1000 символов. Символ "пробел" является разделителем слов.
Задача 10.
Даны два положительных целых числа А,В. Напечатать слово "ДА" или "НЕТ" в соответствии с тем, можно ли получить десятичную запись числа А путем вычеркивания одной или более цифр числа В.
Задача 11.
Пусть А - последовательность букв. После вычеркивания одной буквы из А (в одной позиции)получили последовательность В. После вычеркивания другой буквы из А (в одной позиции) получили последовательность С.
Можно ли по последовательностям B и С
1) Определить вычеркнутые буквы.
2) Определить последовательность A.
Примечание: В и C могут быть получены вычеркиванием одной и той же буквы.
Задача 12.
Имеется N книг и два читателя, А и В, желающих прочитать эти книги. Заданы неотрицательные целые числа A[I] и B[I] такие, что читателю А (или В) потребуется A[I] (соответственно, B[I]) часов для прочтения книги I, 1 <=I <=N. Процесс чтения начинается в момент времени 0. В любой момент времени каждый читатель не может читать более одной книги и каждую книгу не могут читать оба читателя.
Для каждого читателя порядок чтения книг не имеет значения и может быть произвольным. В процессе чтения любой книги любым читателем допускаются прерывания. Это означает, что этот процесс может быть прерван в любой целочисленный момент времени и возобновлен позднее с прерванного места. В промежутке между прерыванием и последующим возобновлением процесса чтения книги читатель может читать любую не до конца прочитанную книгу.
Задано целое число К, 2<=K <=N, и книги пронумерованы таким образом, что ни один читатель не имеет права начать читать книгу J, 2<= J <= K, прежде чем книга J-1 не будет прочитана обоими читателями.
Требуется:
1. Вычислить наименьший момент времени Т, раньше которого все книги не могут быть прочитаны всеми читателями. Вывести вычисленное значение Т.
2. Построить расписание чтения книг каждым читателем, при котором не нарушается ни одно из перечисленных выше условий и процесс чтения всех книг завершается в момент времени Т. Расписание для каждого читателя вывести в виде
< РАСПИСАНИЕ ДЛЯ ЧИТАТЕЛЯ А (или В) >
<Номер книги>
<Начало>
<Конец>
. . . . . .
. . . . .
. . . . .
. . . . . .
. . . . .
. . . . .
В таблицах указанного вида необходимо указать все временные интервалы, в течение которых читатель А (или В) читает книгу и номер этой книги.
3. Постарайтесь сократить число прерываний для каждого читателя.
Задача 15.
Янис и Петрис играют в следующую игру. Петрис загадывает декартовы координаты двух различных точек A(Ax,Ay) и B(Bx,By). Известно, что среди чисел Ax, Ay, Bx, By нет двух одинаковых. Янис может задавать вопросы только следующего вида: "Какое расстояние от точки P(Px,Py) до точки A (до точки B)?", где Px и Py - числа. В ответ Петрис называет число, которое является длиной отрезка PA (или, соответственно, PB). Определить, какое наименьшее количество вопросов должен задать Янис, чтобы он смог назвать координаты какой-либо точки, находящейся на серединном перпендикуляре отрезка AB, независимо от того, какие точки загадал Петрис. Описать, как найти эту точку. Ответ обосновать.
Задача 16.
Известно, что среди 13 монет есть одна отличающаяся по весу (тяжелее одна или легче - неизвестно). За 3 взвешивания на чашечных весах найти эту монету.
Задача 17.
"Быки и коровы"
Пользователь загадывает число из 4 цифр, каждая из которых от 1 до 6, причем все цифры различны. Разработать алгоритм, который угадывает число по следующим правилам: выводится число и пользователь сообщает, сколько в нем "быков" и "коров", т.е. сколько цифр стоят на своих местах и сколько цифр содержатся в обоих числах, но совпадают лишь по значению. Например, пусть загадано число 1264, спрошено 1256. В этом случае 2 быка (1,2) и одна корова (6).
Модификация: Правила игры те же, но загадывается 6-значное число с цифрами от 1 до 9, причем среди цифр допускаются одинаковые.
Примечание: Спрошенное число должно удовлетворять правилам для загадываемого; компьютеру на ход дается 1 минута.
Задача 19 (Прохоров В.В.).
Учитель попросил Диму написать программу вида
Ввод (x,y)
Пока < условия выполнения итерации >
НЦ
< тело цикла >
КЦ
Вывод (x,y)
т.е. такие < условия выполнения итерации > (не содержащие никаких переменных кроме x и y) и < тело цикла >, чтобы этот фрагмент для произвольных введенных в операторе ввода чисел x=x0 и y=y0 выдавал бы оператором вывода числа x=x0+y0 и y=x0-y0.
Помогите Диме.
Задача 20.
Игровой автомат состоит из нескольких изогнутых трубок, по форме похожих на перевернутую вверх ногами букву "Y" . Сверху у трубы находится входное отверстие, а два выходных отверстия - снизу. Труба может находиться в одном из двух возможных состояний:
Шарики кладутся вовнутрь один за другим через входное отверстие. В состоянии 1 (Рис. 3), шарик покидает трубу через незаблокированный правый выход, при этом Состояние 1 автоматически изменяется на Состояние 0 ( Рис.4, правый вход заблокирован, левый -- нет ). В состоянии 0 все происходит наоборот.
Пусть игральный автомат состоит из 8 "Y"-образных трубок, их взаимное расположение показано на Рис.5. Вы можете забрасывать шарики через Вход A, Вход B, или Вход C. Пусть, например, первый шарик опускается через Вход A. Он покидает трубу G1 через левый выход, изменяя ее состояние с 0 на 1, поступает в G6 и покидает автомат через левый выход G6 ( изменяя состояние G6 c 0 на 1). Эту процедуру мы запишем следующим образом:
A
Затем мы забросим шарик через Вход A (он находится в Состоянии 1). Шаpик покидает G1 чеpез пpавый выход, изменяя состояние 1 в состояние 0, попадает в G4, покидает G4 чеpез пpавый выход, изменяя состояние 1 в состояние 0, попадает в G7, покидает автомат чеpез левый выход (изменяя G7 из состояния 0 в состояние 1 ).Все вышеизложенные действия мы запишем в виде:
AA
Если мы опустим третий шарик через Вход B, четвертый - через Вход C, то все действия запишутся следующим образом:
AABC
Необходимо:
1. Ввести с клавиатуры последовательность из 8 двоичных цифр (бит), показывающих соответственно начальное состояние G1-G8:
бит
7
6
5
4
3
2
1
0
Вход
G8
G7
G6
G5
G4
G3
G2
G1
Например, последовательность 11001010 означает, что G8, G7, G4 и G2 находятся в Состоянии 1 ( левый вход заблокирован ), тогда как G6, G5, G3 и G1 находятся в Состоянии 0 (правый вход заблокирован).
2. Ввести с клавиатуры вторую последовательность из 8 бит, показывающих конечные состояния G'1-G'8.
3. Напечатать последовательность ходов A, B, или C, указывающую, каким образом можно получить конечную позицию, забрасывая шарики через Входы A, B и C.
Задача 21.
Определить, является ли периодической последовательностью строка символов A1 A2 ... AN, т.е. имеет ли она вид d d ... d, где d - некоторая подпоследовательность символов.
Задача 22.
Если мы из корректно записанного арифметического выражения, содержащего числа, знаки операций и открывающие и закрывающие круглые скобки выбросим числа и знаки операций, а затем запишем оставшиеся в выражении скобки без пробелов между ними, то полученный результат назовем правильным скобочным выражением [скобочное выражение "(()(()))" - правильное, а "()(" и "())(" - нет].
Найти число правильных скобочных выражений, содержащих N открывающихся и N закрывающихся скобок. N вводится с клавиатуры. N неотрицательное целое число.
Задача 23.
Пусть слово - это последовательность от 1 до 8 заглавных букв латинского алфавита.
Задается множество слов A={a[1], a[2],..., a[n]}, n<10. Из слов множества A составляется текст - последовательность слов, записанных друг за другом без разделителей пробелов. Слова могут встречаться в тексте произвольное число раз.
Дешифровка текста - это разбивка текста на слова множества A. В дешифрованном тексте слова разделяются пробелами.
Необходимо:
1.Определить, существует ли для заданного множества A такой текст, который дешифруется не единственным образом (сам текст приводить не надо).
Примеры:
1) A = { B , C }
Любой текст дешифруется однозначно.
2) A = { B , BC , C }
Существует текст, который дешифруется двумя способами
Текст ---> Дешифровка
BBC ---> B B C
BBC ---> B BC
2. Если такой текст существует, то исключить из множества A минимальное число слов так, чтобы после этого любой текст, составленный из слов полученного множества A, дешифровался однозначно. Напечатать эти исключенные слова. Если такой набор не единственный, то напечатать все наборы.
3.Для введенного текста произвести его дешифровку и, если дешифровка не единственная, вывести все варианты.
Примечания: Порядок выполнения пунктов строго фиксирован.
Задача 24.
На рисунке изображен фрагмент компьютерной сети. Система состоит из двух интерфейсов Международного Союза ORT и двух компьютеров. Каждый интерфейс подключен к отдельному компьютеру, один из которых является компьютером-передатчиком, другой - компьютером-приемником. Интерфейсы соединены друг с другом следующим образом: все восемь выходов интерфейса-передатчика соединены с восемью входами интерфейса-приемника, восьмой выход интерфейса-приемника соединен с восьмым входом интерфейса-передатчика. Реле входов (выходов) интерфейсов нумеруются с 0 по 7. Для включения реле-выхода с номером A запишите в порт с адресом 642 байт, в котором бит с номером A равен 1. Для выключения реле-выхода с номером A запишите в порт с адресом 642 байт, в котором бит с номером A равен 0. Для получения информации о состоянии реле-входа с номером A прочитайте байт из порта компьютера с адресом 642 и проанализируйте бит с номером A. Биты нумеруются, начиная с младшего.
Задание:
Написать программу, которая осуществляет:
1. Ввод с клавиатуры строки символов на компьютере-передатчике. Передачу строки через связанные интерфейсы на компьютер-приемник. Отображение данной строки на компьютере-приемнике.
2. Проверку типа компьютера (приемник или передатчик), на котором загружается программа с выдачей сообщения об этом.
3. Проверку правильности соединения интерфейсов согласно рисунку.
Примечание:
Выдача байта информации D в порт с адресом 642 и считывание байта D из порта с адресом 642 производится следующим образом:
Язык программирования
Запись в порт
Чтение из порта
С
OUTPORTB<642,D>
D:=INPORT<642>
PASCAL
PORT[642]:=D
D:=PORT[642]
BASIC
OUT 642,D
D=INT<642>
Задача 26.
"Дырокол". Бабурин Е.А.
Дырокол пробивает на длинной полосе бумаги по два одинаковых отверстия за одно нажатие его рычага и после нескольких нажатий получается следующее состояние бумаги.
0 0 0 00 0 00 00 0 0
Л П Л ПЛ П ЛЛ ПП Л П
Буквы "Л" и "П" под лентой обозначают, соответственно, левое и правое отверстия дырокола.
По известным координатам отверстий на полосе определить возможную ширину между отверстиями дырокола.
Задача 27.
КОМПОСТЕР
Авторы: АНДРЕЕВА Е.В. МАРЧЕНКО А.П.
В билете пассажира оказалось пробито отверстий больше, чем штырей в компостере. Пассажир утверждал, что пользовался только одним компостером, но случайно нажал на него несколько раз. Контролеру требуется определить, могло ли быть получено заданное расположение отверстий одним и тем же компостером, если билет можно пробивать с обеих сторон неограниченное число раз и произвольно перемещать и поворачивать относительно компостера. Пробитые отверстия не выходят за пределы билета. В билете было пробито N (N<10) отверстий.
ТРЕБУЕТСЯ:
А. Для компостера с двумя штырями (S=2) составить программу, которая:
1. Определяет, можно ли получить заданным компостером требуемое расположение отверстий в билете. Если это возможно, то изображает вид билета после каждого нажатия компостера. В противном случая, выводит соответствующее сообщение.
2. Определяет количество K различных компостеров каждым из которых можно пробить заданную конфигурацию.
3. При K=0 (см. п.2) находит компостер, с помощью которого можно пробить наибольшее количество из заданных отверстий.
4. Находит минимальное число нажатий, требуемое для пробивки заданной конфигурации отверстий, для каждого компостера из пункта 2.
Б. Решить задачу А для компостеров с числом штырей S (S>2).
ПРИМЕЧАНИЯ.
* Все исходные данные - натуральные числа.
* Компостеры, дающие при однократном нажатии совпадающие конфигурации отверстий, считаются одинаковыми.
* Относительное расположение отверстий в билете и штырей в компостере вводится либо с клавиатуры, либо из файла с именем COMP.DAT .
Сруктура вводимой информации: {N,x[1],y[1],...,x[N],y[N],S,u[1],v[1],...,u[S],v[S]},
где x[i], y[i] - координаты отверстий в билете, u[i], v[i] - координаты штырей в компостере.
* Нажатие компостера (см. п.1) моделировать клавишей "Пробел".
* При выводе конфигурации на экран (см. п.п.1,3) изображать координатную сетку. При этом программа должна осуществлять подходящее масштабирование.
