Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=266231 Thu, 18 Dec 2003 21:02:33 +0000 Корни полинома https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=266231 Наиболее польное (за которое я бы решился поставить сдаванту зачет):
если полином до 4-ой степени, то искать его корни можно и аналитически, (решение квадратного уравнения, метод Кардано и т.д.). Если же более чем 4-ой - то тут придется изгаляться численно. ]]> AQL Алгоритмы https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=266192 Thu, 18 Dec 2003 19:19:26 +0000 Корни полинома https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=266192 rodion Алгоритмы https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=264967 Wed, 17 Dec 2003 09:01:12 +0000 Корни полинома https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=264967 smile.gif

Тоже только вещественные корни. ]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=264958 Wed, 17 Dec 2003 08:51:33 +0000 Корни полинома https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=264958
#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 Алгоритмы https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=264824 Wed, 17 Dec 2003 01:47:17 +0000 Корни полинома https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=264824
Цитата (Mtr @ 16.12.03, 23:55)
Мне нужно находить все корни (в том числе и комплексные) полинома с хотя бы вещественными коэффициентами.
Подскажите пожалуйста где взять исходники на C++.

посмотри
может поможет.
вроде тоже полином. мать его так :)]]> freeuser Алгоритмы https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=264727 Tue, 16 Dec 2003 20:55:53 +0000 Корни полинома https://forum.sources.ru/index.php?showtopic=40801&view=findpost&p=264727 Подскажите пожалуйста где взять исходники на C++. ]]> Mtr Алгоритмы