1 Алгоритмизация и программирование Алгоритмы, виды алгоритмов, описания алгоритмов. Формальное исполнение алгоритма
| Вид материала | Документы |
СодержаниеПовтори 5 [Команда1 Команда2] Повтори 5 [Команда1 Команда2] Повтори 7 [Вперед 40 Направо п] Основные алгоритмические конструкции: следование, ветвление, цикл. Блок-схемы. Переменные |
- Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы, 96.46kb.
- Основы алгоритмизации, 754.96kb.
- Язык описания алгоритмов начертательной геометрии adgl, 70.57kb.
- Урок: «типы алгоритмов. Линейные алгоритмы» Тема: Типы алгоритмов. Линейные алгоритмы, 101.98kb.
- Методические рекомендации к занятиям темы 7 «Алгоритмы обработки информации», 163.76kb.
- Список ресурсов интернет «Место алгоритмов в повседневной жизни» определения алгоритма,, 26.36kb.
- Введение Предмет "Программирование", 19.2kb.
- «Численные методы в химии» Общая трудоёмкость дисциплины составляет, 22.46kb.
- «Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов, построение, 84.9kb.
- Разработка алгоритмов методом последовательной детализации. Вспомогательные алгоритмы, 37.3kb.
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)OSN
1.38 (ДВ-2005)
Для составления цепочек используются бусины, помеченные буквами: А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором - любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте - одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Какая из перечисленных цепочек создана по этому правилу?
1) СВЕ 2) ADD 3) ЕСЕ 4) EAD
1.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)60
1.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)47
1.57 (УТМ)
Определите значение переменной s после выполнения следующего фрагмента алгоритма:
1.58 (ОС)
Определите значение переменной с после выполнения фрагмента алгоритма:
1)1 2)45 3)55 4)66
1.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 = 42
1.61 (ОС)
Определите значение целочисленных переменных а и b после выполнения фрагмента программы:
1)а = 22, b = 20
- а = 4682, b = 4680
- а =8246, b = 246
- а = 470, b = 468
1.62 (УТМ)
Определите значение целочисленных переменных х, у и t после выполнения фрагмента программы:
1) х = 4, у = 1, t= 0 2) х = 0, у = 5, t = 4 3) х = 0, у = 4, t = 5 4) х = 4, у = 1, t = 0
1.63 (УТМ)
Определите значение целочисленных переменных b и с после выполнения фрагмента программы (ниже представлена одна и та же программа, записанная на разных языках программирования):
1) b = 3, с =7 2) b = 7, с = 3 3) b = 3, с = 4 4) b = 4, с =3
1.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=2468 b=(a MOD 1000)*10 a=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 W FOR R=1 TO W PRINT “WAR” NEXT R IF R=W THEN GOTO 1 PRINT “SUNDAY” 1: PRINT “PEACE” | READLN W FOR R=1 TO W DO WRITELN (‘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=13 Y=17 Z=2 2: IF X>=4 THEN GOTO 1 PRINT X, Y, Z X=X-1 Y=Y+X Z=Z+1 GOTO 2 1: 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=13 Y=52 Z=99 FOR U=1== TO 1 STEP -2 IF U=X THEN PRINT U IF U=Y THEN PRINT U IF U=Z THEN PRINT U NEXT 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)*C
- N=(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;
- N=R-(R\C)*C
Задание 1.3.8
Значения двумерного массива размера
задают с помощью вложенного оператора цикла в представленном фрагменте программы:| Бейсик | Паскаль |
| FOR i=1 TO 5 FOR j=1 TO 5 F(I,j)=2*j-i NEXT j NEXT i | for i:=1 to 5 do for j:=1 to 5 do F(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=0 S2=0 FOR i=1 TO 5 S1=S1+B(i,i) S2=S2+B(I,6-i) NEXT i R=S1-S2 | S1:=0; S2:=0; For i:=1 to 5 do begin S1:=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=0 FOR I=2 TO10 STEP 2 S=… NEXT I PRINT S | s:=0; i:=2; 1: s:=…; i:=i+2; if i<=10 then goto 1; writeln (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, С2
1.65 (ДВ-2004)
Значения двумерного массива задаются с помощью вложенного оператора цикла в представленном фрагменте программы
| Бейсик | Паскаль | Алгоритмический |
| FOR n=1 TO 5 FOR k=1 TO 5 B(n,k)=n+k NEXT k NEXT n | for n:=1 to 5 for k:=1 to 5 B[n,k]:=n+k; | для n от 1 до 5 нц для k от 1 до 5 нц B[n,k]=n+k кц кц |
Чему будет равно значение В(2,4)?
1) 9; 2)8; 3)7; 4)6
1.66 (ДВ-2005)
Все элементы двумерного массива размером 10x10 элементов первоначально были равны 0. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы {ниже представлена одна и та же программа, записанная на разных языках программирования).
Сколько элементов массива в результате будут равны 1?
1)0 2)16 3)12 4)4
1.67 (УТМ)
Сколько элементов массива в результате будут равны 1?
Все элементы двумерного массива А размером 4x4 элемента первоначально были равны 0. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы (ниже представлена одна и та же программа, записанная на разных языках программирования).
1.68 (УТМ)
Все элементы двумерного массива А размером 10x10 элементов первоначально были равны 1. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы.
Сколько элементов массива в результате будут равны 0?
1.69 (УТМ)
1. Значения двумерного массива задаются с помощью вложенного оператора цикла в представленном фрагменте программы
Чему будет равно значение В(19,21)?
1.70 (УТМ)
Опишите на русском языке или одном из языков программирования алгоритм поиска номера первого из двух соседних элементов в целочисленном массиве из 20 элементов, сумма которых максимальна
1.71 (ДВ-2005)
Опишите на русском языке или одном из языков программирования алгоритм подсчета числа элементов равных максимальному в числовом массиве из 30 элементов.