Понятие задачи и подзадачи

При формулировке любой задачи необходимо определить исходные данные, которые мы будем называть параметрами задачи.

 

Например, если мы решаем задачу нахождения корней уравнения второго порядка ах² + Ьх + с = 0, то эта задача определяется тремя параметрами — ко­эффициентами а, Ь и с. Если же мы хотим решить задачу нахождения среднего арифметического некоторого набора чисел, то параметрами задачи будут ко­личество чисел и их значения.

Поставим целью научиться решать задачи, сводя их к решению подзадач. При таком подходе любая задача может быть формализована в виде некото­рой функции, аргументами которой являются такие величины, как: количество параметров; значения параметров.

В том случае, когда благодаря известному значению количества параметр. Поэтому поставленную задачу можно решить следующим образом:

S[0]: = 1;

а[0]: = 1;

for i:=1 to N do

begin

a[i]: = a[i - 1 ]/x; S[i]: = S[i - 1] + a[i] end;

Отметим, что и в этом случае индексы при S и а можно опустить в связи с тем, что для вычисления текущего элемента каждой из таблиц достаточно знать только значение предыдущего элемента.

Соотношения, связывающие одни и те же функции, но с различными аргу­ментами, называются рекуррентными соотношениями или рекуррентны­ми уравнениями.

ПРАВИЛЬНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ

Правильными рекуррентными соотношениями (уравнениями) будем называть такие рекуррентные соотношения, у которых количество или значения аргументов у функций в правой части соотношения меньше соответственно ко­личества или значений аргументов у функций в левой части соотношения. Если аргументов несколько, то достаточно уменьшения хотя бы одного из аргументов.

Еще раз хочется обратить внимание на то, что соотношения должны быть определены для всех допустимых значений аргументов. Поэтому должны быть известны значения функций при начальных значениях параметров.

В приведенных выше примерах соотношения связывали функции только с двумя различными параметрами:S(i) иS(i-1), а такжеa(i) и а(/-1) для любого натурального /. При этом были определены начальные значения S(0) и а(0). Отметим, что без этих начальных значений рекуррентное соотношение

S(i) = S(/-1) +a(i), / £ 1, было бы неправильным, так как оно не определено при / = 1.