[Pascal] Значение k-й производной

[grozglaz]

Задание:

Цитата:

Значение k-й производной записанного по убывающим степеням многочлена в точке t0, f: сигма(R) > R, f(дельта) = 0.

Требования и рекомендации к выполнению задания:

Цитата:

1) Алгоритм решения задачи должен быть однопроходным и не должен использовать дополнительную память, пропорциональную размеру входного файла (использование массивов для хранения входной последовательности запрещено);
2) Возможны 2 варианта реализации последовательности в виде входного файла: а) файл имеет тип Text, создается с помощью стандартного текстового редактора и просматривается тоже стандартными средствами; б) файл имеет тип file of X, создается и просматривается специальной отдельной программой (или программами) генерации и просмотра;
3) Рекомендуется использовать схему вычисления индуктивной функции, в которой на каждом шаге основного цикла из входного файла читается и обрабатывается 1 элемент последовательности (в этом случае инвариант цикла и ограничивающая функция стандартны);
4) Программа должна выводить поочередно обрабатываемые элементы входного файла, а также другие (промежуточные) данные в виде, позволяющем проанализировать и понять процесс формирования окончательного результата как автору программы, так и проверяющему задание;
5) Выходные данные (включая те, что необходимы для понимания работы алгоритма) должны выводиться на экран для оперативного анализа результатов (в режиме отладки) и в выходной файл (в режиме формирования отчета) для демонстрации проверяющему работоспособности программы;
6) Требуется протестировать основные особые случаи входных данных (например, входной файл пуст или содержит лишь 1 элемент), корректную обработку последнего элемента файла, проверить, учитывается ли наличие стационарного значения индуктивной функции и т. п.

Я смог написать программу для вычисления только первой производной по схеме Горнера:

program work5;

(****************************************************************)

var { значение производной в точке t0 }
    ValueDerivative : real;
    
    { значение полинома в точке t0 }
    ValuePolinom    : real;

    { коэффициент одночлена из файла inputfile.txt }
    k               : real;

    { точка, в которой считаем значение производной n-го порядка от полинома }
    t0              : real;
    
    { Порядок производной }
    OrderDerivative : integer;
    
    { Файл с входными данными }
    InputPolinom    : text;
    
    { Файл с результатом работы программы }
    OutputPolinom   : text;

(****************************************************************)

begin
{ устанавливаем связь между файловой переменной и именем файла }
Assign( InputPolinom, 'inputfile.txt' );
Assign( OutputPolinom, 'outputfile.txt' );
{ подготовка к записи в файл }
Rewrite(OutputPolinom); 
{ подготовка файла к чтению }
Reset(InputPolinom);
{ блок ввода }
Write( 'Введите порядок производной: ' ); 
Readln( OrderDerivative );
Write( 'Введите t0: ' );
Readln( t0 );
ValuePolinom := 0; 
ValueDerivative := 0;
{ вычисляем значение полинома и производной от полинома в точке t0 }
while ( not EOF( InputPolinom )) do
begin
    { считываем значение коэффициента при одночлене из файла inputfile.txt }
    Read( InputPolinom, k );
    ValueDerivative := ValueDerivative * t0 + ValuePolinom;
    ValuePolinom := ValuePolinom * t0 + k;
end;
Writeln( 'ValueDerivative =  ', ValueDerivative );
Readln;
{ записываем полученное значение в файл outputfile.txt }
Writeln( OutputPolinom, ValuePolinom ) ;
Writeln( OutputPolinom, ValueDerivative ) ;
{ заканчиваем работу с файлами inputfile.txt outputfile.txt }
close( InputPolinom );
close( OutputPolinom );
end.

Возможно ли вообще выполнить исходное задание с такими условиями? Т.е. коэффициенты нельзя считать в массив и степень полинома неизвестна, т.к. степень не является входным данным, а алгоритм должен быть однопроходным(т.е. пробежаться по файлу и посчитать колличество коэффициентов нельзя).
Направьте в правильное русло, ибо я уже остатки мозга поломал.

[arseniiv]

Схема Горнера не относится к производным, а относится к делению многочлена на многочлен $x - a$, или я не прав?

Вредная подсказка. Попробуйте вывести формулу $n$-й производной степенной функции.

-- Вс ноя 21, 2010 20:57:46 --

Не такая вредная подсказка. Остерегайтесь использовать факториал в коде.

