Центр дистанционного
обучения
Не рекурсивный способ вычисления Числа
Фибоначчиprivate static int fibonacci(int n)
{ |
|
int Fnm1, Fnm2, Fn; |
|
|
|
||
F0 = 0 |
|
if (n <=1) { |
n //F0 = 0 and F1 = 1; |
F1 = 1 |
|
return |
|
|
}else{ |
|
|
F2 = 1 |
|
|
|
|
Fnm2 |
= 0; |
|
F3 = 2 |
|
||
|
Fnm1 = 1; |
||
F4 = 3 |
|
for (int i = 2; i <= n; i++) { |
|
. |
|
|
Fn = Fnm1 + Fnm2; |
. |
|
|
Fnm2 = Fnm1; |
|
|
Fnm1 = Fn; |
|
. |
|
} |
|
|
|
||
|
|
}return Fn |
|
|
|
|
|
|
} |
|
|
online.mirea
.ru
Центр дистанционного
Рекурсивная функцияобучения
• Рекурсивноеfib определение:
ì
ï
ï
ï
Fib(n) = ï
ï
í
ï
ï
ï
ï
ï
î
0, |
if |
n=0 |
1, |
if |
n=1 |
Fib(n- 1)+Fib(n- 2), |
otherwise |
|
•Последовательность: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
|
|
|
||
• Java: |
int fib(int n) |
|
||
{ |
if (n == 0) |
|
||
|
|
|
return 0; |
|
|
|
else if (n == 1) |
|
|
|
|
|
return 1; |
|
|
fib(n-2)); |
else return( fib(n-1) + |
|
|
|
|
|
||
|
} |
|
|
|
|
|
|
online.mirea |
|
|
|
|
.ru |
|
Центр дистанционного
обучения
Использование
Пример:рекурсиина достаточно быстром компьютере, чтобы рекурсивно вычислить F40 занимает почти минуту. Много времени, учитывая, что вычисление
требует только 39 дополнений.
Пример F5
Проблема! Оказывается, что число рекурсивных вызовов тем больше, чем больше число Фибоначчи, которое мы пытаемся вычислить.
Работа программы имеет экспоненциальную скорость роста (экспоненциальная сложность).
online.mirea
.ru
Центр дистанционного
обучения
Проблемы, связанные с рекурсией
Основополагающая проблема использования рекурсивного метода заключается в том, что он выполняет множество избыточных вычислений.
Пример: n=40, F40 = 102,334,155
Общее число рекурсивных вызовов больше - 300,000,000
online.mirea
.ru
Центр дистанционного
обучения
Стратегия - решение
• Припроблемырешении сложных задач рекомендуется решать большие задачи, разбивая их на несколько небольших
подзадач того же типа, но меньшего размера
• Эти небольшие задачи могут быть решены, и
комбинируя(интегрируя) их решения можно получить ответ к исходной большой задаче
• Разбиение задач на подзадачи рекомендуется выполнять,
пока подзадачи не окажутся элементарными
Эта методология называется: поэтапное доработка (Stepwise
Refinement), декомпозиция (Decomposition), разделяй и властвуй (Divide-and-conquer)
online.mirea
.ru
Центр дистанционного
обучения
Основы рекурсии
•Если подзадачи похожи на оригинал - тогда мы сможем использовать рекурсию.
•Существуют два требования:
(1)подзадачи должны быть проще, чем исходная задача.
(2)После конечного числа подразделений на подзадачи, подзадача должны встретиться, которые могут быть решены сразу
online.mirea
.ru
|
|
|
|
|
Центр дистанционного |
|||||||||
Как происходит обучения |
|
|
|
|
|
|
|
|||||||
|
• В Программе MemoryDemo вызывается метод |
|||||||||||||
|
|
three(), |
three() вызывает two(), а two() вызывает |
|||||||||||
public class MemoryDemo |
памятью? |
|
|
|
|
|
|
|||||||
управление |
|
|
|
|
|
|
||||||||
{ |
|
one(). |
|
|
|
|
|
|
|
|
|
|
|
|
• |
Напомним, что параметры и локальные |
|||||||||||||
int I, J, K; |
||||||||||||||
|
|
переменные располагаются в памяти сверху при |
||||||||||||
public static void main(String[] args){ |
|
входе в функцию ( метод в java) и эта память |
||||||||||||
three(); |
|
освобождается при выходе из метода |
||||||||||||
. . . |
• |
Таким образом, стек памяти будет в |
||||||||||||
} |
|
настоящее время выглядит следующим |
||||||||||||
private static void one(){ |
|
образом: |
|
|
|
|
|
|
|
|
||||
float X, Y, Z; |
• |
Activation Records: |
|
|
|
|
|
|
|
|
||||
return; |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
private static void two(){ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
char B, C, D; |
|
|
|
|
---Доступное |
|
|
|
|
|
|
|
||
one(); |
|
|
|
|
пространство--- |
|
|
|
|
|
|
|||
} |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
private static void three(){ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
boolean P, Q, R; |
|
|
|
|
X |
Y |
Z |
|
|
|
|
|
|
|
|
|
|
|
|
One() |
|
|
|
|
|||||
two(); |
|
|
|
|
|
|
|
|||||||
} |
|
|
|
|
B |
C |
D |
|
|
|
|
|
|
|
|
|
|
|
|
Two() |
|
|
|
|
|||||
} |
|
|
|
|
P |
Q |
R |
|
|
|
|
|
|
|
|
|
|
|
|
Three() |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
J |
K |
|
MemoryDemo |
|
||||
|
|
|
|
|
||||||||||
|
|
|
|
|
|
online.mirea |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
.ru |
|||||
|
|
|
|
|
|
Центр дистанционного |
|||||||||||||
|
Что происходит при |
|
|
|
|
|
|
|
|
|
|||||||||
|
рекурсии? |
|
|
|
|
обучен я |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Отличий нет! |
• |
|
Параметрам и локальным |
|
||||||||||||||
|
|
|
переменным по-прежнему |
|
|||||||||||||||
|
|
||||||||||||||||||
|
public class MemoryDemo |
|
|
выделяется память при входе в метод |
|
||||||||||||||
|
|
|
и высвобождается при выходе из |
|
|||||||||||||||
|
{ |
|
|
метода. |
|
|
|
|
|
|
|
|
|
||||||
|
int I, J, K; |
• |
|
Таким образом, во время рекурсии, |
|
||||||||||||||
|
public static void main(String[] |
|
|
||||||||||||||||
|
|
|
стек памяти будет выглядеть |
|
|||||||||||||||
|
args) |
|
|
следующим образом: |
|
|
|
|
|
|
|
|
|||||||
|
{ |
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. . . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
recursiveOne(); |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. . . |
|
|
|
|
. . . |
|
|
|
|
|
|
|
|
|
|
|
||
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
. . . |
|
|
|
|
||||
|
private static void recursiveOne(); |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
{ |
|
|
|
X |
|
|
Y |
|
|
Z |
|
|
RecursiveOne 3 |
|
||||
|
|
|
|
|
|
||||||||||||||
|
float X,Y,Z; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
RecursiveOne 2 |
|
|||||||
|
|
|
|
X |
|
|
Y |
|
|
Z |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
||||||||||
|
. . . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X |
|
|
Y |
|
|
Z |
|
|
RecursiveOne 1 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
recursiveOne(); |
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
|
|
J |
|
|
K |
|
|
MemoryDemo |
|
|
|
|||
|
. . . |
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
online.mirea |
||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
.ru |
||||
РекурсивныйЦентри дистанционногоне
обучения
рекурсивный способы
Пример найдем сумму последовательности целых чисел от 1 to n)
public class SumDemo
{//итеративный способ
public static void main(String args[])
{
int sum;
int n = 10; // может ввести пользователь
sum = iterativeSum(n); System.out.println("Sum = " + sum);
}
private static int iterativeSum(int n)
{
int tempSum = n; while ( n > 1)
{
n--;
tempSum += n; //tempSum = tempSum
+ n
}
return (tempSum);
}
}
public class SumDemo {// рекурсивный способ
public static void main(String args[])
{
int sum;
int n = 10; //could have user input this
sum = recursiveSum(n);
System.out.println("Sum = " + sum);
}
private static int recursiveSum(int n)
{
if (n <= 1) return n;
else return ( n + recursiveSum(n-1));
}
}
online.mirea
.ru
Центр дистанционного
обучения
Формальное представление методов
Используется в Computer Science для получения математически строгого представления набора пользовательских требований (формальных спецификаций).
•Существует два класса таких методов представления
•Нотация ориентированная на представление состояний:
•Примеры (Деревья решений,Конечные автоматы)
•Нотация ориентированная на отношения:
•Примеры (Рекуррентные соотношения, Алгебраические аксиомы)
online.mirea
.ru