Задание 17 из ЕГЭ по информатике
Русский язык Математика (профильная) Обществознание Физика История Биология Химия Английский язык Информатика Литература
Задания Варианты Теория
Задание 1 Задание 2 Задание 3 Задание 4 Задание 5 Задание 6 Задание 7 Задание 8 Задание 9 Задание 10 Задание 11 Задание 12 Задание 13 Задание 14 Задание 15 Задание 16 Задание 17 Задание 18 Задание 19 Задание 20 Задание 21 Задание 22 Задание 23 Задание 24 Задание 25 Задание 26 Задание 27
Бесплатный интенсив по информатике
3 огненных вебинара, домашние задания, беседа курса, личный кабинет, связь с преподавателем и многое другое.
Курс стартует 24 января.
Подробнее об интенсиве
За это задание вы можете получить 1 балл на ЕГЭ в 2023 году
Разбор сложных заданий в тг-канале:
Посмотреть
Задача 1ДЛЯ 2022
В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от 1 до 100 000 включительно. Определите количество пар послед…
Задача 2
В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –10 000 до 10 000 включительно. Определите количество пар последова…
Задача 3
В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –10 000 до 10 000 включительно. Определите количество пар последова…
Задача 4
В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –10 000 до 10 000 включительно. Определите количество пар последова…
Задача 5
В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от -10 000 до 10 000 включительно. Определите количество пар, в которы…
Задача 6
В файле содержится последовательность целых чисел. Элементы принимают целые значения от -10000 до 10000 включительно. Определите и запишите в ответе два значения:
1) Количество па…
Задача 7
В файле содержится последовательность целых чисел. Элементы принимают целые значения от -10000 до 10000 включительно. Определите и запишите в ответе два значения:
1) Количество па…
Задача 8
В файле содержится последовательность целых чисел. Элементы принимают целые значения от -10000 до 10000 включительно. Определите и запишите в ответе два значения:
1) Количество па…
Задача 9
В файле содержится последовательность целых чисел. Элементы принимают целые значения от -10000 до 10000 включительно. Определите и запишите в ответе два значения:
1) Количество па…
Задача 10
В файле содержится последовательность целых чисел. Элементы принимают целые значения от -10000 до 10000 включительно. Определите и запишите в ответе два значения:
1) Количество па…
Задача 11
В файле содержится последовательность целых чисел. Элементы принимают целые значения от -10000 до 10000 включительно. Определите и запишите в ответе два значения:
1) Количество па…
Задача 12
В файле содержится последовательность целых чисел. Элементы принимают целые значения от -10000 до 10000 включительно. Определите и запишите в ответе два значения:
1) Количество па…
Задача 13
В файле содержится последовательность целых чисел. Элементы принимают целые значения от 1 до 10000 включительно. Определите количество чисел и минимальное число, которые делятся на…
Задача 14
В файле содержится последовательность целых чисел. Элементы принимают целые значения от 1 до 10000 включительно. Определите количество чисел и минимальное число, которые делятся на…
Задача 15
В файле содержится последовательность целых чисел. Элементы принимают целые значения от 1 до 10000 включительно. Определите количество чисел и минимальное число, которые делятся на…
Задача 16
В файле содержится последовательность целых чисел. Элементы принимают целые значения от 1 до 10000 включительно. Определите количество чисел и минимальное число, которые делятся на…
Задача 17
В файле содержится последовательность целых чисел. Элементы принимают целые значения от 1 до 10000 включительно. Определите количество чисел и наибольшее число, которые делятся на …
Задача 18
В файле содержится последовательность целых чисел. Элементы принимают целые значения от 1 до 10000 включительно. Определите количество чисел и наибольшее число, которые делятся на …
Задача 19
В файле содержится последовательность целых чисел. Элементы принимают целые значения от 1 до 10000 включительно. Определите количество чисел и наибольшее число, которые делятся на …
Задача 20
В файле содержится последовательность целых чисел. Элементы принимают целые значения от 1 до 10000 включительно. Определите количество чисел и наибольшее число, которые делятся на …
1 2 3
Задача номер семнадцать в КИМе по информатике является первой, для решения которой вам придется программировать. Составители проверяют ваши умения и знания при обработке числовой последовательности. Решать ее можно несколькими способами. Так как в КЕГЭ нет задач, где требуется развернутый ответ, вы можете писать код на любом языке, который разрешен кодификатором, к примеру, c++ или python. Это достаточно легкий номер, и за правильный ответ вам дается один балл. Советуют тратить на него около пяти минут, поэтому хорошо подготовьтесь.
Формулировка для семнадцатого номера вариативна — вам дается текстовый файл, в котором находится последовательность чисел. В условии будет написано, что требуется найти. Обычно составители просят найти пару элементов, сумма или произведение которых делится на какое-то число. Вариантов формулировки огромное количество, но после решения пары десятков таких задач, вы сможете быстро придумывать условия, по которым код даст вам нужный ответ.
17 задание достаточно легкое, но главное в подготовке именно наработать навык. Теории к нему хоть и немного, но хорошие математические знания вам помогут невероятно сильно, поэтому улучшайте не только уровень программирования, но и навык в математике.
Теория к заданию 17 по информатике: Поисковые системы. Круги Эйлера
<< Задание 16
Задание 18 >>
Популярные материалы
Эйлеровы круги (круги Эйлера). презентация к уроку по информатике и икт (8 класс) на тему
Круги Эйлера
О графическом способе решения задач
на отношение понятий (множеств)
Отношения между понятиями по объему:
1. Тождество или совпадение объемов.
A – столица России
B – город Москва
Отношения между понятиями по объему:
2. Подчинение или включение объемов.
B – живое существо
Отношения между понятиями по объему:
3. Исключение объемов.
B – человек
Отношения между понятиями по объему:
4. Пересечение или частичное совпадение объемов.
A – школьник
B – первоклассник
Определите отношения между понятиями и изобразите эти отношения с помощью кругов Эйлера: сказка, книга, фантастика, «Репка», стихи
Решение
книга
фантастика
сказка
«Репка»
стихи
Задачи
1. В классе 30 учащихся. Из них 18 человек занимаются в секции легкой атлетики, 10 – плаванием, 3 – и тем, и другим. Сколько человек не занимается ничем?
2. Ребята посещают три кружка: биологии, физики и истории. Решено было организовать кружок юных экологов и пригласить тех ребят, которые не занимаются ни в одном из трех перечисленных. Сколько таких ребят, если всего в классе 36 человек, биологией занимаются 18, физикой – 14, историей – 10. Двое посещают все три кружка, 8 – биологию и физику, 5 – биологию и историю, 3 – историю и физику.
Решить задачи с помощью кругов Эйлера .
Домашнее задание:
№ 1
В классе 35 учеников. 20 из них занимаются в математическом кружке, 11 — в биологическом, а 10 ничем не занимаются. Сколько ребят занимаются и математикой, и биологией?
№ 2
Большая группа туристов выехала в заграничное турне. Из них владеет английским языком 28 человек, французским — 13, немецким — 10, английским и французским — 8, французским и немецким — 5, английским и немецким — 6, всеми тремя языками — двое, а 41 человек не владеет ни одним из трёх языков. Сколько всего туристов?
Решение задачи №1
30 — ( 7 + 3 + 15 ) = 5
легкая атлетика
плавание и
легкая атлетика
плавание
Решение задачи №2
7 + 3 + 4 +
36 – 28 = 8
биология
28 учащихся посещают хотя бы 1 кружок, следовательно, 8 – не посещают ни один кружок.
1 слайд
2 слайд
3 слайд
Один из величайших математиков петербургский академик, за свою долгую жизнь он написал более 850 научных работ. В одной из них появились эти круги. Эйлер писал, что «они очень подходят для того, чтобы облегчит наши размышления». Леонардо Эйлер 1707-1783
4 слайд
Задача №1 В классе 35 учеников. Из них 20 занимаются в математическом кружке, 11 – в биологическом, 10 ребят не посещают эти кружки. Сколько биологов увлекаются математикой?
5 слайд
Решение (По рисунку) в левом кругу (М) помещены все математики, а в правом – все биологи, те ребята, которые не ходят на кружки и помещены они в самый большой круг. Теперь посчитаем: Внутри большого круга 35 ребят. Внутри 2-х меньших 35-10=25 ребят. Внутри М находятся 20 ребят. Внутри Б находятся 25-20=5 биологов (не посещающих математический кружок) Внутри МБ находятся 11-5=6 биологов увлекающиеся математикой. М Б МБ
6 слайд
Задача №2 В пионерском лагере 70 ребят. Из них 27 занимаются в драмкружке, 32 поют в хоре, 22 увлекаются спортом. В драмкружке 10 ребят из хора, в хоре 10 спортсменов; 3 спортсмена посещают и драмкружок, и хор. Сколько ребят не поют в хоре, не увлекаются спортом и не занимаются в драмкружке? Сколько ребят заняты только спортом?
7 слайд
Решение (По рисунку) Д – драмкружок, Х – хор, С – спортсмены. 5+3+3=11спортсменов посещают хор и драмкружок тогда 22-11=11 увлекаются только спортом 70-12-7-19-5-3-3-11=10 ребят не поют в хоре, не увлекаются спортом и не занимаются в драмкружке. 2. А В С 5-1-0,5-1=2,5 4-1-0,5-1=1,5 3-1-0,5-1=0,5 1 1 АВС 0,5
10 слайд
Задача №4 В классе 38 человек. Из них 16 играют в баскетбол, 17 – в хоккей, 18 – в волейбол. Увлекаются двумя видами спорта — баскетболом и хоккеем – четверо, баскетболом и волейболом – трое, волейболом и хоккеем – пятеро. Трое не увлекаются ни баскетболом, ни волейболом, ни хоккеем. Сколько ребят увлекается одновременно тремя видами спорта? Сколько ребят увлекается лишь одним из этих видов спорта?
Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
ЛЕОНАРД ЭЙЛЕР ИДЕАЛЬНЫЙ МАТЕМАТИК XVIII ВЕКА, который ввел понятие объединения и пересечения множеств
Эйлер писал, что «круги очень подходят для того, чтобы облегчить наши размышления». При решении целого ряда задач Леонард Эйлер использовал идею изображения множеств с помощью кругов и они получили название «круги Эйлера».
Круги Эйлера Эйлеровы круги — принятый в логике способ моделирования, наглядного изображения отношений между объемами понятий с помощью кругов.
Смысл логических связок становится более понятным, если проиллюстрировать их с помощью кругов Эйлера Круги Эйлера Круги Эйлера – это геометрическая схема, которая помогает находить и/или делать более наглядными логические связи между явлениями и понятиями. А также помогает изобразить отношения между каким-либо множеством и его частью. Школа 5-ые классы 9-ые классы 9 «А» класс Круги Эйлера – это тот метод, который наглядно демонстри-рует: лучше один раз увидеть, чем сто раз услышать. Его заслуга в том, что наглядность упрощает рассуждения и помогает быстрее и проще получить ответ. Метод Эйлера является незаменимым при решении некоторых задач.
Задача 1. «Обитаемый остров» и «Стиляги» Некоторые ребята из нашего класса любят ходить в кино. Известно, что 15 ребят смотрели фильм «Обитаемый остров » 11 человек смотрели фильм «Стиляги», из них 6 смотрели и «Обитаемый остров», и «Стиляги». Сколько человек смотрели только фильм «Стиляги»?
Решение: Чертим два множества таким образом: 6 «Стиляги» «Обитаемый остров» 6 человек, которые смотрели фильмы «Обитаемый остров» и «Стиляги», помещаем в пересечение множеств. 15 – 6 = 9 – человек, которые смотрели только «Обитаемый остров». 11 – 6 = 5 – человек, которые смотрели только «Стиляги». Получаем: «Стиляги» «Обитаемый остров» 9 5 6 Ответ: 5 человек смотрели только «Стиляги».
Задача 2. «Гарри Поттер, Рон и Гермиона » На полке стояло 26 волшебных книг по заклинаниям, все они были прочитаны. Из них 4 прочитал и Гарри Поттер, и Рон. Гермиона прочитала 7 книг, которых не читали ни Гарри Поттер, ни Рон, и две книги, которые читал Гарри Поттер. Всего Гарри Поттер прочитал 11 к ниг. Сколько книг прочитал только Рон?
Учитывая условия задачи, чертеж будет таков: Решение: 4 2 7 Гермиона Рон Гарри Поттер Так как Гарри Поттер всего прочитал 11 книг, из них 4 книги читал Рон и 2 книги – Гермиона, то 11 – 4 – 2 = 5 – книг прочитал только Гарри. Следовательно, 26 – 7 – 2 – 5 – 4 = 8 – книг прочитал только Рон. Ответ. 8 книг прочитал только Рон. 11 8
ВЫВОД: Применение кругов Эйлера (диаграмм Эйлера-Венна) позволяет легко решить задачи, которые обычным путем разрешимы лишь при составлении системы трех уравнений с тремя неизвестными
Источники информации: http:// f1. mylove.ru/0AkEJdLeQl.jpg http:// logika.vobrazovanie.ru/index.php?link=kr_e.html http:// inf.reshuege.ru/test?theme=256
Вычислите значение выражения. Ничего не сказала рыбка, лишь хвостом по воде плеснула и ушла в глубокое море. Сказка о мертвой царевне и семи богатырях. Из какой сказки этот отрывок. Сказка о золотом петушке. Сказка о царе Салтане. К 213–летию со дня рождения А.С.Пушкина. Выполните действия, результаты найдите в таблице и отгадайте зашифрованные слова. Найдите значение выражения. Устная работа. Ответы уравнений в конкурсе «Рыбалка».
«Координаты точек на координатной плоскости» — Карл Гаусс. Тренажер. Выбери нужную ячейку таблицы. Абсцисса точки. Учебники. Координатная плоскость. Координаты точки. Николай Иванович Лобачевский. Объяснение нового материала. Цвет. Леонард Эйлер. Исаак Ньютон. Четверть. Готфрид Лейбниц. Координата. Курсор. Координатная четверть. Точка лежит на оси Х. Великие математики. Тест. Технические рекомендации. Отметьте точку. Рене Декарт. Блез Паскаль.
«Приемы устного умножения» — Умножение и деление на 25 и 75. Значимость устных приёмов умножения. Умножение чисел, оканчивающихся на 1. Устные приёмы умножения двузначных натуральных чисел. Умножение чисел, близких к 100. Умножение двузначных чисел, у которых цифры десятков одинаковые. Умножение на 11. Умножение двузначных чисел, у которых сумма цифр десятков равна. Умножение чисел, оканчивающихся на 5. Умножение на число, оканчивающиеся на 5.
«Дни недели» — Воскресенье — день Солнца (старое название – неделя). Понедельник. Воскресенье -день Солнца. У славян неделя называлась седмица. Суббота – день Сатурна. Гипотеза. Среда. Названия дней недели в русском и английском языках. Загадка. Библия говорит, что семидневная неделя создана Богом. Как появились 7 дней недели. Среда день Меркурия (среда – середина). Неделя днями красна. Конёк – Горбунок. Четверг – день Юпитера (четвёртый).
«Путешествие в мир математики» — Остров « Умейка». Решить с помощью координатной прямой. Измерим температуру за бортом корабля. Прибавить к числу А число В — значит изменить число А на число В. Сумма двух противоположных чисел равна нулю. Остров « Повторика». Найдём сумму чисел. Результаты двух последовательных изменений находят с помощью сложения. Найдём сумму чисел. Показания приборов на корабле. Любое число от прибавления положительного числа увеличивается.
«Десятичная система и двоичная» — Перевод целых десятичных чисел в двоичную систему счисления. Перевод целых чисел из двоичной системы счисления в десятичную. Ей было 1100 лет, она в 101 класс ходила. Калькулятор. Какую цель перед собой мы ставили в начале первого урока. Переведите числа из двоичной системы счисления в десятичную. «Рождение» цветка. Необычное стихотворение. Закрасьте клеточки. Разделить целое десятичное число на 2.
«Письма о разных физических и философических материях, написанные к некоторой немецкой принцессе…», где появились впервые «круги Эйлера» «Письма о разных физических и философических материях, написанные к некоторой немецкой принцессе. ..», где появились впервые «круги Эйлера»
Решение задач с помощью кругов Эйлера. Часть жителей нашего города умеет говорить только по-русски, часть – только по- башкирски и часть умеет говорить на обоих языках. По- башкирски говорят 85%, по-русски 75%. Сколько процентов жителей говорят на обоих языках?
Спортивная задача В футбольной команде «Баймак» 30 игроков: 18 нападающих. 11 полузащитников, 17 защитников Вратари 3 могут быть нападающими и защитниками, 10 защитниками и полузащитниками, 6 нападающими и защитниками 1 и нападающим, и защитником, и полузащитником. Вратари не заменимы. Сколько в команде «Баймак» вратарей?
Решение =28 (игроков) на этой диаграмме. Но в команде всего 30 футболистов. Значит вратарей будет 30-28=2. Ответ: 2 вратаря.
«Озеро Графское» Из 100 отдыхающих на турбазе «Графское», 30 детей — отличники учебы, 28 — участники олимпиад, 42 — спортсмены. 8 учащихся одновременно участники олимпиад и спортсмены, 10 – участники олимпиад и отличники, 5 – спортсмены и отличники учебы, 3 – и отличники, и участники олимпиад, и спортсмены. Сколько отдыхающих не относятся ни к одной из групп?
Выводы Применение кругов Эйлера (диаграмм Эйлера-Венна) позволяет легко решить задачи, которые обычным путем разрешимы лишь при составлении системы трех уравнений с тремя неизвестными. Применение кругов Эйлера (диаграмм Эйлера-Венна) позволяет легко решить задачи, которые обычным путем разрешимы лишь при составлении системы трех уравнений с тремя неизвестными.
Формула Эйлера — GeeksforGeeks
Формула Эйлера занимает видное место в области математики. Это помогает установить существенную связь между тригонометрическими функциями и сложными экспоненциальными функциями. Это важная формула, используемая для решения сложных экспоненциальных функций. Оно также известно как тождество Эйлера. Он имеет множество применений в комплексном анализе и используется для нахождения количества вершин и граней многогранника.
Формула для комплексного анализа
Формула комплексного анализа дает нам способ выразить мнимую степень экспоненциальных функций в виде тригонометрических соотношений. Его формула может быть связана с комплексной плоскостью, где единичная комплексная функция e ix очерчивает единичный круг, так что x — действительное число, измеряемое в радианах.
e ix = cos x + i sin x
где
x — действительное число,
e — основание логарифма,
sin x и cos x — тригонометрические функции,
i — мнимая часть.
Выражение cos x + i sin x также известно как полярная форма комплексного числа.
Вывод
Рассмотрим разложение экспоненциальной функции e x .
е х = 1 + х + х 2 /2! + х 3 /3! + х 4 /4! + …….. + ∞
Подставляя x вместо ix, получаем
e ix = 1 + ix + (ix) 2 /2! + (ix) 3 /3! + (ix) 4 /4! + …….
. + ∞
Используя свойство i 2 = -1 получаем,
= 1 + ix – x 2 /2! — ix 3 /3! + х 4 /4! + …….. + ∞
= (1 – х 2 /2! + х 4 /4! – …….. + ∞) + i (х – х 3 /3! + х 5 /5! – …….. + ∞)
Используя свойство разложения функций синуса и косинуса в ряд, получаем,
= cos x + i sin x
Получается формула Эйлера для комплексного анализа.
Формула многогранника
Формула многогранника Эйлера утверждает, что количество граней, вершин и ребер каждого несамопересекающегося многогранника связано определенным образом. Его формула гласит, что количество вершин и граней многогранника вместе взятых на два больше, чем количество его ребер.
F + V – E = 2
где,
F – количество граней,
V количество вершин,
E количество ребер.
Вывод
Формула Эйлера может быть доказана для пяти платоновых тел: куба, тетраэдра, октаэдра, додекаэдра и икосаэдра.
Сплошные вещества
Количество лиц (F)
Номер (v)
4 (v)
4
F + V – E
Cube
4
4
6
2
Tetrahedron
6
8
12
2
Octahedron
8
6
12
2
Dodecahedron
12
20
30
2
ICOSAHEDRON
20
12
30
2
2
2
2
2
2
0033 Примеры задач Задача 1.
Решение:
Имеем,
x = π/2
Используя формулу получаем,
e ix = cos x + i0 sin x 90 sin π/2
= 0 + i (1)
= 0 + i
Задача 2. Представить e 6i в общем виде по формуле Эйлера.
Решение:
У нас есть
x = 6
с использованием формулы, которую мы получаем,
E IX = cos x + i sin x
= cos 6 + i sin 6
= 0,96 + i (-0,279)
= 0,96 – 0,279i
Задача 3. Выразить e 10i в общем виде по формуле Эйлера.
Решение:
Имеем,
х = 10
Используя формулу получаем,
e ix = cos x + i sin x
= cos 10 + i sin 10
= -0,83 + i (-0,544)
= -0,83 – 0,544i
90 iπ/3 в общем виде по формуле Эйлера.
Решение:
Имеем,
x = π/3
Используя формулу получаем,
e ix = cos x + i0 sin x 90 sin π/3
= 0,5 + i (0,86)
= 0,5 + 0,86i
Задача 5. Проверить формулу Эйлера для треугольной призмы.
Решение:
У нас есть треугольная призма. Известно, что
Количество граней (F) = 5
Количество вершин (V) = 6
Количество ребер (E) = 9
Используя формулу, которую мы имеем,
F + V − E = 5 + 6 − 9
= 11 – 9
= 2
Поскольку значение F + V − E равно 2, формула Эйлера проверена.
Задача 6. Проверить формулу Эйлера для квадратной пирамиды.
Решение:
У нас есть квадратная пирамида. Известно, что
Количество граней (F) = 5
Количество вершин (V) = 5
Количество ребер (E) = 8
Используя формулу, которую мы имеем,
F + V − E = 5 + 5 — 8
= 10 — 8
= 2
Поскольку значение F + V — E равно 2, формула Эйлера проверена.
Задача 7. Найти количество вершин многогранника, если число граней 20 и ребер 30.
Используя формулу получаем,
F + V − E = 2
=> V = E + 2 – F
= 30 + 2 – 20
= 32 – 20
= 12
00 Мосты Кенигсберга. Как Эйлер разработал теорию графов и… | Карл Бичер | Великие моменты в истории вычислений«В целом в математике верно утверждение, что существует промежуток времени между математическим открытием и моментом, когда оно становится полезным». — Джон фон Нейман (1903–1957)
Промежуток времени между математиком, пришедшим с идеей, и тем, кто впоследствии нашел применение этой идее, может быть долгим. Мы можем увидеть это, особенно когда смотрим на что-то вроде информатики, предмета, являющегося приложением математики. Например, Бертран Рассел был очень стар, прежде чем его теория типов, которую он разработал, когда ему было за тридцать, стала использоваться при разработке языков программирования.
Но в качестве примера действительно большого промежутка времени мы можем взять Теорию Графов, нечто фундаментальное для информатики, но впервые придуманное за двести лет до формального существования этого предмета. Чтобы увидеть этот пример зачаточной компьютерной науки в действии, нам придется вернуться в Пруссию восемнадцатого века.
Река Преголя протекает через центр Калининграда, образуя не только северную и южную стороны, но и два крупных острова внутри него. В восемнадцатом веке этот город был прусским и назывался Кенигсберг. В те дни между четырьмя массивами суши было семь мостов. Они были так прекрасны, что жители с удовольствием прогуливались по городу каждое воскресенье, следя за тем, чтобы пройти каждый мост. Когда они это делали, это была популярная игра, в которой они пытались выяснить маршрут, чтобы они могли пройти по каждому мосту, но только по одному разу.
Кенигсберг с отмеченными семью мостами.Как бы давно ни существовала эта традиция, к 1730-м годам никто еще не мог проложить такой маршрут. Вероятно, было заманчиво заявить, что это невозможно после всех этих лет попыток, но как они могли доказать это? Интуитивное чувство или подозрение, каким бы сильным оно ни было, не является доказательством. В конце концов, есть много перестановок; может быть, они просто еще не нашли подходящего.
Проблема показалась мэру Кенигсберга достаточно важной, чтобы он убедил местного гения Леонарда Эйлера избавить всех от страданий. Эйлер был плодовитым математиком и занятым человеком, но что еще поделаешь, если мэр обращается к вам за помощью? Несомненно, со вздохом он отложил свои рукописи и сел решать пустяковую игру. Нам повезло, что он это сделал, потому что в процессе решения головоломки он заложил основы одной из самых важных концепций информатики: теории графов.
Упрощенная версия карты.Эта карта Кенигсберга выглядит довольно загроможденной и отвлекающей, не так ли? Чтобы помочь нам сосредоточиться на решаемой задаче, мы могли бы просто стереть все эти улицы и здания или, что еще проще, просто перерисовать карту без них.
График семи мостов Кенигсберга и его суши.На изображении выше показана наша упрощенная абстрактная карта. Так-то лучше. Все, что имеет отношение к сути проблемы, теперь видно на диаграмме. То, что вы видите, — это граф, схема, которая моделирует информацию, используя узлы (круги) и ребра (линии, соединяющие узлы) для представления вещей и их взаимосвязи.
Он не хотел просто пробовать все возможные решения — кто знает, сколько времени это заняло бы — но он был уверен, что существует более методичный подход к проблеме. Эйлер знал, как и все компьютерщики сегодня, что поиск закономерностей в проблемах всегда должен быть первым шагом к поиску решения, потому что это не только облегчает решение исходной проблемы, но и помогает сделать окончательное решение общим и, следовательно, применимы к другим подобным задачам. В конце концов, что, если бы это положило начало тенденции, побуждающей каждого мэра Пруссии стучаться в дверь Эйлера с картой своего города, умоляя узнать, как лучше пройти через их городских мостов? Гораздо лучше просто дать им некоторые инструкции, чтобы выяснить это самостоятельно.
Эйлер знал, как и все сегодняшние компьютерщики, что поиск закономерностей в задачах всегда должен быть первым шагом к поиску решения.
Эйлер заметил критическую особенность задачи. В исходной задаче каждый мост можно было пересечь только один раз. На графике это означает, что каждый узел должен иметь четное количество соединений, потому что вы должны входить и выходить из узла через разные ребра. Единственными исключениями являются начальный и конечный узлы, потому что вам не нужно входить в начальный узел через ребро, и вам также не нужно покидать конечный узел. Следовательно, чтобы удовлетворить требованиям обхода, все узлы в графе должны быть соединены с четным числом ребер; если есть какие-либо узлы с нечетным номером, мы можем разрешить только два из них, чтобы они могли служить началом и концом путешествия.
Это объяснение демонстрирует мощь теории графов. Вернитесь к предыдущему абзацу и замените каждый экземпляр «узел» на «земля», каждый экземпляр «край» на «мост» и каждый экземпляр «граф» на «город». Вы переведете решение обратно на язык, понятный любому жителю Кёнигсберга восемнадцатого века.
Мы можем легко убедиться, что невозможно пересечь мосты Кенигсберга так, как хотелось бы, потому что все массивы суши связаны через нечетное количество мостов. Эта новость, неоспоримое доказательство того, что их игра не имеет решения, вероятно, разочаровала жителей Кенигсберга. Когда два моста позже были разрушены во время Второй мировой войны, горожане, несомненно, были очень возмущены. По крайней мере, они могли утешать себя тем, что у них осталось ровно два участка суши, соединенных с нечетным числом мостов, что позволило им бродить по городу именно так, как они хотели все эти годы.