0 / 0 / 0
Регистрация: 06.10.2016
Сообщений: 7
1

Алгоритм Карацубы для умножения полиномов

12.12.2016, 16:40. Показов 2256. Ответов 0

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

Вот функция, которую пыталась сделать:
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
struct Polynom {
  double koef;
  int step;
};
 
Polynom kara(Polynom* polyn1, int size1, Polynom* polyn2, int size2) {
  int n;
  if (polyn1[size1].step < polyn2[size2].step)
  n = polyn2[size2].step;
  else 
  n = polyn1[size1].step;
  if (n == 1) {
    // polyn1 = 1x + 1
    // polyn2 = 2x + 2
    // XY =   (1*2)x^2 + ((1+1)(2+2) - 2 - 2)T + (1*2) = 
    Polynom* buff_res = new Polynom[3];
    buff_res[2].koef = polyn1[1].koef*polyn2[1].koef;
    buff_res[0].koef = polyn1[0].koef*polyn2[0].koef;
    buff_res[1].koef = ((polyn1[0].koef+polyn1[1].koef)*(polyn2[0].koef + polyn2[1].koef) - buff_res[2].koef - buff_res[0].koef);
    return *buff_res;
  }
 
  int mid1 = size1/2, mid2 = size2/2;
  Polynom* buff1_l = new Polynom[mid1];
  Polynom* buff1_r = new Polynom[size1-mid1];
  Polynom* buff2_l = new Polynom[mid2];
  Polynom* buff2_r = new Polynom[size2-mid2];
  for (int i = 0; i < mid1; i++) {
    buff1_l[i].koef = polyn1[i].koef;
    buff1_l[i].step = polyn1[i].step;}
  for (int i = mid1+1; i < size1; i++) {
    buff1_r[i].koef = polyn1[i].koef;
    buff1_r[i].step = (polyn1[i].step - 2);}
  for (int i = 0; i < mid1; i++) {
    buff2_l[i].koef = polyn2[i].koef;
    buff2_l[i].step = polyn2[i].step;}
  for (int i = mid2 + 1; i < size2; i++) {
    buff2_r[i].koef = polyn2[i].koef;
    buff2_r[i].step = (polyn2[i].step - 2);}
 
  Polynom* res1 = new Polynom[];
  *res1 = kara(buff1_l, mid1, buff2_l, mid2);
  Polynom* res2 = new Polynom[];
  *res2 = kara(buff1_r, size1 - mid1, buff2_r, size2 - mid2);
  Polynom* res3 = new Polynom[];
  *res3 = kara(polyn1, size1, polyn2, size2);
  Polynom* res  = new Polynom[];
  /*?*/
  return /*?*/;
}
Но запуталась окончательно. Понимаю, что полиномы нужно рекурсивно разбить на части, но до какого предела их нужно разбивать? Пока старшая степень будет равняться единице? Или до свободного о члена? Сейчас я при создании полиномов прибавляю им старшую степень с нулевым коэффициентом, так, что сам многочлен получается нечетной степени, а структура, которая его содержит, имеет четный размер. Это делается из расчета, что разбивать нужно до ax + b, но я перестала понимать, что делать дальше
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.12.2016, 16:40
Ответы с готовыми решениями:

Реализовать алгоритм Карацубы умножения двух чисел
Здравствуйте, стоит задача реализовать алгоритм Карацубы умножения двух чисел. Нужна помощь по...

Метод Карацубы умножения длинных чисел
Реализован клас длинных чисел, с перегруженными операциями сложения, вычитания, умножения столбиком...

Реализовать программу умножения полиномов
Подскажите плиз! нада прогу сдавать а я разобраться немогу(, задали: &quot;Реализовать программу...

Алгоритм умножения столбиком и алгоритм Карацубы
Нужно написать умножение &quot;столбиком&quot; и умножение по методу Карацубы. Столбиком вроде как считает...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.12.2016, 16:40
Помогаю со студенческими работами здесь

Алгоритм Карацубы, время выполнение алгоритма
Прохожу online курс, третий день бьюсь над заданием. Неудается пройти проверку, выдает ошибку:...

Операции сложения, вычитания и умножения полиномов
Здравствуйте! Есть программа, которая осуществляет ввод-вывод полиномов. Помогите написать...

Алгоритм Штрассена для умножения матриц
Доброе время суток. Не могу догнать, как реализовать алгоритм Штрассена. Если размер умножаемых...

Прокомментировать код - алгоритм Штрассена для умножения матриц
Народ Здравствуйте , есть такая задача ( Курсовая работа, алгоритм Штрассена для умножения матриц )...

По значению x и файлу из M полиномов сформировать новый файл из тех полиномов исходного файла ,чье значение в точке X больше нуля
Помогите пожалуйста решить задачу в паскале : Полином степени ,не большей Nmax представлен...

Написать процедуру для сложения, умножения квадратных матриц N*N, и умножения матрицы на вектор
Написать процедуру для сложения, умножения квадратных матриц N*N, и умножения матрицы на вектор


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru