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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.79
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
#1

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

10.04.2011, 16:55. Просмотров 1914. Ответов 17
Метки нет (Все метки)

В input.txt лежат а и b-число и степень.
В output.txt нужно вывести последнюю цифру a^b.
a и b не превышают 10000.
Должно быть какое-то простое решение, но я не могу до него додуматься...
Есть, конечно, закономерности, например 54 в нечетной степени оканчивается на 4, а в четной на 6, но беда в том, что для каждого числа эти закономерности разные...
Выявлять эти закономерности или умножать числа, хранящиеся в строках слишком муторно, должно быть более простое решение...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2011, 16:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти последнюю цифру a^b (C++):

Найти последнюю цифру. - C++
кто знает, как найти последнюю цифру какого-либо числа?

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

Найти последнюю цифру при возведении в степень - C++
найти последную цифру A^B. 1<=A<=1000 и 1<=B<=10^9 ввод данных 24 9 ввод данных 4

Найти в последовательности числа, которые делятся на свою последнюю цифру - C++
Помогите пожалуйста!!!!задача на С++ Дана последовательность.Длина последовательности целых чисел – случайное число от 10 до 30.В выходную...

Нахождение факториала: для заданного N найти последнюю отличную от нуля цифру - C++
Факториалом натурального числа N (обозначается как N!) называется произведение всех натуральных чисел от 1 до N. Например, 5! = 1*2*3*4*5 =...

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

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

Добавлено через 3 минуты
Все, дошло.
Спасибо!
0
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
10.04.2011, 17:20 #7
diagon, для слишком больших степеней работать скорее всего не будет, разве что раскладывать показатель степени на множетели и методично возводить в их степень последнюю цифру... Ну или хитрый математически-акробатический этюд нужен... Больше всего не понятно, как результаты проверять.
Кстати, обратите внимание - я там сначала скобку одну пропустил, потом поправился...
1
IrineK
Заблокирован
10.04.2011, 17:31 #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 написать ))
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.04.2011, 17:34  [ТС] #9
К сожалению, там слишком большие степени.
Через закономерности однако проще будет...
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
10.04.2011, 18:16 #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;
}
Вот вариант с тупым перемножением. Работает, естественно, и для больших степеней
1
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
10.04.2011, 18:43 #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;
}
1
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
10.04.2011, 18:49 #12
UPD: исправил my_pow в предыдущем сообщении (все из-за невнимательности )
1
IrineK
Заблокирован
10.04.2011, 18:56 #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;
}
1
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
10.04.2011, 19:06 #14
IrineK, нулевую степень неправильно обрабатывает:
Код
A = 34
B = 0
last digit: 6
Может, лучше как-то так:
C++
1
2
3
4
5
if(!B)
{
        cout<<"last digit: 1\n";
        continue;
}
?
1
IrineK
Заблокирован
10.04.2011, 19:08 #15
Специально написала в комментах:
от 1 и выше
Для нулевой степени - допишите пару строк.
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2011, 19:08
Привет! Вот еще темы с ответами:

Вводится последовательность n целых чисел Найти сумму и количество тех, которые имеют последнюю цифру 2 или 5 - C++
Пожалуйста помогите решыть! Зарание спасибо. Вводится последовательность n целых чисел Найти сумму и количество тех, которые имеют...

По последней цифре числа найти последнюю цифру квадрата этого числа - C++
Всем привет! Вообщем мне дали практическую из десяти задач.. Осталось сделать 2 шт. Задача 49. Чтобы определить на какую цифру...

Определить сколько цифр в заданном числе, найти сумму цифр, и последнюю цифру - C++
дано натуральное число n (n&lt;10000). определить сколько цифр, найти сумму цифр, и последнюю цифру. Не могу сообразить где косяк вышел ...

Дано трехзначное натуральное число А. В нём зачеркнули последнюю справа цифру и приписали её в начале. Найти полученное число - C++
Дано трехзначное натуральное число А. В нём зачеркнули последнюю справа цифру и приписали её в начале. Найти полученное число.


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
10.04.2011, 19:08
Ответ Создать тему
Опции темы

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