Ответы для варианта 5. Задача 1 (8 баллов). Существует ли система счисления, в которой = 10 и 4 * 5 = 24 и

1 Ответы для варианта = 70? Задача 1 (8 баллов). Существует ли система счисления, в которой = 10 и 4 * 5 = 24 и Ответ:НЕТ. Задача 2 (8 баллов). Некто N жил в XIX в. Суммы цифр года его рождения и смерти одинаковы. Число прожитых им лет начинается цифрой 8. Определить год рождения N. Ответ: 1809 г. Задача 3 (8 баллов). На какое наибольшее число частей могут разделить плоскость 15 прямых? Ответ: 121. В общем случае решение будет таким: n прямых могут разделить плоскость на 1+n(n+1)/2 частей. Задача 4 (8 баллов). Упростить логическую функцию A(A B)(A (B)). Упрощенный вид должен содержать не более 3-х логических операций. Ответ: AB. Задача 5 (8 баллов). В шахматном турнире участвовали два ученика седьмого класса и несколько учеников восьмого класса. Два семиклассника набрали 8 очков, а каждый из восьмиклассников набрал одно и то же количество очков. Сколько восьмиклассников участвовало в турнире? Найти все решения, зная, что каждый с каждым играл один раз. Ответ: 7 или 14. Задача 6 (8 баллов). Замените инфиксное выражение (a^2+b)*(c+d^2), где ^ - знак операции возведения в степень, префиксным. Ответ: *+^a2b+c^d2 Задача 7 (12 баллов). Решить рекуррентную функцию, т. е. найти формулу для n-ого члена ряда чисел a1, a2,, an,, если a1 = 0, a2 = -4 и зная соответствующее количество первых членов последовательности an+2-4 an an = 0. Ответ: an = (1-n)2 n. 100

2 Задача 8 (12 баллов). Учитель предложил трем ученикам перемножить два числа. После умножения множимого на отдельные цифры множителя один из учеников при сложении частных произведений забыл удержать в уме одну единицу некоторого разряда. Разделив при проверке результат на множитель, он получил в частном 971, а в остатке 214. Второй ученик в указанном разряде не сделал ошибки, но при сложении цифр следующего разряда забыл прибавить двойку. Делая проверку таким же образом, как первый, он получил в частном 365, а в остатке 198. Третий сделал подобную же ошибку на единицу в следующем высшем разряде и получил при проверке в частном 940, а в остатке 48. Определить данные для умножения числа и указать, в каких местах были сделаны ошибки. Ответ: 972 и 314. Первый ученик уменьшил на единицу число сотен, второй уменьшил на две единицы число тысяч, третий уменьшил на единицу число десятков тысяч. Задача 9 (12 баллов). Определите, что будет напечатано в результате выполнения следующей программы: var a: byte=54; b: byte=108; begin 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=54, b=108; printf( "%d\n", (byte)(

((byte)(b << 1) & (byte)(b >> 1))) & ((byte)((a b) >> 1) (byte)((a & b) << 1)) ); Ответ: 111. Задача 10 (16 баллов). Постройте матрицу D после выполнения следующей программы и вычислите сумму элементов строго ниже побочной диагонали: const n=5; var D: array[0..n-1,0..n-1] of integer; var i, j, k, l: integer; begin k:=0; l:=0; if ((i+j) mod 2 <> 0) then begin k:=k-1; D[i,j]:=k; end else begin l:=l+1; D[i,j]:=l; end; for k:=0 to 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]); 101

3 Окончательный вид матрицы D: Ответ: Сумма элементов матрицы D строго ниже побочной диагонали:

4 Ответы для варианта 6 Задача 1 (8 баллов). Перевести число 123, из десятичной системы счисления в четверичную систему счисления. Ответ: 1323, Задача 2 (8 баллов). Некто N жил в XIX в. В 1901 г. суммы цифр числа лет, прожитых им, равнялась сумме цифр года его рождения. В каком году родился N? Ответ: 1810 г. Задача 3 (8 баллов). На сколько частей можно разделить поверхность шара плоскостями, проходящими через его центр, при условии, что никакие три плоскости не проходят через один и тот же диаметр? Ответ: 2 + n(n-1). Задача 4 (8 баллов). Упростить логическую функцию (A (B + С)) ((A B) + (A )). Упрощенный вид должен содержать не более 2 х логических операций. Ответ: A + B или A B. Задача 5 (8 баллов). В шахматном турнире участвовали ученики девятых и десятых классов. Десятиклассников было в 10 раз больше, чем девятиклассников, и они набрали вместе в 4.5 раза больше очков, чем все девятиклассники. Сколько очков набрали девятиклассники, если каждый с каждым играл один раз. Ответ: 10. Задача 6 (8 баллов). Замените инфиксное выражение (a^2+b^3)^4, где ^ - знак операции возведения в степень, префиксным. Ответ: ^+^a2^b34. Задача 7 (12 баллов). Решить рекуррентную функцию, т. е. найти формулу для n-ого члена ряда чисел a1, a2,, an,, если a1 = 2, a2 = 8 и зная соответствующее количество первых членов последовательности an+2-4 an+1-4 an = 0. Ответ: an = n 2 n. 105

5 Задача 8 (12 баллов). Знаменатель дроби меньше квадрата ее числителя на единицу; если к числителю и знаменателю прибавить по 2, то значение дроби будет больше 1/4; если от числителя и знаменателя отнять по 3, то значение дроби будет меньше 1/10. Найти эту дробь. Ответ: 3/8, или 4/15, или 5/24. Задача 9 (12 баллов). Определите, что будет напечатано в результате выполнения следующей программы: var a: byte=22; b: byte=220; begin 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))); Ответ: 71. typedef unsigned char byte; byte a=22, b=220; 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; begin k:=0; l:=0; if ((i+j) mod 2 = 0) then begin k:=k+1; D[i,j]:=k; end else begin l:=l-1; D[i,j]:=l; end; for k:=0 to 1 do D[i,j]:=min(D[i,j], D[i,k]+D[k,j]); Решение задачи 10. #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]); Исходный вид матрицы D:

6 Матрица D для k=0: Матрица D для k=1: Ответ: главная диагональ:

7 Ответы варианта 8 Задача 1 (8 баллов). Переведите шестнадцатеричное число A16 = 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. 110

8 Задача 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. 111

9 Задача 7 (12 баллов). Решить рекуррентную функцию, т. е. найти формулу для n-ого члена ряда чисел a1, a2,, an,, если a1 = 1, a2 = 1 и каждое an, начиная с a3, есть an = 2 an-1 an-2. Решение задачи 7. a1 = 1 a2 = 1 a3 = 2 a2 a1 = 2*1 ( 1) = = 1. a4 = 2 a3 a2 = 2*( 1) 1) = 2 1 = 1. a5 = 2 a4 a3 = 2*1 ( 1) = = 1 и т. д. Ответ: an = ( 1) n. Задача 8 (12 баллов). Некоторое количество денег было разложено на n кучек. После этого из первой кучи переложили во вторую 1/n-ю часть бывших в первой кучке денег. Затем из второй кучки 1/n-ю часть оказавшихся в ней после перекладывания денег переложили в третью кучку. Далее 1/n-ю часть денег, получившихся после этого в третьей кучке, переложили в четвертую и т. д. Наконец, из n-ой кучки 1/n-ю часть оказавшихся в ней после предшествующего перекладывания денег переложили в первую кучку. После этого в каждой кучке стало A руб. Сколько денег в каждой кучке было до перекладывания (рассмотреть случай n=5)? Ответ: x1 = n(n-2)/(n-1) 2 *A, x2 = (n 2 2n + 2)/(n-1) 2 *A, x3 = x4 = = xn = A. Задача 9 (12 баллов). Определите, что будет напечатано в результате выполнения следующей программы: var a: byte=217; b: byte=101; begin 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)(

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

📎📎📎📎📎📎📎📎📎📎