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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 62, средняя оценка - 4.69
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
#1

Схема Горнера - C++

15.11.2010, 23:22. Просмотров 7940. Ответов 57
Метки нет (Все метки)

код схемы Горнера
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
/*
 * 6
 * 3
 * 1 3 -2 1 -1 1
 *
 * Ответ: 439
 */
 
#include <stdlib.h>     /** EXIT_FAILURE **/
#include <iostream>
using namespace std;
 
int main( int argc, char *argv[] )
{
    register unsigned int i;
    unsigned int n;
    cout << "Введите количество элементов: ";
    cin >> n;
 
    if ( n < 1 )
    {
        cerr << "Требуется хотя бы два элемента." << endl;
        return EXIT_FAILURE;
    }
 
    double *a = new double [n];
    double *b = new double [n];
 
    cout << "Введите эпсилон: ";
    double eps; cin >> eps;
 
    cout << "Введите " << n << " исходн. элем.:" << endl;
    for ( i = 0; i < n; i++ ) cin >> a[i];
 
    cout << endl;
 
    /* Рисуем верхнюю рамку */
    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] * eps;
        /* В этом месте b[i] будет равно значению, записываемому во вторую строчку */
        b[i] += a[i];
        cout << "| " << b[i] << "\t";
    }
    cout << "+" << endl;
 
    /* И ещё одна завершающая рамка */
    for ( i = 0; i < n; i++ ) cout << "+-------"; cout << "+" << endl << endl;
    cout << "Ответ: " << b[n-1] << endl;
 
    delete []b;
    delete []a;
    return 0;
}
программа на С++, как можно под БорландС переделать.

общаяя задача: Исследование уравнения. Даны натуральное число n и целые числа f0, ... , fn. Исследовать существование целочисленных корней уравнения f0*x^n+f1*x^(n-1)+...+fn=0. Если fn=0, то имеется корень, равный 0; если же fn!=0, то целочисленный корень, если он существует, принадлежит конечному множеству положительных и отрицатльных делителей числа fn. Здесь следует определить подпрограмму, которая по двум заданным числам k и m (m>k>=0) позволяет определить значение наименьшего делителя числа m, превышающего k, а так же подпрограмму вычисления значения многочлена по схеме Горнера : y=(...((f0*x+f1)*x+f2)*x+...+f(n-1)*x+fn

Добавлено через 5 часов 33 минуты
препод будет меня жеско иметь)))
1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2010, 23:22
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Схема Горнера (C++):

Схема горнера - C++
Эта схема основывается на следующем представлении многочлена: p(x) = (( ... ((an*x + an-1)x + an-2)x + ... + a2)x + a1)x + a0 ...

Схема Горнера( - C++
Всем привет, друзья, очень нуждаюсь в вашей помощи.. Я чайник в C++. Очень нужно решить задачу, буду премного благодарен:

Схема Горнера - C++
Дан многочлен P(x)=anxn + an−1xn−1+ … + a1x + a0 и число x. Вычислите значение этого многочлена, воспользовавшись схемой Горнера: ...

Схема Горнера - C++
Дано вещественное целое число x, целое n, n&gt;0. Найти значение многочлена n-й степени P(x) в точке x по схеме Горнера:...

Рекурсия. Схема Горнера. - C++
Вот собственно задача. Я вообще не понимаю как её решать=( Вычислить по формуле Горнера значение многочлена a0xn + + a1xn-1 +…+...

схема Горнера (помогите с курс. работой) - C++
#include&lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; #define n 1 int main() { float x, b, a; int...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
21.11.2010, 13:32 #31
Ну вы молодец - выбрали компилятор Си, хотя программа написана на Си++, и спрашиваете, почему выдаётся куча ошибок... Выберите на сайте компилятор Си++.
0
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
21.11.2010, 13:32  [ТС] #32
http://codepad.org/LcH1gzch
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
21.11.2010, 13:36 #33
Цитата Сообщение от OffSide Посмотреть сообщение
ибо 7 стоит
И что? У меня стоит 7, и прекрасно уживаются несколько компиляторов (сред, точнее)... В чём проблема?

Добавлено через 1 минуту
Сайт - это вам не консоль. У вас в программе есть места, где надо вводить данные, но на сайте вы ничего ввести не сможете. Просто временно закомментируйте все строчки с cin, и те данные, которые в них вводятся, инициализируйте явно.
0
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
21.11.2010, 14:15  [ТС] #34
http://codepad.org/BE0qwzf5 че токо не пробовал, никак

Добавлено через 11 минут
не подскажешь, что почитать на тему "написание программы с использованием подпрограммы", как эта задача
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
21.11.2010, 14:18 #35
Балин, форум глюканул... Я отправил ссылку на исправленный вариант, но она не пришла...
http://codepad.org/fHR3KfU5
0
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
21.11.2010, 14:21  [ТС] #36
а что в моем исправленном варианте не так, вроде то же самое, только по-другому
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
21.11.2010, 14:25 #37
Естественно не так. Мало того, что вы пытаетесь ввести с клавиатуры что-то в тройку (что само по себе абсурдно), так ещё в остальных местах у вас остался ввод с клавиатуры. Просмотрите внимательно свой и мой код и сравните.

Добавлено через 2 минуты
Цитата Сообщение от OffSide Посмотреть сообщение
вроде то же самое, только по-другому
Красиво)))
0
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
21.11.2010, 14:27  [ТС] #38
Цитата Сообщение от silent_1991 Посмотреть сообщение

