| Предыдущая версия справа и слева
Предыдущая версия
Следующая версия
|
Предыдущая версия
|
bb:redbook:204 [2017/08/30 09:36]
prospero78 [2. Вычисление факториала] |
bb:redbook:204 [2020/10/29 07:08] (текущий)
|
| ====2. Вычисление факториала==== | ====2. Вычисление факториала==== |
| | |
| Для расчёта [[https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB|факториала]] можно пойти родственным путём, что и в прошлом примере, но //рекурсивным// он уже не будет. В **КП** рекурсия разрешена и выполняется процедурой при вызове самой себя (прямо или косвенно). Важно понимать, что серия рекурсивных вызовов никогда не закончится, если не установить ограничитель. При вычислении факториала таким ограничителем служит число, по отношению к которому вычисляется факториал. Очень важно помнить, что факториал растёт //чудовищно// быстро, и чтобы избежать ошибки переполнения, это число не должно быть большим. Ниже, пример рекурсивного вычисления факториала на **КП**. | Для расчёта [[https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB|факториала]] можно пойти родственным путём, что и в прошлом примере, но //рекурсивным// он уже не будет((Вообще, вычисление в настоящем случае факториала через [[https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F|рекурсию]] — довольно //неэффективный// алгоритм. Надо стараться искать обходные пути. Вообще с рекурсией надо быть очень внимательным, так как //неограниченная// рекурсия мгновенно вызовет переполнение стека. На этом принципе работают чуть ли не половина вирусов для **MS Windows**. Можно отдельно почитать статью с множеством технических подробностей на http://codenet.ru/.)). В **КП** рекурсия разрешена и выполняется процедурой при вызове самой себя (прямо или косвенно). Важно понимать, что серия рекурсивных вызовов никогда не закончится, если не установить ограничитель. При вычислении факториала таким ограничителем служит число, по отношению к которому вычисляется факториал. Очень важно помнить, что факториал растёт //чудовищно// быстро, и чтобы избежать ошибки переполнения, это число не должно быть большим. Ниже, пример рекурсивного вычисления факториала на **КП**. |
| |
| Hello11.odc | Hello11.odc |
| как можно вычислить произвольный факториал рекурсией. *) | как можно вычислить произвольный факториал рекурсией. *) |
| |
| IMPORT In, Log, Math; | IMPORT мВв := In, |
| | мЛог := Log; |
| |
| PROCEDURE Факт_Получ (пцФактор: INTEGER): INTEGER; | PROCEDURE Факт_Получ (пцФактор: INTEGER): INTEGER; |
| BEGIN | BEGIN |
| IF пцФактор = 1 THEN | IF пцФактор = 1 THEN |
| Log.String('Достигнуто дно '); Log.Ln; | мЛог.String('Достигнуто дно '); мЛог.Ln; |
| RETURN 1 | RETURN 1 |
| ELSE | ELSE |
| Log.String('пцФактор='); Log.Int(пцФактор); Log.Ln; | мЛог.String('пцФактор='); мЛог.Int(пцФактор); мЛог.Ln; |
| RETURN пцФактор * Факт_Получ(пцФактор - 1); | RETURN пцФактор * Факт_Получ(пцФактор - 1); |
| END; | END; |
| |
| BEGIN | BEGIN |
| Log.String('Введите основание факториала: '); | мЛог.String('Введите основание факториала: '); |
| In.Open; | мВв.Open; |
| In.Int(цБаза); Log.Ln; | мВв.Int(цБаза); мЛог.Ln; |
| Log.String('BEGIN цБаза='); Log.Int(цБаза); Log.Ln; | мЛог.String('BEGIN цБаза='); мЛог.Int(цБаза); мЛог.Ln; |
| цФактор := Факт_Получ(цБаза); | цФактор := Факт_Получ(цБаза); |
| Log.String('f('); Log.Int(цБаза); Log.String(')= '); Log.Int(цФактор); Log.Ln; | мЛог.String('f('); мЛог.Int(цБаза); мЛог.String(')= '); мЛог.Int(цФактор); мЛог.Ln; |
| END Старт; | END Старт; |
| |
| | |
| |
| Обратите внимание, что в этом примере можно было использовать только одну переменную для вычисления факториала, если бы вывод в "Log.Int(f)" выполнялся через вызов "Log.Int(GetFactorial(n))". Соответственно, строку выше можно было бы удалить и отказаться от объявления переменной "f". | Обратите внимание, что в этом примере можно было использовать только одну переменную для вычисления факториала, если бы вывод в ''мЛог.Int(цФактор)'' выполнялся через вызов ''мЛог.Int(Фактор_Получ(пцФактор))''. Соответственно, строку выше можно было бы удалить и отказаться от объявления переменной "пцФактор". |
| |
| Вывод программы представлен ниже: | Вывод программы представлен ниже: |
| |
| | компилируется "TestHello11" 220 0 |
| | Введите основание факториала: |
| | BEGIN цБаза= 6 |
| | пцФактор= 6 |
| | пцФактор= 5 |
| | пцФактор= 4 |
| | пцФактор= 3 |
| | пцФактор= 2 |
| | Достигнуто дно |
| | f( 6)= 720 |
| | |
| Как видно из вывода переменная "n" с каждым вызовом действительно уменьшалась на "1", и это была настоящая рекурсия. :-) | Как видно из вывода переменная ''цБаза'' с каждым вызовом действительно уменьшалась на "1", и это была настоящая ''рекурсия''. :-) |
| |
| ====3. Примечания==== | |
| | |
| [↑] Вообще, вычисление в настоящем случае факториала через рекурсию — довольно неэффективный алгоритм. Надо стараться искать обходные пути. Вообще с рекурсией надо быть очень внимательным, так как неограниченная рекурсия мгновенно вызовет переполнение стека. На этом принципе работают чуть ли не половина вирусов для MS Windows. Можно отдельно почитать статью с множеством технических подробностей на http://codenet.ru/. | |
| |
