Форум программистов, компьютерный форум CyberForum.ru

Нахождение целых корней многочлена методом Горнера - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.69
С@talina
0 / 0 / 0
Регистрация: 27.09.2012
Сообщений: 5
28.09.2012, 17:02     Нахождение целых корней многочлена методом Горнера #1
Здравствуйте, помогите мне разобраться с одной проблемой. Мне надо написать программу, которая находит целые корни многочлена по схеме Горнера, через делите свободного члена. Программа считает, но в ответе постоянно выдает ответ "нет".
Программа:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//---------------------------------------------------------------------------
#include <iostream>
#include <conio.h>
#include <vcl.h>
#include <tchar.h>
#include <vcl.h>
#pragma hdrstop
 
//---------------------------------------------------------------------------
#pragma argsused
using namespace std;
char bufRus[256];
 
char *Rus(const char *text)
{
    CharToOem(text, bufRus);
    return bufRus;
}
 
int main(int argc, char *argv[])
{
    register unsigned int i;
    unsigned int n;
 
    cout << Rus("Введите количество элементов: ");
    cin >> n;                        //4
 
    if (n < 1) {
        cerr << Rus("Требуется хотя бы два элемента.") << endl;
        return EXIT_FAILURE;
    }
 
    double *a = new double[n];
    double *b = new double[n];
 
    cout << Rus("Введите делитель свободного члена: ");
    double c;
    cin >> c;                        // 2
 
    cout << Rus("Введите исходн. элем.:") << endl;
    for (i = 0; i < n; i++)
        cin >> a[i];
 
    cout << endl;                // 1 -1 -8 12
 
    /* Рисуем верхнюю рамку */
    for (i = 0; i < n; i++)
        cout << "+-------";
    cout << "+" << endl;
 
    /* Выводим исходные элементы */
    for (i = 0; i < n; i++)
        cout << "| " << a[i] << "t";
    cout << "|" << endl;
 
    /* Снова рамка */
    for (i = 0; i < n; i++)
        cout << "+-------";
    cout << "+" << endl;
 
    /* По условию, первый элемент b равен первому элементу a */
    b[0] = a[0];
    cout << "| " << *b << "t";
    for (i = 1; i < n; i++) {
        b[i] = b[i - 1] * c;
        /* В этом месте b[i] будет равно значению, записываемому во вторую строчку */
        b[i] += a[i];
        cout << "| " << b[i] << "t";
    }
    cout << "+" << endl;
 
    /* И ещё одна завершающая рамка */
    for (i = 0; i < n; i++)
        cout << "+-------";
    cout << "+" << endl << endl;
    if (b[n - 1] == 0)
        cout << Rus("Ответ: ") << c << endl;
    else
        cout << Rus("Ответ: нет");
    delete[]b;
    delete[]a;
    getch();
}
 
//---------------------------------------------------------------------------
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.09.2012, 17:02     Нахождение целых корней многочлена методом Горнера
Посмотрите здесь:

C++ Нужен исходник с++(Нахождение корней уравнения методом обратного интерполирования)
Программа нахождения корней многочлена методом хорд C++
C++ Вычисление корней многочлена
Нахождение корней уравнения C++
C++ Вычисление значений многочлена по схеме Горнера методом сдваивания
Нахождение корней уравнения методом обратного интерполирования C++
Нахождение корней уравнения методом обратного интерполирования C++
Нахождение корней методом Ньютона C++
Нахождение комплексных корней методом Ньютона C++
C++ Написание рекурсивной функции вычисления многочлена по схеме Горнера
Вычислить значение многочлена, воспользовавшись схемой Горнера C++
C++ Нахождение корней НУ в С++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
 Аватар для Catstail
21675 / 10399 / 1687
Регистрация: 12.02.2012
Сообщений: 17,334
28.09.2012, 21:29     Нахождение целых корней многочлена методом Горнера #2
Два раза просмотрел код... Рисование рамок, ввод и вывод вижу. А где же собственно решение?
Buckstabue
 Аватар для Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
28.09.2012, 21:39     Нахождение целых корней многочлена методом Горнера #3
У меня кое-где сохранился код, вроде нормально работает, но он под заточен под контейнеры Qt. Времени нет его на STL переписывать, может, сама разберешься или кого сведующего попросишь?
Там многие qt данные "затипедфены" и по идее не так много работы надо произвести, чтобы перевести на простой C++
gorner.hpp
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef GORNER_HPP
#define GORNER_HPP
 
#include <QList>
#include <QString>
 
typedef QList<qint64> CoefList;
typedef CoefList RootList;
 
namespace gorner
{
/* getRoots() возвращает список корней многочлена.
   В строке inputStr задаются коэффициенты многочлена - целые числа,
   разделенные пробельными символами */
RootList getRoots(QString inputStr);
// а сюда передается список коэффициентов от самого страшего к младшему
RootList getRoots(const CoefList& coefList);
// возвращает остаток от деления многочлена с коэффициентами coefList на (x - x0)
qint64 getRest(const CoefList& coefList, const qint64& x0);
}
#endif // GORNER_HPP

gorner.cpp
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include "gorner.hpp"
 
#include <QtCore>
 
RootList gorner::getRoots(QString inputStr)
{
   QTextStream txtStream(&inputStr);
   CoefList coefList;
   qint64 tmp;
 
   while (!txtStream.atEnd())
   {
      txtStream >> tmp;
      coefList.push_back(tmp);
   }
 
   // избавляемся от лидирующих нулей
   while (!coefList.empty() && coefList.front() == 0)
      coefList.pop_front();
 
   return getRoots(coefList);
}
 
