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

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

Восстановить пароль Регистрация
 
 
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
12.12.2013, 18:42     возведение в степень #1
Привет всем. Люди, помогите с задачей. Я новичок, учусь в универе. Понимаю, что задача элементарная, но не могу понять одного. Нужно возвести число a в степень k.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <conio.h>
#include <math.h>
 
double long a;
int T, count, k;
 
int main()
{
    scanf("%d", &T);
 
    for(count = 1; count <= T; count++){
        scanf("%d%d", &a, &k);
        printf("%d\n", pow(a,k));
    }
 
    getch();
 
    return 0;
}
T - тестовые случаи. Без них не примут решение. При каждом возведении в степень выдает 0. Скажите, где моя ошибка?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2013, 18:42     возведение в степень
Посмотрите здесь:

Возведение в степень C++
C++ Возведение в степень. C++
C++ возведение в степень!
C++ Возведение в степень!
возведение в степень C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
12.12.2013, 18:47     возведение в степень #2
Sh@dow777, функция pow принимает в качестве аргументов данные типа double
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
12.12.2013, 18:47     возведение в степень #3
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
double long a;
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
scanf("%d%d", &a, &k);
не получится
тебе нужно
C
1
scanf("%Lf%d", &a, &k);
почитай что нибудь про scanf и его спецификаторы, хотя бы вот это
http://lord-n.narod.ru/download/book...C/13/scanf.htm
User409368
191 / 168 / 6
Регистрация: 09.09.2013
Сообщений: 524
12.12.2013, 18:51     возведение в степень #4
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
scanf("%d%d", &a, &k);
тип у переменная a long double. а scanf() думает что int
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
12.12.2013, 19:02     возведение в степень #5
Цитата Сообщение от _ Посмотреть сообщение
тип у переменная a long double. а scanf() думает что int
А еще printf ждет, что ему дадут int, а получает double
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
12.12.2013, 19:15     возведение в степень #6
Цитата Сообщение от programina Посмотреть сообщение
А еще printf ждет, что ему дадут int, а получает double
ну тут то все в порядке, если можно так сказать, приведет к int да и все
дробь обрежет, при больших числах больше чем 231 врать будет, но при 23 отработает нормально
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
12.12.2013, 19:23     возведение в степень #7
ValeryS, на gcc вот такой код не прокатит:
C++
#include <stdio.h>
#include <math.h>
 
int main()
{
        printf("%d\n", pow(2.0, 3.0));
}
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
12.12.2013, 19:32  [ТС]     возведение в степень #8
Написал так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <math.h>
 
double long a, k;
int T, count;
 
int main()
{
    scanf("%d", &T);
 
    for(count = 1; count <= T; count++){
        scanf("%Lf%Lf", &a, &k);
        printf("%Lf\n", pow(a,k));
    }
 
    return 0;
}
Теперь вычисляет степень, но задача требует целочисленного результата. И чтобы так же вычисляло без ошибок при больших степенях. Помогите.
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
12.12.2013, 20:15     возведение в степень #9
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Теперь вычисляет степень, но задача требует целочисленного результата. И чтобы так же вычисляло без ошибок при больших степенях. Помогите
C++
#include <stdio.h>
 
long int mul(long int n, int m)
{
    long int l = 1;
    for(int i = 0; i < m; i++)
        l *= n;
 
    return l;
}
 
long int a;
int k;
 
int main()
{
    scanf("%ld", &a);
    scanf("%d", &k);
 
    long int x = mul(a, k);
 
    printf("%ld\n", x);
 
    return 0;
}
genaryok
21 / 21 / 4
Регистрация: 18.10.2013
Сообщений: 62
12.12.2013, 20:49     возведение в степень #10
Я бы так делал
C++
1
2
3
4
5
6
7
8
9
10
int Step(int x,int n)  
{int r=1;
  while  (n != 0)
 {
    if (n % 2 == 1) r=r*x;
    x=x*x;
    n=n / 2;
 }
  return r;
}
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
12.12.2013, 21:57     возведение в степень #11
genaryok,
а что это?
genaryok
21 / 21 / 4
Регистрация: 18.10.2013
Сообщений: 62
13.12.2013, 01:30     возведение в степень #12
Цитата Сообщение от ValeryS Посмотреть сообщение
genaryok,
а что это?
Функция возведения числа в степень на основе его двоичного представления. Проверьте, если не верите.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
13.12.2013, 03:23  [ТС]     возведение в степень #13
Блин, ребят, ничего не получается. Попробовал такой вариант
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 <stdio.h>
#include <conio.h>
#include <math.h>
 
