Задача 1

Mожно заметить, что если к каждым элементам множества К прибавить 1, то получится множество элементов вида: (X+1) аm А(Y+1) аk А, где k,m =0,1,2,...,n,... Тогда для того, чтобы проверить, является ли Z элементом множества К, достаточно проверить, представимо ли Z+1 в виде: Z+1=(X+1) аp А(Y+1) аq А, где p и q - произвольные целые числа. Следовательно,нужно делить Z на X+1 до тех пор, пока делится нацело, затем на Y+1, пока делится нацело, и если в конце деления получится 1, то Z о K. Данная задача не обязательно требует программной реализации.

К задачам

Задача 2

Однозначность раскодируемости обеспечивается тем, что ни один из кодов букв не является началом кода другой буквы. Оптимальным является код Хаффмана,зключающийся в следующем. Две самые редкие буквы образуют одну новую букву с суммарной частотой их появления. При этом код, который будет построен для новой буквы, с дописанной единицей присваивается одной из исходных букв, а с дописанным нулем - другой букве.

Далее алгоритм применяется к новому алфавиту (см. И.М. Яглом, А.М. Яглом "Вероятность и информация"). Ниже прилагается программа для проверки задачи кодирования.

Задача 3

Предполагается, что программа предусматривает следующие действия:

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

"<буква><знак операции><буква><знак операции>..." или " - <буква><знак операции><буква>..."). - определение последовательности вычисления выражения по порядку арифметических действий и последовательное выполнение промежуточных действий. Порядок действий стандартный:

Задача 4

Программу можно составить двумя способами:

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

Второй способ организует многократное поразрядное сложение с учетом переноса 1 в старший разряд и сдвига второго слагаемого на число нулей первого.

Третий способ предполагает перевод числа в 10-тичную систему счисления, используя алгебраическую запись числа: z = a Рk А10 аk А+ a Рk-1 А10 аk-1 А+...+ a Р1 А10 + a Р0 А, где 10 - это 10 Р2 А= 2. После этого над преобразованными числами выполняется умножение, результат переводится в 2 - ичную систему счисления и цифры записываются в результирующую таблицу.

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

К задачам

Задача 5

Без ограничения общности можно считать,что центр окружности совпадает с началом координат. Тогда достаточно подсчитать количество клеток в первой четверти круга и затем умножить полученное значение на 4. Пусть Х,У-координаты правого верхнего угла клетки. Клетка находится в рассматриваемой четверти тогда и только тогда, когда выполняются условия:

1. Х>=1;

2. У>=1;

3. Х*Х + У*У <= R*R (см. теорему Пифагора).

Простейшее решение представляет простой перебор, где Х и У пробегают все значения от 1 до R-1. Некоторое сокращение времени счета можно получить, если проверять последнее неравенство не для каждой клетки. Действительно, если оно справедливо для некоторых Х и У, то оно справедливо и для всех меньших значений. Поэтому достаточно для каждого Х от 1 до R-1 найти максимальное целое значение У, удовлетворяющее неравенству, и просуммировать все эти значения У.

К задачам

Задача 6

Задача представляет собой составление алгоритма, на языке, близком к обычному языку школьной информатики(см. пробный учебник А.Г.Кушниренко и др.).

Наиболее простой алгоритм заключается в обычном последовательном обходе слева-направо поля робота с одновременным исследованием состояния в соседних клетках(соседними считаются клетки, имеющие с данными общую сторону). Очевидно, что граничные клетки не со всех сторон имеют соседей. Граница представляет собой непроницаемую стену и характеризуется состоянием "не свободно" с соответствующей стороны.

К задачам

Задача 7

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

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

К задачам

Задача 8

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

К задачам