Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Составьте программу вычисления степени числа А с н

Автор: teac2012 9.12.2012, 17:43

Составьте программу вычисления степени числа А с натуральным показателем n. (записать варианты программы с разными видами циклов while,for) Желательно в turbo c++ 3.0

Автор: Zhunko 9.12.2012, 22:45

Это конкурс? smile

Код


double Pow(const double dBase, const DWORD dwPow)
 {
   double _dBase = 1;
   for (DWORD i = 0; i < dwPow; i++)
    {
      _dBase *= dBase;
    }
   return(_dBase);
 }

Автор: volatile 9.12.2012, 23:20

Цитата(Zhunko @ 9.12.2012, 22:45

)

double Pow(const double dBase, const DWORD dwPow)
{
   double _dBase = dBase;
   for (DWORD i = 0; i < dwPow; i++)
    {
      _dBase *= dBase;
    }
   return(_dBase);
}

Zhunko, ай-яй-яй, как не стыдно...

Автор: Zhunko 10.12.2012, 00:23

Цитата(volatile @ 10.12.2012, 00:20

)

Zhunko, ай-яй-яй, как не стыдно...

Блин!

Приз не получу?

Автор: volatile 10.12.2012, 00:41

Ладно, чтоб совсем уж скучно не было, я оъявляю конкурс.
Первому, кто напишет эту функцию, без цыклофф (for,while,do), и одним оператором (без вызова библиотечных функций)
+1 в репу.

smile

Автор: Zhunko 10.12.2012, 02:33

Ещё такие циклы умею:

Код


double Pow(const double dBase, DWORD dwPow)
 {
   double dRes = dBase;
   START: dRes *= ((--dwPow) ? (dBase) : (1));
   if (!dwPow) return(dRes); 
   goto START;
 }

volatile, одним оператором?... Может парой операторов побитовых операций?

Автор: math64 10.12.2012, 07:54

А рекурсию можно?

Код


inline double sqr(double x) { return x*x; }
double pow(double x, int n) {
return n == 0 ? 1 : n == 1 ? x : n < 0 ? 1/pow(-n) : sqr(pow(x, n/2))*pow(x,n%2);
}

Автор: feodorv 10.12.2012, 09:35

Цитата(math64 @ 10.12.2012, 08:54

)

А рекурсию можно?

Ну да, если не стандартные функции и не циклы, то только рекурсия:

Код


double Pow( double A, unsigned int n)
{
  return (n == 0) ? 1 : A*Pow( A, n-1);
}

Добавлено через 4 минуты и 8 секунд
Для teac2012 пояснение варианта math64: http://coderlife.ru/progr/bystroe-vozvedenie-chisla-v-naturalnuyu-stepen.html.

Автор: Zhunko 10.12.2012, 11:13

Индийский алгоритм можно побитовыми операциями сделать в одну строку.

Автор: bsa 10.12.2012, 12:59

Zhunko, нука расскажи как?

Автор: Zhunko 10.12.2012, 13:37

Цитата(bsa @ 10.12.2012, 13:59

)

Zhunko, нука расскажи как?

Если вопрос, как или каким образом, то, конечно, путём написания кода.
Над реализацией не думал. Наверняка можно, но только для целых чисел. Хотя, можно double с мантиссой преобразовать в int, потом восстановить порядок.

Автор: bsa 10.12.2012, 14:37

Цитата(Zhunko @ 10.12.2012, 14:37

)

Над реализацией не думал.

А зря. Если бы думал, то этих 4-х постов бы не было. smile

Автор: Zhunko 10.12.2012, 14:49

Цитата(bsa @ 10.12.2012, 15:37

)

А зря. Если бы думал, то этих 4-х постов бы не было.

Если было нельзя, то от Вас было объяснение почему нельзя. И не было Ваших 2-х постов.
Что-то ни у кого одним оператором не получилось.

Автор: baldina 10.12.2012, 16:44

Цитата(Zhunko @ 10.12.2012, 14:49

)

Что-то ни у кого одним операторм не получилось.

есть operator - оператор, операция.
есть statement - оператор, выражение.
наверняка volatile имел в виду statement, т.к. одним оператором (operator) действительно нельзя.

а если statement - тогда можно, код feodorv.

вот еще вариант, быстрое возведение

Код


double pow (double a, unsigned n) {
  return n == 0 ? 1 : [](double p, double a){ return p*p*a; }(pow (a,n/2), n%2 ? a : 1);
}

Автор: bsa 10.12.2012, 17:02

Цитата(Zhunko @ 10.12.2012, 15:49

)

Если было нельзя, то от Вас было объяснение почему нельзя.

Понимаешь, до сего момента для меня было очевидно, что люди говорящие подобные вещи знают математику (хотя бы на уровне 6-го класса средней школы).
Сдвиг (самая сложная битовая операция) позволяет умножать/делить число на 2 в целой степени. Т.е. сдвигами можно решить задачу, если A = 2. Остальные битовые операции тут вообще вряд ли помогут.
Перевод в число с плавающей точкой тоже не вариант, так как оно выглядит как мантисса * 2 ^ экспонента. Т.е. опять, с ее помощью можно решить задачу только для A=2 (при этом будет много головной боли при смене архитектуры и/или разрядности).