long int pow(long int a, long int k);
 
int main()
{
    int T,i;
    long int a, k;
 
    scanf("%d", &T);
 
    for(i = 1;i <= T;i++){
        scanf("%ld%ld", &a, &k);
        printf("%ld", pow(a,k));
    }
 
    getch();
 
    return 0;
}
 
long int pow(long int a, long int k){
    return pow(a,k);
}
Теперь выдает ошибку Stack overflow. В чем теперь ошибка?
iRomul
 Аватар для iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 474
Завершенные тесты: 1
13.12.2013, 03:29     возведение в степень #14
Бесконечная рекурсия - функция pow возвращает результат функции pow и так бесконечно
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.12.2013, 10:08     возведение в степень #15
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
long int pow(long int a, long int k){
* * return pow(a,k);
}
попробуй словами описать что делает эта функция
Цитата Сообщение от genaryok Посмотреть сообщение
Функция возведения числа в степень на основе его двоичного представления.
а что числа в компьютере лежат не в двоичном формате?
Цитата Сообщение от genaryok Посмотреть сообщение
Проверьте, если не верите.
проверяем
32
простой способ
3*3 одно действие 6-12 тактов процессора
твой алгоритм
Цитата Сообщение от genaryok Посмотреть сообщение
while *(n != 0)
3!=0 истина ветвление
Цитата Сообщение от genaryok Посмотреть сообщение
if (n % 2 == 1)
3%2=1 деление с остатком 40 тактов ( здесь правда это будет 3&1 один такт) плюс ветвление
Цитата Сообщение от genaryok Посмотреть сообщение
r=r*x;
1*3 r=3умножение 6-12 тактов процессора
Цитата Сообщение от genaryok Посмотреть сообщение
x=x*x;
3*3 x=9 умножение 6-12 тактов процессора
Цитата Сообщение от genaryok Посмотреть сообщение
n=n / 2;
3/2=1 n=1 деление около 40 тактов( здесь правда будет сдвиг 1 такт)
Цитата Сообщение от genaryok Посмотреть сообщение
while *(n != 0)
1!=0 истина ветвление
Цитата Сообщение от genaryok Посмотреть сообщение
if (n % 2 == 1)
1%2=1 деление с остатком 40 тактов ( здесь правда это будет 1&1 один такт) плюс ветвление
Цитата Сообщение от genaryok Посмотреть сообщение
r=r*x;
3*9 r= 27 умножение 6-12 тактов процессора
Цитата Сообщение от genaryok Посмотреть сообщение
x=x*x;
9*9 x=81 умножение 6-12 тактов процессора
Цитата Сообщение от genaryok Посмотреть сообщение
n=n / 2;
1/2=0 деление около 40 тактов( здесь правда будет сдвиг 1 такт)
Цитата Сообщение от genaryok Посмотреть сообщение
while *(n != 0)
0!=0 ложь -выход ветвление

итого гораздо медленней
плюс неправильный результат
может на больших числах и будет выигрыш, если подправишь свой алгоритм
и заменишь n=n / 2; на сдвиг вправо
а n % 2 на n&0x01
не все компиляторы деление на степень двойки переводят в сдвиг
genaryok
21 / 21 / 4
Регистрация: 18.10.2013
Сообщений: 62
13.12.2013, 18:35     возведение в степень #16
Цитата Сообщение от ValeryS Посмотреть сообщение
попробуй словами описать что делает эта функция

а что числа в компьютере лежат не в двоичном формате?

проверяем
32
простой способ
3*3 одно действие 6-12 тактов процессора
твой алгоритм

3!=0 истина ветвление

3%2=1 деление с остатком 40 тактов ( здесь правда это будет 3&1 один такт) плюс ветвление

1*3 r=3умножение 6-12 тактов процессора

3*3 x=9 умножение 6-12 тактов процессора

3/2=1 n=1 деление около 40 тактов( здесь правда будет сдвиг 1 такт)

1!=0 истина ветвление

1%2=1 деление с остатком 40 тактов ( здесь правда это будет 1&1 один такт) плюс ветвление

3*9 r= 27 умножение 6-12 тактов процессора

9*9 x=81 умножение 6-12 тактов процессора

1/2=0 деление около 40 тактов( здесь правда будет сдвиг 1 такт)

0!=0 ложь -выход ветвление

итого гораздо медленней
плюс неправильный результат
может на больших числах и будет выигрыш, если подправишь свой алгоритм
и заменишь n=n / 2; на сдвиг вправо
а n % 2 на n&0x01
не все компиляторы деление на степень двойки переводят в сдвиг
Не буду спорить, алгоритм может и действительно медленнее других, но как вариант)
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.12.2013, 19:29     возведение в степень #17
Цитата Сообщение от genaryok Посмотреть сообщение
Не буду спорить, алгоритм может и действительно медленнее других,
а зря
нужно уметь отстаивать свою точку зрения
при больших n он действительно быстрее
например n 64 в классическом 64 итерации а в твоем 6
при больших правда результат в int не влезет даже в long
я переписал твой код избавился от ветвления и переименовал
а то в твоем имени читается "шаг"
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
long MyPow(int x,int n)  
{
  long int r=1;
  int m;
  while  (n)
   {
   m=n&0x01
    r=(r*x*m)+(r*(!m));
    x*=x;
     n=n>>1 ;
    }
   return r;
 }
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
13.12.2013, 19:35  [ТС]     возведение в степень #18
Я просто попробовал решить задачу с помощью определения функции. Не получилось.
Вот короче моя задача:

Для заданного целого а и натурального k вычислить a^k.
Input

В первой строке записано количество Т тестов. В каждой из последующих Т строк записаны два числа, разделенных пробелом: a и k (-32000 < a ≤ 32000, 0 < k ≤ 32000).
Output

Для каждого тестового случая вывести в отдельную строку единственное число a^k. Гарантируется, что ответ не превосходит по модулю 2^61-1
Примеры
Входные данные

2
1 1
2 3

Результат работы

1
8

Капец, я не думал, что на простой степени так застопорюсь.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.12.2013, 19:37     возведение в степень #19
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Капец, я не думал, что на простой степени так застопорюсь.
в чем?
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Не получилось.
почему?
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
1 1
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
1
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
2 3
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
8
а сколько, по вашему,
11 и 23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.12.2013, 19:51     возведение в степень
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
cpp_job
 Аватар для cpp_job
4 / 4 / 1
Регистрация: 25.11.2013
Сообщений: 108
13.12.2013, 19:51     возведение в степень #20
Шилдт в помощь Собственно студенты кроме лекций любят почитать книги о программировании, или они им неинтересные?
Собственно кодес
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
#include <iostream>
using namespace std;
 
class pwr {
  double b;
  int e;
  double val;
public:
  pwr(double base, int exp);
  double get_pwr() { return val; }
};
 
pwr::pwr(double base, int exp)
{
  b = base;
  e = exp;
  val = 1;
  if(exp==0) return;
  for( ; exp>0; exp--) val = val * b;
}
 
int main()
{
  pwr x(4.0, 2), y(2.5, 1), z(5.7, 0);
 
  cout << x.get_pwr() << " ";
  cout << y.get_pwr() << " ";
  cout << z.get_pwr() << "\n";
 
  return 0;
}
(с) Г.Шилдт

Добавлено через 1 минуту
Правда там, класс...
Yandex
Объявления
13.12.2013, 19:51     возведение в степень
Ответ Создать тему
Опции темы

Текущее время: 00:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru