СПбГУ НИУ ИТМО. Интернет-олимпиада школьников по информатике (2009-2010 уч. год).

Простая задача (2 балла): Вычислите произведение двух чисел: x и y, если x=10111,0111₂, y=40₈. В ответе укажите результат в десятичной системе счисления.

Решение:

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

(о правилах перевода систем счисления читайте здесь)

Сначала переведем число x=10111,0111₂ в десятичную систему счисления:
x=1*16+0*8+1*4+1*2+1*1+0*0,5+1*0,25+1*0,125+1*0,0625=23+0,4375=23,4375₁₀

Аналогично поступим с числом y=40₈:
y=4*8+0*1=32₁₀

Перемножим результаты:
x*y=23,4375₁₀*32₁₀=750₁₀

Ответ: 750.

Простая задача (1 балл): Укажите через запятую в порядке возрастания все целые положительные десятичные числа, не превосходящие 26, запись которых в троичной системе счисления оканчивается на 22.

Решение:

Очевидно, первым делом мы переводим число 26 в троичную систему счисления (о правилах перевода систем счисления читайте здесь):
26₁₀=222₃

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

000; 001; 002; 010; 011; 012; 020; 021; 022; 100; 101; 102; 110; 111; 112; 120; 121; 122; 200; 201; 202; 210; 211; 212; 220; 221; 222.

Из них на 22 заканчваются всего 3: 022; 122; 222.

Можно и не выписывать все эти числа. Очевидно, что в искомых числах последние две цифры - двойки. Т.е. они имеют вид *22. Сколькими способами можно выбрать первую цифру? Конечно, тремя (0/1/2), т.к. в троичной системе счисления нет других цифр, кроме нуля, единицы и двойки.

Все, что осталось сделать - перевести эти числа в десятичную систему счисления (о правилах перевода систем счисления читайте здесь):

1. 022₃=0*9+2*3+2*1=8₁₀;
2. 122₃=1*9+8=17₁₀;
3. 222₃=2*9+8=26₁₀.

Ответ: 8; 17; 26.

Простая задача (2 балла): Укажите минимальное число символов в алфавите, чтобы с помощью слов из пяти букв можно было бы передавать 220 различных сообщений. Слова могут содержать повторяющиеся символы. Ответ дать в виде целого числа (для решения данной задачи можно почитать этот раздел).

Решение:

Воспользуемся видоизмененной (под 5 событий) формулой N=5ⁱ; отсюда i=log₅N (в какую степень нужно возвести 5, чтобы получить N).

N=220; i=log₅220.

Очевидно, что у пятерки нет степени, возведя в которую, получим 220, значит нужно выбрать минимальную степень, когда мы получим число, большее 220:
5¹=5 - маловато
5²=25 - маловато
5³=125 - маловато
5⁴=625 - подходит!

Ответ: 4.

Простая задача (1 балл): Какая из логических операций не будет иметь истинного значения, когда на входе операции все аргументы истинны? В ответе укажите номер операции в списке.

1. Импликация;
2. Дизъюнкция;
3. Конъюнкция;
4. Исключающее ИЛИ.

Решение:

Для решения просто нужно знать таблицы истинности для всех 4-х операций:

Ответ: 4.

Простая задача (1 балл): Для логической функции F(X,Y,Z) известен фрагмент таблицы истинности:

Какие из предложенных выражений соответствуют функции F? В ответе укажите в порядке возрастаний номера соответствующих выражений через запятую.

1. not (X and Y) and Z;
2. not (X or not Y) or Z;
3. not (X and Y) or Z;
4. (X or Y) and Z;
5. not (X or Z) or not Y.

Решение:

Просто подставим построчно значения из фрагмента таблицы истинности значения в каждую функцию (условно заменим логические операции матемтическими):

1. not(X*Y) * Z = not(0*0) * 0 = 1*0 = 0 - можно дальше не проверять - несовпадение по первой строке;
2. not(X + notY) + Z = not(0 + not0) + 0 = 0 + 0 = 0 - можно дальше не проверять - несовпадение по первой строке;
   
3. not(X*Y) + Z = not(0*0) + 0 = 1;
   not(X*Y) + Z = not(0*0) + 1 = 1;
   not(X*Y) + Z = not(0*1) + 0 = 1 - полное совпадение по всем строкам;
4. (X+Y) * Z = (0+0) * 0 = 0; - можно дальше не проверять - несовпадение по первой строке;
   
5. not(X+Z) + notY = not(0+0) + not0 = 1;
   not(X+Z) + notY = not(0+0) + not1 = 1;
   not(X+Z) + notY = not(0+1) + not0 = 1 - полное совпадение по всем строкам.
   

Ответ: 3, 5.

Простая задача (1 балл): Дан фрагмент программы, обрабатывающей массив, размером в M элементов, заполненный неповторяющимися целыми числами.

Сколько элементов массива после обработки не изменят своего значения, если M=21? В ответе укажите целое число.

Решение:

Эту задачу можно решать блоками в уме, чтобы экономить время.

Однако, покажу подробное полное решение.

Итерация - один "проход" по циклу (развернутые определения и подробный материал по циклам находится здесь).

Возьмем произвольный массив из 21 элемента, подходящий под условие:

Первая итерация: i=1; следующая строка присваивает элементу с "номером" [i] (т.е. первому, т.к. i сейчас равно 1) значение элемента с "номером" [M-i+1] (т.е. 21-1+1=21). Если Вы решаете "в уме" важно помнить, что присваивая переменной новое значение, мы "заменяем" старое, что хорошо видно при письменном решении. Таким образом 21-й элемент получает уже измененное значение первого элемента.

Соответственно, после первого "прохода" (i=1) имеем:

Вторая итерация: i=2; элементу с "номером" i присваивается значение элемента с номером [M-i+1] (т.е. 21-2+1=20). Двадцатый элемент при этом получит измененное значение первого.

После второго "прохода" (i=2) имеем:

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

Исходный массив VS Измененный массив:

P.s. Конечно же, читатель захочет увидеть пошаговое выполнение программы:

Ответ: 11.

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