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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 37, средняя оценка - 4.65
v0l0d1ka
9 / 9 / 0
Регистрация: 14.12.2010
Сообщений: 129
#1

Возведение в степень - C++

09.10.2011, 01:28. Просмотров 5253. Ответов 30
Метки нет (Все метки)

Подскажите, как написать программу возведения 2-ки в миллионную степень и вывести результат на экран.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <math.h>
#include <cstdlib>
 
 
int main ()
{
  printf ("7 ^ 3 = %lf\n", pow (7.0,3.0));
  printf ("4.73 ^ 12 = %lf\n", pow (4.73,12.0));
  printf ("32.01 ^ 1.54 = %lf\n", pow (32.01,1.54));
  printf ("2 ^ 1000000.0 = %lf\n", pow (2.0,1000000.0));
  system("pause");
  return 0;
}
Не работает.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.10.2011, 01:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Возведение в степень (C++):

Возведение в степень - C++
Почему, когда я пытаюсь возвести в квадрат x с типом int, то получается 24, а когда с типом double, то все хорошо и получается 25? ...

Возведение в степень - C++
напишите программный код для С++ Builder

Возведение в степень - C++
Срочно, помогите записать выражение cos^4(x)

Возведение в степень - C++
Дано число n и его нужно возвести в степень s. Можно ли это как-то сделать не используя циклы. Заранее спасибо...

Возведение в степень - C++
Подскажите оператор для возведения числа в n-ую степень. Зарание спасиба

Возведение a в степень b - C++
Пользователь вводит числа а и b, программа считает &quot;а&quot; в степени &quot;b&quot;. Помогите написать код

30
alkagolik
Заблокирован
09.10.2011, 01:33 #2
v0l0d1ka, вы представляете себе агрегат, который в состоянии вычислить
C
1
printf ("2 ^ 1000000.0 = %lf\n", pow (2.0,1000000.0))
это 1000000 / 4 ядер процессора intel x32 плюс еще парочка чтобы вся эта параллель функционировала.
0
v0l0d1ka
9 / 9 / 0
Регистрация: 14.12.2010
Сообщений: 129
09.10.2011, 01:47  [ТС] #3
т.е. на одной обычной машине эта программа будет работать очень долго?
0
aeshes
440 / 203 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 02:00 #4
Такое большое число как 2 в степени 1 млн не влезет в стандартные типы и значит использовать функцию pow нельзя
Нужен или собственный класс больших чисел - но это вряд ли хороший подход, если нужно только двойку рассматривать
Или посмотреть что-то насчет представления степеней двойки, например в двоичном виде 2 в степени 1 млн запишется как 10.......0 - миллион нулей после единицы
А еще можно заметить закономерности построения степеней двойки, например они заканчиваются на 2, 4, 8, 6 всегда и эти цифры повторяются в указанном порядке))
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
09.10.2011, 02:04 #5
ну простая арифметика показывает, что число будет
2 ^ 10e6 = (2^10) ^ 10e5 ~ 10e3 ^ 100000 = 10e300000 ну довольно много
тем не менее есть более менее быстрые алгоритмы возведения в степень, идея такая, несложно распространить на миллион
2^30 = 4^15 = 8^14 = 64^7 = 128^6 = 16384^3 = 32768^2 = 1073741824
получится всего лишь порядка полумиллиона операций умножения и деления
конечно вопрос в том как промежуточные вычисления да и результа в 300000 знаков хранить
0
alkagolik
Заблокирован
09.10.2011, 02:05 #6
Цитата Сообщение от v0l0d1ka Посмотреть сообщение
т.е. на одной обычной машине эта программа будет работать очень долго?
в предыдущем посте я преувеличил конечно, все немного проще... но сути не меняет. максимальную разрядность можно вычислить так
C
1
sizeof(long double) * 8;
это и будет максимальная степень без применения методов длинной арифметики.
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
09.10.2011, 02:15 #7
не, я кстати соврал там для получения степени числа надо порядка 20-30 умножений
но хранить результат все равно както нужно
0
aeshes
440 / 203 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 03:29 #8
Написала программку, решающую задачу "в лоб", т.е. она действительно возводит 2 в степень 100 000 путем перемножения 2*2*2... Естественно, работает ОЧЕНЬ долго) При возведении в степень 1 млн вообще можно будет состариться)
Числа хранятся в виде массивов
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
#include <iostream>
using namespace std;
 
void print(int* a, int N)
{
    for(int i=0;i<N;i++)
        cout<<a[i];
    cout<<endl;
}
 
int main()
{
    int Na=1,Nb;
    int *a;
    int *b;
    a=new int[Na];
    a[0]=2;//стартуем с 2-ки
    int perenos=0;
    int j=1;
    while(j<100000)
    {
        Nb=Na;
        if(a[0]>4)
        {
                Nb++;
        }
        b=new int[Nb];
        //b[0]=0;
        perenos=0;
        for(int i=Na-1;i>=0;i--)
        {
            b[i+Nb-Na]=(a[i]*2)%10;
                if(perenos) b[i+Nb-Na]+=perenos;
            perenos=(a[i]*2)/10;
        }
        if(Nb>Na) 
            b[0]=perenos;
        if(Nb>Na)
        {
            delete []a;
            a=new int [Nb];
        }
        Na=Nb;
        for(int i=0;i<Na;i++)
            a[i]=b[i];
        delete []b;
        j++;
    }
    print(a,Na);
    delete[]a;
}
Завтра попытаюсь реализовать алгоритм быстрого возведения в степень
Если есть какие-то мысли по оптимизации хранения числа. буду рада услышать
0
alkagolik
Заблокирован
09.10.2011, 04:27 #9
а может кто знает реально ли в обход стандарта оперировать в Си деками по пол байта?
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 07:53 #10
На яве у меня полминуты считает.
Ну там бинарное возведение в степень используется, оно за O(log n) работает.
На плюсах можно быстрее.
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
09.10.2011, 08:18 #11
Цитата Сообщение от alkagolik Посмотреть сообщение
реально ли в обход стандарта оперировать в Си деками по пол байта?
Кроме логических операций есть несколько интристик (не знаю, как их по человечески назвать), которые для студии заточены. Циклические сдвиги и т.п., чего в Си нет они реализуют.
А вообще я вопрос не понял.)
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
09.10.2011, 09:25 #12
Цитата Сообщение от diagon Посмотреть сообщение
На яве у меня полминуты считает
haskell считает чуть больше секунды

Добавлено через 32 минуты
Цитата Сообщение от Nameless One Посмотреть сообщение
haskell считает чуть больше секунды
даже меньше, 0.3 секунды
0
aeshes
440 / 203 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 13:46 #13
Так я ж и не претендую на самый оптимальный вариант решения задачи) Я ж сказала, что решаю "в лоб"
А можно глянуть код хоть на яве, хоть на хаскеле - для вдохновения?
Как будут силы, напишу бинарное возведение в степень, это ускорит работу. Еще наверное надо подумать над оптимизацией хранения числа
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 13:49 #14
Цитата Сообщение от aeshes Посмотреть сообщение
А можно глянуть код хоть на яве, хоть на хаскеле - для вдохновения?
Да все также "в лоб"
Java
1
2
3
4
5
6
7
8
9
10
import java.math.BigInteger;
 
class Main
{
    public static void main( String[] args )
    {
        System.out.println( BigInteger.valueOf(2).pow( 1000000 ) );
    }
 
}
Или так(секунд за 10 считает):
Python
1
2 ** 1000000
0
aeshes
440 / 203 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 13:52 #15
ну так здесь используются надстройки для работы с большими числами, включенные в среду, как я поняла
А если без них? т.е. самостоятельно реализовать задачу - есть пример?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.10.2011, 13:52
Привет! Вот еще темы с ответами:

Возведение в степень - C++
Совсем недавно начал изучать C++. Учу по книге. Было задание: Вводишь число Вводишь степень в которую надо возвести это число ...

Возведение в степень! - C++
Возник вопрос - Возможно пока не понятна в чем мысль! Попробую на примере объяснить! Возведение числа 2 в 1000 - ую степень будет...

возведение в степень! - C++
Кто помнит функцию возведения в степень.?? &quot;трам-пам-пам&quot; (a,b) ???? Добавлено через 3 минуты И еще желательно...

Возведение в степень. C++ - C++
можно ли написать программу для возведения в вводимую степень вводимого числа с помощью рекурсивной функции


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
09.10.2011, 13:52
Ответ Создать тему
Опции темы

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