Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.52/75: Рейтинг темы: голосов - 75, средняя оценка - 4.52
2 / 2 / 1
Регистрация: 03.10.2010
Сообщений: 108

Схема Горнера

15.11.2010, 23:22. Показов 15006. Ответов 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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
15.11.2010, 23:22
Ответы с готовыми решениями:

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

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

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

57
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
23.11.2010, 17:51
Студворк — интернет-сервис помощи студентам
Если раньше никто не сделает - напишу вам программу. Сегодня не успеваю.

Добавлено через 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
29 / 28 / 7
Регистрация: 17.11.2010
Сообщений: 152
23.11.2010, 18:18
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
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
23.11.2010, 18:21
Вообще я основывался на здравом смысле - вводе степени многочлена. Как мы знаем, многочлен степени 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
23.11.2010, 18:24

Не по теме:

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

0
2 / 2 / 1
Регистрация: 03.10.2010
Сообщений: 108
25.11.2010, 15:44  [ТС]
.......
Миниатюры
Схема Горнера  
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
25.11.2010, 16:25
OffSide, и что? Это то задание, которое вы выложили в первом посте темы и которое я дословно реализовал в программе (хотя не хотел писать функцию нахождения минимального делителя числа m, большего k, можно было обойтись без неё). Вы хотите сказать, что программа не по заданию?
1
2 / 2 / 1
Регистрация: 03.10.2010
Сообщений: 108
25.11.2010, 16:29  [ТС]
Цитата Сообщение от silent_1991 Посмотреть сообщение
OffSide, и что? Это то задание, которое вы выложили в первом посте темы и которое я дословно реализовал в программе (хотя не хотел писать функцию нахождения минимального делителя числа m, большего k, можно было обойтись без неё). Вы хотите сказать, что программа не по заданию?
не.
можно какой-нибудь комментарий небольшой, или лучше комментарий к кажд. строчке по минимуму, а то большинство мне не понятно(
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
25.11.2010, 16:50
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#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++; // Увеличиваем введённую степень на 1 (т.к. в многочлене степени n на самом
         // деле n+1 коэффициент (n коэффициентов + 1 свободный член), и память надо
         // выделить под все коэффициенты)
 
    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; // Потенциальный корень уравнения
 
            // Находим потенциальный корень с помощью функции minDiv и сравниваем
            // его с нулём (функция вернёт нуль в случае, если не нашла делителей).
            // Если root не равен нулю
            if ((root = minDiv(free, i)) != 0)
            {
                int value; // Значение многочлена в точке root
                
                // Находим значение многочлена в точке root и сравниваем его с нулём.
                // Если значение функции в точке root равно нулю, то root является коренм
                if ((value = Horner(root, factor, n)) == 0)
                {
                    // Выводим найденный корень
                    std::cout << "Root: " << root << std::endl;
                    
                    // Запоминаем, что корень найден, чтобы не выводить сообщение
                    // об отсутствии корней
                    key = true;
                }
 
                // Таким же образом ищем значение многочлена в точке -root (т.к. мы ищем
                // корни среди целых делителей свободного члена, то если root является
                // делителем, то и -root тоже является делителем, и его тоже надо проверить
                // на принадлежность к множеству корней). Т.о. если -root - корень
                if ((value = Horner(-root, factor, n)) == 0)
                {
                    // Выводим его
                    std::cout << "Root: " << -root << std::endl;
                    
                    // И запоминаем, что корень найден, чтобы не выводить сообщение
                    // об отсутствии корней
                    key = true;
                }
                 
                // Делаем скачёк счётчика до значения найденного корня (делителя свободного
                // члена) минус одим, поскольку на промежутке (i; root - 1) явно не будет
                // делителей (ведь функция minDiv, значение которой мы сохраняем в root,
                // находит наименьший целый делитель free, больший i, а значит между
                // root - 1 и i нет других делителей и эти значения мы можем не проверять)
                i = root - 1;
            }
        }
    }
    
    // Если не нашли корней
    if (!key)
        // Сообщаем об этом
        std::cout << "No roots" << std::endl;
 
    // Освобождаем память из-под массива коэффициентов
    delete [] factor;
 
    std::cin.get();
    return 0;
}
 
