2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Значение многочлена в точке
Сообщение14.03.2010, 15:27 
Добрый день! Помогите разобраться с данной задачкой: допустим есть файл, где хранятся числа $a_0, a_1, a_2, \ldots , a_n$. Они задают коэффициенты многочлена, причем данные коэффициенты расположены по возрастанию степеней, т.е. наш многочлен будет выглядить так: $P(x)=a_0+a_1x+a_2x^2+\ldots + a_{n-1}x^{n-1}+a_nx^n$. Как найти его значение в точке $c$?
Конечно, вы можете предложить отсортировать в обратном порядке и применить схему Горнера, но числа из файла нельзя переносить на массив.

 
 
 
 Re: Значение многочлена в точке
Сообщение14.03.2010, 15:32 
Аватара пользователя
А что мешает применить схему Горнера в "обратном" порядке?

$P(c)=a_0+c(a_1+c(a_2+\ldots + c(a_{n-1}+a_nc)))...)$.

Или имеется в виду последовательный файл, который можно только раз прочитать с начала до конца?
Тогда только неэффективное прямое вычисление.

 
 
 
 Re: Значение многочлена в точке
Сообщение14.03.2010, 15:36 
Но ведь здесь мы начинаем вычисления с внутренней скобки? Как нам начать вычисления, стартуя с $a_0$ и заканчивая $a_n$?

Опередили, файл можно читать лишь один раз. Я так и не понял, что преподаватель имеет ввиду, давая эту задачку :(

 
 
 
 Re: Значение многочлена в точке
Сообщение14.03.2010, 15:38 
Аватара пользователя
Или посчитать многочлен относительно $\dfrac 1{c^n}$ по схеме Горнера, а потом умножить на $c^n$

 
 
 
 Re: Значение многочлена в точке
Сообщение14.03.2010, 15:48 
А можно не применять схему Горнера?
Тогда просто в цикле на каждом шаге поддерживаем текущую степень $c$ и прибавляем к итоговой сумме $a_k c^k$.

 
 
 
 Re: Значение многочлена в точке
Сообщение14.03.2010, 15:52 
Аватара пользователя
С Горнером при небольших $n$ экономии не будет, там же одно деление добавляется и вычисление n-ной степени, но если степень многочлена больше 8, то действий потребуется меньше, чем при прямом подсчёте.

 
 
 
 Re: Значение многочлена в точке
Сообщение14.03.2010, 16:02 
А еще можно по формуле, предложенной grisом, но применяя рекурсивный алгоритм.
Что-нибудь такого типа:
Код:
double poly(double c)
{
    if (конец файла)
        return 0;
    else {
        double a <- очередной коэффициент из файла
        return a + с * poly(c);
    }
}

 
 
 
 Re: Значение многочлена в точке
Сообщение14.03.2010, 16:23 
Maslov в сообщении #297542 писал(а):
А еще можно по формуле, предложенной grisом, но применяя рекурсивный алгоритм.

Фактически это все равно будет перенос в массив, построенный на стеке.

 
 
 
 Re: Значение многочлена в точке
Сообщение14.03.2010, 16:28 
Roman Voznyuk в сообщении #297559 писал(а):
Фактически это все равно будет перенос в массив, построенный на стеке.
Это ж по программированию задача, поэтому, я думаю, что запрет переносить числа в массив распространяется исключительно на явное объявление массива и явное перенесение туда содержимого файла.

 
 
 
 Re: Значение многочлена в точке
Сообщение14.03.2010, 16:55 
По моему, Cave предложил лучший вариант в данных условиях.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group