Рекуррентные уравнения

Question

Учитывая проблему, как придумать рекуррентное уравнение?

Например: Пусть S будет набором n>0 различных целых чисел. Предположим, что n является степенью 3. В троичном сравнении можно сравнить три числа из множества S и закажите их от самого большого до самого маленького.

Опишите эффективный алгоритм, который использует как можно меньше троичных сравнений, чтобы найти наибольшее число в наборе S.

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

T(n) = 3T(n/3)+1

и другие студенты придумывают что-то еще.

В общем, что искать при поиске рекурсии для проблемы?

Answer 1

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

Я думаю, что ваш ответ правильный. Как ты добрался до ответа? Можете ли вы объяснить процесс, которым вы следовали?

Вот как бы я это сделал:

Вы можете разбить задачу, разбив целые числа на три меньшие группы одинакового размера. Предположим, вы знаете, как найти максимум каждой меньшей группы в T (n / 3), а затем с помощью своего троичного оператора сравнения найти максимум трех максимумов за один дополнительный шаг (давая +1). Это тогда общий максимум. Это дает повторяющиеся отношения, которые вы описали. Вам также нужно определить базовый случай: T (1) = 0 или T (3) = 1. Это не доказывает, что это оптимально, но я думаю, вы можете доказать, что он использует другой аргумент.

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