RootList gorner::getRoots(const CoefList& coefList)
{
   RootList rootsList; // список корней
   qint64 a0 = qAbs(coefList.back()); // модуль свободного члена
   const qint64 MAX_A0_DIVISOR = a0 / 2; // максимальный делитель свободного члена
 
   if (coefList.empty())
      // если пустое уравнение
      return RootList();
 
   for (qint64 a0_divisor = 1; a0_divisor <= MAX_A0_DIVISOR; ++a0_divisor)
   {
      if (a0 % a0_divisor != 0)
         // если не делится нацело, то это не корень
         continue;
 
      // проверка корней
      if (getRest(coefList, a0_divisor) == 0)
         rootsList.push_back(a0_divisor);
 
      if (getRest(coefList, -a0_divisor) == 0)
         rootsList.push_back(-a0_divisor);
   }
 
   // проверка на корень самого коэффициента свободного члена
 
   if (getRest(coefList, a0) == 0)
      rootsList.push_back(a0);
 
   if (getRest(coefList, -a0) == 0)
      rootsList.push_back(-a0);
 
   return rootsList;
}
 
qint64 gorner::getRest(const CoefList& coefList, const qint64& x0)
{
   qint64 rest = 0;
 
   for (auto const &i : coefList)
   {
      rest = x0 * rest + i;
   }
 
   return rest;
}
С@talina
0 / 0 / 0
Регистрация: 27.09.2012
Сообщений: 5
01.10.2012, 16:11  [ТС]     Нахождение целых корней многочлена методом Горнера #4
А может есть у кого-нибудь на C++?
CableGuy
 Аватар для CableGuy
14 / 14 / 1
Регистрация: 29.03.2012
Сообщений: 41
01.10.2012, 16:21     Нахождение целых корней многочлена методом Горнера #5
Схема Горнера(
Вот, недавно создавалась подобная тема, там я выложил код программы и прокомментировал её.
Buckstabue
 Аватар для Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
01.10.2012, 17:12     Нахождение целых корней многочлена методом Горнера #6
Немного допилил то стандартного C++. Допустим нам надо решить уравнение x^2 + 2*x + 1 = 0, тогда в троке ввода надо ввести "1 2 1", а если надо решить x^3 - 1 = 0, надо ввести "1 0 0 1", т.к. мы по сути решаем 1 * x^3 + 0*x^2 + 0*x + 1
Сам код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <string>
#include <sstream>
#include <cstdlib>
#include <list>
 
typedef std::list<long> CoefList;
typedef CoefList RootList;
 
/* getRoots() возвращает список корней многочлена.
   В строке inputStr задаются коэффициенты многочлена - целые числа,
   разделенные пробельными символами */
RootList getRoots(const std::string& inputStr);
// а сюда передается список коэффициентов от самого страшего к младшему
RootList getRoots(const CoefList& coefList);
// возвращает остаток от деления многочлена с коэффициентами coefList на (x - x0)
long getRest(const CoefList& coefList, const long& x0);
 
int main()
{
   std::string coefStr;
   RootList rootList;
   int n = 0;
 
   std::cout << "введите коэфициенты при неизвестных: ";
   std::getline(std::cin, coefStr);
 
   rootList = getRoots(coefStr);
 
   if (rootList.empty())
   {
      std::cout << "Целых корней нет." << std::endl;
   }
 
   n = 0;
   for (RootList::const_iterator i = rootList.begin(); i != rootList.end(); ++i)
   {
      n++;
      std::cout << "x" << n << " = " << *i << std::endl;
   }
 
   return 0;
}
 
RootList getRoots(const std::string& inputStr)
{
   std::istringstream strStream(inputStr);
   CoefList coefList;
   long tmp;
 
   while (strStream >> tmp)
   {
      coefList.push_back(tmp);
   }
 
   // избавляемся от лидирующих нулей
   while (!coefList.empty() && coefList.front() == 0)
      coefList.pop_front();
 
   return getRoots(coefList);
}
 
RootList getRoots(const CoefList& coefList)
{
   RootList rootsList; // список корней
   long a0 = abs(coefList.back()); // модуль свободного члена
   const long MAX_A0_DIVISOR = a0 / 2; // максимальный делитель свободного члена
 
   if (coefList.empty())
      // если пустое уравнение
      return RootList();
 
   for (long a0_divisor = 1; a0_divisor <= MAX_A0_DIVISOR; ++a0_divisor)
   {
      if (a0 % a0_divisor != 0)
         // если не делится нацело, то это не корень
         continue;
 
      // проверка корней
      if (getRest(coefList, a0_divisor) == 0)
         rootsList.push_back(a0_divisor);
 
      if (getRest(coefList, -a0_divisor) == 0)
         rootsList.push_back(-a0_divisor);
   }
 
   // проверка на корень самого коэффициента свободного члена
 
   if (getRest(coefList, a0) == 0)
      rootsList.push_back(a0);
 
   if (getRest(coefList, -a0) == 0)
      rootsList.push_back(-a0);
 
   return rootsList;
}
 
long getRest(const CoefList& coefList, const long& x0)
{
   long rest = 0;
 
   for (CoefList::const_iterator i = coefList.begin(); i != coefList.end(); ++i)
   {
      rest = x0 * rest + (*i);
   }
 
   return rest;
}
Yandex
Объявления
01.10.2012, 17:12     Нахождение целых корней многочлена методом Горнера
Ответ Создать тему
Опции темы

Текущее время: 06:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru