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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.96
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

A^B mod C - C++

06.08.2011, 20:50. Просмотров 3451. Ответов 22
Метки нет (Все метки)

Найти A^B mod C. Тут как-то надо использовать рекурсию. Кто может помочь?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.08.2011, 20:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос A^B mod C (C++):

mod - C++
Здравствуйте! У меня вопрос наверное глупый. Препод для выбора курсовой поставил следующие условия: Вариант задания выбирается по формуле...

mod (на C) - C++
нужно проверить число на нечётность я сделал так: if (k mod 2 == 1) <действия> но компилятор выдал ошибку типа:syntax error...

div и mod - C++
Помогите, пожалуйста: вводимое с клавиатуры число n нужно разделить следующим образом (n, n1, n2 - целые ): если n четное, то n1 = n2 =...

DIv MOD в С++ - C++
не подскажете как описать оператор ДИВ в С++? суть такова а=5 b=2 x=a DIV 2 y=5/2 printf(...x) (y) мне нужно...

mod и div - C++
вообщем задачка такая. Нужно вычислить сумму средних чисел четырёхзначного числа. На паскале проблем не возникло, а вот С++ постоянно...

mod и div ?? - C++
Подскажите пожалуйста как будет mod и div в С++? Очень нужно)) Добавлено через 9 минут и пожалуйста напишите пример как...

22
Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
06.08.2011, 21:34 #2
Рекурсию нужно использовать при возведении в степень.
Насколько я понял эту запись, то сначала A возводится в степень B, потом от полученного результата находим остаток от деления на C.
Один из самых простых вариантов, работает только со степенями >= 0.
Есть такая оговорка: если один из операндов оператора % ( остаток от деления ) отрицательный, то результат получится зависимый от машины.
Т.е. нужно предусматривать:
- чтобы либо все числа A, B и C были положительными,
- либо если число A отрицательно, то степень B должна быть четная и число C положительно
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
#include <iostream>
using namespace std;
 
int pow_xy( int x, int y ) {
    if ( y == 0 )
        return 1;
    else
        return x * pow_xy( x, y - 1 );
}
 
int main() {
    int a, b, c;
    cout << "Введите a" << endl;
    cin >> a;
 
    cout << "Введите b" << endl;
    cin >> b;
 
    cout << "Введите c" << endl;
    cin >> c;
 
    cout << "Результат: " << ( pow_xy( a, b ) %c ) << endl;
    return 0;
}
0
CAHTEXHUK
Заблокирован
06.08.2011, 21:36 #3
я думал ^ это xor o_0
1
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.08.2011, 21:38 #4
Цитата Сообщение от Roof Посмотреть сообщение
Рекурсию нужно использовать при возведении в степень.
Насколько я понял эту запись, то сначала A возводится в степень B, потом от полученного результата находим остаток от деления.
Один из самых простых вариантов, работает только со степенями >= 0.
Есть такая оговорка: если один из операндов оператора % ( остаток от деления ) отрицательный, то результат получится зависимый от машины.
Т.е. нужно предусматривать:
- чтобы либо все числа A, B и C были положительными,
- либо если число A отрицательно, то степень B должна быть четная и число C положительно
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
#include <iostream>
using namespace std;
 
int pow_xy( int x, int y ) {
    if ( y == 0 )
        return 1;
    else
        return x * pow_xy( x, y - 1 );
}
 
int main() {
    int a, b, c;
    cout << "Введите a" << endl;
    cin >> a;
 
    cout << "Введите b" << endl;
    cin >> b;
 
    cout << "Введите c" << endl;
    cin >> c;
 
    cout << "Результат: " << ( pow_xy( a, b ) %c ) << endl;
    return 0;
}
a = 1000, b = 10000 ?
Могу ошибаться, но тут нужно хранить в А только последние n чисел, n зависит от C(количество разрядов в С + 1).
0
alex_x_x
бжни
2450 / 1655 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
06.08.2011, 21:41 #5
если погуглить, то поятно, что задача олимпиадная и идет речь об математической закономерности
задача дается на большие числа
1
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
06.08.2011, 21:42  [ТС] #6
Roof, A,B,C<10^9 как возводить то?
0
Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
06.08.2011, 21:44 #7
2 CAHTEXHUKну - да, это xor, а я поторопился.
2 AvengerAlive - я решил, что это простая задачка учебная, которая ограничивается небольшими числами, но, видимо, ошибся.
0
alex_x_x
бжни
2450 / 1655 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
06.08.2011, 21:45 #8
Roof,
Цитата Сообщение от alex_x_x Посмотреть сообщение
адача олимпиадная и идет речь об математической закономерности
0
Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
06.08.2011, 21:50 #9
2 alex_x_x - нагуглил, увидел, спасибо.
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
06.08.2011, 21:52  [ТС] #10
CAHTEXHUK, ^ возведение в степень не в С

