Анализ вычислительных алгоритмов в задачах части А и В Задачи повышенной сложности Рахманова М.Н. учитель информатики МАОУ «Физико-технический лицей 1» г. Саратов

А12. Работа с массивами В программе описан одномерный целочисленный массив с индексами от 1 до 10. Ниже представлен фрагмент программы, обрабатывающей данный массив: n:=10; for i:=1 to n do begin s = A[n+1-i]*i; A[n+1-i]:= A[i]*i; A[i]:= s; end; Перед началом выполнения фрагмента все элементы массива равны 1. Укажите утверждение, которое будет верно после выполнения указанного фрагмента программы при изменении индекса от 1 до 10. 1) значения массива возрастают 2) значения массива убывают 3) значения массива постоянны 4) значения массива сначала возрастают, а потом убывают

Решение Если проделать цикл для i от 1 до 5, получится: Далее: S 3 При i = 3 : 1*3 Ответ: 4) значения массива сначала возрастают, а потом убывают

А12. Работа с массивами В программе описан одномерный целочисленный массив A, в представленном фрагменте программы обрабатываются элементы массива с индексами от 1 до 32. s:=0; n:=32; for i:= 2 to n do begin s:=s+3*(A[i]-A[i-1]); end; В начале выполнения этого в элементе массива с индексом i находилось число i (i = 1, …, 32), т. е. A[1] = 1, A[2] = 2 и т. д. Чему будет равно значение переменной s после выполнения данной программы? 1) 93 2) 90 3) 31 4) 30

Решение 123… …111 Ответ: 1) 93

А12. Работа с массивами Дан фрагмент программы, обрабатывающей двухмерный массив A[1..5,1..4]: k:=4; for m:=1 to 4 do begin k:=k+1; for n:=1 to 5 do begin k:=m-k; A[n,m]:=n*n+m*m-2*k; end; Чему будет равно значение A[3,1]? 1) 182) 193) 204) 21

Решение Ответ: 1) 18 i / j ? 4 5 m от 1 до 4 – столбцы n от 1 до 5 – строки заполнение по столбцам A[3,1] - ? Шаг 3 n = 3, k = 1 – 5 = - 4 A[3,1] = 3*3 + 1*1 – 2*(- 4) = 18 Шаг 2 n = 2, k = 1 - (- 4) = 5 A[2,1] = 2*2 + 1*1 – 2*(5) = -5 Шаг 1 k = 4 m = 1, k = 5 n = 1, k = 1 – 5 = - 4 a[1,1] = 1*1 + 1*1 – 2*(- 4) = 10

А13. Выполнение алгоритмов для исполнителя Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F1)? 1)102) 133) 16 4) 20 ПОКА снизу свободно ИЛИ справа свободно ПОКА снизу свободно вниз КОНЕЦ ПОКА вправо КОНЕЦ ПОКА ABCDEF

Решение Ответ: 2) 13 Траектория движения: вниз, пока возможно, затем один раз вправо ××××× 6 ××××× 5 ×××× 4 ××× 3 ××× 2 ××× 1 ABCDEF

А13. Выполнение алгоритмов для исполнителя Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка E5)? 1) 32) 63) 13 4) 16 ПОКА сверху свободно ИЛИ справа свободно ЕСЛИ справа свободно ТО вправо ИНАЧЕ вверх КОНЕЦ ЕСЛИ КОНЕЦ ПОКА ABCDEF

Решение Ответ: 4) 16 Траектория движения: Идем, пока возможно, вправо, затем вверх ×××××× 6 ××× 5 × 4 × 3 ××× 2 ×××××× 1 ABCDEF

А13. Выполнение алгоритмов для исполнителя ABCDEF Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение? 1) 1 2) 2 3) 3 4) 0 НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ

Решение Ответ: 1) 1 Траектория движения: 6 5 V ABCDEF

В8. Анализ программы, содержащей подпрограммы, циклы и ветвления Получив на вход число x, этот алгоритм печатает два числа a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 3, а потом 25. var x, a, b: integer; begin readln(x); a := 0; b := 0; while x > 0 do begin a := a + 1; if (x mod 2) 0 then b := b+(x mod 10); x := x div 10; end; writeln(a); write(b); End. Это алгоритм деления числа на цифры a - кол-во цифр b - сумма нечетных цифр Задача: найти наименьшее трехзначное число, сумма нечетных цифр которого равна = Ответ: 799

В8. Анализ программы, содержащей подпрограммы, циклы и ветвления Укажите наибольшее из таких чисел, при вводе которых алгоритм печатает сначала 3, а потом 3. Допускается диапазон значений для величин целого типа: от 2 31 до var x, a, b, с: longint; begin readln(x); a := 0; b := 0; while x > 0 do begin с:= х mod 2; if c = 0 then a := a + 1 else b := b + 1; x := x div 10; end; writeln(a); write(b); End. Это алгоритм деления числа на цифры a - кол-во четных цифр b – кол-во нечетных цифр Задача: найти наибольшее число, состоящее из 3 нечетных и 3 четных цифр. Ответ:

В8. Анализ программы, содержащей подпрограммы, циклы и ветвления Укажите наибольшее из таких чисел, при вводе которых алгоритм печатает сначала 3, а потом 9. var x, a, b : integer; begin readln(x); a := 0; b := 1; while x > 0 do begin a := a + 1; b := b * (x mod 5); x := x div 5; end; writeln(a); write(b); end. Это алгоритм деления числа на цифры … в 5-ричной системе счисления a - кол-во цифр при переводе в 5-ю систему счисления b – произведение полученных 5-ричных цифр Задача: найти наибольшее трехзначное число, произведение цифр которого равно 9. 9 = 3 * 3 * = Ответ: 799

В8. Анализ программы, содержащей подпрограммы, циклы и ветвления Ниже записан алгоритм. После выполнения алгоритма было напечатано 3 числа. Первые два напечатанных числа - это числа 11 и 66. Какое наибольшее число может быть напечатано третьим? var x, у, z, r, a, b: integer; begin readln(x, у); if у >x then begin z:= x; x:= y; y:= z; end; a:= x; b:= у; while b>0 do begin r := a mod b; a := b; b := r; end; Writeln (a); writeln(x); write(y); end. Это алгоритм поиска НОД х и y – исходные числи, располагаются по убыванию a – в результате это НОД Задача: найти наибольшее число, меньшее 66, такое что НОД этого числа и 66 – 11. Ответ: 55

Алгоритмы поиска НОД 1) while (a>0) and (b > 0) do if a>b then a:=a mod b else b:=b mod a; nod:=a+b; 2) while ab do if a>b then a := a - b else b := b - a; nod:=b;