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

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

Войти
Регистрация
Восстановить пароль
 
Asker
116 / 104 / 11
Регистрация: 18.12.2010
Сообщений: 378
#1

Как работает алгоритм возведения числа a в степень n ? - C++

18.02.2013, 14:53. Просмотров 998. Ответов 4
Метки нет (Все метки)

Добрый день! Собственно, вопрос не по коду, а по алгоритму
Почему после выполнения этой программы в res содержится значение an ? Как оно так получается?
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
...
int a;
unsigned int n, k;
long long int res, c;
 
// ... ввод a и n
 
res=1;
c=a;
k=n;
 
if (!n) res = 1; // до сюда все понятно
else while (k) // а дальше не очень
{
    if (!(k%2))
        {
        k/=2;
        c*=c;
        }
    else
        {
        k--;
        res*=c;
        }
}
cout << res << endl;
Добавлено через 19 минут
я на бумажке представил, как бы работала программа для a = 3, n = 15
k==15
c==3;

по циклу, пока k>0

k было равно 15, стало : res = 31; c = 31, k = 14
k было равно 14, стало : res = 31; c = 32, k = 7
k было равно 7, стало : res = 33; c = 32, k = 6
k было равно 6, стало : res = 33; c = 34, k = 3
k было равно 3, стало : res = 37; c = 34, k = 2
k было равно 2, стало : res = 37; c = 38, k = 1
k было равно 1, стало : res = 315; c = 38, k = 0


КАК ТАК?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2013, 14:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как работает алгоритм возведения числа a в степень n ? (C++):

Алгоритм для быстрого возведения в степень - C++
Всем привет, помогите написать алгоритм для возведения в степень дак чтоб для возведения в 15 степень требуется 6 операций умножения, а для...

Придумать алгоритм вычисления квадратного корня, не использую функции возведения в степень - C++
Необходимо придумать алгоритм, вычисления квадратного корня, не использую функции возведения в степень и соответственно саму функцию...

Программа для возведения числа в степень - C++
Здравствуйте. Преподаватель остался недовольным, из-за того, что я это реализовал через готовый оператор, а надо через цикл(а как это...

Написать функцию возведения числа в степень - C++
нужна функция возведения в степень чтобы возвращала результат.... int involution(int a,int b) { cout&lt;&lt;pow(2,3); return ??? ...

Алгоритмы возведения числа в большую степень. - C++
Здраствуйте ещё раз, уважаемые программисты! Сразу извинюсь за столь надоедливость, но поймите меня правильно, помочь больше некому =(...

Найти ошибку в программе возведения числа в степень - C++
#include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;cmath&gt; using namespace std; int a; int b; int c; float r; int d; int...

4
aLarman
642 / 563 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
Завершенные тесты: 1
18.02.2013, 15:04 #2
C++
1
2
3
4
5
while(k)
{
res *= c
k--
}
просто представляем как последовательное произведение, но этот алгоритм усовершенствованный если у нас степень четная то a^2n = (a^n)*(a^n) т.е вместо того чтобы пробегать последовательно от n до 2n просто представили как произведение, а проверка четности степени производится в условии
C++
1
if (!(k%2))
1
Asker
116 / 104 / 11
Регистрация: 18.12.2010
Сообщений: 378
21.02.2013, 06:34  [ТС] #3
Люди, я нашел, это оказывается Бинарное возведение в степень
0
iifat
2280 / 1435 / 114
Регистрация: 05.06.2011
Сообщений: 3,960
21.02.2013, 08:18 #4
Цитата Сообщение от Asker Посмотреть сообщение
я нашел, это оказывается
Ты что, искал, как это называется?
Цитата Сообщение от Asker Посмотреть сообщение
k было равно 15, стало : res = 31; c = 31, k = 14
k было равно 14, стало : res = 31; c = 32, k = 7
k было равно 7, стало : res = 33; c = 32, k = 6
k было равно 6, стало : res = 33; c = 34, k = 3
k было равно 3, стало : res = 37; c = 34, k = 2
k было равно 2, стало : res = 37; c = 38, k = 1
k было равно 1, стало : res = 315; c = 38, k = 0
Вот и заметь: в конце цикла всегда http://www.cyberforum.ru/cgi-bin/latex.cgi?res\cdot c^k=искомому значению. Главное -- знать, как уменьшить k (в конечном итоге -- до нуля), чтобы не нарушить.
1
palva
2655 / 1882 / 276
Регистрация: 08.06.2007
Сообщений: 7,228
Записей в блоге: 4
21.02.2013, 11:01 #5
Представим http://www.cyberforum.ru/cgi-bin/latex.cgi?n в двоичной системе с двоичными цифрами http://www.cyberforum.ru/cgi-bin/latex.cgi?b_i=0|1 :
http://www.cyberforum.ru/cgi-bin/latex.cgi?n=\sum_{i=0}^{32}n=b^i2^i
тогда
http://www.cyberforum.ru/cgi-bin/latex.cgi?a^n = a^{\sum_{b^i\ne0} 2^i}=\prod_{b^i\ne0} a^{2^i}
Последовательность степеней http://www.cyberforum.ru/cgi-bin/latex.cgi?a^{2^i} вычисляется в строчке 19. А домножение, которое надо производить если соответствующая двоичная цифра не равна нулю делается в строчке 24. Программу можно написать экономней и, я бы сказал, откровенней, используя проверки двоичных цифр и двоичные сдвиги не маскируя их под арифметические операции. Тогда, возможно, будет понятней.
1
21.02.2013, 11:01
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.02.2013, 11:01
Привет! Вот еще темы с ответами:

Программа возведения комплексного числа в вещественную степень !!! - C++
Программа возведения комплексного числа в вещественную степень : (a+Bi) в степени c (по формуле Муавра) Ввод вещественных значений...

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

Составить программу возведения числа n в целую степень - C++
Составить программу возведения числа n в целую степень. Правильно выбирайте раздел для размещения задачи

Реализовать рекурсивную функцию возведения заданного числа в степень n - C++
Напишите рекурсивную функцию int power(int a, int n) которая считает a^n. (a степень n) примеры для проверки 1)220 0 1 ...


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

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

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