От «Математической индукции» к пониманию «Рекурсивных алгоритмов»!

Немного положительной энергии в каждой главе: жизнь человека может сгореть или разрушиться.

предисловие

Я полагаю, что вы время от времени будете сталкиваться с вопросами о рекурсивных алгоритмах или программировании на собеседованиях или на работе. Давайте поговорим об этом сегодня.从数学归纳法到理解递归算法. Если есть какие-либо ошибки, пожалуйста, укажите на них вовремя ~

Эта статья была синхронизирована сGitHub/Gitee/Общедоступный номер, заинтересованные студенты помогают подписаться~

1. Математическая индукция

1.1 Введение

Источник Энциклопедия Baidu

Математическая индукция(Математическая индукция, МИ) — это метод математического доказательства, который обычно используется для доказательства того, что данное утверждение верно для всего (или частичного) диапазона натуральных чисел. В дополнение к натуральным числам математическая индукция в широком смысле также может использоваться для доказательства общих хорошо обоснованных структур, таких как деревья в теории множеств. Этот обобщенный метод математической индукции, применяемый в областях математической логики и информатики, называется структурной индукцией. В теории чисел математическая индукция — это математическая теорема, по-разному доказывающая истинность любой данной ситуации (первой, второй, третьей и т. д.). Хотя в названии математической индукции есть «индукция», математическая индукция — это не метод индуктивного рассуждения, который не является строгим, это метод дедуктивного рассуждения, который является полностью строгим. На самом деле все математические доказательства дедуктивны.

Натуральное числоЭто относится к числу, представляющему количество объектов, то есть начиная с 0, 0, 1, 2, 3, 4, ... один за другим, образуя бесконечную группу, то есть неотрицательное целое число.

1.2 Шаги дедукции

После краткого понимания концепции математической индукции давайте рассмотрим этапы дедукции математической индукции.

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

Шаги доказательства следующие:

Докажите, что выполняется базовый случай (обычно при N = 1). Доказательство верно для N=1. Нам просто нужно начать доказательство с наименьшего натурального числа. Этот шаг обычно очень прост. Главное доказать второй шаг.
При доказательстве N > 1, предполагая, что выполняется N - 1, выполняется и N (N — любое натуральное число больше 1). Этот шаг не является прямым доказательством, но предполагает, что N-1 выполняется, и использует этот вывод, чтобы вывести, что N выполняется. Если его можно вывести, то можно сказать, что он верен для всех натуральных чисел. Поскольку доказательство верно для 1, то оно верно для 2 и верно для 3. Затем доказывается, что это верно для всех натуральных чисел. Мы обнаружим, что математическая индукция хорошо работает для доказательств, таких как обычные арифметические разности, отношения и суммы квадратных и кубических рядов и т. д.

1.3 Маленькие каштаны

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

пример:


证明： 1+2+3+...+n = n(n+1)/2

Давайте поместим выше1.2 推演步骤используй это.

Шаг 1: Докажите, что выполняется базовый случай (обычно при N = 1).

Подставляем N=1 в левую и правую части знака равенства, получаем


1 = 1*(1+1)/2

учредил!

Шаг 2: При доказательстве N > 1, предполагая, что выполняется N - 1, выполняется и N (N — любое натуральное число больше 1).

Здесь нам нужно сделать два шага.

① Предположим, что это верно для случая N-1

Подставляем еще N-1 в левую и правую части знака равенства одновременно, получаем:


1+2+3+...+(n-1) = (n-1)n/2

② Замените вывод гипотезы и одновременно добавьте N

Считаем, что установлено N-1, тогда к левой и правой части знака равенства прибавляем одновременно N, оно тоже должно быть установлено, получаем:


 1+2+3...+(n-1)+n = (n-1)n/2+n

Упростите правую часть, чтобы получить:n(n+1)/2, то наше окончательное доказательство верно!

который:1+2+3+...+n = n(n+1)/2учредил. С помощью вышеуказанных шагов мы можем доказать, что эта формула действительна.

1.4 Резюме

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

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

2. Рекурсия

