Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
1 / 1 / 0
Регистрация: 20.11.2012
Сообщений: 100
1

Возвести число в (7) семизначную степень

28.12.2014, 17:27. Просмотров 1948. Ответов 18
Метки нет (Все метки)

Подскажите пожалуйста, как можно реализовать данную функцию? К примеру необходимо число 2 возвести в 1234567 степень. Проблема заключается в выводе такого большого числа. Зарание благодарен.

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
#include <cmath>
#include <iostream>
 
    using namespace std;
 
    int main()
        
{
    
setlocale (LC_ALL,"Russian");
 
int long A,B;
 
    cout << "Введите число необходимое возвести в степень\n\t";      
 
    cin >> A;
 
    cout << "Введите необходимую степень\n\t";
 
    cin >>B;
 
    cout << "Равно\n\t" << pow(A,B) << "\n";
 
            cin.get();
 
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.12.2014, 17:27
Ответы с готовыми решениями:

Как возвести дробное число в целую степень? К примеру 2,7 возвести в степень 2 на C++.
Как возвести дробное число в целую степень? К примеру 2,7 возвести в степень 2 на C++.

Если введенное число отрицательное и четное, то возвести его в 3 степень, иначе возвести в квадрат
Ввести целое число В. Если В отрицательное и четное, то возвести его в 3 степень, иначе возвести в...

Возвести число в степень
Дано натуральное n. Написать программу вычисления a^n(&quot;а&quot; в степени n)

Возвести число y в степень 2000
Помогите пожалуйста Нужно как-то придумать как возвести число y в степень 2000 на с++ уже не знаю...

18
Заблокирован
28.12.2014, 17:52 2
Если задача в том, чтобы вывести точное значение - то нужна длинная арифметика.

Если задача в том, чтобы просто возвести в степень и получить приблизительное значение мантиссы и порядок - то используйте double.
2
Модератор
Эксперт С++
10147 / 8497 / 5164
Регистрация: 18.12.2011
Сообщений: 22,734
28.12.2014, 18:10 3
С double можно возвести только в 308 степень.
Только длинная арифметика!
1
338 / 338 / 331
Регистрация: 02.10.2014
Сообщений: 666
28.12.2014, 18:12 4
Думаю задача не на длинную арифметику.
Для 5-ти значной степени программа уже работает долго.
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
#include <iostream>
#include <iomanip>
 
const int BASIS = 1000000;
const int N = 10000;
 
using namespace std;
 
void  Transform(int n, int a[], int &n_a);
void Print(int a[], int n_a);
int Max(int a, int b);
void Sum(int a[], int n_a, int b[], int n_b, int c[], int &n_c);
void Product(int a[], int n_a, int b[], int n_b, int c[], int &n_c);
 
int main(){
    
    int in1, n;
    do{
        cout << "in = ";
        cin >> in1;
    }while(in1 < 1 || 100 < in1);
    do{
        cout << "n = ";
        cin >> n;
    }while(n < 1);
    
    int in[N] = {};
    int n_in;
    Transform(in1, in, n_in);
    
    int out[N] = {};
    int n_out;
    Transform(in1, out, n_out);
    
    for (int i = 1; i < n; ++i){
        
        int buf[N] = {};
        int n_buf = n_out;
        for (int j = 0; j < n_out; ++j)
            buf[j] = out[j];
        
        Product(buf, n_buf, in, n_in, out, n_out);
    }
    
    Print(out, n_out);
}
 
void  Transform(int n, int a[], int &n_a){
    
    n_a = 0;
    while (n > 0){
        
        a[n_a] = n%BASIS;
        ++n_a;
        n /= BASIS;
    }
}
 
void Print(int a[], int n_a){
    
    int h = 0;
    int buf = BASIS - 1;
    while(buf > 0){
        buf /= 10;
        ++h;
    }
    
    for (int i = n_a - 1; i >= 0; --i){
        cout << setfill('0') << setw(h) << a[i];
    }
    cout << endl;
}
 
int Max(int a, int b){
    return a > b ? a : b;
}
 
void Sum(int a[], int n_a, int b[], int n_b, int c[], int &n_c){
    
    int p = 0;
    for (int i = 0; i < Max(n_a, n_b); ++i){
        
        c[i] = (a[i] + b[i] + p)%BASIS;
        p = (a[i] + b[i] + p)/BASIS;
    }
    if (p == 0)
        n_c = Max(n_a, n_b);
    else{
        n_c = Max(n_a, n_b);
        c[n_c] = p;
        ++n_c;
    }
}
 
void Product(int a[], int n_a, int b[], int n_b, int c[], int &n_c){
    
    c[0] = 0;
    n_c = 1;
    
    for (int i = 0; i < n_a; ++i){
        
        int buf[N] = {};
        int p = 0;
        for (int j = 0; j < n_b; ++j){
            buf[j] = (a[i]*b[j] + p)%BASIS;
            p = (a[i]*b[j] + p)/BASIS;
        }
        int n_buf = n_b;
        if (p > 0){
            buf[n_buf] = p;
            ++n_buf;
        }
        
        int buf2[N] = {};
        for (int j = 0; j < n_c; ++j)
            buf2[j] = c[j]; 
        int n_buf2 = n_c;
        
        int buf1[N] = {};
        for (int j = i; j < n_buf + i; ++j)
            buf1[j] = buf[j - i];
        int n_buf1 = n_buf + i;
        
        Sum(buf1, n_buf1, buf2, n_buf2, c, n_c);
    }
}

IrineK, думаю Вы правы Спасибо.
1
Заблокирован
28.12.2014, 18:25 5
Цитата Сообщение от Anadrion Посмотреть сообщение
К примеру необходимо число 2 возвести в 1234567 степень
А если ответ нужно записать в бинарном виде - задача очень упрощается )
Но это - только с двойками.

