:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Олимпиадные задачи по программированию » Решения: Арифметика
На правах рекламы
Ремни крепления груза.
  Решения: Арифметика



Решение задачи 1.

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

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

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

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

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

[Назад]


Решение задачи 2.

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

a[n]*Kn + a[n-1]*K(n-1) + ... +a[0]*K0.

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

(a[n]*Kn + a[n-1]*K(n-1) + ... +a[0]*K0) mod m =
mod m = =

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

пусть Ki mod m=t, тогда Ki =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 после окончания работы алгоритма будет храниться искомый остаток.

[Назад]


Решение задачи 3.

Задача решается также, как и предыдущая:
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;

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

[Назад]


Решение задачи 4.

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

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



10 Первые два разряда просто сносятся,
+ 1001 затем применяем правило (2),
+ 01 и добавляем последние два разряда
+ 00 чисел A и B


11001 Для двух первых разрядов применяем правило (3)
+ 01
+ 00


100001
+ 01 Правило (1)
+ 00


100010

[Назад]


Решение задачи 5.

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

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


100 = i and (i-1)

[Назад]


Решение задачи 6.

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

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

a(0)=0;

ряд

a(0)...a(2k-1)

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

0->01->0112->01121223->...

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

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

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

a(l)=1+a(l-2(k-1))),

ч.т.д.

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

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

[Назад]


Решение задачи 7.

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

1.

Оператор

Значение в A

Значение в B

A:=A+B

A+B

B

B:=A-B

A+B

A

A:=A-B

B

A

2. Можно использовать логическую операцию XOR (исключающее или). Таблица истинности для XOR следующая:

1 XOR 1 = 0

1 XOR 0 = 1

0 XOR 0 = 0

0 XOR 1 = 1

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

Оператор

Значение в A

Значение в B

A:=A XOR B

A XOR B

B

B:=A XOR B

A XOR B

(A XOR ) XOR B=A XOR(B XOR B)=A XOR 0 = A

A:=A XOR B

(A XOR B) XOR A=B XOR (A XOR A)=B

A

[Назад]


Решение задачи 8.

Если рассмотреть битовые представления числа 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.

При этом Jt=1, следовательно

(i XOR j XOR M)r = Jr для r>t и
(i XOR j XOR M)t = 0 для r=t,

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

[Назад]


Решение задачи 10.

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

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

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

=

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

A=

Получаем

(bq+a)(p2-1)=(ap+b)(q2-1)
a[p(q2-1)-(p2-1)]=b[q(p2-1)-(q2-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.

[Назад]


Решение задачи 11.

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

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

x=0.a[1] a[2] a[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(' Принадлежит');

[Назад]


Решение задачи 12.

                 Нас интересуют точки решетки (с целыми координата-
  *              ми) в первом квадранте, попадающие внутрь круга
  * * *          радиуса  (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,
   для которых <k,l> не принадлежит 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) шагов.

[Назад]


Решение задачи 13.

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

[(log2N)/2]+1.

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

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

[Назад]


Решение задачи 14.

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

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.

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

[Назад]


Решение задачи 15.

По заданным координатам трех вершин мы можем найти площадь треугольника 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.

[Назад]


Решение задачи 16.

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

[Назад]


Решение задачи 17.

  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, что и требовалось}
  

[Назад]


Решение задачи 18.

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

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

var A: array[1 .. 3750] of word;
    Nach: word;
    I,N,j: word;
begin
    for i:=2 to 3750 do A[i]:=0;
    A[1]:=1; { сначала число в массиве A - это 20=1 }
    read(N); { читаем степень }
    Nach:=2; { индекс первой еще не использованной ячейки }
{ в массиве A }
    for i:=1 to N do
    begin
      Perenos:=0; { перенос в следующий элемент массива A }
      for j:=1 to Nach+1 do
      begin
         A[i]:=A[i]+A[i]+Perenos;
{ складываем 4 текущих разряда друг с другом, }
{ добавляя перенос из предыдущих 4-х разрядов }
          if A[i]>=10000 { если в числе > 4 цифр }
          then begin
            Perenos:=A[i] div 10000; {то формируем перенос}
{ в старшие разряды }
            A[i]:=A[i] mod 10000; { и оставляем в числе }
{ 4 последних цифры }
          end
         else Perenos:=0 { иначе переноса нет }
         end; { к вложенному циклу for j }
         if A[Nach+1]>0 { если был перенос в еще не }
         then Nach:=Nach+1; { использованную ячейку }
{ массива A, то увеличиваем Nach }
      end; { для цикла for i }
{ распечатка }
{ старшая тетрада печатается без ведущих нулей }
     j:=1000; { ищем первую значащую цифру }
     while (A[Nach] div j)=0 do j:=j div 10;
     while j<>0 do begin
       write(A[Nach] div j); { печать цифры }
       A[Nach]:=A[Nach] mod j; { отбрасываем }
       j:=j div 10; { напечатанную цифру }
     end;
     for i:=Nach-1 downto 1 do
       begin
       j:=1000;
       for j:=1 to 4 do { 4 разряда }
         begin
          write(A[i] div j); { печатаем цифру } 
          A[i]:=A[i] mod j; { и отбрасывает ее }
          j:=j div 10;
         end
        end
end. { программы }

[Назад]


Решение задачи 19.

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

N1, N2, ... , NN.

[Назад]


Решение задачи 21.

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

N!=2A2*3A3*5A5*7A7*...,

где Ap - показатель степени, с которой простое число р входит в разложение. Видно, что нулей в конце числа столько же, сколько нулей в конце произведения 2A2*5A5, но так как, очевидно, что A2>A5, то количество нулей равно A5.

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

+... ,

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

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

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

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

[Назад]


Решение задачи 22.

Найдем простые множители числа P. Пусть это будут p1,..., pK. Для каждого множителя pI найдем число sI - степень, с ко торой pI входит в разложение P на простые сомножители. Как и в задаче 21 найдем максимальные числа m1, ..., mK, такие что N! делится на pI в степени mI, но не делится на pI в степени mI+1.

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

,

где R=N!/[(p1m1)*(p2m2)*...*(pkmk)].

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

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

N=15, P=135.
P=3*3*3*5, p1=3, s1=3, m1=15 div 3 + 15 div (3*3)=6
P2=5, s2=1, m2=3.

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

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

M=N div P + N div P2 + N div P3 + ... ?

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

{ Условие задачи.
На входе программе даются два числа 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,pm)=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
 кц
кон.

[Назад]


Решение задачи 23.

Воспользуемся тем, что для 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 вводятся пользователем.

[Назад]


Решение задачи 24.

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

S=S1*S2=S1+S2.

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

S1=(S/2, S2=(S+)/2,

(S-4)2=S2-8*S+16<=S2-4*S<(S-2)2

и

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

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

[Назад]


Решение задачи 25.

Из теоремы Виета получаем, что X1*x2*x3*x4*x5=-A(0)/A(5),

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

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

[Назад]


Решение задачи 26.

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

k=m*p/n+1.

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

m:=0; n:=1
Повторять
    i:=1; j:=1;
    для р:=2 до 15 выполнять
     нц
        k:=m*p div n + 1;
        если k*j < p*i
         то i:=k; j:=p;
        все
     кц
     m:=i; n:=j;
пока i>=j

[Назад]


Решение задачи 27.

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

[Назад]


Решение задачи 28.

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

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

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

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

[Назад]


Решение задачи 29.

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

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

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

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

x4

x3

x2

x1

x0

 

 

 

1

2

1

x2+2x+1

 

2

4

2

 

(x2+2x+1)*2x

1

2

1

 

 

(x2+2x+1)*x2

1

4

6

4

1

 

Получили коэффициенты второй степени полинома. Для третьей степени, поступая аналогично, получаем такую таблицу:

X6

x5

x4

x3

x2

x1

x0

 

 

 

1

4

6

4

1

p(x)*p(x)

 

2

8

12

8

2

 

2x*p(x)*p(x)

1

4

6

4

1

 

 

x2*p(x)*p(x)

1

6

15

20

15

6

1

 

Коэффициенты 4-ой степени:

x8

x7

x6

x5

x4

x3

x2

x1

x0

 

 

1

6

15

20

15

6

1

 

2

12

30

40

30

12

2

 

1

6

15

20

15

6

1

 

 

1

8

28

56

70

56

28

8

1

С произвольным полиномом поступаем так же: последователь-но находим степени 2,3, ..., m. Когда мы знаем коэффициенты полинома в степени i, то вычисляем коэффициенты степени i+1,

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

[Назад]


Решение задачи 30.

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

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

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

[Назад]


Решение задачи 31.

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

Разделить полином p(x)=a[n]*xn + ... + 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.

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

3x2+2x+5 x-2
3x2-6x ..3x+8
....8x+5
....8x-16
.......21

Тут 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].

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

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

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

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

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

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

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

Пример: p(x)=3x2+2x+5, d=-2,

Получаем

3x2+2x+5=3(x-2)2+14(x-2)+21.

[Назад]


Решение задачи 32.

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

f(x+1)=f(x)+(4ax3+(6a+3b)x2+(4a+3b+2c)x+(a+b+c+d)=f(x)+g(x),

где

g(x)=Ax3+Bx2+Cx+D.

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

Далее:

h(x+1)=h(x)+(2A'x+(A'+B'))=h(x)+p(x),

где

p(x)=A"x+B". p(x+1)=p(x)+A".

Имеем:

f(x+4)=f(x+3)+g(x+3)
g(x+3)=g(x+2)+h(x+2)
h(x+2)=h(x+1)+p(x+1)
p(x+1)=p(x)+A".

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

< BLOCK 1 >

x:=5;
repeat
P:=P+A2;
H:=H+P;
G:=G+H;
F:=F+G;
writeln(x,F);
x:=x+1;
until x=10001;

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

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

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

[>]