Люди помогите реализовать рекурсивный алгоритом,на С++ или PASCAL

Ответить
Аватара пользователя
samr
Сообщения: 4
Зарегистрирован: 02 янв 2008, 06:42
Откуда: Kazan
Контактная информация:

Дано. Многочлен n-й степени от одной переменной задан вектором b[1..n] своих корней:P(x)=(x-b1)(x-b2)(x-b3)...(x-bn)
Получить. Стандартное представление этого многочлена, т.е. соответствующий вектор a[0..n]: a0+a1x+a2x*x+.....+an(x*x*x..)
Пусть n является степенью двойки. Исходная задача сводится к подзадачам:
1. Получить стандартное представление для многочлена с корнями b[1.. n DIV 2].
2. Получить стандартное представление для многочлена с корнями b[n DIV 2 +1, n].
3. Получить стандартное представление для произведения этих двух многочленов.
Составить рекурсивную процедуру на основе вышеприведенного сведения и соответствующую программу решения исходной задачи на основе этой рекурсивной процедуры.
Я решил задачу рекурсивно,но тем алгоритмом который предлагается,пожалуйста помогите реализовато алгоритом или более подробно его объяснить,можно и на схеме???? :confused:
Аватара пользователя
Turboworld
Сообщения: 29
Зарегистрирован: 27 дек 2007, 23:31
Контактная информация:

samr писал(а):1. Получить стандартное представление для многочлена с корнями b[1.. n DIV 2].
2. Получить стандартное представление для многочлена с корнями b[n DIV 2 +1, n].
3. Получить стандартное представление для произведения этих двух многочленов.
Попробуй объяснить мне что это за хрени такие? Я например этих пунктов не понял чво-та...
:confused:
Да и ты говоришь что решил рекурсивно... и тем алгоритмом, который тут дан, тогда что еще остаётся сделать то? :)
Решаю задачки на Паскале. Практически любой сложности. Да, дорого. Но договориться всегда можно. Аська 337351594 ;)
Аватара пользователя
samr
Сообщения: 4
Зарегистрирован: 02 янв 2008, 06:42
Откуда: Kazan
Контактная информация:

решение на си++,я решил так
#include <iostream>
using namespace std;
double b[2049];
double* solve(int x, int y) {
double* ans = new double[y - x + 2];
if (y - x == 0) {
ans[0] = -b[x];
ans[1] = 1;
return ans;
}
double* l = solve(x, (x + y) / 2);
double* r = solve((x + y) / 2 + 1, y);
int m = (y - x + 1) / 2;
for (int i = 0; i <= 2 * m; i++) ans = 0;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= m; j++) {
ans[i + j] += l * r[j];
}
}
delete[] l;
delete[] r;
return ans;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> b;
}
double* a = solve(1, n);
for (int i = 0; i <= n; i++) cout << a << ' ';
delete[] a;
}
Ответить