Форум программистов, компьютерный форум, киберфорум
Free Pascal
Форум программистов и сисадминов Киберфорум > Форум программистов > Pascal (Паскаль) > Free Pascal
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
2 из 2 « 1 2
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
1

Оригинальное умножение

04.06.2012, 22:33. Показов 2724. Ответов 27
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Существует код умножения двух длинных чисел:
Pascal
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

type
  numb = array[1..22500] of byte;
 
procedure scanf(var a: numb);
var
  i, n: integer;
  x: byte;
  c: char;
begin
  n := 0;
  repeat    
    read(c);
    if (c in ['0'..'9']) then begin
      inc(n);
      a[n] := ord(c) - 48; end;
  until (c = #13) or (c = ' ');
  for i := 1 to (n div 2) do
  begin
    x := a[i]; a[i] := a[(n - i) + 1]; a[n - i + 1] := x;
  end;
end;
 
function dlina(const a: numb): integer;{определение длины числа}
var
  i: integer;
begin
  i := 22500;
  while(a [i] = 0) and (i > 1) do
    i := i - 1;
  dlina := i;
end;
 
procedure umn(var a, b, c: numb);{собственно умножение длинного на длинное}
var
  i, g, n, m: integer;
  p: 0..9;
  v: byte;
begin
  m := dlina(a);
  n := dlina(b);
  for i := 1 to m do
  begin
    p := 0;
    for g := 1 to n do
    begin
      v := a[i] * b[g] + p + c[i + g - 1];
      c[i + g - 1] := v mod 10;
      p := v div 10;
    end;
    c[i + n] := p;
  end;
  for i := 1 to 22500 do
    a[i] := c[i];
end;
 
procedure printf(var a: numb);
var
  i: integer;
begin
  for i := dlina(a) downto 1 do
    write(a[i]);
  writeln;
end;
 
var
  a, b, c: numb;
 
begin
  scanf(a);
  scanf(b);
  umn(a, b, c);
  printf(c);
end.
Но как произвести умножение по основанию системы счисления не 10, как приведено в примере, а 10000 для экономии места и ускорения процесса? Я, например, даже считать такое число не смогу.
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 04.06.2012, 22:33
Ответы с готовыми решениями:

Оригинальное написание слова
Хочу написать слово только не с помощью букв, а с помощью цифр 1 и 0. Типа 000000 00000 ...

Оригинальное меню в консоли
Доброго вечера, помогите разобраться с некоторым кодом, в котором содержится интересное консольное...

Как вернуть оригинальное оформление?
Здравствуйте Как отредактировать сборку и убрать изображение игры battlefield, вернуть...

Оригинальное фото конвертировать в видео
Здравствуйте, мой фотоаппарат делает снимки с разрешением 3648 на 2736 - это у него самый большой...

27
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
16.06.2012, 10:35 21
Author24 — интернет-сервис помощи студентам
Можно и в байте хранить больше, надо только поменять основание системы. Хотя, процедыр ввода/вывода и в этом случае придётся менять.
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
16.06.2012, 11:23 22
Цитата Сообщение от SeryZone Посмотреть сообщение
valeriikozlov, вот так пойдёт? Вроде бы работает:
ответ на этот вопрос даст тестирующая система e-olimp. Судя по Вашим попыткам Вы забыли что на e-olimp обязательно после вывода ответа нужен переход на новую строку. Добавьте после:
Pascal
1

  WriteLong(c);
Pascal
1

writeln();
и сдавайте задачу.
0
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
16.06.2012, 12:11  [ТС] 23
http://www.e-olimp.com/solutions/704585. Не сработало. Сам алгоритм умножения менять?

Добавлено через 13 минут
Цитата Сообщение от taras atavin Посмотреть сообщение
А если в самом числе есть 0? Или чем больше индекс, тем разряд старше?
Все числа перевёрнуты, поэтому до самого числа нули не учитываются!

Добавлено через 7 минут
Я понял! Система учитывает наверное и считывание числа. Т. к. Я тестировал самые огромные числа.

Добавлено через 8 минут
Я бы попробовал на С++, только ввод/вывод чисел не могу реализовать!
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
16.06.2012, 12:18 24
Цитата Сообщение от SeryZone Посмотреть сообщение
Сам алгоритм умножения менять?
не нужно. Для того что бы работало нужно немного переделать функцию: ReadLong() см комментарии:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

procedure ReadLong(var A: Numb);
var
  c: array[1..24500] of char; 
  t: char;
  i, l, n, k: longint;
begin
  n := 1;  
  repeat
    read(t);
    if (t in ['0'..'9']) then begin
      c[n] := t; inc(n);
    end;
  until (t = #13) or (t = ' ') or eof;   // вот здесь нужно добавить eof (по условию одно число заканчивается пробелом, второе концом файла (концом входного потока))
  l := 1; k := 1;
  for i := n - 1 downto 1 do 
  begin
    a[l] := a[l] + (ord(c[i]) - 48) * k;
    k := k * 10;
    if (n - i) mod 8 = 0 then begin inc(l); k := 1; end;
  end;  
end;
Это позволит пройти некоторые, но не все тесты. Пробуйте пока сами усовершенствовать код. Пока буду занят, как освобожусь, то дальше посмотрю.
1
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
16.06.2012, 18:10  [ТС] 25
В ответе какие-то цифры до ответа выдает!
Pascal
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

program VERY_RAPID_MULTIPLY;
 
 type
  Numb = array[1..49000] of int64;
 
 procedure ReadLong(var A: Numb);
var
  c: array[1..24500] of char; 
  t: char;
  i, l, n, k: longint;
begin
  n := 1;  
  repeat
    read(t);
    if (t in ['0'..'9']) then begin
      c[n] := t; inc(n);
    end;
  until (t = #13) or (t = ' ') or eof or eoln;
  l := 1; k := 1;
  for i := n - 1 downto 1 do 
  begin
    a[l] := a[l] + (ord(c[i]) - 48) * k;
    k := k * 10;
    if (n - i) mod 8 = 0 then begin inc(l); k := 1; end;
  end;  
end;
 
function dlina(const a: numb): longint;{îïðåäåëåíèå äëèíû ÷èñëà}
var
  i: longint;
begin
  i := 49000;
  while(a [i] = 0) and (i > 1) do
    i := i - 1;
  dlina := i;
end;
 
 procedure multiply(var a, b, c: Numb);
var
  i, j, k: longint;
begin
  for i := 1 to dlina(a) do
  begin
    for j := 1 to dlina(b) do    
      c[i + j - 1] := c[i + j - 1] + a[i] * b[j];
    for k := 1 to dlina(c) do
    begin
      if c[k] > 99999999 then begin
        c[k + 1] := c[k + 1] + c[k] div 100000000;
        c[k] := c[k] mod 100000000;
      end; end;
  end;
end;
 
 procedure wr(var a: Numb; k: longint);
begin
  if a[k] < 10 then write('0000000') else
  if a[k] < 100 then write('000000') else
  if a[k] < 1000 then write('00000') else
  if a[k] < 10000 then write('0000') else
  if a[k] < 100000 then write('000') else
  if a[k] < 1000000 then write('00') else
  if a[k] < 10000000 then write('0');
  write(a[k]);
end;
 
 procedure WriteLong(var A: Numb);
var
  i: longint;
  fl: boolean;
begin
  for i := dlina(a) downto 1 do 
  begin
    if fl = true then wr(a, i);
    if (a[i] > 0) and (fl = false) then begin
      write(a[i]); fl := true; end;    
  end;
  if fl = false then write(0); writeln;
end;
 
var
  a, b, c: numb;
 
begin
  Readlong(a);
  readlong(b);
  multiply(a, b, c);
  WriteLong(c);
end.
Добавлено через 7 минут
Нули!
0
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
19.06.2012, 19:53  [ТС] 26
Написал аналогичный код на С++, вааааааааааааще не пашет!
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <stdio.h>
#include <string.h>
__int64 a[49000],b[49000],c[49000]={0};
 
void read(__int64 a[24500])
{
    char c[190000],t='0';
    long i,l=1,n=1,k=1;
    scanf("%s",&c);
    n=(int)strlen(c);
    for (i=n-1;i>=0;i--)
    {
        a[l]=a[l]+(c[i]-48)*k;
        k*=10;
        if ((n-i)%8==0)
        {
            l++; k=1;
        }
    }
}
 
int dlina(__int64 a[])
{
    int i;
    i = 49000;
    while((a [i] = 0)&&(i > 1))
        i--;
    return i;
}
 
void mul(__int64 a[49000],__int64 b[49000], __int64 c[49000])
{
    for (int i=1;i<=dlina(a);i++)
        for (int j=1; j<=dlina(b);j++)
        {
            c[i+j-1]+=a[i]*b[j];
            if (c[i]>99999999) 
            {
                c[i+1]+=c[i]/100000000;
                c[i]%=100000000;
            }
        }
}
 
void wr(__int64 a[49000],int k)
{
    if (a[k] < 10) printf("0000000"); else
    if (a[k] < 100) printf("000000"); else
    if (a[k] < 1000) printf("00000"); else
    if (a[k] < 10000) printf("0000"); else
    if (a[k] < 100000) printf("000"); else
    if (a[k] < 1000000) printf("00"); else
    if (a[k] < 10000000) printf("0");
    printf("%lld",a[k]);
}
 
void write(__int64 a[49000])
{
    int i; bool f=false;
    if (a[dlina(a)]>0) { printf("%lld",a[dlina(a)]); f=true; }
    for (i=(dlina(a)-1);i>0;i--)
    {
        if (f==true) wr(a,i);
        if ((a[i]>0)&&(f==false))
        {
            printf("%lld",a[i]);
            f=true;
        }
    }
    if (f==false) puts("0"); else puts("");
}
 
int main()
{
    read(a);
    read(b);
    mul(a,b,c);
    write(c);
}
0
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
23.06.2012, 16:54  [ТС] 27
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

#include <stdlib.h>
#include <iostream>
 
using namespace std;
 
// Determine Little-Endian or Big-Endian
 
#define CURRENT_BYTE_ORDER       (*(int *)"\x01\x02\x03\x04")
#define LITTLE_ENDIAN_BYTE_ORDER 0x04030201
#define BIG_ENDIAN_BYTE_ORDER    0x01020304
#define PDP_ENDIAN_BYTE_ORDER    0x02010403
 
#define IS_LITTLE_ENDIAN (CURRENT_BYTE_ORDER == LITTLE_ENDIAN_BYTE_ORDER)
#define IS_BIG_ENDIAN    (CURRENT_BYTE_ORDER == BIG_ENDIAN_BYTE_ORDER)
#define IS_PDP_ENDIAN    (CURRENT_BYTE_ORDER == PDP_ENDIAN_BYTE_ORDER)
 
//
// Karatsuba multiplication algorithm
//
//            +------+------+
//            |  x1  |  x0  |
//            +------+------+
//                   *
//            +------+------+
//            |  y1  |  y0  |
//            +------+------+
//                   =
//     +-------------+-------------+
//  +  |    x1*y1    |    x0*y0    |
//     +----+-+------+------+------+
//          . .             .
//          . .             .
//          +-+------+------+
//       +  | x0*y1 + x1*y0 |
//          +-+------+------+
//
 
//
// Params:
//     T  - is type of x0, x1, y0 and y1 halves
//     T2 - is type of x, y and half of res
//
template<typename T, typename T2>
inline void Karatsuba_multiply(const T * x, const T * y, T2 * res)
{
    if (IS_LITTLE_ENDIAN)
        return Karatsuba_multiply_little_endian(x,y,res);
    if (IS_BIG_ENDIAN)
        return Karatsuba_multiply_big_endian(x,y,res);
}
 
template<typename T, typename T2>
inline void Karatsuba_multiply_little_endian(const T * x, const T * y, T2 * res)
{
    // Define vars (differs from byte order)
 
    #define ptrRes ((T*)res)
    T2 &  lowWord = (T2&)(ptrRes[0]);
    T2 &  midWord = (T2&)(ptrRes[1]);
    T2 & highWord = (T2&)(ptrRes[2]);
    T  & highByte = (T &)(ptrRes[3]);
    #undef ptrRes
 
    const T & x0 = x[0];
    const T & x1 = x[1];
    const T & y0 = y[0];
    const T & y1 = y[1];
 
    // Multiply action
 
    lowWord  = x0 * y0;
    highWord = x1 * y1;
 
    T2 m1 = x0 * y1;
    T2 m2 = x1 * y0;
 
    midWord += m1;
    if (midWord < m1) highByte++;
    midWord += m2;
    if (midWord < m2) highByte++;
}
 
template<typename T, typename T2>
inline void Karatsuba_multiply_big_endian(const T * x, const T * y, T2 * res)
{
    // Define vars (differs from byte order)
 
    #define ptrRes ((T*)res)
    T2 & highWord = *(T2*)(ptrRes+0);
    T2 &  midWord = *(T2*)(ptrRes+1);
    T2 &  lowWord = *(T2*)(ptrRes+2);
    T  & highByte = *(T *)(ptrRes+0);
 
    const T & x0 = x[1];
    const T & x1 = x[0];
    const T & y0 = y[1];
    const T & y1 = y[0];
 
    // Multiply action
 
    lowWord  = x0 * y0;
    highWord = x1 * y1;
 
    T m1 = x0 * y1;
    T m2 = x1 * y0;
 
    midWord += m1;
    if (midWord < m1) highByte++;
    midWord += m2;
    if (midWord < m2) highByte++;
}
 
int main()
{
    typedef unsigned char   u8;
    typedef unsigned short u16;
    typedef unsigned int   u32;
 
    u16 a = 1000;
    u16 b = 2000;
    u32 r = 0;
 
    u8  * a_ptr = (u8*)&a;
    u8  * b_ptr = (u8*)&b;
    u16 * r_ptr = (u16*)(void*)&r;
 
    Karatsuba_multiply(a_ptr, b_ptr, r_ptr);
 
    cout << r;
}
А вот крайне непонятный алгоритм Карацубы, и то не для длинных чисел!
0
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
21.07.2012, 21:46  [ТС] 28
В общем, нужно реализовать алгоритм Карацубы.
0
21.07.2012, 21:46
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 21.07.2012, 21:46
Помогаю со студенческими работами здесь

Восстановление HDD в оригинальное сосотяние
Добрый день! Мне необходима Ваша помощь. Отнеситесь к этому серьезно. Есть н/б hp. На нем стояла...

Оригинальное и полезное применение простанств имён
Кто как рекомендует применять пространства имён (namespace) ?

Оригинальное разрешение экрана съедает пуск
Собственно сабж. Ноут подключен к монитору по вга. Монитор Samsung s24d300, оптимальное разрешение...

Получить оригинальное имя файла по ссылке
Есть сайт с ссылками на файлы, но в ссылках указан не настоящий путь (напр...

Как получить оригинальное название файла по URL?
Здравствуйте! Суть задачи состоит в том, что бы получить &quot;оригинальное&quot; название файла, который...

При скачивании файла вернуть ему оригинальное имя
При загрузке файла на сервер он получает имя типа 7f10005450c0169ed4ef8603b1086bc7, это сделано для...


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

Или воспользуйтесь поиском по форуму:
28
Ответ Создать тему
2 из 2 « 1 2
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru