Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
DEVILD_Roma
4 / 4 / 1
Регистрация: 09.10.2014
Сообщений: 125
Завершенные тесты: 1
1

Возведение числа а в степень n

02.02.2016, 18:28. Просмотров 835. Ответов 14
Метки нет (Все метки)

Возведение числа а в степень n ,задача не проста чем , 1<=а<=10 | 1<=n<=7000
Степень может быть 7000 , и тут у меня возникли трудности , есть идеи ?
(обязательно использовать массив, функции нельзя)
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2016, 18:28
Ответы с готовыми решениями:

Возведение числа в степень
Помогите написать программу, возводящщую число M в степень N (-10&lt;M&lt;10, 0&lt;N&lt;10...

Возведение из числа степень
Прошу помочь. Вводим любое число n и надо возвести её степень. (притом, должно...

Возведение числа n в степень m.
Написать программу - возведение числа n в m-ю степень. Входные данные поступают...

Возведение числа в степень n-1
Есть формула {(-1)}^{n-1}*{3}^{n-1} , n увеличивается циклом на 1. Как записать...

Возведение числа в степень!
Хай всем кто на форуме! Помогите с задачей! Надо возвести число в степень...

14
Difaust
111 / 88 / 66
Регистрация: 27.04.2014
Сообщений: 297
02.02.2016, 19:01 2
C++
1
2
3
4
5
6
7
    int a = 3;
    long long s = 1;
    for(int i=0; i<7000; i++)
    {
        s *=a;
        cout << s;
    }
0
DEVILD_Roma
4 / 4 / 1
Регистрация: 09.10.2014
Сообщений: 125
Завершенные тесты: 1
02.02.2016, 19:16  [ТС] 3
а и n нужно вводить с клавиатуры
0
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
02.02.2016, 19:26 4
стандартными средствами только длинной арифметикой
1
zer0mail
2452 / 2089 / 216
Регистрация: 03.07.2012
Сообщений: 7,571
Записей в блоге: 1
02.02.2016, 21:07 5
Цитата Сообщение от Difaust Посмотреть сообщение
int a = 3;
long long s = 1;
37000свыше 3300 знаков. Никакой long long (и даже double) не потянут.
0
sourcerer
Модератор
Эксперт CЭксперт С++
4863 / 2044 / 325
Регистрация: 20.02.2013
Сообщений: 5,545
Записей в блоге: 24
Завершенные тесты: 1
02.02.2016, 21:22 6
DEVILD_Roma, boost::multiprecision Вам в помощь1.
_______________________
1 предвосхищая Ваши вопросы.
0
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
02.02.2016, 22:01 7
gru74ik, или гугле )
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
#include <bits/stdc++.h>
using namespace std;
int main() {
    const int base = 1e9;
    int x, n,b;
    cin >> x >> n;
    b = x;
    int carry = 0;
    vector<int> a;
    a.push_back(x);
    for (int j=1;j < n;j++) {
        for (size_t i = 0; i < a.size() || carry; ++i) {
            if (i == a.size())
                a.push_back(0);
            long long cur = carry + a[i] * 1ll * b;
            a[i] = int(cur % base);
            carry = int(cur / base);
        }
        while (a.size() > 1 && a.back() == 0)
            a.pop_back();
    }
    for (auto i : a)
        cout << i;
    return 0;
}
Добавлено через 2 минуты
только 10 в некоторых степенях не считает ,это автору пофиксить
0
yasno
Заблокирован
02.02.2016, 22:03 8
DEVILD_Roma, длинная арифметика имитация действий в столбик, если надо могу скинуть готовую библиотеку... но лучше самим сделать не так уж и сложно)
0
DEVILD_Roma
4 / 4 / 1
Регистрация: 09.10.2014
Сообщений: 125
Завершенные тесты: 1
05.02.2016, 18:04  [ТС] 9
Я думаю что нужно для начала поместить результат а ^ n куда-то (но если n=7000 врятли оно влезет куда-то )
для этого как то разбить при возведении на отдельные части...или к примеру узнать длину числа результата и N-е количество символов справа налево записывать в массив , и вывести потом все элементы массива , но опять таки размер массива будет непонятно каким...буду рад Вашим идеям,кодам,помощи..
0
DEVILD_Roma
4 / 4 / 1
Регистрация: 09.10.2014
Сообщений: 125
Завершенные тесты: 1
09.02.2016, 17:11  [ТС] 10
Уже делал тему но никто ничего не подсказал...
Возведение числа а в степень n ,задача не проста чем , 1<=а<=10 | 1<=n<=7000
Степень может быть 7000 .10^7000 это 1 и семь тысяч нулей(по условию а=9 , это максимум,из этого следует что размера массива в 7000 хватит чтобы поместить каждую цифру ответа в отдельные элемент массива)но куда поместить сам ответ я не знаю в double он не влезет , может через string ?Буду рад помощи.
(обязательно использовать массив, функции нельзя)
0
provor
3 / 3 / 3
Регистрация: 04.02.2016
Сообщений: 22
09.02.2016, 19:49 11
Очень интересное задание. Вот мой вариант решения:
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
#include <iostream>
using namespace std;
 
