1.2. Алгоритмизация и программированиеАлгоритмы, виды алгоритмов, описания алгоритмов. Формальное исполнение алгоритма.Федеральный институт педагогических измерений Соответствующие задания демо-версии 2007 года: А14, А20, ВЗ, В6, СЗ.1.36 (ДВ-2004) Цепочка из трех бусин формируется по следующему правилу: На первом месте в цепочке стоит одна из бусин А, Б, В. На втором - одна из бусин Б, В, Г. На третьем месте - одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте. Какая из следующих цепочек создана по этому правилу: 1)АГБ 2) ВАГ 3)БГГ 4) ББГ1.37 (ОС) Для составления цепочек используются бусины, помеченные буквами: М, N, О, Р, S. В середине цепочки стоит одна из бусин М, О, S. На третьем - любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На первом месте - одна из бусин О, Р, S, не стоящая в цепочке в середине. Какая из перечисленных цепочек создана по этому правилу? 1)SMP 2)MSO 3)SNO 4)OSN1.38 (ДВ-2005) Для составления цепочек используются бусины, помеченные буквами: А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором - любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте - одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Какая из перечисленных цепочек создана по этому правилу? 1) СВЕ 2) ADD 3) ЕСЕ 4) EAD1.39 (ДВ-2004) В понедельник в одном из классов должно быть проведено 4 урока - по математике, физике, информатике и биологии. Учителя высказали свои пожелания для составления расписания. Учитель математики хочет иметь первый или второй урок, учитель физики - второй или третий урок, учитель информатики - первый или четвертый, учитель биологии -третий или четвертый. Какой вариант расписания устроит всех учителей школы? {Обозначения: М- математика, Ф - физика, И - информатика, Б - биология) 1) ИМБФ 2) МФБИ 3) МИФБ 4) МБФИ1.40 (ОС) В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные а, b, с имеют тип "строка", а переменные i, k - тип "целое". Используются следующие функции: Длина (а) - возвращает количество символов в строке а. (Тип "целое") Извлечь (a, i) - возвращает i-тый (слева) символ в строке а. (Тип "строка") Склеить (а, b) - возвращает строку, в которой записаны сначала все символы строки а, а затем все символы строки b. (Тип "строка") Значения строк записываются в одинарных кавычках (Например, а : = 'дом'). Фрагмент алгоритма: Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной а было 'РОЗА'? 1) 'ПАЗ' 2) 'ПАЗОР' 3) 'ПОЗА 4) 'ПРОЗА1.41 (ДВ-2004) Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: "Вперед N" (Кузнечик прыгает вперед на N единиц); "Назад М" (Кузнечик прыгает назад на М единиц). Переменные N и М могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд "Назад 2" на 12 больше, чем команд "Вперед 3". Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?1.42 (ДВ-2005) У исполнителя Утроитель две команды, которым присвоены номера: вычти 1 умножь на 3 Первая из них уменьшает число на экране на 1, вторая - увеличивает его в три раза. Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.(Например, программа 21211 это программаумножь на 3вычти 1умножь на 3вычти 1вычти 1которая преобразует число 1 в 4.)1.43 (ДВ-2004) Записано 6 строк, каждая имеет свой номер - от 0 до 5. В нулевой строке записана цифра 0 (ноль). Каждая последующая строка состоит из двух повторений предыдущей и добавленного в конец своего номера (в i-й строке в конце приписана цифра i). Ниже показаны первые четыре строки, сформированные по описанному правилу (в скобках записан номер строки): 0 001 0010012 001001200100123 Какая цифра стоит в последней строке на 62-м месте (считая слева направо)?1.44(ДВ-2005) Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:Вперед n, где п - целое число, вызывающая передвижение черепашки на n шагов в направлении движения.Направо т, где т - целое число, вызывающая изменение направления движения на m градусов по часовой стрелке. Запись ^ Повтори 5 [Команда1 Команда2]означает, что последовательность команд в скобках повторится 5 раз. Черепашке был дан для исполнения следующий алгоритм: Повтори 5 [Вперед 10 Направо 72] Какая фигура появится на экране? Незамкнутая ломаная линия Правильный треугольник Квадрат Правильный пятиугольник1.45(ДВ-2006) Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды: Вперед п, вызывающая передвижение Черепашки на n шагов в направлении движения. Направо m, вызывающая изменение направления движения на m градусов по часовой стрелке. Вместо п и т должны стоять целые числа). Запись:^ Повтори 5 [Команда1 Команда2] означает, что последовательность команд в квадратных скобках повторится 5 раз. Какое число необходимо записать вместо n в следующем алгоритме: ^ Повтори 7 [Вперед 40 Направо п], чтобы на экране появился правильный шестиугольник? 1)30 2)45 3)50 4)601.46 (ОС) Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо), 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу 3233241. Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?1.47 (ОС) Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа - цифры "1". Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается еще одно число - номер строки по порядку (на i-м шаге дописывается число “i”). Вот первые 4 строки, созданные по этому правилу: 1 112 1121123 112112311211234 Сколько раз в общей сложности встречаются в девятой строке четные цифры (2, 4, 6, 8)?1.48 (УМТ) Два игрока играют в следующую игру. Имеются три кучи камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой-нибудь куче, или добавить по два камня в каждую из трех куч. Предполагается, что у каждого игрока имеется неограниченный запас камней. Выигрывает тот игрок, после чьего хода в какой-нибудь куче становится 15 камней или во всех трех кучах суммарно становится 25 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре, - первый или второй игрок.1.49 (ОС) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй - 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 3 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.1.50 (ДВ-2005) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй - 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.1.51 (ДВ-2006) Два игрока играют в следующую игру Перед ними лежат две кучки камней, в первой из которых 5, а во второй - 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок? Ответ обоснуйте.^ Основные алгоритмические конструкции: следование, ветвление, цикл. Блок-схемы. ПеременныеФедеральный институт педагогических измерений Соответствующие задания демо-версии 2007 года: А6, А7.1.52 (ДВ-2004) Алгоритмическая конструкция какого типа изображена на фрагменте блок-схемы: линейная циклическая разветвляющаяся вспомогательная 1.53 (ДВ-2005) Фрагмент блок-схемы представляет алгоритм, который содержит две команды ветвления: команду ветвления в сокращенной форме, в которую вложена команда ветвления в полной форме две команды ветвления в полной форме, одна из которой вложена в другую две команды ветвления в сокращенной форме, одна из которой вложена в другую команду ветвления в полной форме, в которую вложена команда ветвления в сокращенной форме1.54 (ДВ-2005) Определите значение целочисленной переменной х после выполнения следующего фрагмента программы: 1)1 2)5 3)10 4)15 1.55 (УТМ) Определите значение переменной В после выполнения следующего фрагмента алгоритма: 1)6 2)5 3)3 4)4 1.56 (УТМ) Определите значение переменной А после выполнения следующего алгоритма: 1)5 2)11 3)23 4)471.57 (УТМ) Определите значение переменной s после выполнения следующего фрагмента алгоритма:1.58 (ОС) Определите значение переменной с после выполнения фрагмента алгоритма: 1)1 2)45 3)55 4)661.59 (ДВ-2004) Определите значение целочисленных переменных х, у и t после выполнения фрагмента программы (ниже представлена одна и та же программа, записанная на разных языках программирования): l)x = 2,y = 5,t = 5 2)x = 7,y = 5,t = 5 3)x = 2,y = 2, t = 2 4)x = 5, у = 5, t = 5 1.60 (ДВ-2005) Определите значение целочисленных переменных а и b после выполнения фрагмента программы (ниже представлена одна и та же программа, записанная на разных языках программирования): l)a = 42, b=14 2)a=l, b = 42 3)a = 0, b = 588 4)а=14, b = 421.61 (ОС) Определите значение целочисленных переменных а и b после выполнения фрагмента программы: 1)а = 22, b = 20 а = 4682, b = 4680 а =8246, b = 246 а = 470, b = 4681.62 (УТМ) Определите значение целочисленных переменных х, у и t после выполнения фрагмента программы: 1) х = 4, у = 1, t= 0 2) х = 0, у = 5, t = 4 3) х = 0, у = 4, t = 5 4) х = 4, у = 1, t = 01.63 (УТМ) Определите значение целочисленных переменных b и с после выполнения фрагмента программы (ниже представлена одна и та же программа, записанная на разных языках программирования): 1) b = 3, с =7 2) b = 7, с = 3 3) b = 3, с = 4 4) b = 4, с =31.64 (УТМ) Определите значение целочисленных переменных а и b после выполнения фрагмента программы (ниже представлена одна и та же программа, записанная на разных языках программирования): l) a = 7, b = 21 2) a = 7, b = 7 3) а = 7, b=14 4) а = 3, b = 21И.К. Сафронов «Готовимся к ЕГЭ. Информатика»Требования к знаниям учащихся Учащиеся должны владеть понятием алгоритм, знать их виды и свойства, способы описания алгоритмов, должны уметь по заданному алгоритму определить его вид, что он делает и результат выполнения. Задания демо-версии ЕГЭ по информатики 2006 годаА6 Определите значение переменной с после выполнения фрагмента алгоритма l) 1 2) 45 3) 55 4) 66 А7 Определите целочисленное значение переменных a и b после выполнения фрагмента программы: Бейсик Паскаль Алгоритмический a=2468b=(a MOD 1000)*10a=a\1000+b(\ и MOD – операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно) a:=2468;b:=(a mod 1000)*10;a:=a div 1000+b;(div и mod – операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно) a:=2468;b:=mod (a, 1000)*10;a:=div (a, 1000)+b;(div и mod – операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно) l) a = 22, b = 20 2) a = 4682, b = 4680 3) а = 8246, b=246 4) а = 470, b = 468Задание 1.3.1 Определите значение переменной w после выполнения фрагмента алгоритма (рис. 1.2). 1)25 2)49 3)64 4)80Задание 1.3.2 Что будет выведено на экран в результате выполнения фрагмента следующей программы (вводится значение w = 3). Бейсик Паскаль INPUT WFOR R=1 TO WPRINT “WAR”NEXT RIF R=W THEN GOTO 1 PRINT “SUNDAY”1: PRINT “PEACE” READLN WFOR R=1 TO W DOWRITELN (‘WAR’)IF R=W THEN GOTO 1 WRITELN (‘SUNDAY’)1: WRITELN (‘PEACE’) 1) WAR 2) WAR 3) WAR 4) WAR WAR WAR WAR WAR WAR WAR WAR WAR SUNDAY PEACE SUNDAY PEACEЗадание 1.3.3 Что будет выведено на экран в результате выполнения фрагмента следующей программы: Бейсик Паскаль X=13Y=17Z=22: IF X>=4 THEN GOTO 1 PRINT X, Y, Z X=X-1 Y=Y+X Z=Z+1 GOTO 21: END X:=13;Y:=17;Z:=2;2: IF Z>=4 THEN GOTO 1; WRITELN (X, Y, Z); X:=X-1; Y:=Y+X; Z:=Z+1; GOTO 2;1: END 1) 13 17 2 2) 12 18 3 3) 13 17 2 4) 13 17 2 12 30 3 11 29 3 12 29 3 12 29 3 11 42 4 11 40 4 11 40 4 10 50 5Задание 1.3.4 Что будет напечатано на экране в результате выполнения фрагмента следующей программы: Бейсик Паскаль X=13Y=52Z=99FOR U=1== TO 1 STEP -2IF U=X THEN PRINT UIF U=Y THEN PRINT UIF U=Z THEN PRINT UNEXT U X:=13;Y:=52; Z:=99; U:=100; 1: IF U=X THEN WRITELN (U);IF U=Y THEN WRITELN (U);IF U=Z THEN WRITELN (U);U:=U-2;IF U>1 THEN GOTO 1; 1) 13 2) 13 3) 52 4) 52 99 52 -2 99Задание 1.3.5 Вычислите значение следующих выражений: 20\6 20 MOD 6 34\4 34 MOD 4 2\5 2 MOD 4 (4*7\3) MOD (6\3) 24 MOD (5\3) Задание 1.3.6 Определите значение целочисленных переменных a и b после выполнения фрагмента программы: Бейсик Паскаль A=2007 B=(A\100)+100 A=B\10-A MOD 1000(\ и MOD – операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно) A:=2007;B:=(A DIV 100)+100;A:=B DIV 10 – A MOD 1000;(div и mod – операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно) 1) a=25, b=20; 2) a=5, b=120; 3) a=120, b=5; 4) a=10, b=120Задание 1.3.7 Клиент делает покупку максимально возможного количества товара по цене Cрублей за штуку. B оплату клиент предлагает R рублей. Тогда можно написать следующую формулу для расчёта сдачи N рублей (первая формула в ответе на Бейсике, вторая – на Паскале): Бейсик Паскаль N=R-(R\C)*C N=R-(C\R)*C N=(R\C)*CN=(C\R)*C N:=R-(R div C)*C; N:=R-(C div R)*C; N:=(R div C)*C;N:=(C div R)*C; Задание 1.3.8 Значения двумерного массива размера задают с помощью вложенного оператора цикла в представленном фрагменте программы: Бейсик Паскаль FOR i=1 TO 5FOR j=1 TO 5F(I,j)=2*j-iNEXT jNEXT i for i:=1 to 5 dofor j:=1 to 5 doF(I,j):=2*j-I; Сколько элементов массива будут иметь отрицательные значения? 1) 4 2) 6 3) 8 4) 10Задание 1.3.9 Задан двумерный массив В(2, 7): 5 8 11 14 17 20 23 1 5 3 9 7 13 11 Определите значение переменной Р после выполнения фрагмента алгоритма: 1) 98 2) 99 3) 100 4) 101 Задание 1.3.10 Дан двумерный массив В(5,5): 8 4 5 6 2 3 6 7 3 2 5 9 4 7 1 8 6 4 3 9 1 7 9 3 2 Определить значение R после выполнения фрагмента программы: Бейсик Паскаль S1=0S2=0FOR i=1 TO 5S1=S1+B(i,i)S2=S2+B(I,6-i)NEXT iR=S1-S2 S1:=0;S2:=0;For i:=1 to 5 do beginS1:=S1+B(i,i);S2:=S2+B(i, 6-i)end;R:=S1-S2 1) 5 2) 7 3) 9 4) 11Задание 1.3.11 Население города Паскальевска занимается составлением различных программ. Но злобный вирус постоянно поедает куски их программ. Жители города Паскальевска попросили восстановить одну из испорченных программ. Вот она: Бейсик Паскаль S=0FOR I=2 TO10 STEP 2S=…NEXT IPRINT S s:=0;i:=2;1: s:=…;i:=i+2;if iwriteln (s); На экране напечаталось число 220. Как же выглядела полностью восстановленная строка s=… (или s:=…) s=(s+i)/2 или s:=(s+i)/2; s=(i+s)*2 или s:=(i+s)*2; s=s+i*i или s:=s+i*i; s=s*i или s:=s*i; Задание 1.3.12 Как правильно записать следующее алгебраическое выражение для его использования компьютером: (a*b)-c/(a+c)/2*b*c (a*b)-c/(a+c)/(2*b*c) ((a*b)-c/(a+c))/(2*b*c) ((a*b)-c/(a+c))/2*b*c Работа с массивамиФедеральный институт педагогических измерений Соответствующие задания демо-версии 2007 года: А8, С21.65 (ДВ-2004) Значения двумерного массива задаются с помощью вложенного оператора цикла в представленном фрагменте программы Бейсик Паскаль Алгоритмический FOR n=1 TO 5FOR k=1 TO 5B(n,k)=n+kNEXT kNEXT n for n:=1 to 5 for k:=1 to 5B[n,k]:=n+k; для n от 1 до 5нц для k от 1 до 5нц B[n,k]=n+kкцкц Чему будет равно значение В(2,4)? 1) 9; 2)8; 3)7; 4)61.66 (ДВ-2005)Все элементы двумерного массива размером 10x10 элементов первоначально были равны 0. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы {ниже представлена одна и та же программа, записанная на разных языках программирования). Сколько элементов массива в результате будут равны 1? 1)0 2)16 3)12 4)41.67 (УТМ) Сколько элементов массива в результате будут равны 1?Все элементы двумерного массива А размером 4x4 элемента первоначально были равны 0. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы (ниже представлена одна и та же программа, записанная на разных языках программирования). 1.68 (УТМ) Все элементы двумерного массива А размером 10x10 элементов первоначально были равны 1. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы. Сколько элементов массива в результате будут равны 0?1.69 (УТМ) 1. Значения двумерного массива задаются с помощью вложенного оператора цикла в представленном фрагменте программы Чему будет равно значение В(19,21)?1.70 (УТМ) Опишите на русском языке или одном из языков программирования алгоритм поиска номера первого из двух соседних элементов в целочисленном массиве из 20 элементов, сумма которых максимальна1.71 (ДВ-2005) Опишите на русском языке или одном из языков программирования алгоритм подсчета числа элементов равных максимальному в числовом массиве из 30 элементов.