Говоря о рекурсивных алгоритмах, на самом деле каждый из нас, разработчиков, наверняка слышал или писал о них. Я помню, когда я впервые столкнулся с рекурсивными алгоритмами, когда я был новичком в языке C, написанном г-ном Танем Хаоцяном, он представил рекурсивные алгоритмы. У меня такое впечатление: называй себя сам. В дальнейшем в своей работе я его почти не использовал, только помнил, что рекурсивный алгоритм применялся при написании каскадного меню один раз. (Не слишком ли водянистый код я написал? Вы также можете поговорить о том, где использовались рекурсивные алгоритмы.) В этой главе мы рассмотрим рекурсивные алгоритмы, которые мы изучили с помощью математической индукции.

2.1 Понимание рекурсии

Основная идея рекурсии:以此类推

В частности, это преобразование крупномасштабной проблемы в мелкомасштабную аналогичную подзадачу для решения. Когда функция реализована, поскольку метод решения больших проблем и метод решения мелких проблем часто являются одним и тем же методом, возникает ситуация, когда функция вызывает сама себя. Кроме того, функция, решающая задачу, должна иметь очевидное конечное условие, чтобы не было бесконечной рекурсии. Более пристальный взгляд на рекурсию показывает:递归的数学模型其实就是归纳法.

2.2 Рекурсивные условия

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

Для выполнения условий:

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

Вышеуказанные условия связаны между собой и также могут быть сведены к двум основным условиям:有规律,有退出条件. Мы используем приведенные выше условия, чтобы понять случай.

2.3 Маленькие каштаны

2.3.1 Рекурсивное суммирование

пример:


1+2+3+...+n=?

первый шаг:Строго определите роль рекурсивных функций, включая параметры, возвращаемые значения и другие переменные.

Когда мы впервые смотрим на заголовок, мы можем знать, что это простое суммирование, то есть, начиная с 1: 1+2+3+... вплоть до n. Таким образом, мы можем определить метод с входным параметром n и типом возвращаемого значения int.Поскольку это рекурсивное суммирование, имя нашего метода называется recursionSum.


public static int recursionSum(int n) { //为了方便调用，我用了static
    
    return 0;
}

System.out.println("公众号：Coder编程：" + recursionSum(0));

Тогда мы закончили с первым шагом.

Шаг 2:Сначала общий случай, потом частный.

Сначала мы используем общий случай для вычисления суммирования, например, подставляя в общем случае 1,2,3. который:


public static int recursionSum(int n) { 
    if(n == 1) {
        return 1;
    }
    
    if(n == 2) {
        return 1+2;
    }
    
    if(n == 3) {
        return 1+2+3;
    }
    return 0;
}

System.out.println("公众号：Coder编程：" + recursionSum(3));

третий шаг:Есть условия выхода. В общем, условия, которые позволяют рекурсии завершиться нормально.

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

четвертый шаг:Каждый вызов должен уменьшать размер задачи, а новая задача имеет ту же форму, что и исходная задача, то есть шаблон.

Этот шаг самый ответственный и самый важный! Нам нужно найти закономерность и иметь возможность уменьшить размер проблемы. Мы обнаружим, что когда нам нужно найти сумму N-го числа, мы должны знать сумму первых N-1 чисел, то есть сумму (N-1). Сумма первых N чисел равна сумме (N-1)+N. Найдя это правило, мы можем определить временную переменную sum для получения суммы первых N чисел.


public static int recursionSum(int n) {

    if(n == 1) {
        return 1;
    }
    
    if(n == 2) {
        return 1+2;
    }
    
    if(n == 3) {
        return 1+2+3;
    }
    
    int sum = recursionSum(n-1)+n;
    return sum;
}

System.out.println("公众号：Coder编程：前5个数的和" + recursionSum(5));

Выходной результат: 15

Давайте оптимизируем его:


public static int recursionSum(int n) {

    if (n < 0){
       throw new Exception("参数不能为负！");
    }
    if(n == 1) {
        return 1;
    }
    
    return recursionSum(n-1)+n;
}

System.out.println("公众号：Coder编程：前5个数的和" + recursionSum(5));

Вы вдруг обнаружили, что рекурсия не так сложна, как вы думали?

