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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 62, средняя оценка - 4.69
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
15.11.2010, 23:22     Схема Горнера #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
/*
 * 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 минуты
препод будет меня жеско иметь)))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2010, 23:22     Схема Горнера
Посмотрите здесь:

Схема горнера C++
C++ Рекурсия. Схема Горнера.
Схема Горнера C++
C++ Рассчитать значение переменной по схеме Горнера
C++ схема Горнера (помогите с курс. работой)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
legend
 Аватар для 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 раз..


че тут не так.. а то у меня крыша ща поеедет
Миниатюры
Схема Горнера  
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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)
legend
23.11.2010, 18:24
  #44

Не по теме:

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

OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
25.11.2010, 15:44  [ТС]     Схема Горнера #45
.......
Миниатюры
Схема Горнера  
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
25.11.2010, 16:25     Схема Горнера #46
OffSide, и что? Это то задание, которое вы выложили в первом посте темы и которое я дословно реализовал в программе (хотя не хотел писать функцию нахождения минимального делителя числа m, большего k, можно было обойтись без неё). Вы хотите сказать, что программа не по заданию?
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
25.11.2010, 16:29  [ТС]     Схема Горнера #47
Цитата Сообщение от silent_1991 Посмотреть сообщение
OffSide, и что? Это то задание, которое вы выложили в первом посте темы и которое я дословно реализовал в программе (хотя не хотел писать функцию нахождения минимального делителя числа m, большего k, можно было обойтись без неё). Вы хотите сказать, что программа не по заданию?
не.
можно какой-нибудь комментарий небольшой, или лучше комментарий к кажд. строчке по минимуму, а то большинство мне не понятно(
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
25.11.2010, 16:50     Схема Горнера #48
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;
}
Саму схему Горнера я описывал выше, поэтому в комментариях подробно в это не вдаюсь, больше опираюсь на описание кода.
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
25.11.2010, 16:53  [ТС]     Схема Горнера #49
спасибо огромное! приезжай к нам в Иваново, бухнем нормально!
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
25.11.2010, 16:58     Схема Горнера #50
Цитата Сообщение от 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 (раньше она не находила корни, которые совпадали с самим свободным членом, условие выхода из цикла надо было поправить)
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
25.11.2010, 18:04  [ТС]     Схема Горнера #51
вникнул в задачу ) блин, как такие задачи нам задают, если я такую не могу решить и даже легче, а еще экзамен будет, и специальность программное обеспечение комп.систем, т.е 5 лет программирование, а я такие не могу решить, теорию почитываю, но все равно никак. спрашивал у препода, что делать, говорит практика решает. а как практика, если не решаются-то))
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
25.11.2010, 18:32     Схема Горнера #52
OffSide, так вы решайте! В смысле производите процесс решения. Только вот тут вопрос встаёт - на каком этапе не решается задача. Если на этапе именно программирования - то надо просто программировать, узнавать новые вещи, реализовывать стандартные задачи: реализация распространённых структур данных - стеки, очереди, кучи, деревья, реализация алгоритмов на них, реализация классических задач - короче практика программирования. Когда учишься программировать, не возбраняется изобретать велосипеды: пусть в algorithm есть реализация сортировки - напишите разные сортировки самостоятельно, пусть в STL есть двусвязный список - напишите и его сами. Тут препод прав - п'гактика, п'гактика и ещё раз п'гактика.
А вот если сложности на этапе алгоритмизации - тут всё намного сложнее... Очень сложно научиться составлять алгоритмы, если ты в упор не можешь их составлять, тут должен быть... Талант, что-ли. Или очень хороший учитель. Тут проблема в том, что решать стандартные математические задачки (я имею ввиду на бумаге ручкой, для примера говорю) научиться можно, ведь для этих стандартных задачек уже существуют алгоритмы. А вот уметь решать нестандартные задачи - это по сути уметь составлять алгоритмы решения на основе более мелких существующих, атомарных, скажем так, алгоритмов. А это своеобразное искусство. Поэтому если очень хочется научиться составлять алгоритмы - надо очень много трудиться, постоянно занимаясь этим самым составлением. Просто возьмите набор задач, не стандартных вроде "отсортируйте строку матрицы, имеющую минимальное количество нулевых элементов и т.д." - это вам никакой пользы не принесёт, да и не интересно, а что-то боле сложное и, главное, разнообразное, и решайте. Пытайтесь решать, пусть на одну задачку уходит неделя, всё равно решайте. Пока не решите одну, не переходите к следующей. Постепенно вы научитесь отыскивать в задачах элементарные, атомарные места, которые можно реализовать известными вам алгоритмами, и вам останется только придумать, как связать эти части в одну общую цепь, отыскивающую решение. Главное - абстрагироваться от известных вам реалий и рассматривать задачу в формальном виде, в виде неких формул и их систем, тогда решение искать будет легче.
Например, такая достаточно известная задача: Отыскать площадь многоугольника, заданного координатами точек. Известная вам реалия - многоугольник. И всё - тупик. Как найти его площадь? А вот абстракция - это то, что многоугольник состоит из набора треугольников. Поэтому если его разбить на треугольники и найти площадь каждого из них, а потом сложить площади - мы найдём площадь исходной фигуры. Как видно, для решение большей задачи мы выделили из неё меньшие, которые мы с лёгкостью можем решить, и связали их так, что эта связь является ключом к решению общей задачи. И вот такие кусочки надо стараться найти в каждой задаче.

Не по теме:

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

OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
25.11.2010, 18:40  [ТС]     Схема Горнера #53
спасибо за ответ!
silent_1991
25.11.2010, 18:46
  #54

Не по теме:

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

OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
08.12.2010, 00:44  [ТС]     Схема Горнера #55
когда вводим с клавиатуры коэффициенты, i это что?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
08.12.2010, 12:28     Схема Горнера #56
i - это счётчик. Отсчитывает индексы массива, куда записываются введённые данные. На первой итерации ввод происходит в ячейку массива factor[0], на второй итерации счётчик увеличивается и ввод происходит уже в ячейку factor[1] и т.д.
OffSide
2 / 2 / 0
Регистрация: 03.10.2010
Сообщений: 111
08.12.2010, 14:13  [ТС]     Схема Горнера #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
#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;         
             
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2010, 14:51     Схема Горнера
Еще ссылки по теме:

C++ Алгоритм схемы Горнера
Схема Горнера( C++
Метод Горнера C++

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
08.12.2010, 14:51     Схема Горнера #58
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;
}
Yandex
Объявления
08.12.2010, 14:51     Схема Горнера
Ответ Создать тему
Опции темы

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