18.04.2022.
Тест. Информатика, 11 класс
Все тесты в этом разделе разработаны пользователями сайта для собственного
использования.
Администрация сайта не
проверяет возможные ошибки,
которые могут встретиться в тестах.
Данный тест проверяет знания учащихся по теме «Поиск путей в графе»
Задачи на количество маршрутов
Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.
Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.
Курьеру требуется проехать из A в Z, посетив не менее 6 населённых пунктов. Пункты A и Z при подсчёте учитываются, два раза проходить через один пункт нельзя. Какова наименьшая возможная длина маршрута курьера? В ответе запишите натуральное число – длину минимального маршрута.
Задание 3. Структурирование информации и поиск кратчайшего пути: Демонстрационный вариант ЕГЭ по информатике 2018; государственный выпускной экзамен 2018; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2018
3 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.
✍ Показать решение:
- Посчитаем сколько ребер у каждой вершины:
- Три ребра имеет только одна вершина — А, поэтому только А может соответствовать П3.
- Уникальное значение количества ребер имеет также вершина Д, — два ребра. В таблице вершине Д будет соответствовать П4.
- Вершины Г и В имеют по 4 ребра. Рассмотрим матрицу, в ней 4 числа соответствуют пунктам П2 и П5.
- В П5 на пересечении с П3 находится число .
Решение 3 задания ЕГЭ по информатике (11 вариант ГВЭ по информатике 2018 года):
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.
Решение 3 задания ЕГЭ по информатике (контрольный вариант № 1 экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков):
Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых приведена в таблице (если ячейка пуста — дороги нет).
Определите длину кратчайшего пути между пунктами A и F.
Решение 2* задания ЕГЭ по информатике 2018, вариант 10 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», С.С. Крылов, Т.Е. Чуркина):
Между населенными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяженность каждой дороги (отсутствие числа в таблице означает, что прямой дороги между пунктами нет).
Сколько существует таких маршрутов из A в Z, которые проходят через пять и более населенных пунктов? Пункты A и Z при подсчете учитывайте. Два раза проходить через один пункт нельзя.
* в новых учебниках задания 2 и 3 поменяли местами: теперь 2 — Поиск кратчайшего пути, а 3 — Алгебра логики
1-я тема характеризуется, как:
— задания базового уровня сложности,
— требуется использование специализированного программного обеспечения — нет,
— время выполнения – примерно 3 минуты,
— максимальный балл — 1
Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)
До ЕГЭ 2021 года — это было задание № 3 ЕГЭ
Решение 1 задания ЕГЭ по информатике (1_3):
Подобные задания для тренировки
📹 Видео
📹 Видеорешение на RuTube здесь
Решение 1 задания ЕГЭ по информатике:
Решение 2* задания ЕГЭ по информатике:
* в учебниках 2018 г задания 2 и 3 поменяли местами: теперь 2 — Поиск кратчайшего пути, а 3 — Алгебра логики
1 (3) задание:
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населенных пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова длина дороги из пункта Д в пункт К. В ответе запишите целое число — так, как оно указано в таблице.
- Рассмотрим граф и посчитаем количество ребер из каждой вершины:
- Мы выделили вершины, с уникальным числом ребер: 3 ребра соответствует только вершине Д, а 5 ребер соответствует только вершине К.
- Рассмотрим таблицу и найдем те строки или столбцы, в которых 5 значений и 3 значения: Это П2 и П4.
- Получаем П2 соответствует Д, а П4 соответствует К. На пересечении находится цифра 20.
Разбор 1 задания ЕГЭ:
На рисунке изображена схема дорог Н-ского района, в таблице звездочкой обозначено наличие дороги из одного населенного пункта в другой, отсутствие звездочки означает, что такой дороги нет. Каждому населенному пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер.
Определите, какие номера населенных пунктов в таблице могут соответствовать населенным пунктам D и E на схеме? В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
- Для начала найдем уникальные вершины — у которых уникальное число ребер: это A (2 ребра) и H (6 ребер). В таблице им соответствуют номера 3 и 4:
- По схеме находим, что смежными вершинами для A являются B и G. В таблице определяем соответствующие им цифры — 1 и 2. Поскольку по заданию они нас не интересуют, обозначим их вместе:
- У обеих вершин B и G смежными являются уже известные A и H и, кроме того, вершины F и C. По первому столбцу или первой строке находим, что F или C будет соответствовать цифра 7, а по второй строке — цифра 8. Обозначим их в таблице:
- В результате получаем, что искомым вершинам — D и E — соответствуют цифры 5 и 6. Поскольку не имеет значения, какой именно цифре должна соответствовать та или иная вершина, то в ответе просто запишем эти цифры в порядке возрастания.
Демонстрационный вариант ЕГЭ по информатике 2021 г. задания №1
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги
из пункта Г в пункт Ж. В ответе запишите целое число – так, как оно указано в таблице.
Демонстрационный вариант ЕГЭ 2019 г. – задание №3
На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам B и C на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Демонстрационный вариант ЕГЭ 2018 г. – задание №3
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация
населённых пунктов в таблице никак не связана с буквенными
обозначениями на графе. Определите, какова протяжённость дороги из
пункта Б в пункт В. В ответе запишите целое число – так, как оно указано в
таблице.
Демонстрационный вариант ЕГЭ 2017 г. – задание №3
https://www.youtube-nocookie.com/embed/YWFR5QgCE4g?wmode=transparent&iv_load_policy=3&autoplay=0&html5=1&showinfo=0&rel=0&modestbranding=1&playsinline=1&theme=light
Демонстрационный вариант ЕГЭ 2016 г. – задание №3
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.
КИМ ЕГЭ 2016 (досрочный период) – задание №3
Между населёнными пунктами А, Б, В, Г, Д, Е и К построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами А и К (при условии, что передвигаться можно только по построенным дорогам).
В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
Путешественник пришел в 07:00 на автостанцию поселка НОЯБРЬ и увидел следующее расписание автобусов:
Определите самое раннее время, когда путешественник сможет оказаться в пункте МАРТ согласно этому расписанию.
1) 07:40 2) 09:45 3) 10:20 4) 11:15
В одной сказочной стране всего 5 городов, которые соединены между собой непересекающимися магистралями. Расход топлива для каждого отрезка и цены на топливо приведены в таблице:
Проезд по магистралям возможен в обоих направлениях, однако в стране действует закон: выезжая из города А, путешественник обязан на весь ближайший отрезок до города Б закупить топливо по ценам, установленным в городе А. Определите самый дешевый маршрут из МУХА в ЖИРАФ.
1) МУХА – СЛОН – ЖИРАФ
2) МУХА – БЕГЕМОТ – ЖИРАФ
3) МУХА – КРОКОДИЛ – БЕГЕМОТ – ЖИРАФ
4) МУХА – КРОКОДИЛ – СЛОН – ЖИРАФ
Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт E (при условии, что передвигаться можно только по построенным дорогам).
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C и не проходящего через пункт B (при условии, что передвигаться можно только по построенным дорогам). Два раза проходить через один пункт нельзя.
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего маршрута между пунктами А и В. Передвигаться можно только по указанным дорогам.
Часть 1.
Ответами к заданиям 1–23 являются число или последовательность цифр. Запишите ответ справа от номера задания без пробелов, запятых и других дополнительных символов.
Между населёнными пунктами А, В, С, D, Е, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из А в С есть дорога протяженностью 3 км, а из С в А дороги нет.)
Сколько существует таких маршрутов из А в Z, которые проходят через шесть и более населённых пунктов? Пункты А и Z при подсчёте учитывайте. Два раза проходить через один пункт нельзя.
Дан фрагмент таблицы истинности выражения F.
Каким выражением может быть F?
1) (Z ~ Y) v (X v 1)
2) (Z ~ Y) ∧ (X ∧ 1)
3) (Z ~ Y) ∧ (X v 1)
4) (Z ~ Y) v (X ∧ 1)
Во фрагменте базы данных представлены сведения о сотрудниках университета. Структура университета такова, что весь институт разделён на факультеты, возглавляемые деканами; факультетам подчиняются кафедры, возглавляемые заведующими кафедрами; на каждой кафедре работают сотрудники (доценты, ассистенты и др.). Определите на основании приведённых данных фамилию и инициалы секретаря декана факультета, которому подчиняется кафедра, на которой работает ассистент Бездонный И. И.
1) Мужнина Д.Д.
2) Козлова В.Д.
3) Дарьян В.Д.
4) Хохлова К.Р.
У исполнителя Прибавлятеля-Умножателя две команды, которым присвоены номера:
1) прибавь 3,
2) умножь на х.
Первая из них увеличивает число на экране на 3, вторая умножает его на х. Программа для исполнителя — это последовательность номеров команд.
Известно, что программа 12112 преобразует число 3 в число 120.
Определите значение х, если известно, что оно натуральное.
Дан фрагмент электронной таблицы.
Какое целое число должно быть записано в ячейке С1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек А2:С2 соответствовала рисунку?
Известно, что все значения диапазона, по которым построена диаграмма, имеют один и тот же знак.
У Тани есть доступ к Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 218 бит в секунду. У Сергея нет скоростного доступа в Интернет, но есть возможность получать информацию от Тани по телефонному каналу со средней скоростью 212 бит в секунду. Сергей договорился с Таней, что та будет скачивать для него данные объёмом 5 Мбайт по высокоскоростному каналу и ретранслировать их Сергею по низкоскоростному каналу.
Компьютер Тани может начать ретрансляцию данных, не раньше чем им будут получены первые 512 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Таней данных до полного их получения Сергеем?
В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.
DIM k, s, d AS INTEGER
INPUT d
s = 0
к = 0
WHILE к < 100
s = s + 32
к = к + d
WEND
PRINT k
var k, s, d: integer;
begin
readln(d);
s : = 0;
k := 0;
while k < 100 do
begin
s : = s + 32;
k : = k + d ; end;
write (k); end.
нач
цел k, s, d
ввод d
s : = 0
k := 0
нц пока k < 100
s := s + 32
k := k + d
кц
вывод k
кон
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А — 0; Б — 1101; В — 11001; Г — 11000; Д — 10.
Укажите, каким кодовым словом должна быть закодирована буква Е. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Пусть искомый IP-aдpec — 192.168.128.0 и дана таблица.
В этом случае правильный ответ будет записан в виде HBAF.
Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля — ровно 10 символов. В качестве символов используются десятичные цифры и 9 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и прописные (регистр буквы имеет значение!).
Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объём памяти (в байтах), который занимает хранение 50 паролей. В ответе укажите только число.
Определите значение переменной с после выполнения следующего фрагмента программы (записанного ниже на разных языках программирования).
На рисунке приведена схема соединения компьютеров А, Б, В, Г, Д, Е, Ж, И, К в локальную сеть. Администратор настроил эту сеть так, что передача данных от компьютера к компьютеру возможна только в направлениях, указанных на рисунке стрелками. Сколько существует различных способов пересылки файла с компьютера А на компьютер К?
Запись числа 3110 в системе счисления с основанием N оканчивается на 1 и содержит 4 цифры. Чему равно основание этой системы счисления N?
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Компьютер печатает количество страниц (в тысячах), которое будет найдено по следующему запросу:
Укажите целое число, которое напечатает компьютер. Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Укажите наибольшую возможную длину промежутка А, для которого формула
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
В программе описан одномерный целочисленный массив с индексами от 0 до 10. Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы, обрабатывающей данный массив.
s = 1
n = 10
FOR i = 1 ТО 5
s = s * A(i) * A(n — i + 1)
NEXT i
В начале выполнения этого фрагмента в массиве находились однозначные чётные натуральные числа. Какое наименьшее значение может иметь переменная s после выполнения данной программы?
Ниже на четырёх языках записан алгоритм. Получив на вход число х, этот алгоритм печатает два числа: L и М. Укажите наибольшее из таких чисел х, при вводе которых алгоритм печатает сначала 3, а потом 0.
Определите, какое целое значение Н нужно ввести, чтобы число, напечатанное в результате выполнения следующего алгоритма, было наименьшим. Если таких значений несколько, то в ответ запишите максимальное из них. Для удобства алгоритм представлен на четырёх языках программирования.
DIM А, В, Т, М, R, Н AS INTEGER
INPUT Н
А = 10: В = 80
М = A: R = F (Н, А)
FOR Т = А ТО В
IF F(H, Т) < R THEN
М = Т
R = F(H, Т)
END IF
NEXT T
PRINT М
FUNCTION F(Н, х)
F = (х — 30) * (х — H)
END FUNCTION
var a, b, t, M, R, H: integer;
function F(H, x: integer): integer;
begin
F := (x — 30) * (x — H) ;
end;
begin
readln(H);
a := 10; b := 80;
M := a; R := F(H, a);
for t := a to b do begin
if (F(H, t) < R) then begin
M := t;
R := F(H, t)
end
end;
write(M)
end.
нач
цел а, b, t, R, М, Н
ввод Н
а := 10; b := 80
М := a; R := F (Н, а)
нц для t от а до b
если F(H, t) < R
то
М := t; R := F(H, t)
все
кц
вывод М
кон
алг цел F(цел Н, х)
нач
знач := (х — 30) * (х — Н)
кон
У исполнителя Увеличитель две команды, которым присвоены номера:
1) прибавь 1,
2) умножь на 2.
Первая из них увеличивает число на экране на 1, вторая умножает его на 2. Программа для Увеличителя — это последовательность команд.
Сколько есть программ, которые число 2 преобразуют в число 13?
(x10 ~ x1) v x1= 0
Часть 2.
Запишите сначала номер задания (24, 27 и т. д.), затем полное решение. Ответы записывайте чётко и разборчиво.
Требовалось написать программу, при выполнении которой с клавиатуры считывается натуральное число N, не превосходящее 109, и выводится произведение цифр этого числа. Программист торопился и написал программу неправильно. (Ниже для Вашего удобства программа представлена на четырёх языках программирования.)
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе числа 133.
2. Найдите все ошибки в этой программе (их может быть одна или несколько). Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, — приведите правильный вариант строки.
Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.
Содержание верного ответа
Решение использует запись программы на Паскале. Допускается использование программы на трёх других языках программирования.
1. Программа выведет число 7.
2. Первая ошибка. Неверная инициализация ответа (переменная product).
Строка с ошибкой:
3. Вторая ошибка. Вместо умножения в цикле производится сложение.
product := product + digit;
product : = product*digit;
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от —1000 до 1000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальное значение среди положительных элементов массива, не оканчивающихся на 5. Если в исходном массиве нет элемента, значение которого положительно и не оканчивается цифрой 5, то вывести сообщение «Не найдено».
Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.
Объявляем массив А из 30 элементов.
Объявляем целочисленные переменные I, J, MAX.
В цикле от 1 до 30 вводим элементы массива А с 1-го по 30-й
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
На языке Паскаль
На алгоритмическом языке
На языке Бейсик
На языке Си
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два или четыре камня или увеличить количество камней в куче в два раза. Например, имея кучу из 10 камней, за один ход можно получить кучу из 12, 14 или 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 62 или больше камней.
В начальный момент в куче было S камней, 2 ≤ S ≤ 60, S чётное.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.
Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах — количество камней в куче.
При значениях S, меньших 32, за один ход нельзя получить кучу, количество камней в которой будет не менее 62.
б) Ваня может выиграть первым ходом (при любой игре Пети), если S = 30. Тогда после первого хода Пети в куче будет 32, 34 или 60 камней. После этого Ваня увеличивает количество камней в два раза и выигрывает в один ход.
При S = 26 или S = 28 у Пети есть выигрышная стратегия, позволяющая ему выиграть своим вторым ходом. В этих случаях Петя не может выиграть первым ходом (см. п. 1а)). Однако он может получить кучу из 30 камней, добавив в кучу два камня (при S = 28) или четыре камня (при S = 26). После этого хода Петя попадает в ситуацию, разобранную в п. 16) для Вани, то есть у игрока, делающего следующий ход (у Вани), нет хода, сразу приводящего его к выигрышу, а у Пети выигрышный ход «удвоить количество камней» есть независимо от того, какой ход сделал Ваня.
При S = 24 у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом. После первого хода Пети в куче будет 26, 28 или 48 камней. Если в куче станет 48 камней, то Ваня увеличит количество камней в два раза и выиграет своим первым ходом. Если после первого хода Пети в куче оказалось 26 или 28 камней, то Ваня попадает в ситуацию, разобранную в п. 2 для Пети и у него есть выигрышная стратегия, позволяющая ему выиграть своим вторым ходом.
В таблице представлено дерево возможных партий при описанной выигрышной стратегии Вани. На рисунке это же дерево изображено в графическом виде. Заключительные позиции, в которых выигрывает Ваня, подчёркнуты. Приведены все возможные ходы Пети и ходы, отвечающие выигрышной стратегии Вани.
От цифровых датчиков в компьютер поступает информация о характеристиках физического процесса. Результатом каждого измерения является неотрицательное целое число.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет выводить третье по величине (считая от максимума) значение измерения. Если несколько измерений имеют одинаковые значения, то они учитываются как одно измерение. Если искомого значения не существует (например, когда все значения измерений равны), то нужно вывести символ «#». Следует учитывать, что количество измерений может быть очень велико.
Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
Программа последовательно читает значения измерений, обновляя при необходимости три наибольших значения. После цикла печатается результат.
Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведёны примеры решения задания на языках Паскаль, Бейсик и алгоритмическом языке. Допускаются решения, записанные на других языках программирования
Пример правильной и эффективной программы на языке Бейсик
Пример правильной и эффективной программы на языке Паскаль
Список вопросов теста
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М?
Вопрос 2
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов из А в З, проходящих через город Е?
Вопрос 3
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов из А в H, которые проходят через пункт С или пункт L?
Вопрос 4
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.
Вопрос 5
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Н, проходящих через пункт Г?
Вопрос 6
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, С, Х, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Т?