// Функция, вычисляющая значение многочлена степени n, представленного
// массивом коэффициентов factor в точке x
int Horner(int x, int *factor, int n)
{
    int result = factor[0]; // Запоминаем коэффициент при старшей степени
 
    // Проходим по всем коэффициентам многочлена
    for (int i = 1; i < n; i++)
        // Рассчитываем resul, тоответствующий очередной вложенности скобок
        // разложении многочлена, на котором и основывается метод Горнера
        result = result * x + factor[i];
 
    // Возвращаем рассчитанное значение многочлена в точке x
    return result;
}
 
// Функция, отыскивающая минимальный делитель числа m, больший k
int minDiv(int m, int k)
{
    // Начинаем цикл со значения k+1
    for (int i = k + 1; i < m; i++)
        // Если нашли делитель
        if (m % i == 0)
            // Возвращаем его
            return i;
    
    // Иначе возвращаем нуль (ни в каком другом случае функция нуль не
    // вернёт, поэтому это значение является индикатором того, что
    // делитель не был найден)
    return 0;
}
Саму схему Горнера я описывал выше, поэтому в комментариях подробно в это не вдаюсь, больше опираюсь на описание кода.
1
2 / 2 / 1
Регистрация: 03.10.2010
Сообщений: 108
25.11.2010, 16:53  [ТС]
спасибо огромное! приезжай к нам в Иваново, бухнем нормально!
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
25.11.2010, 16:58
Цитата Сообщение от OffSide Посмотреть сообщение
приезжай к нам в Иваново, бухнем нормально!


Можно немного поправить код вот так:

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#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++; // Увеличиваем введённую степень на 1 (т.к. в многочлене степени n на самом
         // деле n+1 коэффициент (n коэффициентов + 1 свободный член), и память надо
         // выделить под все коэффициенты)
 
    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; // Потенциальный корень уравнения
 
            // Находим потенциальный корень с помощью функции minDiv и сравниваем
            // его с нулём. Если root не равен нулю
            if ((root = minDiv(free, i)) != 0)
            {
                int value; // Значение многочлена в точке root
                
                // Находим значение многочлена в точке root и сравниваем его с нулём.
                // Если значение функции в точке root равно нулю, то root является коренм
                if ((value = Horner(root, factor, n)) == 0)
                {
                    // Выводим найденный корень
                    std::cout << "Root: " << root << std::endl;
                    
                    // Запоминаем, что корень найден, чтобы не выводить сообщение
                    // об отсутствии корней
                    key = true;
                }
 
                // Таким же образом ищем значение многочлена в точке -root (т.к. мы ищем
                // корни среди целых делителей свободного члена, то если root является
                // делителем, то и -root тоже является делителем, и его тоже надо проверить
                // на принадлежность к множеству корней). Т.о. если -root - корень
                if ((value = Horner(-root, factor, n)) == 0)
                {
                    // Выводим его
                    std::cout << "Root: " << -root << std::endl;
                    
                    // И запоминаем, что корень найден, чтобы не выводить сообщение
                    // об отсутствии корней
                    key = true;
                }
                 
                // Делаем скачёк счётчика до значения найденного корня (делителя свободного
                // члена) минус одим, поскольку на промежутке (i; root - 1) явно не будет
                // делителей (ведь функция minDiv, значение которой мы сохраняем в root,
                // находит наименьший целый делитель free, больший i, а значит между
                // root - 1 и i нет других делителей и эти значения мы можем не проверять)
                i = root - 1;
            }
            // Иначе, если root равен нулю (т.е. minDiv не нашла делителей, а ведь она ищет
            // все делители вплоть до free), то смысла проверять дальше нету
            else
                // Завершаем цикл
                break;
        }
    }
    
    // Если не нашли корней
    if (!key)
        // Сообщаем об этом
        std::cout << "No roots" << std::endl;
 
    // Освобождаем память из-под массива коэффициентов
    delete [] factor;
 
    std::cin.get();
    return 0;
}
 
