Олимпиадные задачи по программированию.

Если вспомнить, что признаком деления на 9 в десятичной системе счисления является делимость на 9 суммы цифр числа действительно, пусть есть число

S = a[n]*10ⁿ + a[n-1]*10^(n-1) + ... + a[1]*10 + a[0].
S mod 9 = (a[n]*(10ⁿ-1)+a[n] + a[n-1]*(10^(n-1)-1)+a[n-1] + ... + a[1]*(10-1)+a[1] + a[0]) mod 9

А так как 10^k - 1 делится на 9 нацело, то и

S mod 9 = (a[n] + ... +a[1] +a[0]) mod 9,

и т.д.), то аналогично получаем, что признаком деления на 15 в системе счисления с базисом 16 будет делимость на 15 суммы всех шестнадцатеричных цифр числа.
Мы разбиваем двоичное число справа налево на тетрады, которые однозначно можно преобразовать в шестнадцатеричные цифры, находим их сумму и делим ее на 15. Если остаток 0, то введенное число делится на 15, иначе - нет.

[Назад]

Разумеется, можно непосредственно вычислить это число в десятичной системе счисления, после чего разделить его на m, но в этом случае придется представлять число в виде (например) массива цифр и моделировать операции над этим числом. Существует другой простой алгоритм.
В системе счисления с основанием K число представляется в виде

a[n]*Kⁿ + a[n-1]*K^(n-1) + ... +a[0]*K⁰.

Найдем остаток от деления его на m (остаток от деления a на b обозначим a mod b):

(a[n]*Kⁿ + a[n-1]*K^(n-1) + ... +a[0]*K⁰) mod m =
mod m = =

Это следует из следующих соображений:

пусть Kⁱ mod m=t, тогда Kⁱ =p*m+t, и
(a[i]*Ki) mod m = (a[i] * (p*m+t)) mod m =
= (a[i]* p*m) mod m + (a[i]*t) mod m =
= (a[i] * (Ki mod m)) mod m,

при этом для любых чисел b[i] выполняется

Отметим также очевидное равенство

Ki mod m =[(K(i-1) mod m) * K] mod m,
т.к. если K(i-1) = p*m+t, то K(i-1) mod m = t,
Ki = p*m*K+t*K и Ki mod m = t*K mod m =
= [(K(i-1) mod m)*K] mod m.

Запись этого алгоритма (тут a[i] - K-ичные цифры числа):

s:=0; t:=1;
for i:=0 to n do
begin
s:=(s+a[i]*t) mod m;
t:=t*K mod m;
end;

В переменной S после окончания работы алгоритма будет храниться искомый остаток.

[Назад]

Задача решается также, как и предыдущая:
N mod K =
где (s+1)! mod K =

Алгоритм запишется следующим образом:
остаток:=0;
faktorial:=1;
for i:=1 to s+1 do
begin
остаток:=(остаток+(d[i-1] mod k)*faktorial) mod k; faktorial:=(faktorial * ((i+1) mod k)) mod k;
end;

В переменной остаток после выхода из цикла будет искомое значение.

[Назад]

Воспользуйтесь тем, что

U[1] + U[1] = U[2], (1)
U[i] + U[i] = U[i] + U[i-1] + U[i-2] = U[1+1] + U[i-2], (2)
U[i] + U[i-1] = U[i+1]. (3)

Суммируем числа A и B поразрядно, используя приведенные выше правила, начиная со старших разрядов. После применения любого из правил опять начинаем просмотр числа со старших разрядов.
Проведем суммирование чисел '10101' и '100' из задачи.
10101
+ 100

[Назад]

Алгоритм следующий:

cnt:=0; cnt - счетчик единиц в i.
while (i<>0) do цикл повторяется число раз, равное
begin числу единиц в i. " Убираем " крайнюю
i:=(i-1) and i; справа единицу в двоичной записи
cnt:=cnt+1; числа.
end;
Пример:
110 = i
101 = i-1

[Назад]

Пусть a(k) - k-ый член последовательности.

Рассмотрим последовательность, формируемую по следующему правилу:

ряд

получаем приписыванием к этой последовательности справа этой же последовательности, но при этом каждый член приписываемой части увеличивается на единицу. Получаем

Докажем, что a(k) есть сумма единиц в двоичном представлении числа k.

Доказательство проведем по индукции. Для a(0)=0 это справедливо. Пусть предположение справедливо для всех a(i),

0<=i<=2^(k-1)-1 (т.е. для всех чисел i, состоящих из не более чем k-1-го двоичных разрядов). Тогда в двоичном разложении числа l, 2^(k-1)<=l<2^k, в k-ом разряде появляется добавочная единица, и поэтому

ч.т.д.

Возьмем a(i) mod 3, и получим число, стоящее на i-ом месте в последовательности, описанной в условии задачи.

Для того, чтобы найти a(i), необходимо, по доказанному, сосчитать количество единиц в двоичной записи числа i - см. задачу 5.

[Назад]

Будем менять местами содержимое переменных A и B. Существует несколько способов сделать это.

1.

Операция XOR над двумя переменными в машине реализуется как побитовая операция над двоичным представлением чисел. Поэтому, в частности, A XOR A = 0, A XOR B = B XOR A, A XOR 0 = A.

[Назад]

Если рассмотреть битовые представления числа A[i,j], помечающего точку (i,j) и чисел i и j, то обнаруживается, что A[i,j]=i XOR j, откуда получается, что A[i,j] XOR i=j,

A[i,j] XOR j=i.

Покажем, что A[i,j]=i XOR j.

1. Число A[i,j]=i XOR j не встречалось еще ни в строке i, ни в столбце j. От противного: существует такое j', что i XOR j = i XOR j' => i XOR j XOR i = i XOR j' XOR i => j'=j;

2. Пусть существует такое k<i XOR j, что k=i XOR L = j XOR M, и k еще не встречалось в строке i и столбце j (напомним, что по предположению все остальные уже заполненные элементы равны i XOR j, поэтому L>j и M>i).

Тогда, так как M>i, то существует бит с номером t такой, что для любого R>t биты Mr и ir равны, t-ый бит Mt=1, it=0. Но так как j XOR M < j XOR i, то Jt=1.

Так как L>j и L XOR i=j XOR M, то L = j XOR M XOR i. Рассмотрим i XOR M. В силу вышесказанного для любого бита с номером R, R>t, (i XOR M)r=0, а (i XOR M)t=1.

то есть L<j ?! Противоречие.

[Назад]

Так как q<p, то цифры a и b должны лежать в пределах от 0 до q-1.

Распишем A в системе с основанием p:

A= ... = (ap+b)(p^-2) + p^-4 + ...) = { находим сумму бесконечно убывающей геометрической прогрессии со знаменателем p^-2} =

=

Аналогично для A в системе с основанием q выполняется

A=

Получаем

(bq+a)(p²-1)=(ap+b)(q²-1)
a[p(q²-1)-(p²-1)]=b[q(p²-1)-(q²-1)].

Вычисляем выражения в квадратных скобках; обозначим их соответственно u и v: au=bv.

Находим НОД(u,v)=s; обозначим r=u/s, f=v/s.
Получаем
ar=bf,
r и f взаимно просты, следовательно, решениями этого равенства
будут числа
a=fk, b=rk, k=1,2, ... ,
при этом мы берем только те a и b, для которых одновременно выполняется
а) a<>b
b) a<r
c) b<r
Нахождение НОД - см. задачу 12.

[Назад]

Очевидное решение: При попытке непосредственно вычислять координаты концов сегментов, принадлежащих множеству K[n], и определить, принадлежит ли a/b одному из этих сегментов даже для не слишком больших n за счет потери точности при вычислениях и из-за ограниченного числа знаков в машинном представлении чисел с плавающей точкой данный подход дает неверный ответ для большинства входных данных. При больших n вообще будет наблюдаться потеря значимости: число при делении на 3 станет таким малым, что в машине оно будет представляться нулем.

Рассмотрим другой метод решения этой задачи. Так как мы постоянно должны делить сегменты на три части, то это наталкивает на мысль использовать троичную систему счисления и троичные дроби. В первой из удаленных интервалов (1/3,2/3) попадают только те точки

в троичном разложении которых a[1]=1, кроме точки 1/3=0.1000... -правого конца сегмента [0,1/3]. Таким образом, в K [1] остаются все те точки, у которых a[1] <>1, либо a[1]=1, a[2] = a[3] = ...= = 0. Аналогично, в множестве K[i], i>=0, содержатся точки, у которых ни одно из чисел a[j], 1<=j<=i, не равно 1, а также точки, удовлетворяющие условию: a[j]=1, j - фиксировано, 1<=j<=i, a[l]<>1, l<j, и a[l] =0 для любого l>j (то есть, в записи троичной дроби только одна позиция равна 1, после нее все остальные позиции нулевые. Эти дроби соответствуют правым концам сегментов из множества K[i]).

Запись алгоритма на Паскале имеет вид:

x:=a; i:=1;
while (i<=n) or (x<>1) or (a<>0) do
begin
a:=a*3 mod b;
x:=a*3 div b;
i:=i+1;
end;
if (x=1) and (a<>0) and (n<>0)
then writeln(' Не принадлежит') else writeln(' Принадлежит');

[Назад]

                 Нас интересуют точки решетки (с целыми координата-
  *              ми) в первом квадранте, попадающие внутрь круга
  * * *          радиуса  (n  в  степени  1/2). Интересующее нас
  * * * *        множество (назовем его X) состоит из  объедине-
  * * * *        ния  вертикальных  столбцов  убывающей  высоты.
  * * * * *      Идея решения состоит в  том,  чтобы  "двигаться
вдоль  его  границы",  спускаясь  по  верхнему  его краю, как по
лестнице. Координаты движущейся точки  обозначим  .  Введем
еще одну переменную s и будем поддерживать истинность такого ус-
ловия:
      находится сразу над k-ым столбцом;
     s - число точек в предыдущих столбцах.

     Формально:
l  - минимальное среди тех l >= 0, для которых  не принад-
    лежит X;
s - число пар натуральных x, y, для которых x < k и   при-
    надлежит X.
Обозначим эти условия через (И).
  k := 0; l := 0;
  while "<0,l> принадлежит X" do begin
  | l := l + 1;
  end;
  {k = 0, l - минимальное среди тех l >= 0,
   для которых  не принадлежит X }
  s := 0;
  {инвариант: И}
  while not (l = 0) do begin
  | s := s + l;
  | {s - число точек в столбцах до k-го включительно}
  | k := k + 1;
  | {точка <k,l> лежит вне X, но,  возможно,  ее  надо сдвинуть
  |    вниз, чтобы восстановить И }
  | while (l <> 0) and ("<k, l-1> не принадлежит X") do begin
  | | l := l - 1;
  | end;
  end;
  {И, l = 0, поэтому k-ый столбец и все следующие пусты, а
    s равно искомому числу}

Оценка числа действий очевидна: сначала мы движемся вверх не более чем на (n в степени 1/2) шагов, а затем вниз и вправо - в каждую сторону не более чем на (n в степени 1/2) шагов.

[Назад]

Число вида 2^p-1 * (2^p - 1), в двоичном представлении имеет р единиц и р-1 нулей. Максимальное значение р определяется как

Затем проверяется является ли число совершенным для полученного значения p. Оно является совершенным, если для простого значения p, число 2^p -1 является простым. Если получили несовершенное число, уменьшаем p на 1 и снова проверяем, является ли данное число простым.

Совершенные числа получаются для значений р равных 2,3,5,7,13,17,19,31,61,89,107,127.

[Назад]

Запишем уравнение в виде

sXeAk + pY = nYmAt + rX.

Приравнивая коэффициенты при X,A и Y, получаем:

X se=k
A p=nm (*)
Y sk=nt

Так как коэффициенты в формуле должны быть взаимно простыми, то следует найти НОД чисел k и t (Задача 12). Пусть (k,t)=d. Тогда s*(k/d)=n*(t/d), и числа k/d и t/d являются взаимно простыми, следовательно, n=k/d, а s=t/d.

По (*) находим остальные коэффициенты.

[Назад]

По заданным координатам трех вершин мы можем найти площадь треугольника ABC

Sabc=(bx-ay)/2

Если a=0, то минимальная площадь Smin=b/2, если b=0, то Smin=a/2. Если же обе координаты отличны от нуля, то из алгоритма Евклида для нахождения НОД(a,b)=(a,b), следует существование таких целых x и y, что ABS(bx-ay)=(a,b), и именно эти x и y минимизируют площадь треугольника ABC.

Нахождение НОД - задача 12.

[Назад]

Обозначим S=НОД(V₁,...,V_n). Если V делится нацело на S, то в сосуд с помощью банок можно налить V литров воды, иначе - нет.

[Назад]

  k := n; a := 1; b := 0;
  {инвариант: 0 <= k, f (n) = a * f(k) + b * f (k+1)}
  while k <> 0 do begin
  | if k mod 2 = 0  then begin
  | | l := k div 2;
  | | {k = 2l, f(k) = f(l), f (k+1) = f (2l+1) = f(l) + f(l+1),
  | |  f (n) = a*f(k) + b*f(k+1) = (a+b)*f(l) + b*f(l+1)}
  | | a := a + b; k := l;
  | end else begin
  | | l := k div 2;
  | | {k = 2l + 1, f(k) = f(l) + f(l+1),
  | |  f(k+1) = f(2l+2) = f(l+1),
  | |  f(n) = a*f(k) + b*f(k+1) = a*f(l) + (a+b)*f(l+1)}
  | | b := a + b; k := l;
  | end;
  end;
  {k = 0, f(n) = a * f(0) + b * f(1) = b, что и требовалось}

[Назад]

В переменной стандартного типа такое большое число не поместится. Будем моделировать возведение 2 в степень n вычисляя последовательно 2¹, 2², ... , 2ⁿ, используя массив. В каждой ячейке массива будем хранить по (например) 4 десятичных цифры числа (т.е. в элементе A[1] - 4 последних цифры числа (разряды 0 -3), в A[2] - 4 предпоследних (разряды 4 - 7) и т.д.).

Оценим количество десятичных цифр в числе 2ⁿ, n<=1000. Это 10 000 * log₁₀(2) + 1 < 15 000 цифр. Количество элементов массива возьмем равным 15000/4=3750. Введем переменную Nach, в которой будем хранить индекс элемента массива A, в котором находятся старшие значащие разряды вычисляемого сейчас числа.

[Назад]

Решается, аналогично задаче 18, моделированием вычисления

N¹, N², ... , N^N.

[Назад]

Мы можем представить N! в виде произведения простых сомножителей:

N!=2^A₂*3^A₃*5^A₅*7^A₇*...,

где A_p - показатель степени, с которой простое число р входит в разложение. Видно, что нулей в конце числа столько же, сколько нулей в конце произведения 2^A₂*5^A₅, но так как, очевидно, что A₂>A₅, то количество нулей равно A₅.

Для того, чтобы найти A₅, необходимо вычислить сумму

+... ,

где - целая часть числа,

т.к. каждое пятое число в произведении N! делится на 5, каждое двадцать пятое число еще раз делится на 5, каждое 5³ число, еще раз делится на 5, и т.д. То есть в (*) мы находим, сколько чисел в произведении N! делится на 5. Фрагмент программы выглядит следующим образом :

k:=5;
s:=0;
repeat
s:=s+N div k;
k:=k*5;
until (k>N);

После работы цикла в переменной S будет находиться A5.

[Назад]

Найдем простые множители числа P. Пусть это будут p₁,..., p_K. Для каждого множителя p_I найдем число s_I - степень, с ко торой p_I входит в разложение P на простые сомножители. Как и в задаче 21 найдем максимальные числа m₁, ..., m_K, такие что N! делится на p_I в степени m_I, но не делится на p_I в степени m_I+1.

Получаем для нахождения m следующее уравнение:

,

где R=N!/[(p1^m₁)*(p2^m₂)*...*(pk^m_k)].

Минимальное из чисел m_i div s_i и даст искомую степень M.

Рассмотрим пример:

N=15, P=135.
P=3*3*3*5, p₁=3, s₁=3, m₁=15 div 3 + 15 div (3*3)=6
P₂=5, s₂=1, m₂=3.

Получаем, что M=min{6 div 3, 3 div 1}=2.

Объясните, почему мы не можем применить формулу

M=N div P + N div P² + N div P³ + ... ?

Приведем полностью программу, реализующую этот алгоритм.

{ Условие задачи.
На входе программе даются два числа N и P. Программа на выходе должна дать такое максимальное число M, что N! делится на P в степени M, но не делится на P в степени M+1.

1. Числа N и P так велики, что нет смысла считать значение N!.
2. Числа N и P являются натуральными.
}

uses crt;
const
max_long = 2147483647;
var
n,p,i,stp,m,mn,km : longint;
flag : boolean;
ch : char;
{ Функция howmany считает, сколько раз в разложении числа n!
присутствует множитель mn.
}
function howmany(mn,n:longint):longint;
var
pr1,pr2,pr3 : longint;
begin
pr1:=mn; pr2:=0; pr3:=1;
while pr3<>0 do
begin
pr3:=trunc(n/pr1);
pr1:=pr1*mn;
pr2:=pr2+pr3
end;
howmany:=pr2
end;
{ Функция st находит степень множителя mn в разложении числа p на простые множители }
function st(mn:longint; var n:longint):longint;
var
prom: longint;
begin
prom:=0;
while (n mod mn)=0 do
begin
inc(prom);
n:=n div mn
end;
st:=prom
end;
begin
clrscr;
while true do
begin
write('Введите число N и P => '); read(n,p); { ввод }
if p<>1 then { если p=1 то число m }
begin { не существует }
m:=max_long;
i:=2;
flag:=true;
repeat
stp:=st(i,p); { stp после присваивания будет равно числу }
if (stp<>0) then { вхождений множителя i в разложении числа p }
begin { на простые множители. Если stp<>0, то km будет равно числу вхождений множителя i }
km:=howmany(i,n);{ в разложении числа n! на простые множители }
if (trunc(km/stp)<m) then { если km/stp меньше минимального отношения, то сохраняем это значение.}
Begin
m:=trunc(km/stp);
if m=0 then flag:=false
end;
end;
if i=2 then i:=3 else inc(i,2);
until (i>p) or (not flag);
writeln('Число M равно ',m)
end
else
writeln('Число M не существует.');
write('Продолжить ? (y/n) ');
repeat
while keypressed do ch:=readkey;
ch:=readkey;
case ch of
'Y','y': writeln('y');
'N','n': begin writeln('n'); exit end
end;
until ch in ['N','n','Y','y'];
end;
end.