[grozglaz]

arseniiv в сообщении #378599 писал(а):

Схема Горнера не относится к производным, а относится к делению многочлена на многочлен $x - a$, или я не прав?

Вредная подсказка. Попробуйте вывести формулу $n$-й производной степенной функции.

-- Вс ноя 21, 2010 20:57:46 --

Не такая вредная подсказка. Остерегайтесь использовать факториал в коде.

Цитата:

алгоритм вычисления значения многочлена, записанного в виде суммы мономов, при заданном значении переменной. Метод Горнера позволяет найти корни многочлена, а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида x − с

Вроде бы можно. Во всяком случае на лекциях нам про такое говорили.
Формулу производной n-ой степени я знаю, но она здесь не пригодится, ибо степень полинома нам неизвестна.

[arseniiv]

А, степени убывающие!

Правильно оформленное задание, если разобрал верно (для однозначности разбора и надо сразу оформлять правильно) писал(а):

Значение $k$-й производной записанного по убывающим степеням многочлена в точке $t_0$, $f : \sigma(\mathbb R) \to \mathbb R$, $f(\delta) = 0$.

А что означают у вас в задании $\sigma(\mathbb R)$ и $\delta$?

Что-то нигде не сказано, как вычислять по схеме Горнера любую производную.

[grozglaz]

arseniiv в сообщении #378846 писал(а):

А, степени убывающие!

Правильно оформленное задание, если разобрал верно (для однозначности разбора и надо сразу оформлять правильно) писал(а):

Значение $k$-й производной записанного по убывающим степеням многочлена в точке $t_0$, $f : \sigma(\mathbb R) \to \mathbb R$, $f(\delta) = 0$.

А что означают у вас в задании $\sigma(\mathbb R)$ и $\delta$?

Только там омега оказалась, а не сигма. Но это не существенно.
Вроде бы это дано для составления индуктивного расширения функции.

arseniiv в сообщении #378846 писал(а):

Что-то нигде не сказано, как вычислять по схеме Горнера любую производную.

Вот это меня и смутило. Именно поэтому придерживаюсь мнения, что задание нерешаемо при таких условиях.

[arseniiv]

В общем, раз первая производная находится по нулевой, вы сможете обобщить это для нахождения $k$-ой по $(k-1)$-ой. А даьше всё ясно. Кстати, я нашёл выражение для второй производной из вашего для первой и головы. Попробуйте.

[grozglaz]

Если вы имеете ввиду:

while ( not EOF( InputPolinom )) do
begin
    { считываем значение коэффициента при одночлене из файла inputfile.txt }
    Read( InputPolinom, k );
    ValueDerivative2 := ValueDerivative2 * t0 + ValueDerivative1;
    ValueDerivative1 := ValueDerivative1 * t0 + ValuePolinom;
    ValuePolinom := ValuePolinom * t0 + k;
end;

То это я уже проходил.
Проблема в том, что вычислить вторую производную программа только по достижению конца цикла.
Без степени полинома этот метод бесполезен.

-- Пн ноя 22, 2010 01:08:55 --

Или я вас как-то не так понял?

[arseniiv]