Добавлено через 2 минуты

Красиво)))
дадада, у меня часто такое)))

/* Рисуем верхнюю рамку */ /* Снова рамка */ /* И ещё одна завершающая рамка */

что за рамки? и можно объяснение какое-нибудь к принципу работы
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
21.11.2010, 15:28 #39
Ну рамки - формирование таблицы из плюсов, тире и вертикальных чёрточек, чтобы красиво было. Таблица, кстати, кривовато рисуется)))
А схема, на самом деле, элементарная)))
Она позволяет вычислять значения многочлена при заданном значении x = x0.
Пусть есть многочлен:

P_n(x) = a_n * x^n + a_(n - 1) * x^(n - 1) + ... + a_1 * x + a_0

(В нашей программе эти коэффициенты - a_n, a_(n - 1), ..., a_1, a_0 - элементы массива, степень многочлена тоже вводится)
Перепишем многочлен в более удобный для нас вид:

P_n(x) = a_0 + a_1 * x + a_2 * x^2 + ... + a_(n - 1) * x^(n - 1) + a_n * x^n

Теперь оставим a_0 за скобками, а из скобок (в которые возьмём всю оставшуюся часть многочлена) вынесем x:

P_n(x) = a_0 + x * (a_1 + a_2 * x + ... + a_(n - 1) * x^(n - 2) + a_n * x^(n - 1))

Как видно, в скобках остался многочлен меньшей на 1 степени, чем исходный, и в качестве свободного члена у него выступает a_1. Повторим с многочленом в скобках ту же операцию, т.е. оставим за скобками a_1, остальное возьмём в скобки (уже вторые для исходного многочлена) и вынесем за них x:

P_n(x) = a_0 + x * (a_1 + x * (a_2 + ... + a_(n - 1) * x^(n - 3) + a_n * x^(n - 2)))

Будем повторять эту процедуру, пока в самых внутренних скобках не получим многочлен первой степени, т.е. пока не добьёмся такого вида:

P_n(x) = a_0 + x * (a_1 + x * (a_2 + ... + x * (a_(n - 1) + a_n * x)...))

Теперь вопрос - начерта мы всё это делали)) Вот ответ: теперь мы легко можем вычислить значение исходного многочлена, не возводя ничего не в какие степени. Делается это просто. Сначала x0 подставляется в самый внутренний многочлен первой степени - в a_(n - 1) + a_n * x, и, соответственно, вычисляется значение этого многочлена. Пусть это будет b_(n - 1). Получим:

P_n(x) = a_0 + x * (a_1 + x * (a_2 + ... + x * (a_(n - 2) + x * b_(n - 1))...))

Т.е. мы уже на один шаг ближе к результату - скобок у нас стало на одну пару меньше. Повторяем предыдущий шаг с внутренним многочленом первой степени - с a_(n - 2) + x * b_(n - 1) - снова получаем результат - некоторое b_(n - 2). Подставив его в P_n(x), получим ещё более простой многочлен. Делаем так, пока не получим выражение вида a_0 + x * b_1, подставив в которое x0 и получим окончательный ответ - значение многочлена b_0 = P_n(x) в точке x0.

Не по теме:

Вообще говоря, вся прелесть схемы Горнера не в этом, а в простом вычислении результата деления двух многочленов, но сейчас не об этом)))