{ Описание задачи.

Если взять два любых натуральных числа a и b, то a будет делиться на b, если все степени множителей при разложении числа a на простые множители больше либо равны аналогичных степеней, получаемых при разложении числа b.

Пример :

120 = 2*2*2 * 3 * 5
40 = 2*2*2 * 5
120 делится на 40

Следовательно, n! делится на p в степени m, если степень любого простого число mn (2<=mn<=p) в разложении числа n! на простые множители больше, чем в аналогичном разложении числа p в степени m.

Если F(i,p) - степень простого числа i в разложении числа p на простые множители, то F(i,p^m)=F(i,p)*m.

Отсюда алгоритм решения :

Степень m будет равна целой части от минимального отношения степени простого числа i в разложении n! к степени числа i в разложении числа p, где 2<=i<=p.

Алгоритм разложения числа р на простые множители достаточно

прост. Основную трудность представляет алгоритм разложения числа n!.

алгоритм степень_простого_числа_в_разложении_числа_n! (нат n,mn,s,k)
дано n,mn
надо s
нач
s:=0
k:=mn
пока [n/k]>0
нц
s:=s+[n/k]
k:=k*mn
кц
кон.

[Назад]

Воспользуемся тем, что для n>=4 выполняется неравенство n<=(n-2)*2, т.е. разбивать число на слагаемые, большие 3, не имеет смысла. Выделяем из числа n слагаемые-двойки, пока не получим остаток меньший либо равный 3 (остаток может быть либо 3, либо 2). Так как 2*2*2<3*3, то заменим каждые три двойки на две тройки. По лученное разложение и является искомым.

Разберите самостоятельно случаи

1) когда необходимо максимизировать произведение, и слагаемые в разложении числа n должны принадлежать промежутку [A,B], A и B вводятся пользователем.

2) когда необходимо минимизировать произведение, и слагаемые в разложении числа n должны принадлежать промежутку [A,B], A и B вводятся пользователем.

[Назад]

Если S>=4 то существуют единственные S₁ и S₂, такие что

S=S₁*S₂=S₁+S₂.

Более того, наименьшее из S₁ и S₂ больше 1 и <=2:

и

1<S₁=(S-)/2<=2.

Итак, если r<4 то разложение на множители закончено, иначе проводим разложение r на два множителя, один из них <=2 (и тем более <4 ), если другой <4 , то процесс закончен, иначе повторяем факторизацию S до тех пор, пока не получим искомое разложение.

[Назад]

Из теоремы Виета получаем, что X₁*x₂*x₃*x₄*x₅=-A(0)/A(5),

откуда следует, что число x_i должно быть делителем A(0)/A(5). Находим все делители A(0)/A(5)=R (Если A(0)=A(1)=...=A(i)=0, то i+1 корень уравнения равен 0. Мы делим уравнение на x⁽ⁱ⁺¹⁾, дальше ищем делители числа r=A(i+1)/A(5)).

i:=1;
пока i<=R повторять
если R делится нацело на i
то проверить, являются ли числа +i
и -i корнями полинома
i:=i+1
конец пока

[Назад]

Пусть m/n - текущая несократимая дробь. Покажем, как найти следующую по значению дробь. Понятно, что она будет среди несокра тимых дробей вида k/р, где р может принимать значения от 2 до 15. Учитывая условие k/р > m/n можно для каждого р прямо вычислять ми нимальное значение k следующим образом:

При этом каждая дробь k/р, полученная описанным выше образом, несократима.

[Назад]

Это условие - равенство нулю суммы всех чисел. Мы всегда можем "перетащить" с помощью последовательности ходов все ненулевые числа, помечающие вершины, в одну какую-либо вершину. Если сумма всех чисел равна 0, то после этих ходов окажется, что во всех вершинах записан 0.

[Назад]

а). Программа вычисления следующая:

P:=a[N]
for i:=N-1 downto 0 do
P:=P*x+a[i];

Посмотрите, как эта схема работает, вручную найдя значение полинома по его коэффициентам и точке x.

b). Решается аналогично.

[Назад]

