VPF::[Pascal] Целые корни полинома - Форум программистов

Stroks

Дата 21.12.2006, 21:42 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 18.10.2006

Репутация: 1
Всего: 1

Дан многочлен вида:

x^n + a1*(x^(n-1)) + a2*(x^(n-2)) + .... + a(n-1)*(x^1) + an = 0
Где n - значение степени уравнения, a1...an - коэффициенты, которые задаются пользователем с клавиатуры.
n<=10
Учитывая, что корни данного многочлена находятся в разложении свободного коэффициена (an), выведите на экран все целые корни.

часть алгоритма должна быть такая:
for i:=1 to an do
if mod(an/i)=0 then подставляем это "i" вместо икса в многочлен. Если он при этом значении "i" обращается в ноль, тогда нужно вывести его на экран.

Решите пожалуйста, нужно к утру.

ICQ: 303-72-72-75

Kuvaldis

Дата 22.12.2006, 05:18 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61

Stroks,
Быстрая версия программы, используется схема Горнера, оптимизация по выборке делителей (просмотр только до корень из длины). Оптимизация при проверке на корень.
Коротко поясню.
Сначала проверяем, являются ли 1 и -1 корнями полинома. Это просто, нужно сложить определенным образом коэффициенты.
Допустим, что А - корень.
значит f(x) = (x - A) * q(x)
q(x) - целый полином, значит q(1) и й(-1) - целые числа.
Но тогда f(1) = - (A - 1) * q(1), f(-1) = - (A + 1) * q(-1)
Значит, А - 1 и А + 1 соотвественно делят f(1) и а(-1)

Это значит, что из делителей А (А <> =-1)  свободного члена для проверки и непосредственного вычисления значения нужно выбирать числа, для которых
f(1) /  (A - 1)
f(-1) /  (A + 1)     - целые числа

Теперь сама программа

Код


program mass;

{$APPTYPE CONSOLE}
uses
  SysUtils;

const
    MAX = 11;
Var
   A : Array [1..MAX] of integer; // коэффициенты
   len : integer = 4;             // вводимая степень полинома
   i, i1, i2, j, k : integer;
   count :  integer;     // количество целых корней
   f1 : integer;         // f(1)
   f2 : integer;         // f(-1)
   sign : integer;       // для подсчета f(-1)
   res : integer;        // для схемы Горнера
   root : integer;       // текущий проверяемый корень
Begin
   Writeln('Input polynom degree (max = 10)');
   Readln(len);

   Inc(len);
   // вывод массива
   writeln('Input coeffs:');
   for i := 1 to len do
      read(A[i]);
    
   f1 := 0;
   f2 := 0;
   sign := 1;
   count := 0;

   for i := 1 to len do
      f1 := f1 + A[i];

   for i := len downto 1 do
   begin
      f2 := f2 + A[i] * sign;
      sign := -sign;
   end;

   if (f1 = 0) then
   begin
       Inc(count);
       writeln(count, ' root = 1');
   end;

   if (f2 = 0) then
   begin
       Inc(count);
       writeln(count, ' root = -1');
   end;

   k := Trunc( sqrt( abs(A[len]) ) );

   for i := 1 to k do
   begin
       if (A[len] mod i <> 0) then          // не целый корень
          continue;

       root := i;

       for i1 := 1 to 2 do               // корни: root и len / root
       begin
           for i2 := 1 to 2 do           // меняем знак у корней
           begin
           // корень - 1 должен делить f(1) и корень + 1 должен делить f(-1)
           // причем корни +- 1 уже не учитываем
               if (root = 1) then
                  Break;
                  
               if (f1 mod (root - 1) = 0) and (f2 mod (root + 1) = 0) then
               begin
                   // значение считаем по схеме Горнера
                   // первый член в схеме Горнера совпадает с первым коэфф.
                   res := A[1];

                   for j := 2 to len do
                      res := res * root + A[j];

                   if (res = 0) then      // корень
                   begin
                       Inc(count);
                       writeln(count, ' root = ', root);
                   end;
                end;
                   
               root := -root;
           end;
           root := A[len] div root;
       end;  
   end;


   if (count = 0) then
      writeln('No integer roots');

   Writeln('Press any key to exit');

   readln;
   readln;
end.

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Stroks

Дата 22.12.2006, 23:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 18.10.2006

Репутация: 1
Всего: 1

Не работает. Точнее работает, но неправильно. И то, что ты написал перед программой - непонятно. Ты полагаешь x равным 1 и -1, но говоришь, что корень - это A.
Тогда x нужно оставить.

smile

Это сообщение отредактировал(а) Stroks - 22.12.2006, 23:13

Kuvaldis

Дата 22.12.2006, 23:28 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61

Stroks,

Цитата

Не работает. Точнее работает, но неправильно.

Дай мне тест, на котором программа легла (на моих всех работает)

Цитата

Ты полагаешь x равным 1 и -1, но говоришь, что корень - это A.
Тогда x нужно оставить.

Сначала проверили на корень числа 1 и -1
Но нужно же проверить и остальные делители свободного члена. Поэтому и написано "допустим, что корень - это А". Т.е. неединичный делитель

Это сообщение отредактировал(а) Kuvaldis - 23.12.2006, 00:01

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »