ОБЛАСТНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ ПО ИНФОРМАТИКЕ
1995-96 учебный год
II ТУР

1. Оптимальный маршрут. Имеется полоска с пронумерованными от 1 до 60 клетками. В одной из них находится исполнитель, который умеет выполнять следующие команды:
1) шаг вперед (перейти на соседнюю клетку с большим номером);
2) шаг назад (перейти на соседнюю клетку с меньшим номером);
3) прыжок вперед (переместиться в клетку, номер которой больше номера текущей клетки на 8);
4) прыжок назад (переместиться в клетку, номер которой меньше номера текущей клетки на 8);
5) в начало (встать на клетку номер 1);
6) в конец (встать на клетку номер 60).

Если выполнение команды приведет к выходу за пределы полоски, исполнитель ее игнорирует.

Написать программу, которая по введенным L (номер клетки с начальным положением исполнителя) и M (номер клетки, куда нужно попасть) находит алгоритм движения из наименьшего числа команд. Результат вывести в виде: 

			команда   номер поля после команды

Техническое требование: при выводе алгоритма движения сначала помещать команды прыжков, а затем — шагов.

Примечание. Для некоторых L и M существует несколько оптимальных решений.

Пример работы программы: 

Введите L: 44
Введите M: 11
Оптимальный маршрут:
в начало 1
прыжок вперед 9
шаг вперед 10
шаг вперед 11

2. Система счисления “8-6-4-2”. В системе счисления “8-6-4-2” для записи чисел в младшем разряде используются цифры: 0, 1; в следующем разряде — 0, 1, 2, 3; в третьем — 0, 1, 2, 3, 4, 5; в четвертом разряде — 0, 1, 2, 3, 4, 5, 6, 7. Будем рассматривать только четырехзначные числа в системе счисления “8-6-4-2”.

Написать программу, которая позволит вводить числа в следующих форматах:

		число в десятичной системе счисления - Dчисло
		число в системе счисления “8-6-4-2” - Iчисло

Программа должна выполнять следующие операции: перевод из одной системы счисления в другую, сложение, вычитание, умножение (+, –, *):

	Dчисло => результат
	Iчисло => результат
	Dчисло операция Dчисло => результат
	Dчисло операция Iчисло => результат
	Iчисло операция Dчисло => результат
	Iчисло операция Iчисло => результат

Результат в записи команды может обозначаться буквами “D” или “I”. Если он обозначен “D”, то программа должна выдать ответ в десятичной системе счисления. Если результат обозначен “I”, то программа должна выдать результат в системе счисления “8-6-4-2”. Первая команда обозначает перевод в систему счисления “8-6-4-2”, а вторая — в десятичную систему счисления.

Примеры работы программы:

	I6420 => D324
	D111  => I2131
	I2121 + I1111 => I3300
	I2121 - D10 => D99

3. Точные значения членов последовательности. Дана последовательность

Написать программу, находящую точное значение an для 0 <= n <= 150.

Пример. При n = 58 получаем an = 10359022039470231387111424.

4. Перевод выражений с одного языка программирования на другой. В двух языках программирования высокого уровня выражения над вещественными переменными и константами могут быть образованы с помощью операций соответственно:

III
1. F(X)1. F(X)
2. *, /, AND2. **
3. +, –, OR3. *, /
4. =, <, >, <=, >=, <>4. +, –
 5. .EQ., .LT., .GT., .LE., .GE., .NE.
 6. .AND.
 7. .OR.
и круглых скобок.

F(X) подразумевает вычисление функции, ** — возведение в степень. Операции в каждом языке пронумерованы в порядке убывания приоритета. Операции .EQ., .LT., .GT., .LE., .GE., .NE. эквивалентны соответственно =, <, >, <=, >=, <>. В языке I существуют функции EXP(X) = ex и LN(X) = ln x, через которые выражается операция возведения в степень (если A > 0 и B — вещественные выражения, A ** B = EXP(B * LN(A))). При отсутствии скобок операции выполняются слева направо в порядке убывания приоритета.
A. Написать программу, переводящую корректное выражение на языке II в эквивалентное выражение на языке I.
B. Удалить лишние скобки в результате.

 

Рейтинг ресурсов УралWeb
Сайт создан в системе uCoz