Сдвигами и сложением можно реализовать умножение. А возведение в целую неотрицательную степень можно реализовать с помощью умножения. Раскрываем скобки и получаем, что возведение в степень можно реализовать через битовые операции и суммирование. НО! Это будет крайне неоптимально. Так как современный процессор делает сдвиг и умножение за одинаковое время, но для реализации 32-х битного умножения нужно сделать 31 сдвиг и столько же сложений.
Можно зайти с другой стороны, и с помощью сдвигов оптимизировать операцию деления на 2, которая используется в индийском варианте решения. Вот только если посмотреть ассемблерный листинг вариантов с делением и со сдвигами, то с большой вероятностью они полностью совпадут, так как компилятор не дурак и знает, что x >> 1 и x / 2 дают одинаковый результат (для целых неотрицательных x).

Автор: Dem_max 10.12.2012, 17:03

ТС это приказ ???

Автор: Zhunko 10.12.2012, 17:31

Цитата(bsa @ 10.12.2012, 18:02

)

Понимаешь, до сего момента для меня было очевидно, что люди говорящие подобные вещи знают математику (хотя бы на уровне 6-го класса средней школы).Сдвиг (самая сложная битовая операция) позволяет умножать/делить число на 2 в целой степени. Т.е. сдвигами можно решить задачу, если A = 2. Остальные битовые операции тут вообще вряд ли помогут.Перевод в число с плавающей точкой тоже не вариант, так как оно выглядит как мантисса * 2 ^ экспонента. Т.е. опять, с ее помощью можно решить задачу только для A=2 (при этом будет много головной боли при смене архитектуры и/или разрядности).Сдвигами и сложением можно реализовать умножение. А возведение в целую неотрицательную степень можно реализовать с помощью умножения. Раскрываем скобки и получаем, что возведение в степень можно реализовать через битовые операции и суммирование. НО! Это будет крайне неоптимально. Так как современный процессор делает сдвиг и умножение за одинаковое время, но для реализации 32-х битного умножения нужно сделать 31 сдвиг и столько же сложений.Можно зайти с другой стороны, и с помощью сдвигов оптимизировать операцию деления на 2, которая используется в индийском варианте решения. Вот только если посмотреть ассемблерный листинг вариантов с делением и со сдвигами, то с большой вероятностью они полностью совпадут, так как компилятор не дурак и знает, что x >> 1 и x / 2 дают одинаковый результат (для целых неотрицательных x).

Вот спасибо! Теперь мне не надо доказывать, что это возможно! smile

Про оптимальность в задании ничего не было.
Математику совсем не знаю. Тем более не в курсе, что сейчас в 6-ом классе изучают. Может то, что раньше в детском саду? Палочки считают? smile

Как Вы думаете, процессор что-нибудь умеет, кроме побитовых операций?

Автор: volatile 10.12.2012, 17:53

Цитата(feodorv @ 10.12.2012, 09:35

)

double Pow( double A, unsigned int n)
{
return (n == 0) ? 1 : A*Pow( A, n-1);
}

Да, угадал, светлая башка, практически один в один

Вот вчерашний мой вариант:

Код


double pw (double a, unsigned n)
{
   return n ? a * pw (a, n - 1) : 1;
}

http://codepad.org/7rA8WEHS (там время поста должно стоять)

Спасибо всем кто принял участие.
Интересные решения у
math64,
feodorv,
baldina,

Плюсики сим товарищам щас поставлю, если получится.
(я не из дома, так что если щас не получится, то расставлю сразу как доберусь до своего компа.)

Автор: bsa 10.12.2012, 17:53

Zhunko, молодец. давай еще на электронный уровень перейдем: вычисление степени числа путем перевода электронов из одного места в другое.

Автор: baldina 10.12.2012, 18:04

Цитата(volatile @ 10.12.2012, 17:53

)

Интересные решения

с лямбдой выпендреж, жаль никто не отметил. можно проще (и понятней)

Код


return n ? (n%2 ? a : 1)*pow(a*a,n/2) : 1;

Автор: Zhunko 10.12.2012, 18:27

Цитата(baldina @ 10.12.2012, 19:04

)

с лямбдой выпендреж, жаль никто не отметил. можно проще (и понятней)

Отметил! Мне понравилось. Хоть, до сих пор не понял, как это работает. smile

Цитата(bsa @ 10.12.2012, 18:53

)

Zhunko, молодец. давай еще на электронный уровень перейдем: вычисление степени числа путем перевода электронов из одного места в другое.

Так оно скоро будет. Типа квантовых компьютеров. Там производительность на 300 порядков выше.

Автор: volatile 11.12.2012, 00:22

Цитата(Zhunko @ 10.12.2012, 18:27

)

Там производительность на 300 порядков выше.

pow (10, 300) ? а хоть и pow (2, 300) это слишком дофига.
Если в ближайшее время изобретут такой комп, первое что будет это глабальный катаклизм.
потому-что банковская система рухнет
потому-как все ключи будут взломаны за минуты.
ну и т.д.

Автор: math64 11.12.2012, 07:55

Можно ещё сделать на шаблонах:

Код


template<unsigned m>
inline double pow(double x, unsigned n) {
  return n == 0 ? 1 : pow<m/2>(x * x, n/2) * pow<0>(x,n);
}

template<>
inline double pow<0>(double x, unsigned n) {
  return n % 2 == 0 ? 1 : x;
}

double pow(double x, int n)
{
return n < 0 ? 1 / pow<unsigned(-1)/2>(x,(unsigned)-n) : pow<unsigned(-1)/2>(x,(unsigned)n);
}