// Функция, вычисляющая значение многочлена степени n, представленного
// массивом коэффициентов factor в точке x
int Horner(int x, int *factor, int n)
{
    int result = factor[0]; // Запоминаем коэффициент при старшей степени
 
    // Проходим по всем коэффициентам многочлена
    for (int i = 1; i < n; i++)
        // Рассчитываем resul, тоответствующий очередной вложенности скобок
        // разложении многочлена, на котором и основывается метод Горнера
        result = result * x + factor[i];
 
    // Возвращаем рассчитанное значение многочлена в точке x
    return result;
}
 
// Функция, отыскивающая минимальный делитель числа m, больший k
int minDiv(int m, int k)
{
    // Начинаем цикл со значения k+1
    for (int i = k + 1; i <= m; i++)
        // Если нашли делитель
        if (m % i == 0)
            // Возвращаем его
            return i;
    
    // Иначе возвращаем нуль (ни в каком другом случае функция нуль не
    // вернёт, поэтому это значение является индикатором того, что
    // делитель не был найден)
    return 0;
}
Также чуток поправил функцию minDiv (раньше она не находила корни, которые совпадали с самим свободным членом, условие выхода из цикла надо было поправить)
1
2 / 2 / 1
Регистрация: 03.10.2010
Сообщений: 108
25.11.2010, 18:04  [ТС]
вникнул в задачу ) блин, как такие задачи нам задают, если я такую не могу решить и даже легче, а еще экзамен будет, и специальность программное обеспечение комп.систем, т.е 5 лет программирование, а я такие не могу решить, теорию почитываю, но все равно никак. спрашивал у препода, что делать, говорит практика решает. а как практика, если не решаются-то))
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
25.11.2010, 18:32
OffSide, так вы решайте! В смысле производите процесс решения. Только вот тут вопрос встаёт - на каком этапе не решается задача. Если на этапе именно программирования - то надо просто программировать, узнавать новые вещи, реализовывать стандартные задачи: реализация распространённых структур данных - стеки, очереди, кучи, деревья, реализация алгоритмов на них, реализация классических задач - короче практика программирования. Когда учишься программировать, не возбраняется изобретать велосипеды: пусть в algorithm есть реализация сортировки - напишите разные сортировки самостоятельно, пусть в STL есть двусвязный список - напишите и его сами. Тут препод прав - п'гактика, п'гактика и ещё раз п'гактика.
А вот если сложности на этапе алгоритмизации - тут всё намного сложнее... Очень сложно научиться составлять алгоритмы, если ты в упор не можешь их составлять, тут должен быть... Талант, что-ли. Или очень хороший учитель. Тут проблема в том, что решать стандартные математические задачки (я имею ввиду на бумаге ручкой, для примера говорю) научиться можно, ведь для этих стандартных задачек уже существуют алгоритмы. А вот уметь решать нестандартные задачи - это по сути уметь составлять алгоритмы решения на основе более мелких существующих, атомарных, скажем так, алгоритмов. А это своеобразное искусство. Поэтому если очень хочется научиться составлять алгоритмы - надо очень много трудиться, постоянно занимаясь этим самым составлением. Просто возьмите набор задач, не стандартных вроде "отсортируйте строку матрицы, имеющую минимальное количество нулевых элементов и т.д." - это вам никакой пользы не принесёт, да и не интересно, а что-то боле сложное и, главное, разнообразное, и решайте. Пытайтесь решать, пусть на одну задачку уходит неделя, всё равно решайте. Пока не решите одну, не переходите к следующей. Постепенно вы научитесь отыскивать в задачах элементарные, атомарные места, которые можно реализовать известными вам алгоритмами, и вам останется только придумать, как связать эти части в одну общую цепь, отыскивающую решение. Главное - абстрагироваться от известных вам реалий и рассматривать задачу в формальном виде, в виде неких формул и их систем, тогда решение искать будет легче.
Например, такая достаточно известная задача: Отыскать площадь многоугольника, заданного координатами точек. Известная вам реалия - многоугольник. И всё - тупик. Как найти его площадь? А вот абстракция - это то, что многоугольник состоит из набора треугольников. Поэтому если его разбить на треугольники и найти площадь каждого из них, а потом сложить площади - мы найдём площадь исходной фигуры. Как видно, для решение большей задачи мы выделили из неё меньшие, которые мы с лёгкостью можем решить, и связали их так, что эта связь является ключом к решению общей задачи. И вот такие кусочки надо стараться найти в каждой задаче.

Не по теме:

Ну ё-моё, разразился... Остапа несло...

2
2 / 2 / 1
Регистрация: 03.10.2010
Сообщений: 108
25.11.2010, 18:40  [ТС]
спасибо за ответ!
0
25.11.2010, 18:46

Не по теме:

OffSide, для "Спасибо" на этом форуме есть специальная кнопочка ;)

0
2 / 2 / 1
Регистрация: 03.10.2010
Сообщений: 108
08.12.2010, 00:44  [ТС]
когда вводим с клавиатуры коэффициенты, i это что?
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
08.12.2010, 12:28
i - это счётчик. Отсчитывает индексы массива, куда записываются введённые данные. На первой итерации ввод происходит в ячейку массива factor[0], на второй итерации счётчик увеличивается и ввод происходит уже в ячейку factor[1] и т.д.
1
2 / 2 / 1
Регистрация: 03.10.2010
Сообщений: 108
08.12.2010, 14:13  [ТС]
оказывается только на нашем факе нельзя юзать "сиауты", а на остальных можно, кароч ппц. и я спешно начал переделывать прогу на паре))) вот что я успел замутить и переделать. в конце препод подлетает, проверяет, говорит , больше половины сделал, но не доделал, сказал, что полож и отриц делители, я долго думал, но так нихера и не додумался, препод сказала, все просто, иди домой думай((

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
#include <stdlib.h>
#include <stdio.h>
 
int Horner (int,int*,int);
int minDiv (int, int);
 
int *factor;
int n;
 
printf ("введите степень многочлена n:\n")
n++; 
factor= new int [n]; 
scanf ("%d", &n);
 
for (int i=0; i<n; i++) 
 
int Horner (int x, int *factor, int n)
 
{  int result=factor[0];              
   for (int i=1; i<n; i++)             
   int 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;         
             
}
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
08.12.2010, 14:51
OffSide, это вообще что у вас? И если препод это одобрил - то сжечь этого препода. Где функция main? И что, cout/cin юзать нельзя, а new/delete - можно? Ещё один идиотизм.

На чистом C это будет выглядеть так:

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h>
#include <stdlib.h>
 
// Прототипы функций
int Horner(int, int *, int);
int minDiv(int, int);
 
int main()
{
    int *factor; // Массив коэффициентов уравнения
    int n;       // Степень многочлена
    int freeMem; // Свободный член
    int root;    // Потенциальный корень уравнения
    int value;   // Значение многочлена в точке root
    int key = 0; // Служебный ключ, служит для того, чтобы вывести сообщение
                 // об отсутствии корней, если ни одного корня не найдено
    int i;
 
    // Вводим степень многочлена
    printf("Enter n: ");
    scanf("%d", &n);
 
    n++; // Увеличиваем введённую степень на 1 (т.к. в многочлене степени n на самом
         // деле n+1 коэффициент (n коэффициентов + 1 свободный член), и память надо
         // выделить под все коэффициенты)
 
    factor = (int *)malloc(n * sizeof(int)); // Выделяем память под массив коэффициентов
 
    // Вводим с клавиатуры коэффициенты
    for (i = 0; i < n; i++)
    {
        printf("factor[%d] = ", i);
        scanf("%d", &factor[i]);
    }
    
    // Запоминаем абсолютное значение (модуль) свободного члена
    freeMem = factor[n - 1] > 0 ? factor[n - 1] : -factor[n - 1];
 
    // Если свободный член равен нулю
    if (freeMem == 0)
    {
         // Выводим корень "нуль"
        printf("Root: 0\n");
        
        // Запоминаем, что корень найден, чтобы не выводить сообщение
        // об отсутствии корней
        key = 1;
    }
    // Иначе, если свободный член не равен нулю
    else
    {
        // В цикле проходим все числа от нуля до свободного члена
        for (i = 0; i <= freeMem; i++)
        {
            // Находим потенциальный корень с помощью функции minDiv и сравниваем
            // его с нулём. Если root не равен нулю
            if ((root = minDiv(freeMem, i)) != 0)
            {
                // Находим значение многочлена в точке root и сравниваем его с нулём.
                // Если значение функции в точке root равно нулю, то root является коренм
                if ((value = Horner(root, factor, n)) == 0)
                {
                    // Выводим найденный корень
                    printf("Root: %d\n", root);
                    
                    // Запоминаем, что корень найден, чтобы не выводить сообщение
                    // об отсутствии корней
                    key = 1;
                }
 
                // Таким же образом ищем значение многочлена в точке -root (т.к. мы ищем
                // корни среди целых делителей свободного члена, то если root является
                // делителем, то и -root тоже является делителем, и его тоже надо проверить
                // на принадлежность к множеству корней). Т.о. если -root - корень
                if ((value = Horner(-root, factor, n)) == 0)
                {
                    // Выводим его
                    printf("Root: %d\n", -root);
                    
                    // И запоминаем, что корень найден, чтобы не выводить сообщение
                    // об отсутствии корней
                    key = 1;
                }
                 
                // Делаем скачёк счётчика до значения найденного корня (делителя свободного
                // члена) минус одим, поскольку на промежутке (i; root - 1) явно не будет
                // делителей (ведь функция minDiv, значение которой мы сохраняем в root,
                // находит наименьший целый делитель free, больший i, а значит между
                // root - 1 и i нет других делителей и эти значения мы можем не проверять)
                i = root - 1;
            }
            // Иначе, если root равен нулю (т.е. minDiv не нашла делителей, а ведь она ищет
            // все делители вплоть до free), то смысла проверять дальше нету
            else
                // Завершаем цикл
                break;
        }
    }
    
    // Если не нашли корней
    if (key == 0)
        // Сообщаем об этом
        printf("No roots\n");
 
    // Освобождаем память из-под массива коэффициентов
    free(factor);
 
    return 0;
}
 
// Функция, вычисляющая значение многочлена степени n, представленного
// массивом коэффициентов factor в точке x
int Horner(int x, int *factor, int n)
{
    int result = factor[0]; // Запоминаем коэффициент при старшей степени
    int i;
 
    // Проходим по всем коэффициентам многочлена
    for (i = 1; i < n; i++)
        // Рассчитываем resul, тоответствующий очередной вложенности скобок
        // разложении многочлена, на котором и основывается метод Горнера
        result = result * x + factor[i];
 
    // Возвращаем рассчитанное значение многочлена в точке x
    return result;
}
 
// Функция, отыскивающая минимальный делитель числа m, больший k
int minDiv(int m, int k)
{
    int i;
 
    // Начинаем цикл со значения k+1
    for (i = k + 1; i <= m; i++)
        // Если нашли делитель
        if (m % i == 0)
            // Возвращаем его
            return i;
    
    // Иначе возвращаем нуль (ни в каком другом случае функция нуль не
    // вернёт, поэтому это значение является индикатором того, что
    // делитель не был найден)
    return 0;
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
08.12.2010, 14:51

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
58
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru