ДС17о08-Рекурсия (1238903)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Carnegie MellonРекурсияАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция8,23 октября,2017Лектор:ДмитрийСеверов,кафедраинформатики608КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771РекурсияСпособконечногоописаниябесконечныхобъектов.¢ Мощныйметодрешениязадачрекуррентнойприроды.¢ Использованиестекадляорганизациинеявногохранениянаборовданных.¢Накладныерасходы,связанныесобращениемфункцииксебе.¢ Экспоненциальныйросттрудоемкостивслучаеопределенияодногозначенияпонесколькимдругим.¢ Сложностьпоискаошибокиверификациипрограмм.¢2n!=1·2·3·4·…·nОтпростогоксложномуx1=1и xn=n·xn-1Отсложногокпростомуn!=n·(n-1)! и1!=1int x=1;for(int i=2;i<=n;i++)x*=i;int f(n)=n>1?n*f(n-1):1;ИтерацииРекурсия3ФормальноепредставлениеПусть:P– рекурсивнаяпроцедура;Si – базовыеоператоры,несодержащиеP;P – композицияоператоров;¢ Тогда:¢P=P[Si,P]¢Средствомсозданиярекурсивныхпрограммявляетсяописаниефункций(процедур,подпрограмм),такприсваиваетсяоператоруимя,спомощьюкоторогоонможетбытьвызван.4КлассификацияиданныеПряморекурсивнаяP=P[Si,P]КосвеннорекурсивнаяP=P[Si,Q]Q=Q[Si,P]Набор локальных объектов, определенных внутри рекурсивной функции,создается заново при каждом вызове такойфункции.Идентификаторы всегда ссылаются намножество переменных, созданноепоследним.5Важно!¢Проблемаокончанияработы.P=P[ Si, if !Bthen P]Наиболеенадежныйспособокончанияработы– связатьсРпараметрn ирекурсивновызыватьРспараметромn-1:P(n)=P[Si, if n>0then P(n-1)]¢Глубинарекурсии.Следуетубедиться,чтоонанетолькоконечна,ноидостаточномала.6ПримерыиспользованиярекурсииприрешениизадачПОИСКПУТИВЛАБИРИНТЕ7своя строкасоздать своюприсвоитьстандартнуюприсвоить своюдобавитьсвоювыбрать символ в саоейравна ли стандартнойравна ли своей8меньше ли своейбольше ли своейизмерить своюнайти свою в своейудалить своювывести своюввести свою9ввести массив своихотметить обратный путьотметить точку путисместиться к началуотметить оставшийся путь10дальшенекудаещё дальшедошлиначатьвывести легендувывести карту111213Разбиениечислаmнаслагаемые65+14+24+1+13+33+2+12+2+22+2+1+11+1+1+1+1+13+1+1+12+1+1+1+1P(6)=1114Разбиениеm наслагаемые £ nQ(m,1)=11+1+…+1+1¢ Q(1,n)=11- " n" n³ m¢ Q(m,n)=Q(m,m)¢ Q(m,m)=1+Q(m,m-1)¢ Q(m,n)=Q(m-n,n)+Q(m,n-1) " n<m¢Разбиения,содержащиеслагаемоеравноеnРазбиения,несодержащиеслагаемоеравноеn1516ЧИСЛАФИБОНАЧЧИИлиотом,чторекурсиюследуетиспользоватьвесьмаосмотрительно…17ВычислениечиселФибоначчиИтеративныйРекурсивныйlong F(int n) {long F(int n) {long a=1,b=1;returndo { a+=b; b=a-b; }n<3 ? 1:F(n-1)+F(n-2);while(--n>2);}return a; }1819ФУНКЦИЯАККЕРМАНАИлиотом,когдарекурсиюнеследуетиспользоватьвообще…20ФункцияАккермана + , = ( − , ),=(, ) = ).

− , (, − )/, , > 0#include <iostream>int A(int m,int n) { return!m ? n+1 : !n ? A(m-1,1) : A(m-1,A(m,n-1)); }void main() { int n,m;cout << "Input m="; cin >> m;cout << "Input n="; cin >> n;cout << "A("<< m << ',' << n << «)= " << A(m,n) <<endl;}21A(2,2)=A(1,A(2,1))m\n012345678…0123456789n+11n+222n+332n+3-34… + , = ( − , ),=(, ) = ). − , (, − )/, , > 022Дерево вычисления функцииА(2,2)2,01,12,11,32,21,51,40,61,20,41,30,51,00,10,21,10,31,20,41,00,21,10,30,11,00,10,2А(2,2)=7 Количество вершин дерева - 27232425Биномиальныекоэффициенты261.Наосновеопределенияint fact(int n) {switch (n) {case 0:case 1: return 1;default: return n*fact(n-1); }}…for(n=0; n<=N; n++) for(k=0; k<=n; k++)cout << fact(n)/fact(k)/fact(n-k) <<(n==k?'\n':' ');272.Наосноверекуррентногосоотношенияint Cnk(int n,int k) {if(!k) return 1;if(!n) return 1;if(n==k) return 1;return Cnk(n-1,k)+Cnk(n-1,k-1);}283.ТреугольникПаскаля11111123401123 136 4 1 4void C(int N) {int *a, i, n;a = new int[++N];a[0]=1; if(N>1) a[1]=1;for(n=3; n<=N; n++) {for(i=n-2,a[n-1]=1; i>0; i--)a[i]+=a[i-1];for(i=0;i<n;i++)cout <<a[i]<<(i==n-1?'\n':' '); }delete a;}2930313233Правильныескобочныевыражения()()()()()() (())()(())()(()) (()()) ((()))343536.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций