Введение
Предположим, вы на вечеринке с девятью другими людьми, и каждый пожимает друг другу руку ровно один раз. Сколько рукопожатий происходит?
Это «задача о рукопожатии», и она одна из моих любимых. Мне, как учителю математики, это нравится, потому что существует множество разных способов прийти к решению, а разнообразие и взаимосвязь этих стратегий прекрасно иллюстрируют силу творческого мышления в математике.
Одно из решений выглядит следующим образом: начните с того, что каждый человек пожимает руку другому человеку. Десять человек, по девять рукопожатий каждый, производят 9 × 10 = 90 рукопожатий. Но при этом каждое рукопожатие учитывается дважды — по одному разу с точки зрения каждого шейкера — поэтому фактическое количество рукопожатий равно $latex frac{90}{2} = 45$. Простой и красивый аргумент в пользу победы!
Есть и совершенно другой способ решения проблемы. Представьте, что гости приходят по одному и, придя, пожимают руки всем присутствующим. У первого человека нет рук, которые он мог бы пожать, поэтому в группе из одного человека общее количество рукопожатий нулевое. Теперь подходит второй человек и пожимает руку первому. Это добавляет одно рукопожатие к общему количеству, поэтому в группе из двух человек общее количество рукопожатий составляет 0 + 1 = 1. Когда третий человек приходит и пожимает руку первым двум гостям, это добавляет к общему числу два рукопожатия. Прибытие четвертого человека добавляет к общей сумме три рукопожатия и так далее.
Эта стратегия моделирует последовательность рукопожатий рекурсивно, то есть каждый термин в последовательности определяется относительно тех, которые предшествуют ему. Вы, вероятно, знакомы с последовательностью Фибоначчи, самой известной рекурсивной последовательностью из всех. Он начинается с 1, 1, 2, 3, 5, 8, 13, 21 и продолжается с каждым последующим членом, равным сумме двух предыдущих.
Как мы увидим ниже, рекурсия — это гибкая и мощная основа для размышлений о широком спектре математических идей. И хотя древним индийским ученым, таким как Хемачандра, приписывают знание о такого рода последовательностях еще в 1150 году, они по-прежнему ставят перед математиками интригующие задачи.
Давайте посмотрим, как рекурсивное мышление помогает решить проблему рукопожатия. Если мы позволим $latex a_n$ равняться количеству рукопожатий в n-person party, мы можем представить эту рекурсивную связь следующей формулой:
$латекс a_n = a_{n-1} + n–1$
Это говорит нам о том, что количество рукопожатий за n-person party ($latex a_n$) равна количеству рукопожатий в (n − 1)-персона ($latex a_{n-1}$) плюс n − Еще 1 рукопожатие, отражающее идею о том, что когда приходит новый человек, они добавляют определенное количество новых рукопожатий к уже состоявшимся.
В нашей конкретной версии задачи о рукопожатии мы хотим знать $latex a_{10}$, количество рукопожатий на вечеринке из 10 человек, чтобы обнаружить, что мы используем рекурсивное отношение
$латекс a_{10} = a_9 + 9$
Чтобы найти значение $latex a_{10}$, нам просто нужно знать значение $latex a_9$ и прибавить к нему 9. Как нам найти значение $latex a_9$? Конечно же, используя рекурсию!
$латекс a_9 = a_8 + 8$
Теперь, чтобы найти значение $latex a_8$, нам нужно найти значение $latex a_7$, для чего необходимо знать $latex a_6$ и так далее. На данный момент вы можете волноваться, что это будет продолжаться вечно в своего рода бесконечном спуске, но как только мы достигнем $latex a_1$, все будет готово, потому что мы знаем, что на вечеринке из одного человека общее количество рукопожатий нулевое.
$латекс a_1 = 0$
Это начальное или «начальное» значение является ключевой особенностью рекурсивной последовательности. Это гарантирует, что процесс возврата по последовательности с использованием рекурсивных отношений завершится. Как только вы достигнете начального значения, обратный поиск прекратится, и вы сможете двигаться вперед по списку, чтобы получить нужное значение.
$латекс a_1 = 0$
$латекс a_2 = a_1 + 1 = 0 + 1 = 1$
$латекс a_3 = a_2 + 2 = 1 + 2 = 3$
$латекс a_4 = a_3 + 3 = 3 + 3 = 6$
$латексные точки$
$латекс a_{10} = a_9 + 9 = 36 + 9 = 45$
Проработав список, мы видим, что на вечеринке из 45 человек всего 10 рукопожатий, что согласуется с нашими первоначальными расчетами. Если вы чем-то похожи на моих студентов, вы можете спросить, зачем нам нужен другой способ решения этой проблемы, если мы уже знаем ответ, тем более что второй подход, похоже, требует больше времени.
Это хороший вопрос. Один из ответов заключается в том, что рекурсивный подход дает нам совершенно иной взгляд на то, что происходит в этой задаче, и разные точки зрения полезны в математике, как и во всем остальном. Они дают нам разные возможности для понимания концепций и позволяют использовать разные инструменты, которые могут помочь, когда мы застряли.
В частности, рекурсия полезна, потому что она повсюду в математике. Оно возникает, например, в линейных отношениях, о которых все узнают на уроках математики, — тех, которые характеризуются постоянной скоростью изменения и представляются линиями на плоскости. Линейную функцию, такую как $latex f(x) = 3x + 5$, можно рассматривать как рекурсивную формулу:
$латекс a_0 = 5$
$латекс a_n = a_{n-1} + 3$
Хотя более очевидный способ представить $latex f(2)$ состоит в том, что $latex f(2) = 3×2 + 5 = 11$, другой способ состоит в том, что $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Рекурсивное моделирование фундаментальной характеристики линейных функций — постоянной скорости изменения — дает нам другой способ подумать об этой взаимосвязи. То же самое можно сделать и с показательными функциями, характеризующимися постоянным мультипликативным изменением.
Рекурсивное мышление работает и за пределами последовательностей чисел. Если вы когда-либо решали систему уравнений, вы, вероятно, применяли рекурсивный подход. Чтобы решить систему
$латекс 2x + y = 10$
$латекс 3x – y = 5$
вы можете сначала сложить два уравнения вместе, чтобы исключить y переменная, что приводит к уравнению $latex 5x = 15$. Решите это, чтобы получить $latex x =$ 3, подставьте его и найдите $latex y = 4$, и все готово. В этом подходе используется рекурсивный алгоритм, в котором решение системы строится на основе решения более мелких связанных систем. Например, чтобы решить систему 3×3, вы исключаете одну переменную, чтобы превратить ее в систему 2×2, а затем еще раз, чтобы превратить ее в систему 1×1. Это простое для решения единственное уравнение похоже на начальное значение этого рекурсивного процесса. Это сигнализирует об окончании обратного поиска, и оттуда вы продолжаете двигаться вверх по цепочке уравнений, как в рекурсивной последовательности.
Существуют даже методы рекурсивного доказательства. Например, известная формула геометрии — это формула суммы углов многоугольника, которая гласит, что сумма мер внутренних углов многоугольника nОдносторонний многоугольник равен $latex (n-2) умноженному на 180^{circ}$. Один из способов доказать этот результат — начать с n-gon и представьте, что произойдет, если вы удалите треугольник.
Удаление треугольника превращает n-гон в (n − 1)-угольник, а также удаляет 180 градусов меры внутреннего угла. Это рекурсивная зависимость: сумма внутренних углов для n-gon на 180 градусов больше, чем сумма внутренних углов для (n − 1)-гон. Чтобы получить общий результат, продолжайте удалять треугольники, пока не достигнете начального значения, что в этой ситуации происходит, когда вы удалили все треугольники, кроме трех. n-вершины угольника. На этом этапе исходный многоугольник превратился в треугольник, сумма внутренних углов которого, как известно, равна 180 градусам. Теперь вернитесь назад, прибавляя 180 градусов на каждом этапе, и вы получите формулу.
Возвращаясь к нашей вечеринке, проблема рукопожатия сама по себе показывает нам, что возможно, когда мы думаем творчески, а затем соединяем вместе эти различные точки зрения на проблему. Если мы поиграем с рекурсивной моделью нашей последовательности рукопожатий:
$латекс a_1 = 0$
$латекс a_n = a_{n-1} + n – 1$
получается красивая закономерность:
$латекс a_2 = a_1 + 1 = 0 + 1$
$латекс a_3 = a_2 + 2 = 0 + 1 + 2$
$латекс a_4 = a_3 + 3 = 0 + 1 + 2 + 3$
$латексные точки$
$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$
Теперь у нас есть новый и общий подход к проблеме: количество рукопожатий в n-человека партия равна сумме первых n − 1 положительное целое число.
Вспомните наш первоначальный подход. В n- вечеринка, каждый человек пожимает друг другу руки n − 1 человек. Продукт $latex n (n-1)$ считает каждое рукопожатие дважды, поэтому общее количество рукопожатий равно $latex frac{n(n-1)}{2}$. Но поскольку наши разные методы рассчитывают одно и то же, они должны давать один и тот же результат. В частности, это означает:
$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$
Соединив разные подходы к проблеме рукопожатия, получаем замкнутую формулу суммы первых n − 1 положительное целое число. Но мы получаем даже больше: выражение $latex frac{n(n-1)}{2}$ включает в себя дробь, но поскольку она равна сумме целых чисел, она тоже должна быть целым числом. Это доказывает простой факт теории чисел: для каждого целого числа n, $latex frac{n(n-1)}{2}$ — целое число.
Аргументы того же рода продолжают лежать в основе современной математики. Например, исследователи начала 2000-х гг. доказал некоторые удивительные результаты о рекурсивных последовательностях, известных как последовательности Сомоса, показав, что они тоже что-то считают. Благодаря силе творческих связей математики еще раз открыли, куда они могут пойти, поняв, где они были.
Введение
Упражнения
1. Найдите замкнутую формулу для последовательности, которая определяется рекурсивно как
$латекс a_1 = 1$
$латекс a_n = a_{n-1} + 2n – 1$
Нажмите, чтобы увидеть ответ 1:
Небольшое исследование дает вам $latex a_2 = 1 + 4 – 1 = 4$, $latex a_3 = 4 + 6 – 1 = 9$, $latex a_4 = 9 + 8 – 1 = 16$, что приводит к $latex a_n. = n^2$. Это показывает, что совершенные квадраты можно определить рекурсивно, что следует из алгебраического тождества $latex (n+1)^2 = n^2 + 2n + 1$. Возвращаясь к последовательности, вы также можете показать, что $latex n^2$ — это сумма первых n последовательных нечетных чисел: $latex n^2 = 1 + 3 + 5 + 7 + cdots + (2n-1)$ .
Введение
2. В конце столбца было показано, что выражение $latex frac{n(n-1)}{2}$ является целым числом, даже несмотря на то, что выражение содержит дробь, поскольку $latex frac{n(n-1) )}{2}$ — это результат подсчета чего-либо. Существует также аргумент теории чисел, который показывает, что это выражение должно быть целым числом. Что это такое?
Нажмите, чтобы увидеть ответ 2:
Числа n и n − 1 — целые последовательные числа, поэтому одно из них должно быть четным; таким образом, их произведение $latex n(n-1)$ также четно, и поэтому $latex frac{n(n-1)}{2}$ должно быть целым числом.
Введение
3. Найдите первые несколько членов рекурсивной последовательности.
$латекс a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$
Нажмите, чтобы увидеть ответ 3:
Итак, $latex a_2 = frac{1}{1+1}=frac{1}{2}$, $latex a_3 = frac{1}{1+frac{1}{2}}=frac{2}{3 }$, $latex a_4 = frac{1}{1+frac{2}{3}}=frac{3}{5}$, $latex a_5 = frac{1}{1+frac{3}{5} }=frac{5}{8}$ и так далее. Эта последовательность состоит из отношений последовательных чисел Фибоначчи и связана с «непрерывной дробью» $latex frac{1}{1+frac{1}{1 + frac{1}{1 + cdots}}}$, другой разновидностью рекурсивного объекта.
Введение
4. Найдите первые несколько членов рекурсивной последовательности.
$латекс a_1 = 1$
$латекс a_2 = 1$
$латекс a_n = a_{n-1} – a_{n-2}$
Нажмите, чтобы увидеть ответ 4:
Эта последовательность, подобная Фибоначчи, равна 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, …, показывая, что даже периодическое поведение можно моделировать рекурсивно.
- SEO-контент и PR-распределение. Получите усиление сегодня.
- PlatoData.Network Вертикальный генеративный ИИ. Расширьте возможности себя. Доступ здесь.
- ПлатонАйСтрим. Интеллект Web3. Расширение знаний. Доступ здесь.
- ПлатонЭСГ. Углерод, чистые технологии, Энергия, Окружающая среда, Солнечная, Управление отходами. Доступ здесь.
- ПлатонЗдоровье. Биотехнологии и клинические исследования. Доступ здесь.
- Источник: https://www.quantamagazine.org/math-that-connects-where-were-going-to-where-weve-been-20240322/
- :имеет
- :является
- :куда
- ][п
- $UP
- 1
- 10
- 13
- 180
- 36
- 7
- 8
- 9
- a
- О нас
- фактического соединения
- Добавить
- добавить
- Добавляет
- снова
- соглашается с тем,
- алгоритм
- Все
- позволять
- уже
- причислены
- an
- Древний
- и
- угол
- Другой
- ответ
- все
- прикладной
- подхода
- подходы
- МЫ
- аргумент
- около
- прибытие
- Прибыл
- AS
- спросить
- At
- назад
- BE
- красиво
- , так как:
- было
- до
- поведение
- ниже
- Beyond
- построенный
- но
- by
- расчет
- CAN
- Захват
- определенный
- цепь
- проблемы
- изменение
- характеристика
- отличающийся
- класс
- закрыто
- Column
- как
- полностью
- понятия
- Свяжитесь
- Соединительный
- Коммутация
- подключает
- последовательный
- состоит
- постоянная
- продолжается
- может
- считать
- подсчет
- творческий
- определенный
- различный
- открытый
- Разнообразие
- do
- сделанный
- каждый
- Рано
- ликвидировать
- Еще
- возникает
- конец
- полностью
- равный
- уравнения
- особенно
- установить
- Даже
- НИКОГДА
- Каждая
- все члены
- везде
- точно,
- пример
- исследование
- экспоненциальный
- выражение
- факт
- знакомый
- знаменитый
- далеко
- избранное
- Особенность
- несколько
- Fibonacci
- Найдите
- Во-первых,
- гибкого
- после
- следующим образом
- Что касается
- навсегда
- формула
- вперед
- Четвертый
- доля
- Рамки
- от
- функция
- Функции
- фундаментальный
- Общие
- получить
- Дайте
- дает
- Go
- идет
- будет
- хорошо
- гарантии
- Гости
- рука
- Руки
- происходить
- происходит
- Есть
- помощь
- помогает
- Удар
- Как
- HTTPS
- i
- идея
- идеи
- Личность
- if
- иллюстрировать
- картина
- in
- Индийская кухня
- Бесконечный
- начальный
- интерьер
- в
- интригующий
- включает в себя
- IT
- саму трезвость
- всего
- Сохранить
- Основные
- Вид
- виды
- Знать
- знание
- известный
- Лиды
- узнает
- позволять
- такое как
- линейный
- линий
- Список
- мало
- дольше
- любят
- журнал
- многих
- математике
- математический
- математика
- Май..
- смысл
- означает
- проводить измерение
- меры
- методы
- может быть
- модель
- моделирование
- Модели
- Модерн
- БОЛЕЕ
- самых
- с разными
- должен
- my
- Необходимость
- Новые
- хороший
- 9
- нет
- сейчас
- номер
- номера
- объект
- Очевидный
- of
- предлагают
- on
- консолидировать
- ONE
- те,
- Возможности
- or
- оригинал
- Другое
- наши
- внешний
- особый
- вечеринка
- шаблон
- Люди
- ИДЕАЛЬНОЕ
- периодический
- человек
- перспектива
- перспективы
- Часть
- самолет
- Платон
- Платон Интеллектуальные данные
- ПлатонДанные
- Играть
- плюс
- Точка
- Polygon
- положительный
- возможное
- мощностью
- мощный
- представить
- предыдущий
- вероятно
- Проблема
- процесс
- производит
- Продукт
- доказательство
- Доказывать
- доказывает
- Квантовый журнал
- вопрос
- ассортимент
- Обменный курс
- коэффициенты
- достигать
- рекурсивный
- Цена снижена
- Связанный
- отношения
- Отношения
- относительный
- удален
- удаляет
- удаление
- представлять
- представленный
- требуется
- исследователи
- результат
- Итоги
- то же
- говорит
- Ученые
- Во-вторых
- посмотреть
- семя
- кажется
- Последовательность
- показывать
- показ
- показанный
- Шоу
- сигналы
- просто
- с
- одинарной
- ситуация
- меньше
- So
- Решение
- РЕШАТЬ
- некоторые
- удалось
- квадраты
- Начало
- начинается
- Шаг
- По-прежнему
- Останавливает
- стратегий
- Стратегия
- Студенты
- последующее
- удивительный
- система
- системы
- взять
- приняты
- снижения вреда
- говорит
- 10
- срок
- terms
- чем
- который
- Ассоциация
- их
- Их
- тогда
- теория
- Там.
- Эти
- они
- задача
- вещи
- think
- мышление
- В третьих
- этой
- те
- хоть?
- мысль
- три
- Через
- Таким образом
- время
- раз
- в
- сегодня
- вместе
- слишком
- инструменты
- Всего
- ОЧЕРЕДЬ
- Получается
- Дважды
- два
- понимать
- понимание
- до
- us
- использование
- полезный
- через
- использует
- ценностное
- переменная
- версия
- Вид
- хотеть
- законопроект
- Путь..
- способы
- we
- WebP
- ЧТО Ж
- Что
- Что такое
- когда
- который
- чья
- зачем
- широкий
- Широкий диапазон
- будете
- Работа
- работает
- работает
- беспокоиться
- бы
- X
- Уступать
- Ты
- ВАШЕ
- зефирнет
- нуль