Задача 2 (8 баллов). Найти два целых положительных числа, зная, что их разность равна 66, а их наименьшее общее кратное равно 360.

1 Второй (заключительный) этап академического соревнования Олимпиады школьников «Шаг в будущее» по образовательному предмету «Информатика», весна 2017 г. Вариант 8 Задача 1 (8 баллов). Число 357,45, заданное в десятичной системе счисления, перевели в восьмеричную систему счисления. Найти 1997-ю цифру после запятой. Задача 2 (8 баллов). Найти два целых положительных числа, зная, что их разность равна 66, а их наименьшее общее кратное равно 360. Задача 3 (8 баллов). На какое наибольшее число частей могут разделить плоскость 15 прямых? Задача 4 (8 баллов). Упростить логическую функцию ( (A B + )) (A + B A B). Упрощенный вид должен содержать не более 3-х логических операций. Задача 5 (8 баллов). Ученик должен перемножить два трехзначных числа и полученное произведение разделить на пятизначное число. Но он не заметил знака умножения и принял оба рядом стоящие числа за одно шестизначное. Поэтому полученное частное оказалось в три раза больше истинного. Определить все три числа Задача 6 (8 баллов). Замените префиксное выражение ^+^a2+^b2^c23, где ^ - знак операции возведения в степень, инфиксным. В искомом результате допустимы лишние круглые скобки, которые не являются ошибкой. Задача 7 (12 баллов). Решить рекуррентную функцию, т. е. найти формулу для n-ого члена ряда чисел a 1, a 2,, a n,, если a 1 = -1, a 2 = 1 и каждое a n, начиная с a 3, есть a n = -2 a n-1 - a n-2. Задача 8 (12 баллов). Некоторое количество денег было разложено на n кучек. После этого из первой кучи переложили во вторую 1/n-ю часть бывших в первой кучке денег. Затем из второй кучки 1/n-ю часть оказавшихся в ней после перекладывания денег переложили в третью кучку. Далее 1/n-ю часть денег, получившихся после этого в третьей кучке, переложили в четвертую и т. д. Наконец, из n-ой кучки 1/n-ю часть оказавшихся в ней после предшествующего перекладывания денег переложили в первую кучку. После этого в каждой кучке стало A руб. Сколько денег в каждой кучке было до перекладывания (рассмотреть случай n=5)? 1

2 Задача 9 (12 баллов). Определите, что будет напечатано в результате выполнения следующей программы: var a: byte=217; b: byte=101; writeln( byte(not(byte(b shl 1) and byte(b shr 1))) and (byte((a or b) shr 1) or byte((a and b) shl 1))); typedef unsigned char byte; byte a=217, b=101; printf( "%d\n", (byte)(

((byte)(b << 1) & (byte)(b >> 1))) & ((byte)((a b) >> 1) (byte)((a & b) << 1)) ); Задача 10 (16 баллов). Постройте матрицу D после выполнения следующей программы и выпишите элементы ее побочной диагонали: const n=5; var D: array[0..n-1,0..n-1] of integer; var i, j, k, l: integer; k:=0; l:=0; for i:=0 to n-1 do if ((i+j) mod 2 = 0) then k:=k-1; D[i,j]:=k; end else l:=l+1; D[i,j]:=l; end; for k:=0 to 1 do for i:=0 to n-1 do D[i,j]:=min(D[i,j], D[i,k]+D[k,j]); #define MIN(X,Y) ((X) < (Y)? (X) : (Y)) const int n=5; int D[n][n]; int i, j, k=0, l=0; if ((i+j) % 2 == 0) D[i][j]=--k; else D[i][j]=++l; for (k=0; k<2; k++) D[i][j]=MIN(D[i][j], D[i][k]+D[k][j]); 2

3 Ответы варианта 8 Задача 1 (8 баллов). Переведите шестнадцатеричное число A 16 = 32AB,1 в десятичную систему счисления. Ответ можно дать с точностью до 3-го знака после запятой. Решение задачи 1. 32AB,1 = 3* * * * * *16-2 = ,75 + 0, = , = 12971, Ответ: 12971, Задача 2 (8 баллов). Найти два целых положительных числа, зная, что их разность равна 66, а их наименьшее общее кратное равно 360. Решение задачи 2. Обозначим искомые числа через Х и Y. Эти числа связаны соотношением Y=Х+66. Ясно, что Y>66. Число 360 делится на Х и на Y. Пара чисел 6 и 72 не удовлетворяет условиям задачи, так как их НОК равен 72. Пара чисел 24 и 90 подходит. Ответ: 24 и 90. Задача 3 (8 баллов). На плоскости расположены два треугольника и две прямые. Определите наибольшее возможное число точек пересечения всех прямых и сторон треугольников. Решение задачи 3. Две прямые имеют не более одной точки пересечения, отрезок или прямая имеют не более двух точек пересечения со сторонами треугольника. Так как один треугольник состоит из трех отрезков, то его стороны имеют не более 6 точек пересечения со сторонами другого треугольника. Таким образом, число точек пересечения не превосходит суммы чисел точек пересечений двух прямых, сторон треугольников, одной и другой прямой со сторонами двух треугольников, т.е. числа =15. Поэтому ответ: 15. Ответ: 15. Задача 4 (8 баллов). Упростить логическую функцию ( (A B + )) (A + B A B). Упрощенный вид должен содержать не более 3-х логических операций. Ответ: + B A. 3