Roof, лонг лонг заработал только ошибку даёт на больших значениях
0
Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
06.08.2011, 22:01 #11
2 AvengerAlive - мой алгоритм неверен для больших чисел.
0
grizlik78
Эксперт С++
1971 / 1464 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
06.08.2011, 22:13 #12
Вот, переделал из обычного возведения в степень, надеюсь ничего лишнего не выкинул в процессе.
Идея в том, чтобы представить возведение в степень в виде возведений в квадрат и умножений на основание. Например
http://www.cyberforum.ru/cgi-bin/latex.cgi?5^{11} =  5\Bigl(5\bigl(5^2\bigr)^2\Bigr)^2
Операцию приведения по модулю надо выполнять после каждой промежуточной операции, чтобы не возникало переполнения.
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
#include <stdio.h>
 
unsigned pow(unsigned a, unsigned b, unsigned m)
{
    unsigned n = 0;
    unsigned k = 1;
    unsigned long long res;
    if (0 == a)
        return 0;
    if (0 == b)
    return 1;
 
    while ( (n = k << 1) <= b && n )
        k = n;
    if (0 == n)
        return 0;
    res = a;
    k >>= 1;
    while (k)
    {
        res = (res*res) % m;
        if (k & b)
            res = (res*a) % m;
        k >>= 1;
    }
    return (unsigned)(res);
}
 
int main()
{
    unsigned a;
    unsigned b;
    unsigned m;
    scanf("%u%u%u", &a, &b, &m);
    printf("%u**%u mod %u = %u\n", a, b, m, pow(a, b, m));
    return 0;
}
0
alex_x_x
бжни
2450 / 1655 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
06.08.2011, 22:22 #13
чегото вроде
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
unsigned f( unsigned a, unsigned now_b, unsigned c )
{
   std::cout << a << " " << now_b << std::endl;
   switch( now_b )
   {
     case 1: return a;
     case 2: return a*a;
     default: 
     {
        unsigned  left_b_power = now_b / 2, 
                  right_b_power = now_b - left_b_power;
        return f( a, left_b_power, c ) * f( a, right_b_power, c ) % c;
     }
   }
}
 
int main()
{
   std::cout << f( 15, 15, 34 );
}
это по свойству (A*B) mod C = ((A mod C)*(B mod C)) mod C

Добавлено через 6 минут
долговато на больших числах выходит
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
06.08.2011, 22:53  [ТС] #14
grizlik78, спасибо, тесты 2^31 прошёл, а вот 2^63 под unsigned long long уже не получается...
0
grizlik78
Эксперт С++
1971 / 1464 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
06.08.2011, 22:55 #15
AvengerAlive, в смысле если операнды 63 бита длиной? так я этого не обещал.
Когда показания на ходу меняются — я так не играю
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Roof, A,B,C<10^9 как возводить то?
0
06.08.2011, 22:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.08.2011, 22:55
Привет! Вот еще темы с ответами:

Div и mod в С++ - C++
Здравствуйте. Перехожу из паскаля в c++. Есть отрывок кода который проверяет есть ли в числе N цифра 3 и есть ли в числе вводимое с...

Операция mod() - C++
Подскажите, pls, как осуществить операцию m mod n (вычисление остатка) не используя операцию деления в процессе вычисления?

mod и div (Чистый С) - C++
Здравсвтуйте,как на чистом С описывать эти функции mod и div????

Что такое mod в с++ ? - C++
что такое mod в с++ и как он работает? например, m=12*17^9 mod 23. (m должно получиться 15)


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

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

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