Продемонстрируем метод нахождения коэффициентов полинома на примере возведения p(x)=(x²+2*x+1) в четвертую степень.

Будем последовательно возводить полином в степени 2, 3,4.

Для второй степени справедливо равенство p(x)*p(x)=(x²+2x+1)*(x²+2x+1)=(x²+2x+1)*x²+ +(x²+2x+1)*2x+(x²+2x+1)*1

Будем складывать коэффициенты у одинаковых степеней x, выписывая коэффициенты полинома первой степени с соответствующим сдвигом и умножаем на коэффициент:

выписывая со сдвигом коэффициенты полинома степени i, умноженные на соответствующие коэффициенты исходного полинома, а затем складываем их в столбик.

[Назад]

Решается аналогично предыдущей задаче. Рассмотрите полином

p(x)=(x-A[1])*...*(x-A[N])

и вычислите его коэффициенты. На каждом из шагов, в отличие от предыдущей задачи, умножение будет производиться на новый одночлен (x-A[i]).

[Назад]

Рассмотрим следующую задачу:

Разделить полином p(x)=a[n]*xⁿ + ... + a[1]*x+a[0] на v(x)=(x-d), т.е. найти такую константу - остаток r и такое частное s(x)=s[n-1]*x^(n-1)+ ... + s[1]*x+s[0], что
p(x)=s(x)(x)+r.

Делить будем в столбик. Рассмотрим операцию деления полиномов на примере:

Тут r=21, s(x)=3x+8.

Видно, что коэффициент s[n-1] при старшей степени x в s равен коэффициенту при старшей степени x в p, а остальные коэффициенты в s находятся по формулам:

s[t-1]=(-d)*s[t]+p[t];

r=(-d)*s[0]+p[0].

В наглядной форме это можно записать в виде так называемой схемы Горнера:

Тогда проведенное выше деление можно записать в следующем виде:

Вернемся к исходной задаче. Приравняем полиномы: p₀(x)=a[n]*xⁿ+a[n-1]*x^(n-1)+ ... +a[1]*x+a[0]=

=b[n](x-d)ⁿ+ ... +b[1]*(x-d)+b[0].

Находим остаток от деления полиномов справа и слева от знака равенства на (x-d). Слева все слагаемые, кроме последнего, делятся на (x-d) нацело. Поэтому

P₀(x)=(x-d)*p1(x)+b[0].
Получаем, что
P₁(x)=b[n]*(x-d)^(n-1)+ ... +b[2]*(x-d)+b[1].
Аналогично находим b[1]:
P₁(x)=(x-d)*p₂(x)+b[1],
затем по p₂(x) определяем b[2], и т.д., пока не найдем b[n].

Особенно удобно это записывается в виде схемы Горнера (обратите внимание, что в верхней строке записаны коэффициенты p₀, то, что получается в строке ниже - это коэффициенты p₁, к которым также можно применить схему Горнера, находя коэффициенты p₂, и т.д.)

[Назад]

Пусть f(x)=ax⁴+bx3+cx²+dx+e. Выразим f(x+1) через f(x):

f(x+1)=f(x)+(4ax³+(6a+3b)x²+(4a+3b+2c)x+(a+b+c+d)=f(x)+g(x),

где

Поступим аналогично и с g(x): g(x+1)=g(x)+(3Ax²+(3A+2B)x+(A+B+C))=g(x)+h(x), где h(x)=A'x²+B'x+C'.

Далее:

где

Имеем:

Отсюда получаем фрагмент программы:

Итак, на каждое значение, начиная с 5, тратится 5 операций сложения. Остается около 1000 операций на вычисление f(1), f(2), f(3), f(4), для инициализации

P:=p(1); H:=h(2); G:=g(3); (F:=f(4));

и на вычисление A₂:=A". Ясно, что 1000 операций хватит на все эти вычисления.

[Назад]

Вверх по странице, к оглавлению и навигации.