Если (справа свободно) и (не снизу свободно) то. Для повторения последовательности команд можно использовать цикл «пока», имеющий следующий вид:
Вправо
Все
Для повторения последовательности команд можно использовать цикл «пока», имеющий следующий вид:
нц пока условие
последовательность команд
кц
Например, для движения вправо, пока это возможно, можно использовать следующий алгоритм:
нц пока справа свободно
Вправо
кц
Выполните задание.
Робот находится в правой клетке узкого горизонтального коридора. Ширина коридора — одна клетка, длина коридора может быть произвольной. Возможный вариант начального расположения Робота приведён на рисунке (Робот обозначен буквой «Р»):
Напишите для Робота алгоритм, закрашивающий все клетки внутри коридора и возвращающий Робота в исходную позицию. Например, для приведённого выше рисунка Робот должен закрасить следующие клетки (см. рисунок). Алгоритм должен решать задачу для произвольного конечного размера коридора. При исполнении алгоритма Робот не должен разрушиться. Алгоритм может быть выполнен в среде формального исполнителя или записан в текстовом редакторе.
20.2
Напишите программу, которая в последовательности натуральных чисел определяет количество трёхзначных чисел, кратных 4. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 — признак окончания ввода, не входит в последовательность).
|
|
Количество чисел не превышает 1000. Введённые числа не превышают 30 000. Программа должна вывести одно число: количество трёхзначных чисел, кратных 4.
Пример работы программы:
Входные данные | Выходные данные |
120 9 365 4 0 | 1 |
Контрольная работа
Тема: Единый государственный экзамен по информатике
Задание 1.Вычислите: 101011102 – 2568 + A16. Ответ запишите в десятичной системе счисления. В ответе запишите только число, основание системы счисления писать не нужно.
Задание 2.Дан фрагмент таблицы истинности выражения F:
x1 | x2 | x3 | x4 | x5 | x6 | F |
0 | 1 | 0 | 0 | 1 | 1 | 0 |
0 | 0 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 0 | 1 | 0 | 1 | 0 |
Каким выражением может быть F?
1) (x1 ∧ x2) ∨ (x3 ∧ x4) ∨ (x5 ∧ x6)
2) (x1 ∧ x3) ∨ (x3 ∧ x5) ∨ (x5 ∧ x1)
3) (x2 ∧ x4) ∨ (x4 ∧ x6) ∨ (x6 ∧ x2)
4) (x1 ∧ x4) ∨ (x2 ∧ x5) ∨ (x3 ∧ x6)
Задание 3.Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
|
A | B | C | D | E | F | |
A | 1 | |||||
B | 1 | 10 | 7 | 10 | ||
C | 10 | 8 | ||||
D | 7 | 2 | ||||
E | 10 | 8 | 2 | 5 | ||
F | 5 |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Задание 4.В некотором каталоге хранился файл Задача5. После того, как в этом каталоге создали подкаталог и переместили в созданный подкаталог файл Задача5, полное имя файла стало Е:\Класс9\Физика\Задачник\Задача5. Каково было полное имя этого файла до перемещения?
1) Е:\Физика\Задачник\Задача5
2) Е:\Физика\Задача5
3) Е:\Класс9\Задачник\Задача5
4) Е:\Класс9\Физика\Задача5
Задание 5.Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:
A — 11011, Б — 10000, В — 00111.
При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 10010, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается «x»).
|
|
Получено сообщение: 01111 10001 11100 11011. Декодируйте это сообщение.
Задание 6.У исполнителя Троечник две команды, которым присвоены номера:
Прибавь 2,
Умножь на 3.
Первая из этих команд увеличивает число на экране на 2, а вторая — умножает его на 3. Программа исполнителя Троечник — это последовательность номеров команд. Например, 1211 — это программа
Прибавь 2
Умножь на 3
Прибавь 2
Прибавь 2
Эта программа преобразует, например, число 2 в число 16.
Запишите программу, которая преобразует число 12 в число 122 и содержит не более 5 команд. Если таких программ более одной, запишите любую из них.
|
|
Задание 7.В ячейке Е16 электронной таблицы записана формула. Эту формулу скопировали в ячейки D17 и С18. В соответствии с формулой, полученной в ячейке D17, значение в этой ячейке равно сумме значений в ячейках D31 и С32; в соответствии с формулой, полученной в ячейке С18, значение в этой ячейке равно сумме значений в ячейках D32 и В32.
Укажите, какая формула могла быть написана в ячейке Е16.
Примечание: знак $ используется для обозначения абсолютной адресации.
1) =$D30 + D$32
2) =$D$32 + $В$32
3) =$D$31 + $С$32
4) =Е$32 + $D30
Задание 8.Определите число, которое будет напечатано в результате выполнения программы (записанной ниже на разных языках программирования).
Бейсик | Паскаль |
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 249 S = S + 24 N = N + 3 WEND PRINT N | var n, s: integer; begin n : = 0; s : = 0; while s <= 249 do begin s : = s + 24; n : = n + 3 end; write(n) end. |
Си | Алгоритмический язык |
#include <stdio.h> void main() { int n, s; n = 0; s = 0; while (s <= 249) { s = s + 24; n = n + 3; } printf("%d", n); } | алг нач цел n, s n : = 0 s : = 0 нц пока s <= 249 s : = s + 24 n : = n + 3 кц вывод n кон |
Задание 9.Производится двухканальная (стерео) звукозапись с частотой дискретизации 16 кГц и 32-битным разрешением. Запись длится 12 минут, ее результаты записываются в файл, сжатие данных не производится.
Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?
1) 30
2) 60
3) 75
4) 90
Задание 10.Все 5-буквенные слова, составленные из букв Б, К, Ф, Ц, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. БББББ
2. ББББК
3. ББББФ
4. ББББЦ
5. БББКБ
……
Запишите слово, которое стоит на 239-м месте от начала списка.
Задание 11.Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 3
F(n) = F(n–1) * (n–1), при n >1
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Задание 12.В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. По заданным IP-адресу узла и маске определите адрес сети.
IP-адрес узла: 200.135.210.135
Маска: 255.255.248.0
При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-адреса и запишите в нужном порядке соответствующие им буквы, без использования точек.
A | B | C | D | E | F | G | H |
0 | 102 | 110 | 130 | 135 | 200 | 208 | 210 |
Пример.
Пусть искомый IP-адрес 151.167.201.0, и дана таблица.
A | B | C | D | E | F | G | H |
255 | 167 | 128 | 151 | 157 | 0 | 191 | 201 |
В этом случае правильный ответ будет записан в виде: DBHF.
Задание 13.При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов и содержащий только символы из 26-символьного набора латинского алфавита. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.
Для хранения сведений о 10 пользователях потребовалось 500 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число — количество байт.
Задание 14.Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a, b) (где a, b – целые числа), перемещающую Чертёжника из точки с координатами (x, y), в точку с координатами (x+a, y+b). Если числа a, b положительные, значение соответствующей координаты увеличивается, если отрицательные — уменьшается.
Например, если Чертёжник находится в точке с координатами (1, 1), то команда Сместиться на (–2, 4) переместит его в точку (–1, 5).
Запись
Повтори k раз
Команда1 Команда2 Команда3
Конец
означает, что последовательность команд Команда1 Команда2 Команда3 повторится k раз.
Чертёжнику был дан для исполнения следующий алгоритм:
Сместиться на (–3, 1)
Повтори 2 раз
Сместиться на (1, 1) Сместиться на (−3, 2) Сместиться на (0, −4)
Конец
Какую единственную команду надо выполнить Чертёжнику, чтобы вернуться в исходную точку, из которой он начал движение?
1) Сместиться на (–7,–1)
2) Сместиться на (7, 1)
3) Сместиться на (–4,–2)
4) Сместиться на (4, 2)
Задание 15.На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т, Ф. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Ф?
Задание 16.Запишите десятичное число 48 в системе счисления с основанием 4. Основание системы счисления (нижний индекс после числа) писать не нужно.
Задание 17.В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос | Найдено страниц (в тысячах) |
театр & комедия | 315 |
театр & Москва | 225 |
театр & Москва & комедия | 110 |
Компьютер печатает количество страниц (в тысячах), которое будет найдено по следующему запросу:
(Москва | комедия) & театр
Укажите целое число, которое напечатает компьютер. Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Задание 18.Какое из приведенных названий животных удовлетворяет логическому условию: В слове пять букв /\ Четвертая буква гласная?
1) Зебра
2) Слон
3) Кабан
4) Олень
Задание 19.Ниже приведён фрагмент программы, записанный на четырёх языках программирования. Массив A одномерный; в программе рассматривается его фрагмент, соответствующий значениям индекса от 1 до n.
Бейсик | Паскаль |
n = 10 FOR i = 0 TO n K = A(i) A(K) = 0 NEXT i | n:=10; for i:=0 to n do begin K := A[i]; A[K] := 0; end; |
Си | Алгоритмический язык |
n=10; for (i = 0; i <= n; i++){ K = A[i]; A[K] = 0; } | n:=10 нц для i от 0 до n K := A[i] A[K] := 0 кц |
В начале выполнения этого фрагмента в массиве находились числа 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, т. е. A[0] = 10, A[1] = 9 и т. д. Сколько элементов массива после выполнения программы будут иметь ненулевые значения?
Задание 20.Ниже на пяти языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа a и b. Укажите наибольшее из таких чисел x, при вводе которого алгоритм печатает сначала 2, а потом 5.
Бейсик | Python |
DIM X, A, B AS INTEGER INPUT X A = 0: B = 1 WHILE X > 0 A = A+1 B = B * (X MOD 100) X = X\100 WEND PRINT A PRINT B | x = int(input()) a, b = 0, 1 while x > 0: a = a + 1 b = b * x%100 x = x//100 print(a) print(b) |
Паскаль | Алгоритмический язык |
var x, a, b: integer; begin readln(x); a := 0; b := 1; while x > 0 do begin a := a+1; b := b*(x mod 100); x := x div 100; end; writeln(a); write(b); end. | алг нач цел x, a, b ввод x a:=0; b:=1 нц пока x > 0 a := a+1 b := b*mod(x,100) x := div(x,100) кц вывод a, нс, b кон |
Си | |
#include <stdio.h> void main() { int x, a, b; scanf("%d", &x); a = 0; b = 1; while (x > 0) { a = a+1; b = b * (x%100); x = x/100; } printf("%d\n%d", a, b); } |
Задание 21.Определите, какое число будет напечатано в результате выполнения следующего алгоритма:
Var a, b, t, M, R : integer;
Function F(x : integer) : integer;
Begin
F:=4*(x-5)*(x+3);
end;
BEGIN
a:= −20; b:=0;
M:=a; R:=F(a);
for t:=a to b do begin
if (F(t)< R) then begin
M:=t;
R:=F(t);
end;
end;
write(R);
END.
Задание 22.Исполнитель Осень16 преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1) Прибавить 1;
2) Прибавить 2;
3) Прибавить 4.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья — увеличивает на 4.
Программа для исполнителя Осень16 — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 15 и при этом траектория вычислений содержит число 8?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.
Задание 23.Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5,x6, y1, y2, y3, y4, y5, y6, которые удовлетворяют всем перечисленным ниже условиям
(x1→x2) ∧ (x2→x3) ∧ (x3→x4) ∧ (x4→x5) ∧ (x5→x6) = 1
(y2→y1) ∧ (y3→y2) ∧ (y4→y3) ∧ (y5→y4) ∧ (y6→y5) = 1
x6→y6 = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4,x5, x6, y1, y2, y3, y4, y5, y6, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Задание 24.Дано натуральное число N, не превосходящее 108. Необходимо найти и вывести число, которое получится при записи N справа налево и удалении всех единиц. Ведущие нули выводить не надо. Если в числе N нет цифр кроме единиц и нулей, необходимо вывести 0. Например, при вводе числа 1984 нужно вывести 489, а при вводе 2001 нужно вывести 2. Для решения этой задачи ученик написал такую программу:
Бейсик | Паскаль |
DIM N, M AS LONG DIM D AS INTEGER INPUT N M = 0 WHILE N>=1 D = N MOD 10 IF D>1 THEN M = 10*D + M END IF N = (N – D) \ 10 WEND PRINT M END | var n, m: longint; d: integer; begin read(n); m := 0; while n>=1 do begin d := n mod 10; if d > 1 then begin m := 10*d + m; end; n := (n – d) div 10; end; write(m); end. |
Си | Алгоритмический |
#include <stdio.h> void main(){ long int n, m; int d; scanf("%ld",&n); m = 0; while (n>=1) { d = n%10; if (d>1) { m = 10*d + m; } n = (n – d) / 10; } printf("%ld", m); } | алг нач цел n, m цел d ввод n m := 0 нц пока n>=1 d := mod(n,10) если d>1 то m := 10*d + m все n := div(n-d,10) кц вывод m кон |
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе числа 1984.
2. Приведите пример числа, при вводе которого программа выдаст верный ответ.
3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.
Обратите внимание: Вам нужно исправить приведённую программу, а не написать свою. Вы можете только заменять ошибочные строки, но не можете удалять строки или добавлять новые. Заменять следует только ошибочные строки: за исправления, внесённые в строки, не содержащие ошибок, баллы будут снижаться.
Задание 25.Дан целочисленный массив из 50 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, в которых оба числа двузначные. В данной задаче под парой подразумевается два подряд идущих элемента массива.
Например, для массива из пяти элементов: 16 2 14 91 21 — ответ: 2. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.
Бейсик | Python |
CONST N = 50 DIM A (1 TO N) AS INTEGER DIM I, J, K, AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I ... END | //допускается также использовать //две целочисленные переменные j и k a = [] n = 50 for i in range(0, n): a.append(int(input())) ... |
Алгоритмический язык | Паскаль |
алг нач цел N = 50 целтаб a[1:N] цел i, j, k нц для i от 1 до N ввод a[i] кц ... кон | const N = 50; var a: array [1..N] of integer; i, j, k: integer; begin for i := 1 to N do readln(a[i]); ... end. |
Си | Естественный язык |
#include <stdio.h> #define N 50 int main() { int a[N]; int i, j, k; for (i = 0; i<N; i++) scanf("%d", &a[i]); ... return 0; } | Объявляем массив A из 50 элементов. Объявляем целочисленные переменные I, J, K. В цикле от 1 до 50 вводим элементы массива A с 1-го по 50-й. … |
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Free Pascal 2.6) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
Задание 26.Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй - 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди, первый ход делает Петя. Ход состоит в том, что игрок или утраивает число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Игра завершается в тот момент, когда общее количество камней в двух кучах становится не менее 20. Если в момент завершения игры общее число камней в двух кучах не менее 35, то выиграл Ваня, в противном случае - Петя. Кто выигрывает при безошибочной игре обоих игроков? Укажите, стратегию выигрывающего игрока - какой ход он должен сделать в каждой из позиций, которые могут ему встретиться при правильной игре. Докажите, что описанная стратегия - выигрышная.
Задание 27.В телевизионном танцевальном марафоне с определением победителя с помощью телезрителей после каждого тура объявляется sms-голосование, в котором зрители указывают наиболее понравившуюся им пару из максимум 16 пар, которые участвуют в проекте. Вам предлагается написать программу, которая будет обрабатывать результаты sms-голосования по данному вопросу. Результаты голосования получены в виде номеров пар (каждый элемент списка соответствует одному sms-сообщению).
Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.
Задание А. Имеется набор данных, состоящий из 15 чисел.
Напишите программу для решения такой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу – 2 балла.
Задание Б. Имеется набор данных, состоящий из целых чисел. Набор может быть очень большим.
Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Следует учитывать, что количество голосов в списке может быть очень велико. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших sms-сообщений N. В каждой из последующих N строк записан номер пары от 1 до 16. Пример входных данных:
4
2
16
3
2
Программа должна вывести список всех пар, встречающихся в списке, в порядке убывания (невозрастания) количества голосов, отданных за ту или иную пару, с указанием количества отданных за неё голосов. При этом каждая пара должна быть выведена ровно один раз вне зависимости от того, сколько раз она встречается в списке. Пример выходных данных для приведённого выше примера входных данных:
2 2
3 1
16 1
Дата добавления: 2018-02-28; просмотров: 1346; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!