0
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
22.11.2010, 18:24  [ТС] #40
общаяя задача: Исследование уравнения. Даны натуральное число n и целые числа f0, ... , fn. Исследовать существование целочисленных корней уравнения f0*x^n+f1*x^(n-1)+...+fn=0. Если fn=0, то имеется корень, равный 0; если же fn!=0, то целочисленный корень, если он существует, принадлежит конечному множеству положительных и отрицатльных делителей числа fn. Здесь следует определить подпрограмму, которая по двум заданным числам k и m (m>k>=0) позволяет определить значение наименьшего делителя числа m, превышающего k, а так же подпрограмму вычисления значения многочлена по схеме Горнера : y=(...((f0*x+f1)*x+f2)*x+...+f(n-1)*x+fn


а под общую задачу мою, что нужно подделать и схему горнера, просят как подпрограамму сделать
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.11.2010, 17:51 #41
Если раньше никто не сделает - напишу вам программу. Сегодня не успеваю.

Добавлено через 30 минут
Особо не тестил, но на элементарных тестах отрабатывает на ура.

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
#include <iostream>
 
int Horner(int, int *, int);
int minDiv(int, int);
 
int main()
{
    int *factor;
    int n;
    bool key = false;
 
    std::cout << "Enter n: ";
    std::cin >> n;
 
    n++;
 
    factor = new int [n];
 
    for (int i = 0; i < n; i++)
    {
        std::cout << "factor[" << i << "] = ";
        std::cin >> factor[i];
    }
 
    int free = factor[n - 1] > 0 ? factor[n - 1] : -factor[n - 1];
 
    if (free == 0)
    {
        std::cout << "Root: 0" << std::endl;
 
        key = true;
    }
    else
    {
        for (int i = 0; i <= free; i++)
        {
            int root;
 
            if ((root = minDiv(free, i)) != 0)
            {
                int value;
 
                if ((value = Horner(root, factor, n)) == 0)
                {
                    std::cout << "Root: " << root << std::endl;
 
                    key = true;
                }
 
                if ((value = Horner(-root, factor, n)) == 0)
                {
                    std::cout << "Root: " << -root << std::endl;
 
                    key = true;
                }
 
                i = root - 1;
            }
        }
    }
 
    if (!key)
        std::cout << "No roots" << std::endl;
 
    delete [] factor;
 
    std::cin.get();
    return 0;
}
 
int Horner(int x, int *factor, int n)
{
    int result = factor[0];
 
    for (int i = 1; i < n; i++)
        result = result * x + factor[i];
 
    return result;
}
 
int minDiv(int m, int k)
{
    for (int i = k + 1; i < m; i++)
        if (m % i == 0)
            return i;
 
    return 0;
}
1
legend
28 / 27 / 0
Регистрация: 17.11.2010
Сообщений: 152
23.11.2010, 18:18 #42
silent_1991,
C++
1
2
3
4
5
6
7
   
cin<<n;
 for (int i = 0; i < n; i++)
    {
        std::cout << "factor[" << i << "] = ";
        std::cin >> factor[i];
    }
я само задание не читал.. но я так понял что я должен ввести n чисел..

чето или у меня глюки.. и еще чето.. но у меня запрашивает ввести на n+1 раз..


че тут не так.. а то у меня крыша ща поеедет
0
Миниатюры
Схема Горнера  
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.11.2010, 18:21 #43
Вообще я основывался на здравом смысле - вводе степени многочлена. Как мы знаем, многочлен степени n имеет вид P_n(x) = a_n * x^n + a_(n - 1) * x^(n - 1) + ... + a_1 * x + a_0 - т.е. коэффициентов на самом деле n + 1. Если хотите - закомментируйте 15 строчку - тогда надо будет вводить n свободных членов (а многочлен будет степени n - 1)
1
legend
23.11.2010, 18:24
  #44

Не по теме:

у меня с математикой явно проблемы..

0
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
25.11.2010, 15:44  [ТС] #45
.......
0
Миниатюры
Схема Горнера  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2010, 15:44
Привет! Вот еще темы с ответами:

Полином по правилу Горнера - C++
Здравствуйте ребят, помогите с задачкой, пожалуйста? Плохо знаю С++, желательно на начальном уровне написать код. &quot;Посчитать значение...

Алгоритм схемы Горнера - C++
Задача такова: необходимо посчитать Сумму произведения ((-1)^k)*(((x/2)^2k)/((k!)^2)), где k изменяеться от 1 до бесконечности. Мною...

Правильно ли я разложил по схеме Горнера? - C++
Было задание разложить многочлен по схеме Горнера с использованием рекурсии. Вопрос в том, правильно ли я разложил? Формула x+3-e^-x ...

Рассчитать значение переменной по схеме Горнера - C++
задание по схеме Горнера : как это делать? неврублюсь Оффициальным языком форума является русский язык. В дальнейшем Ваши темы...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.11.2010, 15:44
Ответ Создать тему
Опции темы

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