(В. Баур, Ф.Штрассен) Дана программа вычисления значения некоторого многочлена P(x₁,..., x_n), содержащая только команды присваивания. Их правые части — выражения, содержащие сложение, умножение, константы, переменные x₁,..., x_n и ранее встречавшиеся (в левой части) переменные. Доказать, что существует программа того же типа, вычисляющая все n производных P/x₁,...,P/x_n, причём общее число арифметических операций не более чем в C раз превосходит число арифметических операций в исходной программе. Константа C не зависит от n.

   Решение

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 55]      

Написать модифицированный вариант алгоритма Евклида, использующий соотношения НОД(a,b) = НОД(a mod b, b) при a≥b, НОД(a,b) = НОД(a, b mod a) при b≥a.

Прислать комментарий

Решение

(В. Баур, Ф.Штрассен) Дана программа вычисления значения некоторого многочлена P(x₁,..., x_n), содержащая только команды присваивания. Их правые части — выражения, содержащие сложение, умножение, константы, переменные x₁,..., x_n и ранее встречавшиеся (в левой части) переменные. Доказать, что существует программа того же типа, вычисляющая все n производных P/x₁,...,P/x_n, причём общее число арифметических операций не более чем в C раз превосходит число арифметических операций в исходной программе. Константа C не зависит от n.

Прислать комментарий

Решение

Даны натуральные a и b, не равные 0 одновременно. Найти d = НОД(a,b) и такие целые x и y, что d = a ^. x + b ^. y.

Прислать комментарий

Решение

В массивах a: array[0..k] of integer и b: array[0..l] of integer хранятся коэффициенты двух многочленов степеней k и l. Поместить в массив c: array[0..m] of integer коэффициенты их произведения. (Числа k,l,m — натуральные, m = k + l; элемент массива с индексом i содержит коэффициент при степени i.)

Прислать комментарий

Решение

Решить предыдущую задачу, используя в алгоритме Евклида деление с остатком.

Прислать комментарий

Решение

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 55]