4 Задача 5 (8 баллов). Замените префиксное выражение ^+^a2+^b2^c23 на инфиксное. Решение задачи 5. Переход от префиксного выражения к инфиксному может быть осуществлен посредством следующей процедуры: 1. Начинать считывание выражения слева направо. 2. Если считанный символ не является символом операции, то поместить его в стек и продолжать чтение. 3. Если считанный символ является символом операции, то: a. Вытолкнуть из стека два верхних элемента; b. Поместить символ операции между вторым и первым элементом из стека и поставить скобки; c. Поместить выражение, полученное на шаге (b), обратно в стек. 4. Продолжать чтение слева направо и выполнять шаги (2) и (3) до завершения. Ответ: (a^2+b^2+c^2)^3. Задача 6 (8 баллов). Найдите частное q, остаток r и наименьшее по модулю равноостаточное с a число b при делении a на d: а) a=1650, d= 105 б) a= 539, d=90. Решение задачи 6. а) При делении уголком a на d получим 1650= Откуда 1650=( 105) ( 15)+75 и поэтому q= 15, r=75. Среди чисел 75 и = 30 наименьшим по модулю будет число 30, а, значит, b= 30. б) При делении уголком a на d получим 539= Откуда следует 539=90 ( 5) 89=90 ( 5) =90 ( 6)+1, поэтому q= 6 и r=1 (остаток должен быть неотрицательным!). Далее, из чисел 1 и 1 90 = 89 выбираем b=1. Ответ: a) q= 15, r=75, b= 30. b) q= 6, r=1, b=1. 4

5 Задача 7 (12 баллов). Решить рекуррентную функцию, т. е. найти формулу для n-ого члена ряда чисел a 1, a 2,, a n,, если a 1 = 1, a 2 = 1 и каждое a n, начиная с a 3, есть a n = 2 a n-1 a n-2. Решение задачи 7. a 1 = 1 a 2 = 1 a 3 = 2 a 2 a 1 = 2*1 ( 1) = = 1. a 4 = 2 a 3 a 2 = 2*( 1) 1) = 2 1 = 1. a 5 = 2 a 4 a 3 = 2*1 ( 1) = = 1 и т. д. Ответ: a n = ( 1) n. Задача 8 (12 баллов). Некоторое количество денег было разложено на n кучек. После этого из первой кучи переложили во вторую 1/n-ю часть бывших в первой кучке денег. Затем из второй кучки 1/n-ю часть оказавшихся в ней после перекладывания денег переложили в третью кучку. Далее 1/n-ю часть денег, получившихся после этого в третьей кучке, переложили в четвертую и т. д. Наконец, из n-ой кучки 1/n-ю часть оказавшихся в ней после предшествующего перекладывания денег переложили в первую кучку. После этого в каждой кучке стало A руб. Сколько денег в каждой кучке было до перекладывания (рассмотреть случай n=5)? Ответ: x 1 = n(n-2)/(n-1) 2 *A, x 2 = (n 2 2n + 2)/(n-1) 2 *A, x 3 = x 4 = = x n = A. Задача 9 (12 баллов). Определите, что будет напечатано в результате выполнения следующей программы: var a: byte=217; b: byte=101; writeln( byte(not(byte(b shl 1) and byte(b shr 1))) and (byte((a or b) shr 1) or byte((a and b) shl 1))); Ответ: 252. typedef unsigned char byte; byte a=217, b=101; printf( "%d\n", (byte)(

6 for i:=0 to n-1 do if ((i+j) mod 2 = 0) then k:=k-1; D[i,j]:=k; end else l:=l+1; D[i,j]:=l; end; for k:=0 to 1 do for i:=0 to n-1 do D[i,j]:=min(D[i,j], D[i,k]+D[k,j]); if ((i+j) % 2 == 0) D[i][j]=--k; else D[i][j]=++l; for (k=0; k<2; k++) D[i][j]=MIN(D[i][j], D[i][k]+D[k][j]); Решение задачи 10. После первичного заполнения матрица D будет иметь вид: Для k=0 матрица D будет иметь вид: Для k=1 матрица D будет иметь вид: Эта матрица будет итоговой. Ответ: Элементы побочной диагонали итоговой матрицы:

📎📎📎📎📎📎📎📎📎📎