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

Длинная арифметика - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.63
grisha770
0 / 0 / 0
Регистрация: 14.06.2010
Сообщений: 21
20.06.2010, 18:30     Длинная арифметика #1
Здравствуйте!

Есть задание:
Составить программу для вычисления числа: (2^64) - 1. В результате сохранить все цифры.
2^64 - это 2 в 64-ой степени.

Если честно - то таких задач никогда и не решал. И на занятиях таких работ не было. За то на практике задачу такую дали.

Есть код, который "вроде как" с этой задачей справляется:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[20];
int q;
int i,j;
a[0]=1;
for (i=0; i<64; i++)
       {
       q=0;
       for (j=0; j<20; j++)
            {
             a[j]=a[j]*2+q;
             q=a[j]/10;
             a[j]=a[j]%10;
            }
       }
Но я что-то в нем не разберусь, да и выводить что в результате - непонятно.
Есть у кого по этому поводу мысли?

2^64 = 18446744073709551616 (вот такое число )
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.06.2010, 18:30     Длинная арифметика
Посмотрите здесь:

Длинная арифметика C++
C++ Длинная арифметика
C++ Длинная арифметика
C++ Длинная арифметика
C++ Длинная арифметика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
21.06.2010, 00:20     Длинная арифметика #2
Это как столбиком на бумажке.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[20]; // число, каждый элемент - одна десятичная цифра
int q;
int i,j;
a[0]=1; // 2^0
for (i=0; i<64; i++) // 64 раза умножается на 2
       {
       q=0;
       for (j=0; j<20; j++) // всё, как в школе учили, по циферке
            {
             a[j]=a[j]*2+q; // умножили на 2 цифру, результат может быть от 0 до 18
             q=a[j]/10; // в следующий разряд переносится кол-во десятков
             a[j]=a[j]%10; // а здесь остаётся кол-во единиц - одна цифра
            } // вот и умножили на 2
       } // возвели в нужную степень
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
21.06.2010, 02:08     Длинная арифметика #3
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
#include <iostream>
#include <deque>
#include <algorithm>
#include <functional>
 
typedef std::deque<int>  T_digits;
 
void  normalize(T_digits&  digits)
{
    int  ostatok = 0;
    for(T_digits::reverse_iterator dig_rev_it = digits.rbegin(); 
        dig_rev_it != digits.rend(); ++dig_rev_it)
    {
        *dig_rev_it += ostatok;
        ostatok = *dig_rev_it / 10;
        *dig_rev_it %= 10;
    }
    if(ostatok)
    {
        digits.push_front(ostatok);        
        normalize(digits);
    }    
}
 
T_digits&  operator*=(T_digits&  digits, int  mnozhitel)
{
    std::transform(digits.begin(), digits.end(), digits.begin(), 
                   std::bind2nd(std::multiplies<int>(), mnozhitel));
    normalize(digits);
    return digits;    
}
 
T_digits big_pow(int osnovanie, int stepen)
{
    T_digits  res_digits(1, 1);
    for(int i = 0; i < stepen; ++i)
    {        
        res_digits *= osnovanie;
    }
    return  res_digits;
}
 
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        int osn;
        do
        {
            std::cout << std::endl
                      << "Введите целое основание степени  (>= 0): "; 
            std::cin >> osn;
        }while(osn < 0);
        int stepen;
        do
        {
            std::cout << "Введите целый показатель степени (>= 1): ";        
            std::cin >> stepen;        
        }while(stepen < 1);        
        
        std::cout << osn
                  << " ^ "
                  << stepen
                  << " = ";
        T_digits  res_digits = big_pow(osn, stepen);
        std::copy(res_digits.begin(), res_digits.end(),                   
                  std::ostream_iterator<int>(std::cout)); 
        std::cout << std::endl;
    }
    return 0;
}
Progernata
 Аватар для Progernata
0 / 0 / 0
Регистрация: 07.05.2012
Сообщений: 35
22.05.2012, 19:00     Длинная арифметика #4
Вы не могли бы поподробней объяснить переопределение звёздочки?
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
23.05.2012, 16:35     Длинная арифметика #5
Цитата Сообщение от Progernata Посмотреть сообщение
Вы не могли бы поподробней объяснить переопределение звёздочки?
Если я правильно догадался, то это вопрос ко мне, и он относится к перегрузке оператора «*=».
Это вам надо STL смотреть, а в ней определения шаблонов
• transform
• bind2nd
• multiplies.

Шаблон transform с унарной функцией применяет к каждому элементу входного диапазона заданную функцию и записывает результат в выходной диапазон.

Шаблон bind2nd задает постоянное значение второму аргументу бинарной функции, превращая ее в унарную.

Шаблон multiplies перемножает свои аргументы.
Progernata
 Аватар для Progernata
0 / 0 / 0
Регистрация: 07.05.2012
Сообщений: 35
23.05.2012, 16:58     Длинная арифметика #6
Точно, перегрузка
Я никак не допру, как мы в конце-концов разлагаем огромное число на цифры? В нормализации именно такой процесс - остатки от деления - это цифры числа, но как это в цикле, на каждой итерации умножения - непонятно
Yandex
Объявления
23.05.2012, 16:58     Длинная арифметика
Ответ Создать тему
Опции темы

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