int main(){
    int a, n, result[4000], cur, res;
    cout<<"Введите число> ";
    cin>>a;
    cout<<"Введите степень> ";
    cin>>n;
    if(a==10){
        result[0]=1;
        for(int i=1;i<=n;i++){
            result[i]=0;
        }
        cur=n+1;
    }
    if(a==1){
        result[0]=1;
        cur=1;
    }
    if(a<10){
        result[0]=a;
        cur=1;
        for(int i=0;i<(n-1);i++){
            res=a*result[cur-1];
            if(cur==1 && res>10){
                result[1]=res%10;
                result[0]=res/10;
                cur++;
            }
            else if(cur==1 && res<10)result[cur-1]=res;
            else{
                int memory=0;
                for(int j=(cur-1);j>=0;j--){
                    res=a*result[j]+memory;
                    if(res<10){
                        result[j]=res;
                        memory=0;
                    }
                    else{
                        if(j==0){
                            for(int k=cur;k>1;k--){
                                result[k]=result[k-1];
                            }
                            result[1]=res%10;
                            result[0]=res/10;
                            cur++;
                        }
                        else{
                            result[j]=res%10;
                            memory=res/10;
                        }
                    }
                }
            }
        }
    }
    cout<<"\nОтвет: ";
    for(int i=0;i<cur;i++)cout<<result[i];
    return 0;
}
Может не по максимуму оптимально, но зато все корректно и правильно

Добавлено через 27 минут
количество элементов в массиве правда нужно будет увеличить, если нужны будут выражения типа 9^7000
1
Krock21rus
74 / 74 / 27
Регистрация: 18.11.2013
Сообщений: 373
Завершенные тесты: 2
09.02.2016, 23:38 12
должен же кто-то бинарное возведение в степень рассказать

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long double stepen(long long a, long long b)
{
  if(b==0)return 1;
  long double ans = stepen(a,b/2);
  ans*=ans;
  if(b%2!=0) ans *= a;
  return ans;
}
 
int main()
{
  long long a,n;
  cin >> a >> n;
  long double ans = 1;
  ans = stepen(a,n);
  printf("%.0Lf", ans);
}
работает на 5^7000, ломается на 6^7000
так же теряется точность

остаётся заменить long double на массив\класс и реализовать * длинных чисел на длинное, стандартный алгоритм за квадрат от длины максимального из этих чисел, итого O(n^2) вроде
так же, если полениться и реализовать просто умножение длинного на короткое, что значительно проще, то будет O(n^2), при 7000 это займёт не больше 1ой секунды

почему бинарное возведение в степень не дало асимптотически лучший результат? или я неправильно посчитал?

сейчас реализую 2ое решение

Добавлено через 6 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
cin.sync_with_stdio(false);
    long long a,n;
    cin >> a >> n;
    int ans[10000];
    long long p=1;
    ans[0]=1;
    for(int i=0;i<n;i++)
    {
        long long tmp=0;
        for(int j=0;j<p;j++)
        {
            ans[j]*=a;
            ans[j]+=tmp;
            tmp=ans[j]/10;
            ans[j]%=10;
            if(j==p-1 && tmp!=0)p++;
        }
    }
    for(int i=p-1;i>=0;i--) cout << ans[i];
241 мс в режиме отладки при тесте 9 7000
1
DEVILD_Roma
4 / 4 / 1
Регистрация: 09.10.2014
Сообщений: 125
Завершенные тесты: 1
16.02.2016, 10:03  [ТС] 13
Цитата Сообщение от Krock21rus Посмотреть сообщение
241 мс в режиме отладки при тесте 9 7000
У Вас тоже правильное решение , но 9 в 7000 не досчитывает до правильного ответа (примерно 10-12 цифр у конце)
0
Krock21rus
74 / 74 / 27
Регистрация: 18.11.2013
Сообщений: 373
Завершенные тесты: 2
16.02.2016, 11:28 14
Цитата Сообщение от DEVILD_Roma Посмотреть сообщение
У Вас тоже правильное решение , но 9 в 7000 не досчитывает до правильного ответа (примерно 10-12 цифр у конце)
увы, всё верно
http://www.wolframalpha.com/input/?i=9^7000
если вы сравнивали со своим решением, то скорее всего у вас не верное
0
DEVILD_Roma
4 / 4 / 1
Регистрация: 09.10.2014
Сообщений: 125
Завершенные тесты: 1
16.02.2016, 15:56  [ТС] 15
Цитата Сообщение от Krock21rus Посмотреть сообщение
увы, всё верно
после удаления строчки : cin.sync_with_stdio(false);
ответ такой как и в моей программе и такой же как на сайте который Вы скинули выше
0
16.02.2016, 15:56
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.02.2016, 15:56

Возведение отрицательного числа в степень
Написал программу по нахождению суммы ряда с заданной точностью(условия ниже)....

Возведение числа в отрицательную степень
#include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int main() {...

Возведение числа в целую степень
Задачка из методички моего вуза. Даны действительные числа a1,…,a10. Вычислить...


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

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

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