На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS RSS
>  Форум на Исходниках.RU
       Программирование
         Алгоритмы
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишите свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, esperanto
   Новое голосование

> Корни полинома, Надо исходники на C++
Mtr
Сообщ. #1, 16.12.03, 20:55
Unregistered

Мне нужно находить все корни (в том числе и комплексные) полинома с хотя бы вещественными коэффициентами.
Подскажите пожалуйста где взять исходники на C++.
freeuser
Сообщ. #2, 17.12.03, 01:47
Member
**
Профиль · PM

Рейтинг (т): 3

Цитата (Mtr @ 16.12.03, 23:55)
Мне нужно находить все корни (в том числе и комплексные) полинома с хотя бы вещественными коэффициентами.
Подскажите пожалуйста где взять исходники на C++.

посмотри
может поможет.
вроде тоже полином. мать его так :)
Прикреплённый файл: Прикреплённый файл____2.zip (21.12 Кбайт, скачиваний: 194)
tserega
Сообщ. #3, 17.12.03, 08:51

Profi
*****
Профиль · PM

Поощрения: 1 Dgm
Рейтинг (т): 80

Только сегодня сдал лабу. Правда, ищет только действительные корни, но строит и график.
#include <iostream.h>
#include <conio.h>
#include <math.h>
#include <graphics.h>
#include <stdlib.h>

#define maxN 6
#define epsilon 0.000001

struct tKoef {
 long double koef;
 int pow;
};

int n;
tKoef a [maxN][maxN];
double roots [maxN];
double derivRoots [maxN];
int derivRootCount;
double tmpRoots [maxN];
int rootCount;

double max(double x, double y) {
 if (x > y) {
  return x;
 } else {
  return y;
 }
}

double min(double x, double y) {
 if (x < y) {
  return x;
 } else {
  return y;
 }
}

long double f(int lev, long double x) {
 long double res = 0.0;
 long i;
 for (i = n; i >= 0; i--) {
  if (a[lev][i].pow > 0) {
   res += a[lev][i].koef * pow((long double) x, (long double) a[lev][i].pow);
  }
  if (a[lev][i].pow == 0) {
   res += a[lev][i].koef;
  }
 }
 return res;
}

double findMaxRoot(int lev) {
 //Меняем все Ai на |Ai|, где 0 <= i <= N
 //Меняем все  Ai*X^i на Ai*X^(n-1), где 0 <= i <= N -1
 //Макс. корень = |A(n-1) + A(n-2) + ... + A(1) + A(0)|/|An|
 double s = 0;
 long i;
 for (i = 0; i < n; i++) {
  s += abs(a[lev][i].koef);
 }
 return (s / fabs(a[lev][n].koef)) + 1;
}

double divide(int lev, double a, double b) {
 //Метод деления отрезка пополам на интервале [a;b]
 double c;
 while (b - a > epsilon) {
  c = (a + b) / 2;
  if (f(lev, c) == 0) {
   break;
  }
  if (f(lev, a) * f(lev, c) < 0) {
   b = c;
  } else {
   a = c;
  }
 }
 return (a + b) / 2;
}

void findRoots(int lev) {
 //Для решения уравнения степени Lev используется
 //корни уравнения производной (Lev-1)
 double maxRoot;
 maxRoot = findMaxRoot(0);
 roots[0] = -maxRoot;
 roots[rootCount - 1] = maxRoot;
 int rc = 0;
 int i;
 for (i = 0; i < rootCount; i++) {
  derivRoots[i] = roots[i];
 }
 derivRootCount = rootCount;
 for (i = 0; i < rootCount - 1; i++) {
  if (f(lev, roots[i]) * f(lev, roots[i + 1]) <= 0) {
   double x = divide(lev, roots[i], roots[i + 1]);
   rc ++;
   tmpRoots[rc] = x;
  }
 }
 tmpRoots[0] = -maxRoot;
 tmpRoots[rc + 1] = maxRoot;
 for (i = 0; i <= rc + 1; i++) {
  roots[i] = tmpRoots[i];
 }
 rc = 0;
 while (roots[rc + 1] - roots[rc] > 2 * epsilon) {
  rc++;
 }
 rootCount = rc + 1;
}

long myFloor(long double x) {
 if (fabs(x) > 10e3) {
  if (x > 0) {
   return 320;
  } else {
   return -320;
  }
 } else {
  long t = floor(x);
  return t;
 }
}

void drawFunction() {
 int gdriver = DETECT, gmode = VGAHI;
 long i;

 initgraph(&gdriver, &gmode, "");
 cleardevice();
 line(0, 240, 639, 240);
 line(320, 0, 320, 479);
 double ratio = min(640/(2 * (abs(roots[1]) + abs(roots[rootCount - 2]) + 1)), 50);
 for (i = 0; i * ratio < 320; i++) {
  line(320 + floor(i * ratio), 237, 320 + floor(i * ratio), 242);
  line(320 - floor(i * ratio), 237, 320 - floor(i * ratio), 242);
  if (ratio > 15) {
   char p [10];
   itoa(i, p, 10);
   if (i != 0) {
    itoa(-i, p, 10);
    outtextxy(325 - floor(i * ratio), 243, p);
   }
   itoa(i, p, 10);
   outtextxy(325 + floor(i * ratio), 243, p);
  }
 }
 for (i = 0; i * ratio < 240; i++) {
  line(317, 240 + floor(i * ratio), 322, 240 + floor(i * ratio));
  line(317, 240 - floor(i * ratio), 322, 240 - floor(i * ratio));
  if (ratio > 15) {
   char p [10];
   itoa(i, p, 10);
   if (i != 0) {
    itoa(-i, p, 10);
    outtextxy(325, 243 + floor(i * ratio), p);
   }
   itoa(i, p, 10);
   outtextxy(325, 243 - floor(i * ratio), p);
  }
 }
 line(320, 0, 317, 3);
 line(320, 0, 323, 3);
 line(639, 240, 636, 237);
 line(639, 240, 636, 243);
 long double dx = 0.01;
 long double x = (-320/ratio);
 moveto(myFloor(320 + x * ratio), 240 - myFloor(f(0, x) * ratio));
 setcolor(YELLOW);
 while (x < 320/ratio) {
  long double fx = f(0, x);
  int y = 240 - myFloor(fx * ratio);
  lineto(myFloor(320 +  x * ratio), y);
  x += dx;
 }
 getch();
 closegraph();
}

int main() {
 cout << "Программа решает уравнение N-ой степени.\n";
 cout << "A(n)*X^(n) + A(n-1)*X^(n-1) + .... + A(1)*X + A(0) = 0\n";
 do {
  cout << "Введите N (1 < N < " << maxN - 1 << "): "; cin >> n;
 } while ((n < 2) || (n > maxN));
 int i;
 for (i = n; i >= 0; i--) {
  cout << "Введите A" << i << ": ";
  cin >> a[0][i].koef;
  a[0][i].pow = i;
 }
 for (i = 1; i < n; i++) {
  for (int j = n - i; j >= 0; j--) {
   a[i][j].koef = a[i-1][j + 1].koef * (j + 1);
   a[i][j].pow = a[i-1][j+1].pow - 1;
  }
 }
 rootCount = 2;
 for (i = 0; i < n; i++) {
  findRoots(n - i - 1);
 }
 cout << "У производной " << derivRootCount - 2 << " корней:\n";
 for (i = 1; i < derivRootCount - 1; i++) {
  cout.precision(5);
  cout << "X = " << derivRoots[i] << "\n";
 }
 cout << rootCount - 2 << " коней у уравнения:\n";
 for (i = 1; i < rootCount - 1; i++) {
  cout << "X = " << roots[i] << "\n";
 }
 getch();
 drawFunction();
 return 0;
}


Сообщение отредактировано: tserega - 17.12.03, 08:55
___________
Р. Беллманн: "Если вы смогли решить задачу, значит это было упражнение; иначе - это научная проблема."
Visitor
Сообщ. #4, 17.12.03, 09:01

Profi
*****
Профиль · PM

Поощрения: 1 Dgm
Рейтинг (т): 22

Запостю и я старую лабу ­http://forum.sources.ru/html/emoticons/smile.gif' border='0' style='vertical-align:middle' alt='smile.gif' />

Тоже только вещественные корни.
Прикреплённый файл: Прикреплённый файлpolyroots.zip (2.68 Кбайт, скачиваний: 246)
___________
В соответсвтии с Первой Поправкой Марселя, "hello, world!" на древнем языке C следует произносить так:
main(t,O){int _=main;char m[]=",!((+hd3+6( e";return O==_?((int(*)())O)(_,t+1),68:
t==_?(*(char*)O?*(char*)O^=((int(*)())t)(O,t):17),O:printf(((int(*)())_)(_,m));}
все здесь
rodion
Сообщ. #5, 18.12.03, 19:19
Master
******
Профиль · PM

Рейтинг (т): 17

Методом Ньютона находишь корень если он комплексный значит ты нашел два второй комплексно сопряженый за тем делишь свой полином поак есть корни
___________
Вот посмотришь на все это... И изобретешь порох
(Румата Эсторский)
Бобёр
Сообщ. #6, 18.12.03, 21:02

бухантер
******
Профиль · PM

Поощрения: 37 Dgm
Рейтинг (т): 119

есть несколько вариантов решения.
Наиболее польное (за которое я бы решился поставить сдаванту зачет):
если полином до 4-ой степени, то искать его корни можно и аналитически, (решение квадратного уравнения, метод Кардано и т.д.). Если же более чем 4-ой - то тут придется изгаляться численно.
___________
Opinions are like assholes, everyone's got one.
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:

> Форум на Исходниках.RU · Алгоритмы

Новое голосование


[ Script Execution time: 0,0941 ]   [ 15 queries used ]   [ Generated: 19.04.14, 14:30 GMT ]  

Rambler's Top100