Задача эйлера – Задача Эйлера Википедия

Содержание

Задача Эйлера Википедия

Запрос «Семь мостов Кёнигсберга» перенаправляется сюда; о самих городских мостах см. Мосты Кёнигсберга. Кёнигсберг в XVII—XVIII вв. (карта 1652 года)

Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах (лат. Problema Regiomontanum de septem pontibus, нем. Königsberger Brückenproblem[1]) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером[2][3][4], доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.

История

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог[источник не указан 923 дня].

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Джованни Джакобо Маринони

[de] от 13 марта 1736 года. В этом письме Эйлер приводит правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя»[2]. В письме Карлу Готлибу Элеру[en] от 3 апреля 1736 года Эйлер обосновывает найденное им правило[3], а позднее на эту тему Эйлер публикует статью в научном журнале Петербургской академии наук «Commentarii Academiae Scientiarum Imperialis Petropolitanae»[4].

Решение задачи по Леонарду Эйлеру

На упрощённой схеме города (графе) мостам соответствуют линии (ребра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

  • Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
  • Если все вершины графа чётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
  • Если ровно две вершины графа нечётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом нужно начинать с одной из нечётных вершин и завершить его в другой нечётной вершине.
  • Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все) — следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Дальнейшая история

В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. Всего до 2016 года в Калининграде было восемь мостов.

См. также

Примечания

Литература

wikiredia.ru

Задача Эйлера | Социальная сеть работников образования

Слайд 1

Задача Эйлера Автор презентации: Бондаренко Антон, ученик 10 Б Руководитель Стеняева Наталья Сергеевна Г.Выборг 2012 год Министерство образование Российской Федерации МБОУ «Средняя школа № 12» г. Выборг Ленинградская область

Слайд 2

Цели презентации: Кратко рассказать об авторе задачи великом математике Леонард Эйлер Выделить основные утверждения, которые доказываются в задаче Эйлера Показать решение этих утверждений

Слайд 3

Леонард Эйлер 1707 – 1783 Леонард Эйлер – один из величайших ученых, внесший огромный вклад в развитие отечественной и науки вообще. За свою жизнь написал более 800 работ по направлениям: математический анализ, дифференциальная геометрия, теория чисел, приближенным вычислениям, теории музыки, кораблестроению , оптике, баллистике и другие. Его учениками являются первые российские академики Котельников и Румовский. Работал в Петербургской Академии наук с 1731 – 1741, а также с 1766.

Слайд 4

Задача Эйлера: Доказать, что в произвольном треугольнике: 1) точки симметричные точке Н пересечения высот (или их продолжений) относительно сторон треугольника и из середин, лежат на описанной окружности; 2) середины сторон, основания высот и середины отрезков, соединяющих точку Н с вершинами, лежат на одной окружности, центром которой является середина отрезка, соединяющего точку Н с центром описанной окружности, а её радиус в два раза меньше радиуса описанной окружности (окружности Эйлера) 3) точка пересечения медиан лежит на отрезке, соединяющем точку Н с центром описанной окружности, и делит этот отрезок в отношении 1:2, считая от центра описанной окружности (прямая, на которой лежат четыре точки – точка Н , точка пересечения медиан, центр описанной окружности и центр окружности Эйлера, называется прямой Эйлера) 4) точки, симметричные центру описанной окружности относительно прямых, содержащих средние линии треугольника, лежат на окружности Эйлера

Слайд 5

B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G ∆ ABC – данный треугольник O 9 — центр окружности Эйлера OR — описанная окружность СС 1 , АА 1 ВВ 1 – медианы, G – точка их пересечения СС 2 , АА 2 ВВ 2 – высоты А 4 С 4 В 4 – точки, симметричные точке Н относительно сторон треугольника А 5 С 5 В 5 – точки, симметричные точке Н относительно середин этих сторон треугольника А 3 С 3 В 3 – середины отрезков АН , ВН и СН ОН — прямая Эйлера

Слайд 6

Если угол А = 90 о , то точки Н, В 4 и С 4 совпадают с точкой А , точка В 5 с точкой С , а точка С 5 – с точкой В . Угол ВА 4 С = ВА 5 С= А, то А, А 4 и А 5 лежат на окружности с диаметром ВС = > А 5 ,В 4 ,В 5 , С 4 ,С 5 лежат на окружности описанной треугольника АВС B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Докажем утверждение 1

Слайд 7

Допустим ∆ АВС не является прямоугольным. Поскольку углы АВ 2 Н = АС 2 Н = 90 ₀ , то точки В 2 и С 2 лежат на окружности с диаметром АН = > вписанные углы и ВНС либо равны, либо их сумма равна 180 о . В обоих случаях sin ВНС = sin ВАС . Пусть R 1 – радиус окружности, описанной около ∆ НВС . По теореме ВС =2 R 1 sin ВНС = 2 Rsin ВАС . Но sin ВНС = sin ВАС, значит R 1 =R = > окружности описанные около ∆ АВС и ∆ НВС , симметричны относительно прямой ВС и относительно середины ВС . Точка Н лежит на окружности описанной около ∆ НВС , значит точки А 4 и А 5 лежат на окружности около АВС . Аналогично для В 4 , В 5 , С 4 , С 5 . A 5 B A C A 1 A 2 A 4 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Утверждение 1 доказано

Слайд 8

B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Докажем утверждение 2 Рассмотрим центральное подобие с центром Н и коэффициентом 1:2 При этом подобии окружность переходит в окружность радиуса R :2, центр О 9 является серединой отрезка ОН , а точки В 4 , В 5 , С 4 , С 5 , А 5 , А 4 , А , В , С – переходят в точки А 1 , B 1 , С 1 , А 2 , В 2 , С 2 , А 3 , В 3 , и С 3 = > лежат на окружности с центром О 9 и радиусом R:2 Утверждение 2 доказано

Слайд 9

B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Докажем утверждение 3 Рассмотрим центральное подобие с центром G и коэффициентом -1:2, при этом подобие вершины АВС перейдут в середины А 1 , В 1 и С 1 , противоположных сторон. Из этого следует, что прямые содержащие высоты перейдут в прямые перпендикулярные к его сторонам, т. е. в серединные перпендикуляры сторон. Значит, точка Н перейдет в центр окружности О . Это означает, что точка G лежит на ОН и делит его в отношении 1:2. считая от точки О . Утверждение 3 доказано

Слайд 10

B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Докажем утверждение 4 Из доказанного в утверждение 3 следует: А) окружность описанная около ∆ АВС , переходит в окружность Эйлера Утверждение 4 доказано Задача Эйлера решена! Б) точки А 4 , В 4 и С 4 , симметричные точке Н относительно прямых ВС, СА и АВ, переходят в точки А 6 , В 6 и С 6 окружности Эйлера, симметричные точке относительно прямых В 1 С 1 , С 1 А 1 и А 1 В 1 . Таким образом А 6 , В 6 и С 6 , лежат на окружности Эйлера

nsportal.ru

Project Euler — решайте алгоритмические задачи и смотрите как это делали другие 30к участников на огромном количестве языков.

Пару-тройку месяцев назад наткнулся на замечательный ресурс Project Euler.

Project Euler представляет собой набор математических задач, которые вам предлагается решить хоть программным методом, хоть на бумаге.

Для участия в проекте надо пройти быструю регистрацию, после чего можно смело штурмовать алгоритмы.

подробно — внутри
Изюминка ресурса в том, что вы можете решить задачу на любом удобном для вас языке, надо только вписать в форму правильный ответ.
После того как будет дан ответ вы сможете войти в ветку форума по данной задаче и увидеть какими методами данную задачу решили остальные участники, которых за время проекта набралось огромное количество (So far 29276 users have submitted 537919 correct solutions; that is an average of 18 problems per user).

Вы можете посмотреть как данную задачу решили на почти всех живых языках программирования, увидеть красивые решения и грубый брутофорс)

По мере прохождения сложность задач увеличивается.

Посоревноваться в скорости алгоритма и просто обсудить математический аспект задачи.

Выдержки из статистики:

язык
количество участников
C/C++ 3726
python 2900
Java 1782
C# 917
Assembler 37
F# 97
Haskell 945
Fortran 32
Nemerle 8
Ada 16
R 7
Prolog 2
Boo 6
PHP 425
Pencil/Paper 291
Ruby 804

Вот так, к примеру, выглядит самая первая задача из 200штук:
Add all the natural numbers below one thousand that are multiples of 3 or 5.

Вот так 50-я
Which prime, below one-million, can be written as the sum of the most consecutive primes?

100я
Investigate the optimum polynomial function to model the first k terms of a given sequence.
Удачного погружения

habr.com

О Проекте Эйлера

О проекте

Leonhard Euler (1707-1783)

Что такое Проект «Эйлер»?

Проект «Эйлер» — это набор интригующих задач по математике и программированию, для решения которых, однако, недостаточно одной только математической интуиции. Разумеется, математика поможет прийти к красивому и элегантному решению, но для успешного решения большинства задач без навыков программирования не обойтись.

Основная мотивация для создания и поддержки проекта — предоставить пытливым умам платформу для погружения в незнакомые области и добавить немного веселья в процесс изучения новых идей.


Для кого предназначены задачи?

Целевая аудитория проекта включает в себя студентов, которым мало университетского курса, не-математиков, которым, тем не менее, интересна математика, а также профессионалов, которым хотят быть в хорошей математической форме.


Значит, задачи может решить кто угодно?

Задачи эти разной степени сложности, и большинство их предполагает индуктивное обучение. То есть очередная решённая задача открывает нечто новое, что позволит подобраться к ранее недоступной задаче. Таким образом упорный участник проекта будет медленно, но верно продвигаться по списку задач.


С чего мне начать?

Это зависит от ваших навыков и способностей. В таблице «Задачи» можно посмотреть сколько человек уже решило каждую из них. В общем случае — чем больше людей решило задачу, тем она проще.


Я написал программу, теперь придётся ждать результата вычислений пару дней?

Разумеется, нет! Каждая задача подчиняется «правилу одной минуты», которое гласит: несмотря на то, что на построение алгоритма решения могут уйти часы, эффективная реализация позволяет получить ответ на компьютере средней вычислительной мощности меньше, чем за одну минуту.


А если моя программа проработала дольше минуты, решение не засчитывается?

Засчитывается. Однако в идеале это должно побудить вас вернуться к задаче и проверить, можно ли как-то улучшить решение. Как только вы решите задачу, вы получите доступ к ветке форума с её обсуждением, где могут найтись советы по отпимизации от других участников.


Можно ли пользоваться поисковиком в процессе решения?

Многие задачи таят в себе настоящие математические сокровища, и использование интернета для их поиска никоим образом не возбраняется. Но существует чёткая граница между собственным исследованием и копипастой решения с другого сайта. Чему вы научитесь, списывая с решебника?


Я перепроверил свою программу десять раз, а ответ всё равно не принимается! Может, у вас там ошибка?

Мы постоянно выкладываем новые задачи, поэтому в самые свежие вполне могут закрасться мелкие ошибки, или же условие может быть сформулировано недостаточно чётко. Но согласитесь, что когда большинство попадает в цель, а один стрелок промахивается десять раз подряд, вряд ли ему придёт в голову стрелять себе в ногу и заключать, что раз оружие работает как нужно, то во всём виновата мишень.


Можете дать парочку советов по решению задач?

Внимательно прочитайте условие и изучите приведённые примеры. Карандаш и бумага помогут лучше понять идею, лежащую в основе задачи. Если идея эта для вас нова, обратитесь к дополнительной литературе и интернету; в условии могут содержаться подсказки, на что обратить внимание. Попробуйте написать программу для простых случаев и удостоверьтесь, что она правильно работает на тестовых данных из условия, это послужит знаком того, что вы вникли в суть задачи и продвигаетесь в верном направлении. Попытайтесь оценить время, которое потребуется для получения окончательного ответа, и если оно явно будет больше минуты, пересмотрите свою стратегию.


Я столько всего изучил, пока решал задачу ХХХ, можно мне публиковать своё решение?

На самом деле, ответ заключается в самом вопросе. Ничто не сравнится с удовлетворением от решения задачи, над которой вы ломали голову не один час. Конечно, желая поделиться своим озарением с другими, вы действуете из лучших побуждений, но увы, скорее всего вы оказывате своим читателям медвежью услугу. Настоящее обучение — это активный процесс, одно дело наблюдать за процессом, и совсем другое — переживать этот опыт самому. Пожалуйста, не лишайте других столь ценного удовольствия.


Кто это всё придумал?

Проект «Эйлер» был основан Colin Hughes (aka euler) в октябре 2001 как подраздел сайта mathschallenge.net. Кто бы мог подумать, что такие задачи окажутся настолько популярными? Поскольку количество пользователей продолжало неуклонно расти, Проект «Эйлер» переехал на отдельный домен в 2006 году.


Кто поддерживает работу Проекта «Эйлер»?

Идеи для новых задач приходят к нам от участников проекта. Затем над ними работает команда трудолюбивых и талантливых математиков и программистов. Проще говоря, Проект живёт благодаря своим участникам.


Благодарности

За создание сайта — Виталию aka Vitalg.
За перевод задач — Элану aka Konnektor, Виталию aka Stumbler.
За адскость — Антону aka antox(z*)

 

 

euler.jakumo.org

Отправить ответ

avatar
  Подписаться  
Уведомление о