18.11.2007, 19:24
общий
это ответ
Здравствуйте, piit!
Общего алгоритма не существует и не надейтесь: люди изобратетельны и могут придумать абсолютно разные последовательности.
Можете посмотреть <a href="http://www.research.att.com/~njas/sequences/">The On-Line Encyclopedia of Integer Sequences</a>.
Существуют общие формулы, которые позволяют найти многочлен степени n-1, который проходит через n точек (x<sub>i</sub>, y<sub>i</sub>).
Например, <a href="http://en.wikipedia.org/wiki/Lagrange_polynomial">Lagrange Polynomial</a>.
Этот многочлен - сумма n дробей в знаменателе которых стоит y<sub>i</sub>(x-x<sub>1</sub>)(x-x<sub>2</sub>)...(x-x<sub>i-1</sub>)(x-x<sub>i+1</sub>)...(x-x<sub>n</sub>),
а в знаменателе (x<sub>i</sub>-x<sub>1</sub>)(x<sub>i</sub>-x<sub>2</sub>)...(x<sub>i</sub>-x<sub>i-1</sub>)(x<sub>i</sub>-x<sub>i+1</sub>)...(x<sub>i</sub>-x<sub>n</sub>).
Если Вы попробуете подставить числа x = x<sub>i</sub> в такую сумму, то вы увидите, что все дроби, кроме одной превратятся в 0, так как у них есть (x - x<sub>i</sub>).
А дробь, у которой нет этого множителя в числителе, равна y<sub>i</sub>.
Если Вы посмотрите ссылки на этой странице там есть и другие формы интерполяционных полиномов.
Эти формулы дают возможность написать полином, но он будет чрезвычайно сложным.
В Вашем случае это будет 5 дробей с 4 скобками в каждом числителе и знаменателе.
В Вашем случае есть более прямолинейный подход, основанный на <a href="http://en.wikipedia.org/wiki/Newton_polynomial">Newton polynomial</a>.
Начинайте считать разницы между последовательными числами.
У Вас это будет 3 5 7 9.
Считайте разности между ними:
2 2 2
Как только Вы увидели ряд с постоянными коэффициентами - это значит, что вы нашли степень Вашего полинома. В нашем случае - 2.
Т.е. Вам надо начать искать выражение в виде an<sup>2</sup>+bn+c.
На самом деле ссылка <a href="http://en.wikipedia.org/wiki/Newton_polynomial">Newton polynomial</a> указывает как напрямую посчитать a, b и с из Ваших данных.
Я особо никогда не вникал, но знаю, что для получения коэффициента при старшем члене надо разделить ту константу, что мы получили (2) на факториал степени (2! в нашем случае).
Т.е. наш многочлен имеет вид n<sup>2</sup>+bn+c.
Если Вы увидели, что ряда с постоянными кофээфифциентами нет, а каждая разность - масштабированный вариант предыдущей строки:
1 3 9 27 81
2 6 18 54 = 2*(1 3 9 27)
то это явный признак, что у Вас геометрическая последовательность.
Но это всё общие правила. Чтобы быстро находить закономерности нужна практика.
В Вашем случае я стал считать разности и увидел 1, 3, 5, 7, 9, ...
Известно, что сумма последовательных нечетных чисел от 1 до 2n-1 равна n<sup>2</sup>.
В Вашем случае 1 выброшен, т.е. формула будет a<sub>n</sub> = a<sub>1</sub> + n<sup>2</sup> - 1.
Тот факт, что сумма последовательных нечетных чисел от 1 до 2n-1 равна n<sup>2</sup> легко доказывается, если заменить
каждое нечётное число 2k-1 в сумме на </span>k<sup>2</sup>-(k-1)<sup>2</sup>.