2.3.2 Вывод из одного случая в другой?

Далее мы улучшим сложность! Посмотрите, все ли это понимают. Я не такой многословный, как приведенное выше суммирование!

2.3.2.1 Нахождение факториала

Пример: найти факториал числа n (n>1, n — целое положительное число)

Рекурсивная формула для факториала: factorial(n)=n*factorial(n-1), где n — целое неотрицательное число, а 0!=1,1!=1 Я не буду вдаваться в подробности здесь, это то же самое, что и процесс пост-вычисления.Вы можете имитировать процесс суммирования.Вы можете сначала попробовать написать его самостоятельно.Я вставлю код прямо ниже:


public static int factorial(int n) throws Exception {
    if (n < 0){
        throw new Exception("参数不能为负！");
    }else if (n == 1 || n == 0) {
        return 1;
    }else {
        return n * factorial(n - 1);
    }
}

System.out.println("公众号：Coder编程：3的阶乘:" + factorial(3));

Результат вывода: Официальный аккаунт: Программирование кодера: факториал 3:6

2.3.2.2 Последовательность Фибоначчи

斐波那契数列Думаю, с ней все тоже знакомы.Продолжим рассмотрение, что же такое последовательность Фибоначчи?

Последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21...

Видно, что начиная с третьей позиции: третий элемент равен сумме двух предыдущих элементов. Суммируйте рекурсивную формулу: :Fib(n)=Fib(n-1)+Fib(n-2). Таким образом, мы можем использовать первые два бита в качестве условия для выхода из рекурсии. который:if(n==1) retrun 1 if(n==2) return 1

Следовательно, мы можем напрямую использовать формулу (правило) и условие выхода для написания программного кода:


public static int fib(int n) throws Exception {
    if (n < 0) {
        throw new Exception("参数不能为负！");
    }else if (n == 0 || n == 1){
        return n;
    }else {
        return fib(n - 1) + fib(n - 2);
    }
}

System.out.println("公众号：Coder编程：斐波那契数列:" + fib(3));

2.3.2.3 Проблема Ханойской башни

По легенде, в древнеиндийских храмах есть своего рода汉诺塔(Hanoi)игра. Игра ведется на медном пластинчатом устройстве с тремя стержнями (пронумерованными А, В, С). На стержне А размещено разное количество золотых дисков в порядке снизу вверх и от большего к меньшему (как показано на рисунке ниже). .

Цель игры: переместить все золотые диски с полюса А на полюс С и сохранить первоначальный порядок.

Правила работы: за один раз можно перемещать только одну пластину, и три стержня всегда должны держать большую пластину внизу, а маленькую пластину вверху во время процесса движения.Плиту можно поместить на любой стержень A, B, или C во время операции.

Прежде чем обобщать правила и писать код, поиграем в несколько простых (Сначала общие, потом специальные):

Примечание: мы принимаем размер номера за размер тарелки.

Корпус пластины:

1.1 Переместите пластину 1 колонки А прямо в колонку С. 1.2 Конец.
В случае двух пластин:

2.1 Переместите пластину 1 из колонки А в колонку В. 2.2 Переместите пластину 2 из колонки А в колонку С. 2.3 Переместите пластину 1 из колонки B в колонку C. 2.4 Конец.
Корпус из трех пластин:

3.1 Переместите пластину 1 из колонки А в колонку С. 3.2 Переместите пластину 2 из колонки А в колонку В. 3.3 Переместите пластину 1 из колонки C в колонку B. 3.4 Переместите пластину 3 из колонки А в колонку С. 3.5 Переместите пластину 1 из колонки B в колонку A. 3.6 Переместите тарелку 2 из колонки B в колонку C. 3.7 Переместите пластину 1 из колонки А в колонку С. 3.8 Конец.

Мы обнаружим, что по мере увеличения числа тарелок увеличивается и трудность перемещения тарелок.

Не бойтесь пока, давайте вернемся назад и посмотрим на эту задачу: когда количество тарелок 4, 5...N, как мы ее решим? Можем ли мы использовать идею математической индукции или идею рекурсии для ее решения? Ответ: да. На этот раз нам нужно найти их законы.

