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

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

2 А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) значения массива сначала возрастают, а потом убывают

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

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

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

6 А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

7 Решение Ответ: 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

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

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

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

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

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

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

14 В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

15 В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 четных цифр. Ответ:

16 В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

17 В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

18 Алгоритмы поиска НОД 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;