Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
AlekseyL
0 / 0 / 0
Регистрация: 02.05.2014
Сообщений: 3
#1

Алгоритм Карацубы - C++

04.05.2014, 02:39. Просмотров 1220. Ответов 0
Метки нет (Все метки)

Помогите, пожалуйста с задачей. Ответ вроде верный, но по времени не проходит. Подскажите что переделать.
C++ (Qt)
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
51
52
53
54
55
#include <cstdio>
#include <cstring>
#define forn(i, n) for (int i = 0; i < (int)(n); i++)
void Karatsuba( int n, int *c, int *a, int *b )
{
  if (n <= 8)
  {
    forn(i, 2 * n)
      c[i] = 0;
    forn(i, n)
      forn(j, n)
        c[i + j] += a[i] * b[j];
    return;
  }
  int k = n / 2;
  int *f = new int[n];
  int *a12 = new int[k];
  int *b12 = new int[k];
 
  Karatsuba(k, c, a, b);
  Karatsuba(k, c + n, a + k, b + k);
  forn(i, k)
  {
    a12[i] = a[i] + a[i + k];
    b12[i] = b[i] + b[i + k];
  }
  Karatsuba(k, f, a12, b12); 
  forn(i, n)
    f[i] -= c[i] + c[i + n];
  forn(i, n)
    c[i + k] += f[i];
}
const int N = 20;
int a[N], b[N], c[2 * N];
void read( int *a )
{
  static char s[N + 1];
  gets(s);
  int k = 0;
  for (int i = strlen(s) - 1; i >= 0; i--)
    a[k++] = s[i] - '0';
}
void out( int n, int *a ){
  forn(i, n)
    printf("%d", a[n - i - 1]);
}
int main(){
  read(a);
  read(b);
  Karatsuba(N, c, a, b);
  forn(i, 2*N)
    if (c[i] >= 10)
      c[i + 1] += c[i] / 10, c[i] %= 10;
  out(2 * N, c);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.05.2014, 02:39     Алгоритм Карацубы
Посмотрите здесь:

C++ Алгоритм
Волновой алгоритм (алгоритм Ли) C++
C++ c++/алгоритм
алгоритм C++
C++ Алгоритм
Помогите алгоритм для char переделать в алгоритм для float C++
Метод Карацубы умножения длинных чисел C++
C++ Умножение Карацубы
C++ QR алгоритм
C++ Алгоритм
C++ алгоритм бм
Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 23:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru