Единый государственный экзамен по ИНФОРМАТИКЕ и ИКТ
Инструкция по выполнению работы
Экзаменационная
работа состоит из двух частей, включающих в себя 27 заданий. Часть 1 содержит
23 задания с кратким ответом, часть 2 содержит 4 задания с развёрнутым ответом.
На выполнение экзаменационной работы по
информатике и ИКТ отводится 3 часа 55 минут (235 минут).
Ответы к заданиям 1–23 записываются
в виде числа, последовательности букв или цифр. Ответы запишите в поле ответа в
тексте работы, а затем перенесите в бланк ответов № 1.
Задания 24–27 требуют развёрнутого ответа. В
бланке ответов № 2 укажите номер задания и запишите его полное решение.
Все бланки ЕГЭ заполняются яркими чёрными
чернилами. Допускается использование гелевой, капиллярной или перьевой ручек.
При выполнении заданий можно пользоваться
черновиком. Записи в черновике не учитываются при оценивании работы.
Баллы, полученные Вами за
выполненные задания, суммируются. Постарайтесь выполнить как можно больше
заданий и набрать наибольшее количество баллов.
Желаем успеха!
В экзаменационных заданиях используются следующие
соглашения.
1. Обозначения
для логических связок (операций):
a) отрицание
(инверсия, логическое НЕ) обозначается ¬ (например, ¬А);
b) конъюнкция
(логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В);
c) дизъюнкция
(логическое сложение, логическое ИЛИ) обозначается \/
(например, А \/ В) либо | (например, А | В);
d) следование
(импликация) обозначается → (например, А → В);
e) тождество
обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда,
когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);
f) символ
1 используется для обозначения истины (истинного высказывания);
символ 0 – для обозначения лжи (ложного высказывания).
2.
Два логических выражения, содержащих переменные, называются
равносильными (эквивалентными), если значения этих выражений совпадают при
любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А
\/ В и А /\ В неравносильны (значения выражений разные, например, при А = 1, В
= 0).
3.
Приоритеты логических операций: инверсия (отрицание), конъюнкция
(логическое умножение), дизъюнкция (логическое сложение), импликация
(следование), тождество. Таким образом, ¬А /\ В \/ С /\ D
означает то же, что и ((¬А) /\ В) \/ (С /\ D).
Возможна запись А /\ В /\ С вместо (А /\ В)
/\ С. То же относится и к дизъюнкции: возможна запись А \/ В \/ С вместо
(А \/ В) \/ С.
4.
Обозначения Мбайт и Кбайт используются в традиционном для
информатики смысле – как обозначения единиц измерения, чьё соотношение с
единицей «байт» выражается степенью двойки.
Часть
1
Ответами к
заданиям 1–23 являются число, последовательность букв или цифр, которые
следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего
задания, начиная с первой клеточки, без пробелов, запятых и других
дополнительных символов. Каждый символ пишите в отдельной клеточке в
соответствии с приведёнными в бланке образцами.
|
Перем. 1
|
Перем. 2
|
Функция
|
???
|
???
|
F
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
Пример. Пусть задано выражение x → y,
зависящее от двух переменных x и y, и таблица истинности:
Укажите наименьшее четырёхзначное восьмеричное число,
двоичная запись
которого содержит ровно 5 нулей. В
ответе запишите только само восьмеричное число, основание системы счисления
указывать не нужно.
Ответ:
___________________________.
Тогда
1-му столбцу соответствует переменная y, а 2-му столбцу соответствует
Логическая функция
F задаётся выражением ¬(х \/ (¬z)) \/ (¬x) & z .
Определите, переменная x. В ответе нужно написать: yx.
какому столбцу таблицы истинности функции F
соответствует каждая из переменных x, y, z. Ответ:
___________________________.
Перем. 1
|
Перем. 2
|
Перем. 3
|
Функция
|
???
|
???
|
???
|
F
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
|
A
|
B
|
C
|
D
|
E
|
F
|
A
|
|
2
|
|
|
|
17
|
B
|
2
|
|
4
|
8
|
|
|
C
|
|
4
|
|
3
|
|
|
D
|
|
8
|
3
|
|
3
|
6
|
E
|
|
|
|
3
|
|
2
|
F
|
17
|
|
|
6
|
2
|
|
Между населёнными пунктами A, B, C, D, E, F построены
дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице
означает, что прямой дороги между пунктами нет.)
В ответе напишите буквы x, y, z
в том порядке, в котором идут соответствующие
им
столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква,
соответствующая 2-му столбцу; затем – буква,
соответствующая 3-му столбцу). Определите длину кратчайшего пути между пунктами
A и F (при условии, что Буквы в ответе пишите подряд, никаких разделителей
между буквами ставить не передвигаться можно только по построенным дорогам).
нужно.
Ответ:
___________________________.
4
|
В фрагменте базы данных представлены сведения о родственных
отношениях.
|
6
|
Таблица 1
|
|
Таблица 2
|
ID
|
Фамилия_И.О.
|
Пол
|
ID_Родителя
|
ID_Ребёнка
|
866
|
Карпец Д.К.
|
Ж
|
866
|
911
|
867
|
Коротич Б.Ф.
|
М
|
866
|
938
|
879
|
Лемешко В.А.
|
Ж
|
867
|
911
|
885
|
Месхи К.Г.
|
М
|
867
|
938
|
900
|
Сердюк Л.А.
|
Ж
|
911
|
879
|
904
|
Петрик А.И.
|
М
|
911
|
1041
|
911
|
Коротич А.Б.
|
Ж
|
904
|
900
|
932
|
Петрик П.А.
|
Ж
|
938
|
995
|
938
|
Коротич И.Б.
|
М
|
938
|
1017
|
949
|
Фоменко Г.Р.
|
Ж
|
949
|
995
|
970
|
Сердюк А.П.
|
М
|
949
|
1017
|
995
|
Кортич Т.И.
|
Ж
|
970
|
879
|
1017
|
Кортич П.И.
|
М
|
970
|
1041
|
1026
|
Мухина Р.Г
|
Ж
|
904
|
932
|
1041
|
Гейко М.А.
|
Ж
|
1026
|
900
|
1056
|
Сердюк П.А.
|
М
|
1026
|
932
|
|
А
|
В
|
С
|
1
|
2
|
|
44
|
2
|
=44-В1∙В1∙5
|
=В1∙В1/2+22
|
44-20
|
У исполнителя ДваПять две команды, которым присвоены
номера:
На
основании приведённых данных определите, сколько внуков и внучек есть у
Карпец
Д.К. 1.
отними 2
2.
раздели на 5
Выполняя первую из них, ДваПять
отнимает от числа на экране 2, а выполняя вторую, делит это число на 5 (если
деление нацело невозможно, ДваПять отключается).
Запишите порядок команд в программе,
которая содержит не более 5 команд и переводит число 152 в число 2.
В ответе указывайте лишь номера
команд, пробелы между цифрами не ставьте. Так, для программы
раздели
на 5 отними 2 отними 2
нужно написать 211. Эта программа преобразует, например,
число 55 в число 7.
Ответ:
___________________________.
Ответ:
___________________________. Дан фрагмент электронной таблицы:
По каналу связи передаются
сообщения, содержащие только 4 буквы: И, Г, Л, А. Для кодирования букв И,
Г, Л используются 6-битовые кодовые слова:
И — 000000, Г — 001110, Л — 110110.
Для этого набора кодовых слов
выполнено такое свойство: любые два слова из набора отличаются не менее, чем в трёх позициях.
Это свойство важно для расшифровки сообщений при наличии помех. Нужно
подобрать кодовое слово Какое целое число должно быть записано в ячейке B1,
чтобы построенная после для буквы А так, чтобы указанное свойство выполнялось
для всех четырёх выполнения вычислений диаграмма по значениям диапазона ячеек
A2:С2 кодовых слов. соответствовала рисунку? Известно, что все значения
диапазона А1:С2 имеют один и тот же знак.
Какое
из слов можно использовать: 111110, 111000, 000110?
Ответ:
___________________________.
Ответ:
___________________________.
Запишите число, которое будет
напечатано в результате выполнения следующей Ниже на записан рекурсивный
алгоритм F: программы:
Паскаль
|
procedure F(n: integer); begin
writeln(n); if n > 0 then begin
F(n - 1); F(n - 3) end end
|
Паскаль
|
var n, s: integer; begin n :
= 1; s : = 6; while s <= 365 do begin
s : = s + 36; n : = n * 2 end; write(n) end.
|
Чему равна сумма всех чисел, напечатанных на экране при
выполнении вызова F(5)?
Ответ:
___________________________. Ответ:
___________________________.
Производилась
четырехканальная (квадро) звукозапись с частотой
дискретизации 24 кГц и 16-битным разрешением. В результате
был получен В терминологии сетей TCP/IP маска
сети - двоичное число, меньшее 232; в файл размером 1800 Мбайт, сжатие данных не производилось.
Определите
маске сначала (в старших разрядах) стоят единицы, а
затем с некоторого приблизительно, сколько минут производилась запись. места нули. Маска определяет, какая часть
IP-адреса узла сети относится к
В качестве ответа укажите ближайшее к времени записи целое
число минут.
адресу сети, а какая — к адресу
самого узла в этой сети. Обычно маска запи-
Ответ: ___________________________.
сывается по тем же правилам, что и
IP-адрес – в виде четырёх байт, причём каждый байт
записывается в
виде десятичного числа. Адрес сети получается в результате
применения поразрядной конъюнкции к
заданному IP-адресу узла и маске.
Сколько слов длины 5,
начинающихся с согласной буквы и заканчивающихся Например, если IP-адрес узла равен 231.32.255.131, а маска
равна гласной
буквой, можно составить из букв З, И, М, А? Каждая буква может 255.255.240.0, то адрес сети равен
231.32. 240.0. входить в слово несколько раз. Слова не обязательно
должны быть осмысленны-
ми словами русского языка. Для узла с IP-адресом 227.138.127.144
адрес сети равен 227.138.64.0.
Чему равен
третий слева байт маски? Ответ запишите в виде десятичного числа.
Ответ:
___________________________.
Ответ:
___________________________.
13 При регистрации в компьютерной
системе каждому пользователю выдаётся пароль, состоящий из 11 символов и содержащий
только символы А, Б, В, Е, Ж, М, Н, Р, У, Я (таким образом, используется 10
различных символов). Каждый такой пароль в компьютерной системе записывается
минимально возможным и одинаковым целым количеством байт (при этом используют
посимвольное кодирование и все символы кодируются одинаковым и минимально
возможным количеством бит). Укажите объём памяти в байтах, отводимый этой
системой для записи 70 паролей. В ответе запишите только число, слово «байт»
писать не нужно.
Ответ: ___________________________.
Исполнитель Чертёжник перемещается на
координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться
на (a, b) (где a, b – целые числа),
перемещающую Чертёжника из точки с координатами (x, y) в точку с
координатами (x + a, y + b). Чертёжнику был дан для
исполнения следующий алгоритм:
Например, если Чертёжник находится в точке с координатами
(4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).
Цикл
ПОВТОРИ число
РАЗ последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена
указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм
(буквами n, a, b обозначены неизвестные числа, при этом n
> 1):
НАЧАЛО сместиться
на (60, 100)
ПОВТОРИ n РАЗ сместиться
на (a, b) сместиться на (33, 44)
КОНЕЦ ПОВТОРИ сместиться
на (13, 200) сместиться на (-1; 60)
КОНЕЦ
После выполнения этого алгоритма Чертёжник возвращается в исходную точку.
Какое наибольшее число повторений могло быть указано в конструкции
«ПОВТОРИ n РАЗ»?
Ответ: ___________________________.
На рисунке – схема дорог, связывающих города А, B, C, D, E,
F, H, P, K, L, M
По каждой дороге можно двигаться только в одном
направлении, указанном стрелкой.
Сколько существует различных путей, ведущих из города А в
город М?
B
F P
Ответ: ___________________________.
Сколько единиц содержится в двоичной записи выражения
42020+22017−15?
Ответ: ___________________________.
17 В языке запросов поискового сервера
для обозначения логической операции «ИЛИ» используется символ «|», а для
логической операции «И» — символ «&». В таблице приведены запросы и
количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
|
Найдено страниц (в тысячах)
|
Леннон & Маккартни & Старр
|
1100
|
Леннон & Маккартни & Харрисон
|
1300
|
Леннон & Маккартни & Старр & Харрисон
|
1000
|
Какое количество страниц (в тыс.) будет найдено по запросу (Леннон
& Маккартни & Старр) | (Леннон & Маккартни & Харрисон)?
Считается, что все запросы выполнялись
практически одновременно, так что набор страниц, содержащих все искомые слова,
не изменялся за время выполнения запросов.
Ответ: ___________________________.
На числовой прямой даны два отрезка: P
= [25; 50] и Q = [32; 47]. Укажите наибольшую возможную длину промежутка A,
для которого формула
(¬ (x A) → (x P)) → ((x A) → (x Q))
тождественно истинна, то есть принимает значение 1 при
любом значении переменной х.
Ответ: ___________________________.
В программе используется
одномерный целочисленный массив A с индексами от 0 до 9. Значения
элементов равны 4; 2; 6; 6; 7; 7; 7; 5; 5; 9 соответственно, т.е.
A[0] = 4; A[1] = 2 и т.д.
Определите значение переменной c после
выполнения следующего фрагмента программы, записанного ниже на разных языках
программирования.
Паскаль
|
c := 0;
for i := 1 to 9 do
if A[i - 1] >= A[i] then begin
t := A[i]; A[i] := A[i - 1]; A[i - 1] := t; c := c +
1; end;
|
Ответ: ___________________________.
Ниже записан алгоритм. Получив на вход число x, этот
алгоритм печатает два числа a
и b. Укажите наибольшее четырёхзначное число x, при вводе которого алгоритм
печатает сначала 5, а потом 7?
Паскаль
|
var x, y, a,
b: integer; begin a := 10; b := 0; readln(x);
while x > 0 do begin
y := x mod 10; x := x div 10 if
y < a then a := y; if y > b then
b := y; end; writeln(a); writeln(b) end.
|
Ответ: ___________________________.
Сколько существует различных наборов
значений логических переменных 21 Напишите в ответе число различных значений
входной переменной k, при x1,
x2, ... x8, которые удовлетворяют всем перечисленным ниже
условиям?
которых
программа выдаёт тот же ответ, что и при входном значении k = 55.
Значение
k = 55 также включается в подсчёт различных значений k. ((x1
≡ x2) ∨ (x3
≡ x4)) ∧ (¬(x1
≡ x2) ∨ ¬(x3
≡ x4)) = 1
((x3
≡ x4) ∨ (x5
≡ x6)) ∧ (¬(x3
≡ x4) ∨ ¬(x5
≡ x6)) = 1
Паскаль
|
var k, i : longint;
function f(n: longint):longint; begin
f := 3*n*n+1 end; begin
readln(k); i := 0; while (f(i)<k) do
i := i+1; writeln(i) end.
|
((x5 ≡ x6) ∨ (x7 ≡ x8)) ∧ (¬(x5 ≡ x6)
∨ ¬(x7 ≡ x8))
= 1
В
ответе не нужно перечислять все различные наборы значений переменных x1,
x2, … x8 при которых выполнена данная система равенств.
В
качестве ответа Вам нужно указать количество таких наборов.
Ответ:
___________________________.
Ответ: ___________________________.
Исполнитель А22 преобразует целое число, записанное на
экране. У
исполнителя
три команды, каждой команде присвоен номер:
1)
Прибавь 1 2) Прибавь 2 3)
Прибавь предыдущее
Не забудьте перенести все
ответы в бланк ответов № 1 в соответствии с инструкцией по выполнению
работы.
|
Первая команда увеличивает число на
экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на
экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11
прибавляется 10 и т. д.). Программа для исполнителя А22 — это последовательность
команд.
Сколько
существует программ, которые число 2 преобразуют в число 9?
Ответ: ___________________________.
Для записи
ответов на задания этой части (24–27) используйте БЛАНК ОТВЕТОВ № 2. Запишите
сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы
записывайте чётко и разборчиво.
|
Часть 2
Дан целочисленный массив из 20 элементов. Элементы
массива могут принимать
целые значения от –10 000 до 10 000
включительно. Опишите на одном из языков программирования алгоритм, позволяющий
найти и вывести количество пар элементов массива, в которых сумма элементов
делится на 2, но не делится на 4. В данной задаче под парой подразумеваются два
соседних элемента масси ва.
Требовалось
написать программу, при выполнении которой с клавиатуры Исходные данные
объявлены так, как показано ниже на примерах для
считывается натуральное число x, не
превосходящее 1000, и выводится количе- некоторых языков программирования.
Запрещается использовать переменные, не ство значащих цифр в двоичной записи
этого числа. Программист торопился и описанные ниже, но разрешается не
использовать некоторые из описанных написал программу неправильно: переменных.
Паскаль
|
var x,cnt: integer; begin
readln(x); cnt := 0; while x > 0 do begin
cnt:=cnt + x mod 2; x := x div 10 end;
writeln(cnt) end.
|
|
Паскаль
|
const
N = 20; var
a: array
[1..N] of integer; i, j, k: integer; begin
for i := 1 to N do readln(a[i]);
… end.
|
|
Последовательно выполните следующее:
В качестве ответа Вам необходимо привести фрагмент программы,
который
1. Напишите,
что выведет эта программа при вводе числа 15. должен находиться на месте многоточия.
2.
Приведите пример такого числа x, что, несмотря на ошибки,
программа печатает правильный ответ.
3. Найдите
все ошибки в этой программе (их может быть одна или несколько). Известно, что
каждая ошибка затрагивает только одну строку и может быть исправлена без изменения
других строк.
Для каждой ошибки:
1)
выпишите строку, в которой сделана ошибка;
2)
укажите, как исправить ошибку, т.е. приведите правильный вариант
стро- ки.
Достаточно
указать ошибки и способ их исправления для одного языка про- граммирования.
Обратите внимание, что требуется найти ошибки в имеющейся программе, а не
написать свою, возможно, использующую другой алгоритм решения. Исправление
ошибки должно затрагивать только строку, в которой нахо- дится ошибка.
26
|
Два игрока, Петя и Ваня, играют в следующую игру. Перед
игроками лежит куча
|
27
|
По каналу связи
передаются положительные целые числа, не превышающие камней. Игроки ходят по
очереди, первый ход делает Петя. За один ход игрок 1000, – результаты
измерений, полученных в ходе эксперимента (количество может добавить в кучу
один камень или увеличить количество камней в измерений известно заранее).
После окончания эксперимента передаётся конкуче в пять раз. Например,
имея кучу из 10 камней, за один ход можно трольное значение – наибольшее число
R, удовлетворяющее следующим условиполучить кучу из 11 или 50 камней. У каждого
игрока, чтобы делать ходы, есть ям:
неограниченное
количество камней. 1) R — сумма двух различных переданных
элементов последовательности
(«различные»
означает, что нельзя просто удваивать переданные числа, суммы
Игра завершается в тот момент,
когда количество камней в куче становится различных, но равных по величине
элементов допускаются); более 200. Победителем считается игрок, сделавший
последний ход, то есть 2) R — нечётное число.
первым
получивший кучу, в которой будет 201 или больше камней. В начальный
момент в куче было S камней, 1 ≤ S ≤
200. Если чисел, соответствующих приведённым условиям, нет, считается, что R =
–1. В результате помех при передаче как сами числа, так и контрольное
Говорят,
что игрок имеет выигрышную стратегию, если он может выиграть значение
могут быть искажены.
при любых ходах противника. Описать стратегию игрока -
значит описать, какой Напишите эффективную, в том числе по используемой памяти,
программу ход он должен сделать в любой ситуации, которая ему может встретиться
при (укажите используемую версию языка программирования, например, Free Pascal
различной игре противника. 2.6.4),
которая будет проверять правильность контрольного значения. Программа должна
напечатать отчёт по следующей форме:
Выполните
следующие задания. Во всех случаях обосновывайте свой ответ.
Вычисленное
контрольное значение: …
Задание 1. а) При каких
значениях числа S Петя может выиграть первым Контроль пройден (или Контроль не
пройден) ходом? Укажите все такие значения и выигрывающий ход Пети.
б)
Укажите такое значение S, при котором Петя не может выиграть за один Если
удовлетворяющее
условию
контрольное
значение
определить
ход,
но при любом ходе Пети Ваня может выиграть своим первым ходом. невозможно
(то есть R = –1), то выводится только фраза «Контроль не пройден».
Опишите выигрышную стратегию Вани. Перед
текстом программы кратко опишите используемый Вами алгоритм решения.
Задание 2. Укажите два значения S, при
которых у Пети есть выигрышная На вход программе в первой строке подаётся
количество чисел N. В каждой стратегия, причём (а) Петя не может
выиграть первым ходом, но (б) Петя может из последующих N строк записано
одно натуральное число, не превышающее выиграть своим вторым ходом, независимо
от того, как будет ходить Ваня. 1000. В последней строке записано контрольное
значение. Для указанных значений S опишите выигрышную стратегию Пети
.
Пример
входных данных:
Задание
3. Укажите такое значение S, при котором
-
у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или 6
вторым ходом при любой игре Пети, и при этом 100 - у Вани
нет стратегии, которая позволит ему гарантированно выиграть первым 8
ходом. 33
Для указанного значения S
опишите выигрышную стратегию Вани. 45 Постройте дерево всех партий, возможных
при этой выигрышной стратегии 19 Вани (в виде рисунка или таблицы). На рёбрах
дерева указывайте, кто делает 90
ход,
в узлах — количество камней в позиции. 145
Пример выходных данных для
приведённого выше примера входных данных:
Вычисленное
контрольное значение: 145
Контроль
пройден
Система оценивания экзаменационной
работы по информатике и ИКТ Часть
2
Часть 1 Критерии
оценивания заданий с развернутым ответом
За
правильный ответ на задания 1–23 ставится 1 балл; за неверный ответ Требовалось
написать программу, при выполнении которой с клавиатуры или его отсутствие – 0 баллов. считывается натуральное
число x, не превосходящее 1000, и выводится количе ство значащих цифр в двоичной записи этого
числа. Программист торопился и
№ задания
|
Ответ
|
1
|
1017
|
2
|
yxz
|
3
|
15
|
4
|
4
|
5
|
111000
|
6
|
12211
|
7
|
2
|
8
|
1024
|
9
|
164
|
10
|
256
|
11
|
11
|
12
|
192
|
13
|
420
|
14
|
72
|
15
|
36
|
16
|
2015
|
17
|
1400
|
18
|
15
|
19
|
6
|
20
|
7775
|
21
|
27
|
22
|
57
|
23
|
32
|
Паскаль
|
var x,cnt: integer; begin
readln(x); cnt := 0; while x > 0 do begin
cnt:=cnt
+ x mod 2; x := x div 10 end; writeln(cnt) end.
|
написал
программу неправильно:
Последовательно
выполните следующее:
1.
Напишите, что выведет эта программа при вводе числа 15.
2.
Приведите пример такого числа x, что, несмотря на ошибки,
программа печатает правильный ответ.
3.
Найдите все ошибки в этой программе (их может быть одна или
несколько). Известно, что каждая ошибка затрагивает только одну строку и может
быть исправлена без изменения других строк.
Для
каждой ошибки:
1) выпишите
строку, в которой сделана ошибка;
2)
укажите, как исправить ошибку, т.е. приведите правильный вариант
строки.
Достаточно
указать ошибки и способ их исправления для одного языка про граммирования.
Обратите внимание, что требуется найти ошибки в имеющейся программе, а
не написать свою, возможно, использующую другой алгоритм ре шения. Исправление
ошибки должно затрагивать только строку, в которой на ходится ошибка.
Решение использует запись программы на Паскале.
Допускается использо-
вание программы на
четырех других языках. 25
Дан целочисленный массив из 20 элементов. Элементы массива могут принимать
целые значения от –10 000 до 10 000 включительно. Опишите на одном из
1.
Программа выведет число 2. языков программирования
алгоритм, позволяющий найти и вывести количество пар элементов
массива, в которых сумма элементов делится на 2, но не делится
2.
Программа напечатает правильный ответ при x=1. Замечание для
прове- на 4. В данной задаче под парой подразумеваются два соседних элемента
массиряющего: это единственный случай, когда программа сработает верно. ва.
Исходные
данные объявлены так, как показано ниже на примерах для
3.
Первая ошибка. Неверный подсчёт количества цифр. Программа не
учи- некоторых языков программирования. Запрещается использовать переменные, не
тывает значащие нули. описанные ниже, но разрешается не использовать некоторые
из описанных
Строка с ошибкой: переменных.
cnt:=cnt + x mod 2;
Возможный
вариант исправления:
Паскаль
|
const
N = 20; var
a: array [1..N] of
integer; i, j, k: integer; begin
for i := 1 to N do readln(a[i]);
… end.
|
cnt:=cnt + 1;
4.
Вторая ошибка. Неверная обработка числа x в цикле. Строка с
ошибкой:
x := x div 10; Возможный вариант
исправления:
x := x div 2;
В качестве ответа Вам необходимо привести фрагмент программы,
который должен
находиться на месте многоточия.
Решение:
Паскаль
k := 0;
for i := 1 to N-1 do
if ((a[i]+a[i+1]) mod 2=0) and ((a[i]+a[i+1]) mod
4<>0) then inc(k); writeln(k);
Алгоритмический язык
k := 0; нц для i от 1 до N-1
если mod(a[i]+a[i+1],2)=0 и mod(a[i]+a[i+1],4)<> 0 то
|
k := k+1 все кц вывод k
Бейсик
K = 0
K = 0
FOR I = 1 TO N-1
IF (A(I)+A(I+1)) MOD 2 = 0 AND (A(I)+A(I+1)) MOD 4
<>0 THEN
K = K+1
END IF
NEXT I
PRINT K
Python k = 0 for i in range(0, n – 1): if ((a[i]+a[i+1])%2 == 0
and (a[i]+a[i+1])%4 <> 0): k += 1
print(k)
Си
k = 0; for (i = 0; i if ((a[i]+a[i+1])%2 == 0 &&
(a[i]+a[i+1])%4 != 0)
k++;
printf("%d", k);
|
26 Два игрока, Петя и Ваня,
играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по
очереди, первый ход делает Петя. За один ход игрок может добавить в кучу
один камень или увеличить количество камней в куче в пять раз. Например,
имея кучу из 10 камней, за один ход можно получить кучу из 11 или 50 камней. У
каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда
количество камней в куче становится более 200. Победителем считается игрок,
сделавший последний ход, то есть первым получивший кучу, в которой будет 201
или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 200.
Говорят, что игрок имеет выигрышную
стратегию, если он может выиграть при любых ходах противника. Описать
стратегию игрока - значит описать, какой ход он должен сделать в любой
ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте
свой ответ.
Задание 1. а) При каких значениях
числа S Петя может выиграть первым ходом? Укажите все такие значения и
выигрывающий ход Пети.
б) Укажите такое значение S,
при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня
может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2. Укажите два значения S, при которых
у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть первым
ходом, но (б) Петя может выиграть своим вторым ходом, независимо от того, как
будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети
.
Задание 3. Укажите такое значение S, при котором
- у Вани есть
выигрышная стратегия, позволяющая ему выиграть первым или
вторым
ходом при любой игре Пети, и при этом
- у Вани нет
стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную
стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной
стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева
указывайте, кто делает ход, в узлах — количество камней в позиции.
1. а) Петя
может выиграть, если S=41, ...,200. При меньших значениях S за 27 По
каналу связи передаются положительные целые числа, не превышающие один ход
нельзя получить кучу, в которой больше 200 камней. Пете достаточ- 1000, – результаты
измерений, полученных в ходе эксперимента (количество
но увеличить количество камней в 5 раз. При S < 41
получить за один ход измерений известно заранее). После окончания эксперимента
передаётся конбольше 200 камней невозможно. трольное значение – наибольшее
число R, удовлетворяющее следующим условиб) Ваня может выиграть первым ходом
(как бы ни играл Петя), если ис- ям:
ходно в куче будет S = 40 камней. Тогда после первого хода
Пети в куче будет 1) R — сумма двух различных переданных элементов последовательности
41 камень или 200 камней. В обоих случаях Ваня увеличивает количество
(«различные» означает, что нельзя просто удваивать переданные числа, суммы
камней в 5 раз и выигрывает в один ход. различных, но равных по величине
элементов допускаются);
2)
R — нечётное число.
2. Возможные значения S: 8,
39. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он
может получить кучу из 40 камней (при Если чисел, соответствующих приведённым
условиям, нет, считается, что R S=8 он увеличивает количество камней в 5 раз;
при 5=39 - добавляет 1 ка- = –1. В результате помех при передаче как сами
числа, так и контрольное мень). Эта позиция разобрана в п. значение могут быть
искажены.
1 б. В ней игрок, который будет ходить
(теперь это Ваня), выиграть не Напишите эффективную, в том числе по
используемой памяти, программу может, а его противник (то есть Петя) следующим
ходом выиграет. (укажите используемую версию языка программирования, например,
Free Pascal
2.6.4),
которая будет проверять правильность контрольного значения. Программа
3. Возможное значение S: 38.
После первого хода Пети в куче будет 39 должна напечатать отчёт по следующей
форме: или 190 камней. Если в куче станет 190 камней, Ваня увеличит
количество камней в 5 раз и выиграет своим первым ходом. Ситуация, когда в
куче 39 Вычисленное контрольное значение: …
камней, разобрана в п. 2. В этой ситуации игрок,
который будет ходить (те- Контроль пройден (или Контроль не пройден) перь это
Ваня), выигрывает своим вторым ходом.
Если
удовлетворяющее условию
контрольное значение
определить
В таблице изображено дерево возможных
партий при описанной страте- невозможно (то есть R = –1), то выводится только
фраза «Контроль не пройден». гии Вани. Заключительные позиции (в них выигрывает
Ваня) подчёркнуты. Перед текстом программы кратко опишите используемый Вами
алгоритм На рисунке это же дерево изображено в графическом виде (оба способа
изоб- решения.
ражения
допустимы). На вход
программе в первой строке подаётся количество чисел N. В каждой
из последующих N строк записано одно натуральное
число, не превышающее 1000. В последней строке записано контрольное значение.
Пример
входных данных:
6
100
8
33
45
19
90
145
Пример выходных данных для
приведённого выше примера входных данных:
Вычисленное
контрольное значение: 145
Контроль
пройден
Сумма двух чисел
нечетна, если одно из них — чётное, а другое — нечетное. Программа,
вычисляющая контрольное значение, читает все входные данные один раз, не
запоминая их в массиве. Для прочитанного фрагмента входной
последовательности программа хранит значения двух величин: М0 – самое
большое чётное число; M1 – самое большое нечётное число. После того как все
данные прочитаны, искомое контрольное значение вычисляется как сумма M0 +
M1. Ниже приведены реализующие этот алгоритм программы на языке Паскаль, а
также на алгоритмическом языке. Допускаются решения, записанные на других
языках программирования.
Пример правильной и эффективной программы на языке
Паскаль.
var R,M0,M1,res,i,N,dat: longint; begin M0 := 0; M1 := 0;
readln(N); for i := 1 to N do
begin readln(dat);
if (dat mod 2 = 0) and (dat > M0) then
M0 := dat; if (dat mod 2 <> 0) and (dat > M1)
then
M1 := dat; end;
if (M0>0) and (M1>0) then
res := M0+M1
else res := -1; readln(R); if res > 0 then
writeln('Вычисленное контрольное значение: ',res); if (R
> 0) and (R = res) then writeln('Контроль пройден') else
writeln('Контроль не пройден'); end.
Пример
правильной и эффективной программы на Алгоритмическом языке.
ввод x
если mod(x,2) = 0 и x > m0 то m0 := x все
если mod(x,2) <> 0 и x > m1
|
|
то m1 := x все кц
если m0 > 0 и m1 > 0 то res := m0+m1 иначе
res := -1 все ввод R если res>0
то вывод нс, 'Вычисленное контрольное значение: ',res все
если R>0 и R=res
то вывод нс, "Контроль пройден" иначе вывод нс,
"Контроль не пройден" все кон
|
|
|
|
|
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.