Читайте также:
|
Дві рекурсивні функції, розглянуті дотепер, були досить простими. Тому, щоб не склалося неправильне враження про те, наскільки складні рекурсивні функції, представимо наступну, досить просту на перший погляд, двічі рекурсивну функцію, відому як функція Акермана. Функція двічі рекурсивна, якщо сама функція й один з її аргументів визначені через самих себе.
А(М, N}= 
Розбивки цілого
Розбивка позитивного цілого числа М — це представлення М в виді суми цілих чисел. Класична рахункова задача — визначення кількості Р(М} розбивок числа М. Для М=6 розбивками є
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1.
Цікавий спосіб вираження функції Р(М) через іншу функцію Q(M, N), що визначається як число розбивок цілого М із що складаються, не перевищуючими N. Нескладні рекурсивні міркування приводять до наступного:
1. Q(M, 1)=1. Це значить, що існує тільки одна розбивка цілого числа М, у якому найбільший доданок є одиниця, а саме M=1+1+...+1.
2. Q(1, N)=1. Очевидно, існує тільки одна розбивка цілого числа 1 незалежно від величини N найбільшого доданка.
3. Q(M, N)=Q(M, M), якщо M<N. Зрозуміло, що ніяка розбивка М не може містити доданку N, більшого M.
4. Q(M, M}=1+Q(M, М—1). Існує тільки одна розбивка М з доданком, рівним М. Всі інші розбивки М мають найбільший доданок N£M— 1.
5. Q(M, N)=Q(M, N—l}+Q(M—N, N). Це означає, що будь-яка розбивка М з найбільшим доданком, меншим чи рівним N, чи не містить N як доданок — у такому випадку дана розбивка також входить у число Q(M, N— 1), або містить N — при цьому інші доданки утворять розбивка числа М-N.
Рівняння 1÷5 рекурсивно визначають функцію Q(M, N). Вони визначають Р(М), тому що P(M)=Q{M, M).
Дата добавления: 2015-01-30; просмотров: 40 | Поможем написать вашу работу | Нарушение авторских прав |