мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Предыдущая версия справа и слеваПредыдущая версия
Следующая версия		Предыдущая версия
pascal:recur [09/11/2012 14:55] – ocapascal:recur [16/11/2012 14:23] (текущий) – oca
Строка 1: Строка 1:
 ===== Рекурсия и рекуррентные соотношения ===== ===== Рекурсия и рекуррентные соотношения =====
 +
 +
 +
 +
  
 ==== Рекуррентные соотношения ==== ==== Рекуррентные соотношения ====
  
  
 +Согласно [[http://dic.academic.ru/dic.nsf/enc_physics/4527/%D0%A0%D0%95%D0%9A%D0%A3%D0%A0%D0%A0%D0%95%D0%9D%D0%A2%D0%9D%D0%AB%D0%95| Физической энциклопедии]], **рекуррентные соотношения**(от лат. recur-rens, род. падеж recurrentis - возвращающийся) - однотипные формулы, которые связывают между собой идущие друг за другом элементы некоторой последовательности (это может быть последовательность чисел, функций и т. д.). В зависимости от природы объектов, связанных рекуррентными соотношениями, эти соотношения могут быть алгебраическими, функциональными, дифференциальными, интегральными и т. п. 
 +
 +Короче говоря, мы имеем способ получения некоторой последовательности каких-то (зависит от наших целей и/или желаний) объектов, которые связаны соотношением вида 
 +
 +A[0] = A;
 +
 +A[i] = F(A [i-1]), 
 +
 +где A[0] задаётся отдельно, а F каким-то образом, возможно - неформально, определяет следующий элемент последовательности из предыдущего, уже определённого. 
 +
 +Внимание! Иногда рекуррентные соотношения рассматриваются в расширенном виде A[i] = F(A[0], A[1] ... A[i-1]), т.е. для определения очередного элемента последовательности используются все или несколько предыдущих элементов последовательности. Пример - числа Фибоначчи, где 
 +
 +A[0] = A[1] = 1;
 + 
 +A[i] = A[i-1] + A[i-2];
 +
 +
 +Также "Рекуррентным соотношением называется закономерность, связывающая объект более высокого порядка с объектом меньшего порядка" ([[ http://glaznev.sibcity.ru/1kurs/integr/list3.htm |]])
 +
 +**Ссылки по теме**
 +
 +[[http://www.intuit.ru/department/algorithms/algocombi/7/|
 +intuit: Комбинаторные алгоритмы для программистов 7. Лекция: Рекуррентные соотношения]] - рекуррентные соотношения  для получения комбинаторных объектов.
 +
 +[[http://dic.academic.ru/dic.nsf/ruwiki/503457| Последовательность Падована]]
 +
 +[[http://dic.academic.ru/dic.nsf/ruwiki/638596| Задача Иосифа Флавия]]
  
 ==== Рекурсия ==== ==== Рекурсия ====
 +
 +Рекурсия
 +
 +=== Пример применения рекурсии ===
 +
  
 === Программа, рисующая квадраты от центра (квадрата) === === Программа, рисующая квадраты от центра (квадрата) ===
Строка 17: Строка 53:
 var  var 
   gd, gm: smallint;         gd, gm: smallint;      
-  mx, my, cx, cy:smallint,           +  mx, my, cx, cy:smallint;          
-  x, y, d:smalint;+  x, y, d:smallint;
    
 begin begin
Строка 27: Строка 63:
 {далее все, что Вы хотите нарисовать, например:} {далее все, что Вы хотите нарисовать, например:}
  
-mx := maxX; +mx := getmaxX; 
-my := maxY;+my := getmaxY;
 cx := mx div 2; cx := mx div 2;
 cy := my div 2; cy := my div 2;
Строка 60: Строка 96:
 var  var 
   gd, gm: smallint;         gd, gm: smallint;      
-  mx, my, cx, cy:smallint,           +  mx, my, cx, cy:smallint;           
-  x, y, d:smalint;+  x, y, d:smallint;
      
      
Строка 81: Строка 117:
 {далее все, что Вы хотите нарисовать, например:} {далее все, что Вы хотите нарисовать, например:}
  
-mx := maxX; +mx := getmaxX; 
-my := maxY;+my := getmaxY;
 cx := mx div 2; cx := mx div 2;
 cy := my div 2; cy := my div 2;
Строка 245: Строка 281:
 var  var 
   gd, gm         : smallint;         gd, gm         : smallint;      
-  mx, my, cx, cy :smallint,           +  mx, my, cx, cy : smallint;           
-  x1, y1, x2, y2 : Real; +  x, y, d  : smallint; 
- +  
-procedurue Serp(x1, y1, x2, y2: Real; n: Integer);+procedure Serp(x1, y1, x2, y2: smallint; n: Integer);
 var var
- x1n, y1n, x2n, y2n: Real; + x1n, y1n, x2n, y2n: smallint; 
 + 
 begin begin
  if  n > 0  then   if  n > 0  then 
  begin  begin
- x1n := 2*x1/3 + x2 / 3; + x1n := 2*x1 div 3 + x2 div 3; 
- x2n := x1/3 + 2*x2 / 3; + x2n := x1 div 3   + 2*x2 div 3; 
- y1n := 2*y1/3 + y2 / 3; + y1n := 2*y1 div 3 + y2 div 3; 
- y2n := y1/3+2*y2 / 3; + y2n := y1 div 3   + 2*y2 div 3; 
- Rectangle(Round(x1n), Round(y1n), Round(x2n), Round(y2n));+ Rectangle(x1n, y1n, x2n, y2n);
  Serp(x1, y1, x1n, y1n, n-1);  Serp(x1, y1, x1n, y1n, n-1);
  Serp(x1n, y1, x2n, y1n, n-1);  Serp(x1n, y1, x2n, y1n, n-1);
Строка 268: Строка 304:
  Serp(x1n, y2n, x2n, y2, n-1);  Serp(x1n, y2n, x2n, y2, n-1);
  Serp(x2n, y2n, x2, y2, n-1)  Serp(x2n, y2n, x2, y2, n-1)
- en;+ end;
 end; end;
 + 
 begin begin
         gd := Detect;                    // Автоматическая установка разрешения         gd := Detect;                    // Автоматическая установка разрешения
         gm := DetectMode;         gm := DetectMode;
         initgraph(gd, gm, '');           // Открытие "графического окна"          initgraph(gd, gm, '');           // Открытие "графического окна" 
-        + 
         mx := getmaxX;         mx := getmaxX;
         my := getmaxY;         my := getmaxY;
Строка 285: Строка 321:
         x  := cx;         x  := cx;
         y  := cy;         y  := cy;
- 
    
- Rectangle(x-d, y-d, x+d, x+d); +  
- Serp(x-d, y-d, x+d, x+d, 4);+     Rectangle(x-d, y-d, x+d, x+d); 
 +     Serp(x-d, y-d, x+d, x+d, 4);
         repeat until graphkeypressed;    // Задержка закрытия графического окна до нажатия          repeat until graphkeypressed;    // Задержка закрытия графического окна до нажатия 
                                          // клавиши для завершения работы программы -                                           // клавиши для завершения работы программы - 
Строка 294: Строка 330:
    
         closegraph();                    // закрытие графического окна - не обязательно, но рекомендуемо.         closegraph();                    // закрытие графического окна - не обязательно, но рекомендуемо.
-  + 
 end. end.
 +
  
 </code> </code>