Добавлено через 4 минуты
Цитата Сообщение от zss Посмотреть сообщение
С double можно возвести только в 308 степень.
Так степень можно периодически "снимать" и хранить отдельно.
А мантиссу считать дальше.
2
1 / 1 / 0
Регистрация: 20.11.2012
Сообщений: 100
28.12.2014, 18:45  [ТС] 6
Цитата Сообщение от IrineK Посмотреть сообщение
Если задача в том, чтобы вывести точное значение
Да, задача состоит именно в том, что бы вывести точное значение.
Цитата Сообщение от IrineK Посмотреть сообщение
А если ответ нужно записать в бинарном виде - задача очень упрощается )
Нет, необходимо получить десятичное значение.
0
Заблокирован
28.12.2014, 19:14 7
Тогда:
1) Научитесь умножать строку на число (от 2 до 9)
2) Научитесь складывать строки
3) На основании (1) и (2) постройте умножение строки на любое число
0
1 / 1 / 0
Регистрация: 20.11.2012
Сообщений: 100
28.12.2014, 19:18  [ТС] 8
Цитата Сообщение от D_in_practice Посмотреть сообщение
Думаю задача не на длинную арифметику.
Для 5-ти значной степени программа уже работает долго.
Как сделать то-же самое, но для 7-ми значной степени, время отработки программы, не столь важны в данной задаче.

Добавлено через 3 минуты
Что вы имели в виду под:
Цитата Сообщение от IrineK Посмотреть сообщение
умножать строку
0
338 / 338 / 331
Регистрация: 02.10.2014
Сообщений: 666
28.12.2014, 19:18 9
Anadrion, Программа работает для 7-ми значной степени!
Только Вы никогда не дождетесь что она досчитает, и я понятия не имею как написать программу с длинной арифметикой способной посчитать такое за нормальное время.
Со строками еще медленнее.
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
30599 / 19972 / 7801
Регистрация: 22.10.2011
Сообщений: 34,772
Записей в блоге: 6
28.12.2014, 19:23 10
Что считается "нормальным" временем? Программа с длинной арифметикой вычисляет все 371642 символа числа 21234567меньше чем за 5 секунд. Включая вывод на экран. Вполне приемлемое время для таких вычислений...
1
Заблокирован
28.12.2014, 19:24 11
Умножать строку:
"797979797979797979797979797979" х 3 =
и умножаем "в столбик": 7 пишем - 2 на ум пошло.
0
338 / 338 / 331
Регистрация: 02.10.2014
Сообщений: 666
28.12.2014, 20:04 12
volvo, ну для 2 может и легко посчитать но надо не только для 2 -ки.
Нормальное время 10 секунд.
10^5 умножений длинных чисел за 10 секунд не посчиталось, больше ждать я не смог.

Добавлено через 31 минуту
371642 символа уже не влезает в мои числа,
1^1234567 программа считала 10 секунд
2^12345 около 30 секунд
0
1401 / 643 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
28.12.2014, 20:16 13
Можно использовать бинарное возведение в степень - a^b за O(log b)
1
Заблокирован
28.12.2014, 21:21 14
Цитата Сообщение от D_in_practice Посмотреть сообщение
2^12345 около 30 секунд
Где-то также

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
//------------------------------------------------------возведение в степень чисел от 2 до 9
#include <iostream>
#include <vector>
 
void Multiplication (std::vector <int> &base, int multiplicator)
{
    int rest = 0;
    for (int i = base.size()-1 ; i>-1; i--)
    {
        base.at(i) *= multiplicator;
        if (rest)
            base.at(i) += rest;
        rest = base.at(i) / 10;
        base.at(i) %= 10;
    }
 
    if (rest)
        base.insert(base.begin(), rest);
}
 
void Print (std::vector <int> &v)
{
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); it++)
        std::cout << *it;
    std::cout << "\n";
}
 
 
//----------------------------------------------------------------------------
int main()
{   
    int base, power; 
 
    std::cout << "Base b = ";
    std::cin >> base;
    std::cout << "Power p = ";
    std::cin >> power;
 
    std::vector <int> result;
    result.push_back(base);
 
    while(--power)
        Multiplication (result, base);
 
    std::cout << "\n\nResult = ";
    Print (result);
    
    std::cin.sync(); std::cin.get();
    return 0;
}
//-----------------------------------------------------------------------------

