close

Вход

Забыли?

вход по аккаунту

...лРЕШУ ЕГЭ (http://информатика.решуегэ.рф) Вариант

код для вставкиСкачать
Образовательный портал «РЕШУ ЕГЭ» (http://информатика.решуегэ.рф)
Вариант № 774026
1. За​да​ние 1 № 3669. Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит,
для не​ко​то​рых - из трех). Эти коды пред​став​л е​ны в таб​л и​це:
a
b
c
d
e
000
110
01
001
10
Опре​де​л и​те, какой набор букв за​ко​ди​ро​ван дво​ич​ной стро​кой 1100000100110
1) baade
2) badde
3) bacde
4) bacdb
По​яс​не​ние.
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова,
по​это​му од​но​знач​но можем рас​ко​ди​ро​вать со​о б​щ е​ние с на​ча​л а.
Разобьём код слева на​п ра​во по дан​ным таб​л и​цы и пе​ре​ведём его в буквы:
110 000 01 001 10 — b a c d e.
Пра​виль​ный ответ ука​зан под но​ме​ром 3.
Ответ: 3
02.03.2015
Стр. 1 из 17
Образовательный портал «РЕШУ ЕГЭ» (http://информатика.решуегэ.рф)
2. За​да​ние 2 № 4833. Дан фраг​мент таб​л и​цы ис​тин​но​сти вы​ра​же​ния F:
Каким вы​ра​же​ни​е м может быть F?
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
2) x1 ∨ ¬x2 ∨ x3 ∨¬x4 ∨ x5 ∨ ¬x6 ∨ x7
3) ¬x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
4) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7
По​яс​не​ние.
Проанализируем варианты ответов. Они представляют собой либо конъюнкцию, либо дизъюнкцию данных семи
пе​ре​мен​ных или про​ти​во​п о​л ож​ных к ним (если x1 — пе​ре​мен​ная, то про​ти​во​п о​л ож​ная к ней — это ¬x1).
Сна​ча​л а вы​я с​ним, яв​л я​е т​ся F конъ​юнк​ци​е й или дизъ​юнк​ци​е й.
Каковы бы ни были логические переменные х1, х2, ... х7 и отрицания к ним, их конъюнкция может быть равна 1
только в одном случае — когда все они равны 1. Из таблицы истинности следует, что функция F принимает значение
1 для двух различных наборов переменных и их отрицаний, поэтому F не может быть конъюнкцией. тем самым,
от​ве​ты 1 и 4 не под​хо​дят.
По​сле​до​ва​тель​но под​ста​вим 2 и 3 ва​ри​а н​ты от​ве​та.
Ва​ри​а нт 2 (дизъ​юнк​ция x1, x3, x5, x7, ¬x2, ¬x4, ¬x6):
В первой строке данной таблицы значение F равно 1. Это значит, что хотя бы одна переменная из x1, x3, x5, x7,
¬x2, ¬x4, ¬x6 должна быть равна 1, и такая есть — это х5. Значит, по первой строке вариант 2 удовлетворяет
функ​ции F.
Во второй строке данной таблицы значение F равно 1. Это значит, что хотя бы одна переменная из x1, x3, x5, x7,
¬x2, ¬x4, ¬x6 должна быть равна 1, и такая есть — это, например, х6. Значит, по второй строке вариант 2
удо​вле​тво​ря​е т функ​ции F.
В третьей строке данной таблицы значение F равно 0. Это значит, что все переменные x1, x3, x5, x7, ¬x2, ¬x4, ¬x6
должна быть равны 0. Так как в третьей строке переменные, около которых в варианте 2 стоит отрицание, равны 1, а
пе​ре​мен​ные без от​ри​ца​ния равны 0, то по тре​тьей стро​ке ва​ри​а нт 2 удо​вле​тво​ря​е т функ​ции F.
Ва​ри​а нт 2 удо​вле​тво​ря​е т функ​ции F по всем стро​кам таб​л и​цы.
Пра​виль​ный ответ — 2.
Ответ: 2
3. За​да​ние 3 № 1319. Для групповых операций с файлами используются маски имен файлов. Маска представляет
собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут
встре​чать​ся сле​ду​ю​щ ие сим​во​л ы:
сим​вол «?» (во​п ро​си​тель​ный знак) озна​ча​е т ровно один про​из​воль​ный сим​вол;
символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может
за​да​вать и пу​стую по​сле​до​ва​тель​ность. Опре​де​л и​те, какое из ука​зан​ных имен фай​л ов удо​вле​тво​ря​е т маске: pr*.*?s
1) prog.s
2) prog.pas
3) prs.sa
4) my_programma. pas
По​яс​не​ние.
Символ «?» означает ровно 1 произвольный символ ,значит, до «s» должен стоять хотя бы один символ, этому
усло​вию удо​вле​тво​ря​е т толь​ко ответ 2.
Ответ: 2
02.03.2015
Стр. 2 из 17
Образовательный портал «РЕШУ ЕГЭ» (http://информатика.решуегэ.рф)
4. За​да​ние 4 № 136. Дво​ич​ным эк​ви​ва​л ен​том де​ся​тич​но​го числа 99 яв​л я​е т​ся:
1) 1111111 2
2) 1101011 2
3) 1100011 2
4) 1010101 2
По​яс​не​ние.
Ответ: 3
5. За​да​ние 5 № 1020. Между четырьмя местными аэропортами: ПОЛЕВОЕ, СОКОЛИНОЕ, ГРИГОРЬЕВО и ЛИПКИ,
еже​днев​но вы​п ол​ня​ют​ся авиа​рей​сы. При​ведён фраг​мент рас​п и​са​ния перелётов между ними:
Путешественник оказался в аэропорту ПОЛЕВОЕ в полночь. Определите самое раннее время, когда он может
попасть в аэропорт ЛИПКИ. Считается, что путешественник успевает совершить пересадку в аэропорту, если между
вре​ме​нем при​л е​та в этот аэро​п орт и вре​ме​нем вы​л е​та про​хо​дит не менее часа.
1) 12:55
2) 13:35
3) 13:40
4) 14:00
По​яс​не​ние.
Ищем все ва​ри​а н​ты вы​л е​та из на​чаль​но​го пунк​та, рас​смат​ри​ва​е м пря​мые рейсы и с пе​ре​сад​ка​ми.
ПОЛЕВОЕ(10:30) - СОКОЛИНОЕ(11:20) => СОКОЛИНОЕ(12:10) - ЛИПКИ(13:55), на пересадку 50 минут, что
мень​ше часа.
ПО​ЛЕ​ВОЕ(11:00) - ГРИ​ГО​РЬЕ​ВО(11:45) => ГРИ​ГО​РЬЕ​ВО(12:55) - ЛИПКИ(13:35).
ПО​ЛЕ​ВОЕ(11:50) - ЛИПКИ(13:40).
Самое ранне время при​б ы​тия 13:35 минут.
Пра​виль​ный ответ ука​зан под но​ме​ром 2.
Ответ: 2
02.03.2015
Стр. 3 из 17
Образовательный портал «РЕШУ ЕГЭ» (http://информатика.решуегэ.рф)
6. За​да​ние 6 № 3726. Джентльмен пригласил даму в гости, но вместо кода цифрового замка своего подъезда
отправил ей такое сообщение: «В последовательности 52186 все четные цифры нужно разделить на 2, а из
нечетных вычесть 1. Затем удалить из полученной последовательности первую и последнюю цифры». Опре​де​л и​те
код циф​ро​во​го замка.
1) 104
2) 107
3) 218
4) 401
По​яс​не​ние.
Вы​п ол​ня​е м де​л е​ние чётных цифр:
2 / 2 = 1,
8 / 2 = 4,
6/ 2 = 3,
Вы​п ол​ня​е м вы​чи​та​ние из ис​ход​ных нечётных цифр:
5 - 1 = 4,
1 - 1 = 0.
Новое число 41043. Уби​ра​е м край​ние цифры и по​л у​ча​е м 104.
Пра​виль​ный ответ ука​зан под но​ме​ром 1.
Ответ: 1
7. За​да​ние 7 № 3492. В ячейке F7 электронной таблицы записана формула =D$12+$D13. Какой вид приобретет
фор​му​л а, после того как ячей​ку F7 ско​п и​ру​ют в ячей​ку G8?
При​ме ​ча ​ние: знак $ ис​п оль​зу​е т​ся для обо​зна​че​ния аб​со​л ют​ной ад​ре​са​ции.
1) =C$12+$D11
2) =D$11+$C13
3) =D$13+$E13
4) =E$12+$D14
По​яс​не​ние.
D$12: ме​ня​е т​ся стол​б ец и не ме​ня​е т​ся номер стро​ки.
$D13: стол​б ец не ме​ня​е т​ся, ме​ня​е т​ся номер стро​ки.
Номер столб​ца G боль​ше но​ме​ра столб​ца F на 1. Зна​чит стол​б ец D ста​нет столб​цом Е.
Номер стро​ки 8 на 1 боль​ше но​ме​ра стро​ки 7, зна​чит, стро​ка 13 ста​нет стро​кой 14.
Окон​ча​тель​ный вид =Е$12+$D14.
Пра​виль​ный ответ ука​зан под но​ме​ром 4.
Ответ: 4
02.03.2015
Стр. 4 из 17
Образовательный портал «РЕШУ ЕГЭ» (http://информатика.решуегэ.рф)
8. За​да​ние 8 № 6458. Определите число, которое будет напечатано в результате выполнения программы
(за​п и​сан​ной ниже на раз​ных язы​ках про​грам​ми​ро​ва​ния).
Бей​с ик
DIM N, S AS INTEGER
N = 20
S=0
WHILE S <= 257
S = S + 10
N=N+3
WEND
PRINT N
Си
#include
void main()
{
int n, s;
n = 20;
s = 0;
while (s <= 257)
{
s = s + 10;
n = n + 3;
}
printf("%d", n);
}
Пас​каль
var n, s: integer;
begin
n := 20;
s := 0;
while s <= 257 do
begin
s := s + 10;
n := n + 3
end;
write(n)
end.
Ал​го​рит​ми​че​с кий язык
алг
нач
цел n, s
n := 20
s := 0
нц пока s <= 257
s := s + 10
n := n + 3
кц
вывод n
кон
По​яс​не​ние.
Цикл while выполняется до тех пор, пока истинно условие s <= 257, т. е. переменная s определяет, сколько раз
вы​п ол​нит​ся цикл.
Заметим, что
На 26 шаге s станет равной 260 и условие s <= 257 окажется невыполненным, цикл
пре​рвет​ся. Сле​до​ва​тель​но, зна​че​ние n будет равно 20 + 26·3 = 98.
Ответ: 98.
Ответ: 98
02.03.2015
Стр. 5 из 17
Образовательный портал «РЕШУ ЕГЭ» (http://информатика.решуегэ.рф)
9. За​да​ние 9 № 2433. До​ку​мент объ​е ​мом 5 Мбайт можно пе​ре​дать с од​но​го ком​п ью​те​ра на дру​гой двумя спо​со​б а​ми:
А) Сжать ар​хи​ва​то​ром, пе​ре​дать архив по ка​на​л у связи, рас​п а​ко​вать.
Б) Пе​ре​дать по ка​на​л у связи без ис​п оль​зо​ва​ния ар​хи​ва​то​ра.
Какой спо​соб быст​рее и на​сколь​ко, если
– сред​няя ско​рость пе​ре​да​чи дан​ных по ка​на​л у связи со​став​л я​е т 2 18 бит в се​кун​ду,
– объем сжа​то​го ар​хи​ва​то​ром до​ку​мен​та равен 80% от ис​ход​но​го,
– время, тре​б у​е ​мое на сжа​тие до​ку​мен​та – 35 се​кунд, на рас​п а​ков​ку – 3 се​кун​ды?
В ответе напишите букву А, если способ А быстрее или Б, если быстрее способ Б. Сразу после буквы напишите
ко​л и​че​ство се​кунд, на​сколь​ко один спо​соб быст​рее дру​го​го.
Так, на​п ри​мер, если спо​соб Б быст​рее спо​со​б а А на 23 се​кун​ды, в от​ве​те нужно на​п и​сать Б23.
Слов «се​кунд», «сек.», «с.» к от​ве​ту до​б ав​л ять не нужно.
По​яс​не​ние.
Способ А. Общее время складывается из времени сжатия, распаковки и передачи. Время передачи t
рас​счи​ты​ва​е т​ся по фор​му​л е t = Q / q, где Q — объём ин​фор​ма​ции, q — cко​рость пе​ре​да​чи дан​ных.
Найдём сжа​тый объём: 5 * 0,8 = 4 Мбай​та
Пе​ре​ведём Q из Мбайт в биты: 4 Мбай​та = 4 * 2 20 байт = 4 * 2 23 бит.
Найдём общее время: t = 35 с + 3 с + 4 * 2 23 бит / 2 18 бит/с = 38 + 2 7 с = 166 с.
Спо​соб Б. Общее время сов​п а​да​е т с вре​ме​нем пе​ре​да​чи: t = 5 * 2 23 бит / 2 18 бит/с = 5 * 2 5 с = 160 с.
Видно, что спо​соб Б быст​рее на 166 - 160 = 6 с.
Ответ: Б6.
Ответ: Б6
10. За​да​ние 10 № 3567. Все 5-буквенные слова, составленные из букв Е, Ж, И, записаны в алфавитном порядке и
про​ну​ме​ро​ва​ны.
Вот на​ча​л о спис​ка:
1. ЕЕЕЕЕ
2. ЕЕЕЕЖ
3. ЕЕЕЕИ
4. ЕЕЕЖЕ
……
За​п и​ши​те слово, ко​то​рое стоит под но​ме​ром 238.
По​яс​не​ние.
Всего из трёх букв можно составить 3 5 = 243 слова. Очевидно, что последнее слово ИИИИИ. Тогда слово с
но​ме​ром 242 за​п и​шет​ся как ИИИИЖ, 241 — ИИИИЕ, 240 — ИИИЖИ, 239 — ИИИЖЖ, 238 — ИИИЖE,.
Ответ: ИИИЖE.
Ответ: ИИИЖЕ
11. За​да​ние 11 № 5650. Алгоритм вычисления
сле​ду​ю​щ и​ми со​о т​но​ше​ни​я ​ми:
значения
функции F(n),
где n — натуральное число, задан
F(n) = n + 1 при n ≤ 2;
F(n) = F(n − 1) + 2 · F(n − 2) при n > 2.
Чему равно зна​че​ние функ​ции F(4)? В от​ве ​те за ​пи​ши​те толь​ко на ​ту​р аль​ное число.
По​яс​не​ние.
По​сле​до​ва​тель​но на​хо​дим:
F(1) = 2;
F(2) =3;
F(3) = 3 + 4 = 7;
F(4) = 7 + 6 = 13;
Таким об​ра​зом, ответ F(4) = 13.
Ответ: 13
02.03.2015
Стр. 6 из 17
Образовательный портал «РЕШУ ЕГЭ» (http://информатика.решуегэ.рф)
12. За​да​ние 12 № 5655. В тер​ми​но​л о​гии сетей TCP/IP маской сети называется дво​ич​ное число, определяющее, какая
часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска
записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной
конъ​юнк​ции к за​дан​но​му IP-ад​ре​су узла и маске. По за​дан​ным IP-ад​ре​су узла и маске опре​де​л и​те адрес сети.
IP-адрес узла: 208.64.195.128
Маска: 255.255.224.0
П ри записи ответа выберите и з приведённых в таблице чисел четыре элемента IP-адреса сети и запишите в
нуж​ном по​ряд​ке со​о т​вет​ству​ю​щ ие им буквы без ис​п оль​зо​ва​ния точек.
A
B
C
D
E
F
G
H
0
64
128
192
195
208
224
255
При​мер. Пусть ис​ко ​мый IP-адрес: 192.168.128.0, и дана таб ​л и​ца:
A
B
C
D
E
F
G
H
128
168
255
8
127
0
17
192
В этом слу​чае пра ​виль​ный ответ будет за ​пи​сан в виде: HBAF.
По​яс​не​ние.
1. За​п и​шем числа маски сети в дво​ич​ной си​сте​ме счис​л е​ния.
2. Адрес сети получается в результате поразрядной конъюнкции чисел маски и чисел адреса узла (в двоичном
коде). Так как конъюнкция 0 с чем-либо всегда равна 0, то на тех местах, где числа маски равны 0, в адресе узла стоит
0. Аналогично, там, где числа маски равны 255, стоит само число, так как конъюнкция 1 с любым числом всегда равна
этому числу.
3. Рас​смот​рим конъ​юнк​цию числа 195 с чис​л ом 224.
Ре​зуль​та​том конъ​юнк​ции яв​л я​е т​ся число
.
4. Со​п о​ста​вим ва​ри​а н​ты от​ве​та по​л у​чив​шим​ся чис​л ам: 208, 64, 192, 0.
Таким об​ра​зом, ответ: FBDA.
Ответ: FBDA
02.03.2015
Стр. 7 из 17
Образовательный портал «РЕШУ ЕГЭ» (http://информатика.решуегэ.рф)
13. За​да​ние 13 № 6982. Автомобильный номер состоит из 6 символов. Допустимыми символами считаются 10 цифр и 8
заглавных букв: A, B, C, E, H, K, M и P. Для хранения каждого из 18 допустимых символов используется одинаковое и
наименьшее возможное количество бит. Для хранения каждого номера используется одинаковое и минимально
возможное количество байт. Сколько байт памяти потребуется для хранения 400 автомобильных номеров? Номера
хра​нят​ся без раз​де​л и​те​л ей.
1) 800
2) 1200
3) 1600
4) 2000
По​яс​не​ние.
Согласно условию, в номере могут быть использованы 18 символов. Известно, что с помощью N бит можно
закодировать 2 N различных вариантов. Поскольку 2 4 < 18 < 2 5 , то для записи каждого из 6 символов минимально
не​о б​хо​ди​мо 5 бит.
Для хранения всех 6 символов номера нужно 5 · 6 = 30 бит , а т.к. для записи используется целое число байт, то
берём ближайшее не меньшее значение, кратное восьми, это число 32 = 4 * 8 бит (4 байт). Тогда для записи 400
ав​то​мо​б иль​ных но​ме​ров не​о б​хо​ди​мо 4 · 400 = 1600 байт.
Пра​виль​ный ответ ука​зан под но​ме​ром 3.
Ответ: 3
14. За​да​ние 14 № 7622. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде
линии. Чертёжник может выполнять команду Сместиться на (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, –6)
По​вто​ри 3 раз
Ко​ман​да1 Сме​с тить​с я на (2, –5) Сме​с тить​с я на (3, 3)
конец
Какую команду надо выполнить Чертёжнику вместо команды Команда1, чтобы вернуться в исходную точку, из
ко​то​рой он начал дви​же​ние?
1) Сме​стить​ся на (–4, –4)
2) Сме​стить​ся на (–2, 8)
3) Сме​стить​ся на (4, –4)
4) Сме​стить​ся на (–4, 4)
По​яс​не​ние.
Сначала происходит смещение на (−3; −6). Команда По​вто​ри 3 раз означает, что команды Сместиться на (2, –5) и
Сместиться на (3, 3) выполнятся три раза. В результате Чертёжник переместится на (–3, –
6) + 3·(2 + 3, (−5) + 3) = (12, −12).
Чтобы Чертёжник вернулся в исходную точку, необходимо переместить его на (−12, 12). Учитывая, наличие
ко​ман​ды По​вто​ри 3, при​хо​дим к вы​во​ду, что Ко​ман​да 1 это ко​ман​да Сме​с тить​с я на (−4, 4).
Ответ: 4.
Ответ: 4
02.03.2015
Стр. 8 из 17
15. За​да​ние 15 № 3754. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно
двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в
город З?
По​яс​не​ние.
Начнем считать количество путей с конца маршрута – с города З. N X — количество различных путей из города А в
город X, N — общее число путей.
В "З" можно при​е ​хать из Е, Б, Д, Г или Ж, по​это​му N = N З = N Е + N Б + N Д + N Г + N Ж (1)
Ана​л о​гич​но:
N Е = N Б = 1;
N Б = N А = 1;
N Д = N Б + N Г = 1 + 2 = 3;
N Г = N А + N В = 1 + 1 = 2;
N Ж = N Г = 2.
N В = N А = 1.
Под​ста​вим в фор​му​л у (1):
N = N К = 1 + 1 + 3 + 2 + 2 = 9.
Ответ: 9
16. За​да​ние 16 № 2308. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 30,
за​п ись ко​то​рых в си​сте​ме счис​л е​ния с ос​но​ва​ни​е м 5 на​чи​на​е т​ся на 3?
По​яс​не​ние.
Сначала определим запись числа 29 в пятеричной системе.
ко​то​рых в пя​те​рич​ной си​сте​ме на​чи​на​е т​ся на 3: 3, 30, 31, 32, 33, 34.
Переведем их в десятичную систему счисления.
,
Ответ: 3,15,16,17,18,19
. Выпишем числа, меньшие
,
,
,
запись
,
17. За​да​ние 17 № 5219. В языке запросов поискового сервера для обозначения логической операции «ИЛИ»
ис​п оль​зу​е т​ся сим​вол «|», а для ло​ги​че​ской опе​ра​ции «И» - сим​вол «&».
В таб​л и​це при​ве​де​ны за​п ро​сы и ко​л и​че​ство най​ден​ных по ним стра​ниц не​ко​то​ро​го сег​мен​та сети Ин​тер​нет.
За​прос
Най​де​но стра​ниц
(в ты​с я​чах)
(Су​во​ров & Альпы) | (Су​во​ров & Вар​ша​ва)
1100
Су​во​ров & Вар​ша​ва
600
Су​во​ров & Вар​ша​ва & Альпы
50
Какое ко​л и​че​ство стра​ниц (в тыс.) будет най​де​но по за​п ро​су Су​во​ров & Альпы?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все
ис​ко​мые слова, не из​ме​нял​ся за время вы​п ол​не​ния за​п ро​сов.
По​яс​не​ние.
Ко​л и​че​ство за​п ро​сов в дан​ной об​л а​сти будем обо​зна​чать N i.
Наша цель — N 5 + N 6 .
Тогда из таб​л и​цы на​хо​дим, что:
N 4 + N 5 = 600,
N 5 = 50,
N 4 + N 5 + N 6 = 1100.
Из пер​во​го и вто​ро​го урав​не​ния: N 4 = 550.
Из по​след​не​го урав​не​ния: N 5 + N 6 = 550.
Ответ: 550
18. За​да​ние 18 № 7675. Эле​мен​та​ми мно​же​ства А яв​л я​ют​ся на​ту​раль​ные числа. Из​вест​но, что вы​ра​же​ние
(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {3, 6, 9, 12, 15}) ∧ ¬(x ∈ A)) → ¬(x ∈ {2, 4, 6, 8, 10, 12}))
истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное
зна​че​ние суммы эле​мен​тов мно​же​ства A.
По​яс​не​ние.
Вве​дем обо​зна​че​ния:
(x ∈ {2, 4, 6, 8, 10, 12}) ≡ P; (x ∈ {3, 6, 9, 12, 15}) ≡ Q; (x ∈ {2, 4, 6, 8, 10, 12}) ≡ R; (x ∈ A) ≡ A.
Пре​о б​ра​зо​вав, по​л у​ча​е м:
P → ((Q ∧ ¬A) → ¬R) = P → (¬(Q ∧ ¬А) ∨ ¬R) = ¬P ∨ (¬(Q ∧ ¬А) ∨ ¬R)
Логическое ИЛИ истинно, если истинно хотя бы одно утверждение. Выражения ¬P и ¬R истинны при всех
значениях x, кроме 2, 4, 6, 8, 10, 12. То есть выражение ¬(Q ∧ ¬А) должно быть истинно в этих точках. То есть Q ∧ ¬А
ложно в точках 2, 4, 6, 8, 10, 12. Учтём, что Q ≡ x ∈ {3, 6, 9, 12, 15}), следовательно, в отрицании промежутка А должны
от​сут​ство​вать точки 6 и 12. То есть ми​ни​маль​ный набор точек в про​ме​жут​ке А ≡ {6, 12}.
Сумма эле​мен​тов мно​же​ства А равна 18.
Ответ: 18.
Ответ: 18
19. За​да​ние 19 № 6804. В программе описан одномерный целочисленный массив с индексами от 0 до 9. Ниже
представлен записанный на разных языках программирования фрагмент одной и той же программы,
об​ра​б а​ты​ва​ю​щ ей дан​ный мас​сив.
Бей​с ик
n=9
FOR i = 0 TO n
K = A(i)
A(K) = 0
NEXT i
Си
n=9;
for (i = 0; i <= n; i++){
K = A[i];
A[K] = 0;
}
Пас​каль
n:=9;
for i:=0 to n do begin
K := A[i];
A[K] := 0;
end;
Ал​го​рит​ми​че​с кий язык
n:=10
нц для i от 0 до n
K := A[i]
A[K] := 0
кц
В на​ча​л е вы​п ол​не​ния этого фраг​мен​та в мас​си​ве на​хо​ди​л ись числа 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, т. е. A[0] = 9, A[1] = 8 и т.
д. Сколь​ко эле​мен​тов мас​си​ва после вы​п ол​не​ния про​грам​мы будут иметь не​ну​л е​вые зна​че​ния?
1) 5
2) 2
3) 3
4) 4
По​яс​не​ние.
Всего в массиве 10 элементов. В то время как значение переменной K изменяется от 9 до 6, элементы с седьмого
по девятый принимают значение 0. Когда i = 5, переменная K принимает значение 5, а пятый элемент обращается в
нуль. На всех последующих шагах цикла элементу A[0] присваивается значение 0. Таким образом, после выполнения
цикла че​ты​ре эле​мен​та будут иметь не​ну​л е​вые зна​че​ния: A[1], A[2], A[3], A[4].
Пра​виль​ный ответ ука​зан под но​ме​ром 4.
Ответ: 4
20. За​да​ние 20 № 7677. Ниже на пяти языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два
числа a и b. Ука​жи​те наи​мень​шее из таких чисел x, при вводе ко​то​ро​го ал​го​ритм пе​ча​та​е т сна​ча​л а 2, а потом 13.
Бей​с ик
DIM X, A, B AS INTEGER
INPUT X
A = 0: B = 0
WHILE X > 0
A = A+1
B = B + (X MOD 100)
X = X\100
WEND
PRINT A
PRINT B
Python
x = int(input())
a, b = 0, 0
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 := 0;
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:=0
нц пока x > 0
a := a+1
b := b+mod(x,100)
x := div(x,100)
кц
вывод a, нс, b
кон
Си
#include
void main()
{
int x, a, b;
scanf("%d", &x);
a = 0; b = 0;
while (x > 0) {
a = a+1;
b = b + (x%100);
x = x/100;
}
printf("%d\n%d", a, b);
}
По​яс​не​ние.
Рас​смот​рим цикл, число шагов ко​то​ро​го за​ви​сит от из​ме​не​ния пе​ре​мен​ной x:
while x > 0 do begin
...
x:= x div 100;
end;
Т. к. оператор div возвращает целую часть от деления, то при делении на 100 это равносильно отсечению
по​след​них двух цифр.
На каждом шаге от десятичной записи x отсекается две последних цифры до тех пор, пока все цифры не будут
отсечены, то есть x не станет равно 0. Для того, чтобы a стало равным 2, x должно быть трёхзначным или
четырёхзнач​ным.
Те​п ерь рас​смот​рим из​ме​не​ние b:
while x>0 do begin
b:=b+(x mod 100);
end;
Оператор mod возвращает остаток от деления, при делении на 100 это последние две цифры x. Разобьём 13 на
два сла​га​е ​мых так, чтобы можно было со​ста​вить трёхзнач​ное число: 13 = 1 +12. Ис​ко​мое число — 112.
Ответ: 112.
Ответ: 112
21. За​да​ние 21 № 3752. Определите, какое число будет напечатано в результате выполнения следующего
ал​го​рит​ма:
var a,b,t,M,R :integer;
Function F(x: integer):integer;
begin
F := -2*(x+2)*(x-6);
end;
BEGIN
a := -11; b := 11;
M := a; R := F(a);
t:=a;
while t < b do
begin
if (F(t)>=R) then
begin
M := t;
R := F(t);
end;
t:=t+2;
end;
write(M);
END.
По​яс​не​ние.
1. Ал​го​ритм ищет такое не​чет​ное t, при ко​то​ром F(t) при​ни​ма​е т наи​б оль​шее зна​че​ние на от​рез​ке от a до b.
2.
, график функции – парабола, ветви которой направлены вниз,
она при​ни​ма​е т наи​б оль​шее зна​че​ние в вер​ши​не или на одном из кон​цов от​рез​ка.
3. Най​дем абс​цис​су вер​ши​ны:
4. Так как t все​гда уве​л и​чи​ва​е т​ся на 2 (t:=t+2), оно все​гда остаётся нечётным. Най​ден​ная вер​ши​на — чётное число.
Сле​до​ва​тель​но, надо смот​реть бли​жай​шие нечётные зна​че​ния t: 1 и 3. F(1) = F(3).
Т. к. имеем усло​вие F(t) >= R, за​п о​ми​на​е т​ся номер по​след​не​го эле​мен​та, рав​но​го мак​си​му​му. Ответ: 3.
Ответ: 3
22. За​да​ние 22 № 6345. У ис​п ол​ни​те​л я Удво​и​тель две ко​ман​ды, ко​то​рым при​сво​е ​ны но​ме​ра:
1. при​бавь 1,
2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая удваивает его. Программа для Удвоителя — это
по​сле​до​ва​тель​ность ко​манд. Сколь​ко есть про​грамм, ко​то​рые число 2 пре​о б​ра​зу​ют в число 23?
По​яс​не​ние.
Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее
крат​ное 2, не пре​вос​хо​дя​щ ее n. Верны сле​ду​ю​щ ие со​о т​но​ше​ния:
1. Если n не делится на 2, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) —
при​б ав​л е​ни​е м еди​ниц.
2. Пусть n делится на 2. Тогда R(n) = R(n / 2) + R(n − 1) = R(n / 2) + R(n − 2) (если n > 2). Таким образом, достаточно
вы​чис​л ить зна​че​ния R(n) для всех чисел, крат​ных 2 и не пре​вос​хо​дя​щ их 23. Имеем:
R(2)= 1 = R(3),
R(4) = R(2) + R(3) = 1 + 1 = 2 = R(5),
R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),
R(8) = R(4) + R(7)= 2 + 3 = 5 = R(9),
R(10) = R(5) + R(9) = 2 + 5 = 7 = R(11),
R(12) = R(6) + R(11) = 3 + 7 = 10 = R(13),
R(14) = R(7) + R(13) = 3 + 10 = 13 = R(15),
R(16) = R(8) + R(15) = 5 + 13 = 18 = R(17),
R(18) = R(9) + R(17) = 5 + 18 = 23 = R(19),
R(20) = R(10) + R(19) = 7 + 23 = 30 = R(21),
R(22) = R(11) + R(21) = 7 + 30 = 37.
Ответ: 37.
Ответ: 37
23. За​да​ние 23 № 3590. A, B и С – целые числа, для ко​то​рых ис​тин​но вы​ска​зы​ва​ние
¬(А = B) ∧ ((B < A)→(2C > A)) ∧ ((A < B)→(A > 2C))
Чему равно A, если C = 8 и B = 18?.
По​яс​не​ние.
Ло​ги​че​ское "И" ис​тин​но тогда и толь​ко тогда, когда ис​тин​ны оба утвер​жде​ния.
1) ¬(А = B) = 1, то есть А ≠ 18 = 1.
2) ((B < A)→(2C > A)) При​ме​ним пре​о б​ра​зо​ва​ние им​п ли​ка​ции: (18 > A) ∨ (16 > A) = 1
3) (A < B)→(A > 2C) При​ме​ним пре​о б​ра​зо​ва​ние им​п ли​ка​ции: (A > 18) ∨ (A > 16) = 1
Из 2) и 3) сле​ду​е т, что (18 > A) и (A > 16), так как в про​тив​ном слу​чае воз​ни​ка​е т про​ти​во​ре​чие А = 17.
Ответ: 17
24. За​да​ние 24 № 6789. Требовалось написать программу, при выполнении которой с клавиатуры вводится
натуральное число, не превосходящее 10 8 , и выводится его первая (старшая) цифра. Ученик написал такую
про​грам​му:
Бей​с ик
DIM N AS LONG
INPUT N
WHILE N>10
N = N MOD 10
WEND
PRINT N
END
Си
#include
void main(){
long int n;
scanf("%ld",&n);
while (n>10) {
n = n%10;
}
printf("%ld", n);
}
Пас​каль
var n: longint;
begin
read(n);
while n>10 do begin
n := n mod 10
end;
write(n);
end.
Ал​го​рит​ми​че​с кий
алг
нач
цел n
ввод n
нц пока n>10
n := mod(n,10)
кц
вывод n
кон
По​сле​до​ва​тель​но вы​п ол​ни​те сле​ду​ю​щ ее.
1. На​п и​ши​те, что вы​ве​дет эта про​грам​ма при вводе числа 1984.
2. При​ве​ди​те при​мер числа, при вводе ко​то​ро​го про​грам​ма вы​даст вер​ный ответ.
3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в
которой она допущена, и приведите эту же строку в исправленном виде. Обратите внимание: вам нужно исправить
приведённую программу, а не написать свою. Вы можете только заменять ошибочные строки, но не можете удалять
строки или добавлять новые. Заменять следует только ошибочные строки: за исправления, внесённые в строки, не
со​дер​жа​щ ие оши​б ок, баллы будут сни​жать​ся.
По​яс​не​ние.
Эле​мен​ты от​ве​та:
1. При вводе числа 1984 программа выведет число 4. (Ком​мен​та ​р ий Приведённая программа выводит ответ 10
для n = 10 и по​след​нюю цифру для лю​б о​го дру​го​го зна​че​ния n.)
2. Пример числа, для которого программа даёт верный ответ: 2012. (Ком​мен​та ​р ий Программа даст верный ответ
для лю​б о​го числа, у ко​то​ро​го сов​п а​да​ют пер​вая и по​след​няя цифры. В част​но​сти, для лю​б о​го од​но​знач​но​го числа.)
3. Ошиб​ки со​дер​жат​ся в двух стро​ках про​грам​мы:
1) Не​вер​ное усло​вие цикла: не​ра​вен​ство долж​но быть не​стро​гим, иначе можно в ка​че​стве от​ве​та по​л у​чить 10.
2) Неверная операция отбрасывания последней цифры: вместо нахождения остатка нужно использовать
це​л о​чис​л ен​ное де​л е​ние.
При​мер ис​прав​ле​ния для языка Пас​каль:
Первая строка с ошибкой: while n>10 do begin. Исправленная строка: while n>=10 do begin. Другой способ
ис​п рав​л е​ния: while n>9 do begin
Вто​рая стро​ка с ошиб​кой: n := n mod 10. Ис​п рав​л ен​ная стро​ка: n := n div 10.
В про​грам​мах на дру​гих язы​ках оши​б оч​ные стро​ки и их ис​п рав​л е​ния ана​л о​гич​ны.
25. За​да​ние 25 № 2904. Опишите на русском языке или на одном из языков программирования алгоритм получения из
заданного целочисленного массива размером 30 элементов другого массива, который будет содержать модули
зна​че​ний эле​мен​тов пер​во​го мас​си​ва.
По​яс​не​ние.
Const N=30;
var a, b:array[1..N] of integer;
i: integer;
begin
for i:=1 to N do { ввод всех эле​мен​тов мас​си​ва с кла​ви​а ​ту​ры }
read(a[i]);
for i:=1 to N do { фор​ми​ро​ва​ние мас​си​ва B }
b[i]:= abs(a[i])
end.
26. За​да​ние 26 № 4884. Два игрока, Петя и Вася, играют в следующую игру. Перед ними лежат две кучки камней, в
первой из которых 2, а во второй — 1 камень. У каждого игрока неограниченно много камней. Игроки ходят по
очереди, первым ходит Петя. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или
добавляет 3 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 24
кам​ней. Кто вы​иг​ры​ва​е т при без​о ши​б оч​ной игре? Каким дол​жен быть пер​вый ход вы​иг​ры​ва​ю​щ е​го иг​ро​ка?
Ответ обос​нуй​те.
По​яс​не​ние.
Выигрывает Петя, своим первым ходом он должен увеличить в 3 раза количество камней во второй куче. Для
доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны
пары чисел, разделенные запятой. Эти числа соответствуют количеству камней на каждом этапе игры в первой и
вто​рой кучах со​о т​вет​ствен​но.
Таблица содержит все возможные варианты ходов Васи. Из неё видно, что при любом его ответе у Пети имеется
ход, при​во​дя​щ ий к по​б е​де.
27. За​да​ние 27 № 6824. Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит
конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а
оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных
конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не
записывает. Когда утренники закончились, Деду Морозу стало интересно, сколько различных чисел встречается в
записях Снегурочки. Дед Мороз и Снегурочка — волшебные, поэтому число утренников N, на которых они побывали,
может быть очень большим. Напишите программу, которая будет решать эту задачу. Перед текстом программы
крат​ко опи​ши​те ал​го​ритм ре​ше​ния за​да​чи и ука​жи​те ис​п оль​зу​е ​мый язык про​грам​ми​ро​ва​ния и его вер​сию.
Желательно, чтобы программа была эффективной как по времени работы, так и по используемой памяти.
Программу будем считать эффективной по памяти, если используемая память не зависит от размера входных
данных (то есть числа утренников). Программу будем считать эффективной по времени, если при увеличении
раз​ме​ра вход​ных дан​ных N в t раз (t — любое число) время её ра​б о​ты уве​л и​чи​ва​е т​ся не более чем в t раз.
Опи​с а​ние вход​ных дан​ных
В первой строке вводится одно целое положительное число — количество утренников N. Каждая из следующих
N строк содержит два целых числа: сначала D — количество пришедших на очередной утренник детей, а затем K –
ко​л и​че​ство кон​фет в мешке Деда Мо​ро​за на этом утрен​ни​ке. Га​ран​ти​ру​е т​ся вы​п ол​не​ние сле​ду​ю​щ их со​о т​но​ше​ний:
1 ≤ N ≤ 10000
1 ≤ D ≤ 100 (для каж​до​го D)
D ≤ K ≤ 1000 (для каж​дой пары D, K)
Опи​с а​ние вы​х од​ных дан​ных
Про​грам​ма долж​на вы​ве​сти одно число — ко​л и​че​ство раз​л ич​ных чисел в за​п и​сях Сне​гу​роч​ки. Если Сне​гу​роч​ка ни
разу ни​че​го не за​п и​сы​ва​л а, надо вы​ве​сти ноль.
При​мер вход​ных дан​ных:
7
10 58
15 315
20 408
100 1000
32 63
32 63
11 121
При​мер вы​х од​ных дан​ных для при​ведённого выше при​ме​ра вход​ных дан​ных:
2
По​яс​не​ние.
Поскольку количество детей не превышает 100, остаться может не больше 99 конфет. Можно создать массив из
99 элементов и использовать их в качестве счётчиков, хранящих информацию о количестве записей каждого числа.
Программа читает исходные данные, не запоминая их в массиве. Для каждой пары (D, K) количество оставшихся
конфет определяется как остаток от деления K на D. Если этот остаток положителен, надо увеличить
соответствующий счётчик. По окончании ввода и обработки данных надо подсчитать количество ненулевых
эле​мен​тов в мас​си​ве счётчи​ков.
При​мер пра​виль​ной и эф​фек​тив​ной про​грам​мы на языке Пас​каль
program c4;
const DMAX=100; {мак​си​маль​но воз​мож​ное ко​л и​че​ство
детей}
var
N: integer; {ко​л и​че​ство утрен​ни​ков}
D: integer; {ко​л и​че​ство детей на утрен​ни​ке}
K: integer; {ко​л и​че​ство кон​фет}
r: integer; {оста​ток}
c: array[1..DMAX-1] of integer; {счет​чи​ки остат​ков}
i: integer;
m: integer; {счет​чик раз​ных чисел в за​п и​сях}
begin
{пред​ва​ри​тель​ная очист​ка счет​чи​ков}
for i:=1 to DMAX-1 do c[i]:=0;
readln(N);
{ввод дан​ных, под​счет ко​л и​че​ства каж​до​го остат​ка}
for i:=1 to N do begin
readln(D, K);
r := K mod D;
if r>0 then c[r]:=c[r]+1;
end;
{под​счет ко​л и​че​ства раз​ных за​п и​сей}
m:=0;
for i:=1 to DMAX-1 do begin
if c[i]>0 then m:=m+1;
end;
writeln(m);
end.
Возможны другие варианты решения. Например, можно вместо массива целочисленных счетчиков использовать
массив данных логического типа, отмечающих только факт использования того или иного значения. Можно
подсчитывать итоговое значение непосредственно в процессе ввода данных, увеличивая величину m на 1 каждый
раз, когда встре​ча​е т​ся новое (не встре​чав​ше​е ​ся ранее) зна​че​ние остат​ка.
1/--страниц
Пожаловаться на содержимое документа