Процесс последовательных разбиений
Для решения комбинаторных задач часто применяют метод, использованный в предыдущем пункте: устанавливают для данной задачи рекуррентное соотношение и показывают, что оно совпадает с рекуррентным соотношением для другой задачи, решение которой нам уже известно. Если при этом совпадают и начальные члены последовательностей в достаточном числе, то обе задачи имеют одинаковые решения.
Применим описанный прием для решения следующей задачи.
Пусть дано некоторое множество из предметов, стоящих в определенном порядке. Разобьем это множество на две непустые части так, чтобы одна из этих частей лежала левее второй (то есть, скажем, одна часть состоит из элементов от первого до - го, а вторая - из элементов от -го до -го). После этого каждую из частей таким же образом разобьем на две непустые части (если одна из частей состоит уже из одного предмета, она не подвергается дальнейшим разбиениям). Этот процесс продолжается до тех пор, пока не получим части, состоящие из одного предмета каждая. Сколько существует таких процессов разбиения (два процесса считаются различными, если хотя бы на одном шагу они приводят к разным результатам)?
Обозначим число способов разбиения для множества из
предметов через
. На первом шагу это множество может быть разбито
способами (первая часть может содержать один предмет, два предмета,…,
предметов). В соответствии с этим множество всех процессов разбиений распадается на
классов - в
- класс входят процессы, при которых первая часть состоит из
предметов.
Подсчитаем число процессов в
-м классе. В первой части содержится
элементов. Поэтому ее можно разбивать далее
различными процессами. Вторая же часть содержит
элементов, и ее можно разбивать далее
процессами. По правилу произведения получаем, что
- класс состоит из
различных процессов. По правилу суммы отсюда вытекает, что
Таким образом получено рекуррентное соотношение для
. Двоичный поиск, поиск делением пополам. Поиском по числам Фибоначчи называется поиск, основанный на том, что область поиска делится в точках, являющихся числами Фибоначчи.
Содержание раздела