Сейчас попробую быстрый алгоритм. Но он - неточный.
1
1401 / 643 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
28.12.2014, 21:30 15
IrineK, и почему же он неточный?

Добавлено через 5 минут
Другое дело, что при реализации бинарного возведения в степень потребуется возводить длинное число в квадрат, что накладно по времени - простейшая реализация будет работать за O(n^2), где n - длина числа. В таком случае можно написать алгоритм Карацубы или какой-нибудь из этой области.
0
Заблокирован
29.12.2014, 02:35 16
Dani, ну тогда карацубьте )

Добавлено через 5 часов 3 минуты
Цитата Сообщение от IrineK Посмотреть сообщение
Где-то также
Теперь уже 2^12345 - сразу

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
//------------------------------------------------------возведение в степень чисел от 2 до 9
#include <iostream>
#include <vector>
 
typedef unsigned long long ULL; 
const ULL denom = 1000000000000000000; 
 
void Multiplication (std::vector <ULL> &base, ULL multiplicator)
{
    int rest = 0;
    for (int i = base.size()-1 ; i>-1; i--)
    {
        base.at(i) *= multiplicator;
        if (rest)
            base.at(i) += rest;
        
        if (base.at(i) > denom)
        {
            rest = base.at(i) / denom;
            base.at(i) %= denom;
        }
        else
            rest = 0;
    }
 
    if (rest)
        base.insert(base.begin(), rest);
}
 
void Print (std::vector <ULL> &v)
{
    for (std::vector<ULL>::iterator it = v.begin(); it != v.end(); it++)
        std::cout << *it;
    std::cout << "\n";
}
 
 
//----------------------------------------------------------------------------
int main()
{   
    ULL base; 
    int power; 
 
    std::cout << "Base b = ";
    std::cin >> base;
    std::cout << "Power p = ";
    std::cin >> power;
 
    std::vector <ULL> result;
    result.push_back(base);
 
    while(--power)
        Multiplication (result, base);
 
    std::cout << "\n\nResult = ";
    Print (result);
    
    std::cin.sync(); std::cin.get();
    return 0;
}
//-----------------------------------------------------------------------------
1
1350 / 989 / 313
Регистрация: 28.07.2012
Сообщений: 2,746
29.12.2014, 02:58 17
Цитата Сообщение от IrineK Посмотреть сообщение
Сейчас попробую быстрый алгоритм. Но он - неточный.
Можешь попробовать еще и алгоритм быстрого умножения. Например, алгоритм Карацубы...
0
338 / 338 / 331
Регистрация: 02.10.2014
Сообщений: 666
29.12.2014, 08:13 18
Мысль появилась после этого поста:
Цитата Сообщение от Dani Посмотреть сообщение
Можно использовать бинарное возведение в степень - a^b за O(log b)
Придумал простой алгоритм:
3^6 = 0*3^1 * 1*3^2 * 1*3^4 (6 = 2 + 4)

6 | 0 (6%2 = 0) 6/2 = 3
3 | 1 (3%2 = 1) 3/2 = 1
1 | 1 (1%2 = 1) 1/2 = 0
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//out = in^n
LONG in;
int n;
LONG out = 1;
LONG p = in;
while (n > 0){
    
    if (n%2 == 1)
        out *= p;
    n /= 2;
    p *= p;
}
 
Print(out);
2^24 = 16 777 216 > 9 999 999 (итого не более 2*24 = 48 умножений больших чисел)
(моя программа не тянет, запутался пытаясь переписать на динамические массивы (в обычные число не влезает))
PS позже допишу обязательно.

Добавлено через 23 минуты
было
Цитата Сообщение от IrineK Посмотреть сообщение
Сейчас попробую быстрый алгоритм. Но он - неточный.
Добавлено через 4 минуты
Хотя нет, где деление степени на 2
Цитата Сообщение от IrineK Посмотреть сообщение
C++
1
2
while(--power)
* * * * Multiplication (result, base);
0
Заблокирован
29.12.2014, 11:39 19
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Можешь попробовать еще и алгоритм быстрого умножения.
Хорошо бы кто-то еще попробовал.

Добавлено через 2 минуты
Цитата Сообщение от D_in_practice Посмотреть сообщение
Хотя нет, где деление степени на 2
Пост 16 - это просто улучшение поста 14. Умножение происходит in chunks по 18 позиций.
Что ускоряет процесс.
Не более того.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.12.2014, 11:39

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Возвести число в 7000 степень
Сегодня был на олимпиаде. Проверка была через contester, в задачи есть место где нужно возвести...

Как возвести число в степень
Как возвести число в степень ???

Возвести число в a степень 7 за 4 операций
Нужно использовать только операцию умножения #include &lt;iostream&gt; using namespace std; int...

Возвести число в степень(дробную)
В соседней теме помог сделать возведение в целочисленную степень и вот стало интересно, но что-то...

Asm вставка в С++ возвести число в степень
Возвести число А в степень n (на Assemblerе в С++)

Возвести введенное с клавиатуры число в степень n
Возвести, введенное с клавиатуры число, в степень n, степень тоже вводится с клавиатуры. Возведение...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.