Да, вы не так меня поняли. Попробуйте не просто скопировать и исправить, а сделать трассировку (на бумаге). Возьмите многочлен $k_1 x^n + k_2 x^{n-1} + \ldots + k_n x + k_{n+1}$ и подавайте его на вход алгоритму (лучше сделать таблицу $i$, $k_i$, $p_i$, $p'_i$, $p''_i$). Вы увидите, что надо сделать, чтобы вторая производная вычислялась правильно (и третья, и $k$-я). А в текущем коде вторая производная вообще не вычислится никогда, даже в конце цикла.

[ewert]

grozglaz в сообщении #378365 писал(а):

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

Условие действительно выглядит (на мой взгляд) довольно нелепым, но всё же не настолько безнадёжным. Если входной файл текстовой -- сделать за один проход, действительно, ничего нельзя. Но там разрешены и типизированные файлы, а тогда к-во элементов заранее определяется просто как FileSize(f) div SizeOf(X).

Кстати, а что такое "индуктивная функция", "инвариант цикла" и "ограничивающая функция"?

[arseniiv]

А что я вчера вечером на бумаге тогда изобразил? Можно получить любую производную!

-- Пн ноя 22, 2010 18:18:12 --

ewert в сообщении #379031 писал(а):

FileSize(f) div SizeOf(X)

Делить не стоит:

http://www.codenet.ru/progr/delphi/Object-Pascal/files.php писал(а):

function FileSize(var F): Integer;

Возвращает размер в байтах файла F. Однако, если F - типизированный файл, FileSize возвратит число записей в файле.

[ewert]

arseniiv в сообщении #379037 писал(а):

Делить не стоит:

Упс, пардон. Я привык работать с бестиповыми файлами.

arseniiv в сообщении #379037 писал(а):

А что я вчера вечером на бумаге тогда изобразил?

Не видел, что Вы вчера вечером на бумаге изобразили. Могу лишь смутно догадаться, что имелось в виду. Но там без вспомогательного массива текущих значений всех производных всё равно не обойтись, и если порядок требуемой производной заранее не определён -- тот массив будет иметь такой же размер, что и сам файл.

[arseniiv]

ewert в сообщении #379065 писал(а):

Но там без вспомогательного массива текущих значений всех производных всё равно не обойтись, и если порядок требуемой производной заранее не определён -- тот массив будет иметь такой же размер, что и сам файл.

Думаю, тут можно придумать более-менее разумное ограничение на $k$, например, 1024. В память влезет!

[Ой, не заметил, что там используется Real. Если это не Delphi (там это синоним Double, а старый называется Real48 на всякий случай), то очень плохо. Лучше использовать Double или Extended (а преподавателей, пишущих Real, надо привязывать к стулу).] Так переменная типа array[0..1023] of Extended займёт «всего» 10 килобайт!

[grozglaz]

arseniiv в сообщении #379015 писал(а):

Да, вы не так меня поняли. Попробуйте не просто скопировать и исправить, а сделать трассировку (на бумаге). Возьмите многочлен $k_1 x^n + k_2 x^{n-1} + \ldots + k_n x + k_{n+1}$ и подавайте его на вход алгоритму (лучше сделать таблицу $i$, $k_i$, $p_i$, $p'_i$, $p''_i$). Вы увидите, что надо сделать, чтобы вторая производная вычислялась правильно (и третья, и $k$-я). А в текущем коде вторая производная вообще не вычислится никогда, даже в конце цикла.

Можно как-то поподробнее? Не очень понятно.

[arseniiv]

Используя реккурентные соотношения для значений полинома и производной полинома на шаге $i$ $p_i$ и $p'_i$ (очевидно, верные) попробуйте использовать для $p''_i$ то же соотношение, что и для $p'_i$ и отметьте, чего не хватает для правильности. Потом попробуйте найти выражение для $p^{(3)}_i$, а уже затем для $p^{(n)}_i$. А чтобы проверять правильность, представьте себя программой и на листе бумаги для первых, например, 5 итераций распишите все эти значения по-очереди.

(Если вы не знаете, как из кода получить рекуррентные соотношения, то вот они)

$\left\{\begin{array}{l} p_0 = 0 \\ p_{i + 1} = p_i x + k_i \end{array}\right.$
$\left\{\begin{array}{l} p'_0 = 0 \\ p'_{i + 1} = p'_i x + p_i \end{array}\right.$

[grozglaz]

arseniiv в сообщении #379106 писал(а):

Используя реккурентные соотношения для значений полинома и производной полинома на шаге $i$ $p_i$ и $p'_i$ (очевидно, верные) попробуйте использовать для $p''_i$ то же соотношение, что и для $p'_i$ и отметьте, чего не хватает для правильности. Потом попробуйте найти выражение для $p^{(3)}_i$, а уже затем для $p^{(n)}_i$. А чтобы проверять правильность, представьте себя программой и на листе бумаги для первых, например, 5 итераций распишите все эти значения по-очереди.

(Если вы не знаете, как из кода получить рекуррентные соотношения, то вот они)

$\left\{\begin{array}{l} p_0 = 0 \\ p_{i + 1} = p_i x + k_i \end{array}\right.$
$\left\{\begin{array}{l} p'_0 = 0 \\ p'_{i + 1} = p'_i x + p_i \end{array}\right.$

$\left\{\begin{array}{l} $p^{(n)}_i$_0 = 0 \\ $p^{(n)}_i$_{i + 1} = ( $p^{(n)}_i$_i x + $p^{(n-1)}_i$_i ) * n! \end{array}\right.$
Вот это? Или я опять что-то напутал? =\