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

Найти последнюю цифру a^b - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.79
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.04.2011, 16:55     Найти последнюю цифру a^b #1
В input.txt лежат а и b-число и степень.
В output.txt нужно вывести последнюю цифру a^b.
a и b не превышают 10000.
Должно быть какое-то простое решение, но я не могу до него додуматься...
Есть, конечно, закономерности, например 54 в нечетной степени оканчивается на 4, а в четной на 6, но беда в том, что для каждого числа эти закономерности разные...
Выявлять эти закономерности или умножать числа, хранящиеся в строках слишком муторно, должно быть более простое решение...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2011, 16:55     Найти последнюю цифру a^b
Посмотрите здесь:

Найти последнюю цифру. C++
По последней цифре числа найти последнюю цифру квадрата этого числа C++
Дано трехзначное натуральное число А. В нём зачеркнули последнюю справа цифру и приписали её в начале. Найти полученное число C++
Нахождение факториала: для заданного N найти последнюю отличную от нуля цифру C++
Некоторое число оканчивается на 2. Если же эту его последнюю цифру переставить на первое место, то число удвоится. Найти это число C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
10.04.2011, 16:58     Найти последнюю цифру a^b #2
Самое простое: взять последнюю цифру а и ее возводить в степень.
Потом от результата брать последнюю цифру.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.04.2011, 17:02  [ТС]     Найти последнюю цифру a^b #3
Видел такое, но, к примеру, 24 в 9й степени оканчивается на 4.
По такому алгоритму берем 4, возводим в квадрат, получаем 16.
Берем последнюю цифру-6, возводим в квадрат, получаем 36.
Из 6 будет получатся 36, это замкнутый круг, и четверки в нем не видно.
IrineK
Заблокирован
10.04.2011, 17:09     Найти последнюю цифру a^b #4
Значит, нужно выявлять закономерности.
Одна - налицо: что закачивается на 0,1,5,6 - в любой степени на них и заканчивается
Все остальное - к этому приводится через несколько шагов.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
10.04.2011, 17:10     Найти последнюю цифру a^b #5
diagon, Всё проще
C
1
printf("%d", (int)pow((double)(a % 10), (double)b)) % 10);
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.04.2011, 17:16  [ТС]     Найти последнюю цифру a^b #6
Цитата Сообщение от easybudda Посмотреть сообщение
diagon, Всё проще
C
1
printf("%d", (int)pow((double)(a % 10), (double)b) % 10);
Хм... Не совсем понятен алгоритм
Зачем возводить в степень последние числа?

Добавлено через 3 минуты
Все, дошло.
Спасибо!
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
10.04.2011, 17:20     Найти последнюю цифру a^b #7
diagon, для слишком больших степеней работать скорее всего не будет, разве что раскладывать показатель степени на множетели и методично возводить в их степень последнюю цифру... Ну или хитрый математически-акробатический этюд нужен... Больше всего не понятно, как результаты проверять.
Кстати, обратите внимание - я там сначала скобку одну пропустил, потом поправился...
IrineK
Заблокирован
10.04.2011, 17:31     Найти последнюю цифру a^b #8
Закономерности:
2: 2,4,8,6 - период
3: 3,9,7,1
4: 4,6
7: 7,9,3,1
8: 8,4,2,6
9: 9,1

0,1,5,6 - все время остаются

Осталось только case написать ))
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.04.2011, 17:34  [ТС]     Найти последнюю цифру a^b #9
К сожалению, там слишком большие степени.
Через закономерности однако проще будет...
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
10.04.2011, 18:16     Найти последнюю цифру a^b #10
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
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int get_unsigned(const char*, size_t*);
size_t my_pow(size_t, size_t);
 
int main(int argc, char* argv[])
{
    size_t base, exp, result;
    
    if(argc != 3)
    fprintf(stderr, "Usage: %s BASE EXP\n", *argv), exit(1);
    
    if(!get_unsigned(argv[1], &base))
    fprintf(stderr, "%s is not a legal unsigned integer\n", argv[1]), exit(1);
 
    if(!get_unsigned(argv[2], &exp))
    fprintf(stderr, "%s is not a legal unsigned integer\n", argv[2]), exit(1);
 
    result = my_pow(base, exp);
    
    printf("Last digit of %u ^ %u is %u\n", base, exp, result);
    
    exit(0);
}
 
int get_unsigned(const char* buf, size_t* result)
{
    static char* endptr;
    long int temp;
 
    temp = strtol(buf, &endptr, 10);
 
    if(temp == LONG_MIN || temp == LONG_MAX || !(*buf != '\0' && *endptr == '\0') || temp < 0)
    {
    *result =0;
    return 0;
    }
 
    *result = (size_t) temp;
 
    return 1;
}
 
size_t my_pow(size_t base, size_t exp)
{
    size_t result = 1;
 
    base %= 10;
            
    while(exp--)
    {
    result *= base;
    result %= 10;
    }
 
    return result;
}
Вот вариант с тупым перемножением. Работает, естественно, и для больших степеней
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
10.04.2011, 18:43     Найти последнюю цифру a^b #11
Вот немного улучшенный вариант функции my_pow (невооруженным глазом заметно, что на больших степенях работает быстрее). Заметь, что теперь функция принимает уже последнюю цифру от числа-основания степени, а не само основание (см. строку 21):
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
52
53
54
55
56
57
58
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int get_unsigned(const char*, size_t*);
size_t my_pow(size_t, size_t);
 
int main(int argc, char* argv[])
{
    size_t base, exp, result;
    
    if(argc != 3)
    fprintf(stderr, "Usage: %s BASE EXP\n", *argv), exit(1);
    
    if(!get_unsigned(argv[1], &base))
    fprintf(stderr, "%s is not a legal unsigned integer\n", argv[1]), exit(1);
 
    if(!get_unsigned(argv[2], &exp))
    fprintf(stderr, "%s is not a legal unsigned integer\n", argv[2]), exit(1);
 
    result = my_pow(base % 10, exp);
    
    printf("Last digit of %u ^ %u is %u\n", base, exp, result);
    
    exit(0);
}
 
int get_unsigned(const char* buf, size_t* result)
{
    static char* endptr;
    long int temp;
 
    temp = strtol(buf, &endptr, 10);
 
    if(temp == LONG_MIN || temp == LONG_MAX || !(*buf != '\0' && *endptr == '\0') || temp < 0)
    {
    *result =0;
    return 0;
    }
 
    *result = (size_t) temp;
 
    return 1;
}
 
size_t my_pow(size_t base, size_t exp)
{
    size_t temp;
 
    if(exp == 0)
    return 1;
        
    if(exp & 1)
    return (my_pow(base, exp - 1) * base) % 10;
    
    temp = my_pow(base, exp / 2);
    return (temp * temp) % 10;
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
10.04.2011, 18:49     Найти последнюю цифру a^b #12
UPD: исправил my_pow в предыдущем сообщении (все из-за невнимательности )
IrineK
Заблокирован
10.04.2011, 18:56     Найти последнюю цифру a^b #13
Обошлось без case:

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 <iostream>
#include <sstream>
#include <cmath>
using namespace std;
 
int main()
{   string A;
    long B;
    int N;
 
while(1)
{   cout<<"A = ";  //число - оочень большое
    getline(cin,A);
    cout<<"B = "; //степень - поменьше, от 1 и выше
    cin>>B;
    N = A[A.length()-1]-'0';
    B %= 4;
    if(!B) B=4;
    
    N = (int)pow(1.0*N,B)%10;
 
    cout<<"last digit: "<<N<<"\n";
    cin.sync();
}
    return 0;
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
10.04.2011, 19:06     Найти последнюю цифру a^b #14
IrineK, нулевую степень неправильно обрабатывает:
Код
A = 34
B = 0
last digit: 6
Может, лучше как-то так:
C++
1
2
3
4
5
if(!B)
{
        cout<<"last digit: 1\n";
        continue;
}
?
IrineK
Заблокирован
10.04.2011, 19:08     Найти последнюю цифру a^b #15
Специально написала в комментах:
от 1 и выше
Для нулевой степени - допишите пару строк.
Nameless One
10.04.2011, 19:10
  #16

Не по теме:

О, не заметил...

diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.04.2011, 19:11  [ТС]     Найти последнюю цифру a^b #17
А нулевой и нету, минимальная-один.
Спасибо всем.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2011, 21:34     Найти последнюю цифру a^b
Еще ссылки по теме:

Найти в последовательности числа, которые делятся на свою последнюю цифру C++
C++ Вводится последовательность n целых чисел Найти сумму и количество тех, которые имеют последнюю цифру 2 или 5
В трехзначном числе зачеркнули последнюю справа цифру и переписали ее в начало. Найти полученное число C++

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

Или воспользуйтесь поиском по форуму:
IrineK
Заблокирован
10.04.2011, 21:34     Найти последнюю цифру a^b #18
С учетом нулевой степени )):
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
#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;
 
int main()
{   string A;
    long B;
    int N;
 
while(1)
{   cout<<"A = ";  //число - оочень большое
    getline(cin,A);
    cout<<"B = "; //степень - поменьше, от 0 и выше
    cin>>B;
    if(!B) 
    {   cout<<"last digit: "<<1<<"\n";
        cin.sync();
        continue;
    }
 
    N = A[A.length()-1]-'0';
    B %= 4;
    if(!B) B=4;
    
    N = (int)pow(1.0*N,B)%10;
 
    cout<<"last digit: "<<N<<"\n";
    cin.sync();
}
    return 0;
}
Добавлено через 2 часа 20 минут
В строке 17 корректней будет:
C++
1
cout<<"last and the only one digit: "<<1<<"\n";
))
Yandex
Объявления
10.04.2011, 21:34     Найти последнюю цифру a^b
Ответ Создать тему
Опции темы

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