ЗАДАЧИ VIII ГОРОДСКОЙ ОЛИМПИАДЫ

ПО ИНФОРМАТИКЕ 1996/97 уч.года.


 
Участники и победители

Теоретический тур :

  1. Задача на знание логических операций - 6 баллов
  2. Логическое выражение - 6 баллов
  3. Задача на системы счисления - 3 балла
  4. Алгоритм Маркова - 13 баллов
  5. По блок-схеме определить, какой алгоритм она описывает - 12 баллов

Практический тур :

  1. Два Ферзя - 6 баллов
  2. Фанта -15 баллов
  3. Лабиринт - 18 баллов
  4. Арифметика по-русски - 21 балл


Теоретический тур


1. Логическая операция XOR имеет следующую таблицу истинности:

истина XOR истина = ложь

истина XOR ложь = истина

ложь XOR истина = истина

ложь XOR ложь = ложь

Выразить эту операцию через операции AND , OR, NOT.

(6 баллов)

2. Дано следующее логическое выражение:

((А AND B) OR (NOT (B OR C))) OR (C AND NOT (А))

Переписать его, использовав только операции AND и NOT.

(6 баллов)

3. На уроке арифметики в начальной школе на планете W решают следующие примеры:

2553 + 530 = 3303

555 + 555 = ?

Какой ответ они бы написали во втором примере ?

(3 балла)

 4. Алгоритм Маркова. Алгоритм преобразования входной строки S описывается конечным упорядоченным набором па р строк, называемых подстановками. Первая строка в подстановке называется левой, а вторая - правой. Некоторые подстановки могут быть помечены как завершающие.

Если в S имеется подстрока, совпадающая с одной из левых строк подстановок,то она заменяется соответствующей правой строкой. Поиск такой подстроки происходит с начала строки S для первой подстановки, затем для второй, третьей и т.д. После каждого выпо лнения подстановки работа начинается сначала уже с преобразованной строкой.

Алгоритм завершается, когда выполняется завершающая подстановка или не удается выполнить ни одной подстановки.

Например, алгоритм, описываемый парой подстановок :

пи - ма

м - п

преобразует входную строку мама в строку папа, а строку пир в пар.

Написать последовательность подстановок, преобразующих символьную строку, представляющую натуральное число < 100 в строку, представляющую число на единицу большее.

(13 баллов)

 

5.  Что вычисляет данный алгоритм ?

Rnd(1) - функция, которая генерирует случайное число на промежутке от -1 до 1.

N -достаточно большое число.

 

  (12 баллов)


Практический тур.


 
1. Два Ферзя. На шахматной доске (8 х 8) стоят два ферзя. Выяснить, бьют ли они друг друга.

(6 баллов)

2. Фанта. Всю неделю бутылка Фанты стоила k рублей, а пустая бутылка стоила m рублей. Компания друзей, собравшихся в понед ельник, располагала первоначальным капиталом в n рублей и купила на все эти деньги Фанту. Употребив все, они на следующий день сдали пустые бутылки, добавили сдачу с предыдущего дня и снова на все деньги купили Фанту. Данная процедура продолжалась каждый день, пока была возможность.

Напишите программу нахождения минимальной суммы n, при которой в пятницу друзьям будет, что употребить.

(15 баллов)

3. Лабиринт. Попав в лабиринт, состоящий из одинаковых квадратных комнат, каждая из которых может иметь от 1 до 4 дверей в соседние комнаты, путник долго блуждал по нему, пока не нашел клад. Во время поиска он составил описание своего маршрута, обозначая каждый переход из комнаты в комнату буквами С (север), В (восток), З (запад), Ю (юг). Напишите программу, определяющую по данному описанию самый короткий путь назад.

(18 баллов)

4. Арифметика по-русски. Написать программу, преобразующую словесное описание арифметического действия в словес ное описание его результата. Во входной строке для обозначения арифметического действия должно быть использовано одно из следующих слов:

плюс, минус, умножить на.

 Например:

вход: сорок восемь умножить на три

выход: сто сорок четыре

 Операнды и результат должны быть натуральными числами < 100. Использование предлогов, согласование падежей и порядок слов должны соответствовать правилам русского языка.

(21 балл)

В начало данной страницы                      На начальную страницу