Заметим еще раз, где правило перемещения тарелки вообще?

1. Когда есть только одна тарелка, тарелку можно переместить непосредственно в целевой столбец C. который退出条件.
2. Когда есть только две тарелки, нам нужно использовать только колонку B в качестве промежуточного звена, сначала поместите тарелку 1 на промежуточную колонку B, затем поместите тарелку 2 на целевую колонку C и, наконец, поместите тарелку на промежуточную. столбец B. в целевой столбец C.

Второй момент можно рассматривать так: когда у нас есть N тарелок, N-я тарелка рассматривается как тарелка, а (N-1) тарелки рассматриваются как тарелка. Необходимо разместить (N-1) тарелок на промежуточную колонку B и N тарелок на целевую колонку C. который规律.

Когда у нас есть три пластины, мы найдем проблему:изменение роли

Считайте (N-1)~1-ю пластину Башни А пластиной, поместите ее на среднюю колонну B, а затем поместите N-ю пластину на целевую колонну C. В этот момент柱子A空了!柱子A成为中介柱子，柱子B成为起始柱子.
Столб B в это время имеет N-1 тарелку, расценивайте тарелку (N-2)~1 как тарелку, поместите ее на промежуточную колонку A, а затем поместите (N-1) тарелку колонны B на целевой столбец С. В этот момент柱子B空了!柱子B又成为了中介柱子，A成为了起始柱子!

Повторяйте шаги 1 и 2, пока все пластины не будут размещены на целевой башне C.

в заключении:

Переместите тарелки с n-1 из начального столбца A в промежуточный столбец B.
Поместите оставшуюся тарелку (самую большую) в исходную колонку A в целевую колонку C.
Переместите n-1 тарелок на промежуточной колонке B в целевую колонку C.


move(3,"A","B","C");

/**
 * 汉诺塔问题
 * @param dish 盘子个数(也表示名称)
 * @param from 初始柱子
 * @param temp 中介柱子
 * @param to   目标柱子
 */
public static void move(int dish,String from,String temp,String to){
    if(dish == 1){
        System.out.println("将盘子"+dish+"从柱子"+from+"移动到目标柱子"+to);
    }else{
        move(dish-1,from,to,temp);//A为初始柱子，B为目标柱子，C为中介柱子
        System.out.println("将盘子"+dish+"从柱子"+from+"移动到目标柱子"+to);
        move(dish-1,temp,from,to);//B为初始柱子，C为目标柱子，A为中介柱子
    }
}

move(dish-1,from,to,temp);//A — исходный столбец, B — целевой столбец, C — промежуточный столбец Здесь вам нужно поставить все тарелки до n-1 в столбец B и, наконец, поставить n-ю тарелку в столбец C.
move(dish-1,temp,from,to);//B — начальный столбец, C — целевой столбец, A — промежуточный столбец В это время B становится начальным столбом, а A становится целевым столбом. Поместите предыдущие n-1 пластин в целевой столбец C.

распечатать результат:

конец статьи

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

подучить английский

JRE Java Runtime Environment (Java Runtime Environment), набор сред, необходимых для запуска программ JAVA, включая стандартные реализации JVM и основные библиотеки классов Java.
JSDK Java Software Development Kit, эквивалентный JDK и J2SE.
JDK Java Development Kit (Java Development Kit): включая среду выполнения, инструменты компиляции и другие инструменты, исходный код и т. д., в основном эквивалентные J2SE.
Спецификация API J2ME Java 2 Micro Edition (JAVA2 Lite) основана на J2SE, но была изменена, чтобы соответствовать отдельным требованиям продукта. J2ME позволяет легко применять программы JAVA к небольшим устройствам, таким как телефонные карты и пейджеры.Он включает в себя два типа компонентов, а именно конфигурацию и профиль.

Добро пожаловать в публичный аккаунт:Программирование кодераПолучайте последние оригинальные технические статьи и соответствующие бесплатные учебные материалы и изучайте технические знания в любое время и в любом месте!

Справочная статья:

Блог Woohoo.cn на.com/so ocean/afraid/8…

Woohoo.now A magic.net/library is/VE…