Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/30: Рейтинг темы: голосов - 30, средняя оценка - 4.50
5 / 5 / 3
Регистрация: 30.05.2012
Сообщений: 89
1

Нахождение факториала: для заданного N найти последнюю отличную от нуля цифру

30.10.2012, 22:28. Показов 5928. Ответов 6
Метки нет (Все метки)

Факториалом натурального числа N (обозначается как N!) называется произведение всех натуральных чисел от 1 до N. Например, 5! = 1*2*3*4*5 = 120. Требуется написать программу, позволяющую для заданного N находить последнюю отличную от нуля цифру в числе N!
Исходные данные
В первой строке записано натуральное K<=1000. В каждой из следующих K строк записано очередное число Ni, для которого нужно получить ответ (1<=Ni<=1000000).
Результат
Выведите K цифр, каждую в отдельной строке

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

Добавлено через 1 час 50 минут

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
#include <iostream>
 
int ch(int &a){
        int k,s,t,i,j;
        k = a / 5;
        s = 0;
        while ( k > 0){
                s += k;
                k /= 5;
        }
        t = 1;
        for (int i = 2; i <= a; i++){
                j = i;
                while ( j % 5 == 0){
                        j /= 5;
                }
                while ( s > 0 && j % 2 == 0){
                        j /= 2;
                        s -= 1;
                }
                t = t * ( j % 10 ) % 10;
        }
        return t;
}
 
 
int main(){
        int n,a;
        std::cin >> n;
        for (int i = 0; i < n; i++){
                std::cin >> a;
                std:: cout <<ch(a)<<std::endl;
        }
        std::system("pause");
        return 0;
}
вот то что я придумал но как это уже понятно мой алгоритм не проходит по времени
есть у кого какие мысли?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.10.2012, 22:28
Ответы с готовыми решениями:

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

Найти последнюю ненулевую цифру факториала n
Помогите решить задачу: Нужно найти последнюю ненулевую цифру числа n! . 1&lt;n&lt;1000000. Помгите...

Нахождение двойного факториала заданного числа N
Дано целое число N (&gt; 0). Найти двойной факториал N: N!! = N·(N–2)·(N–4)·… (последний сомножитель...

Нахождение факториала из заданного натурального числа
Здравствуйте! Возникла проблема с написанием кода в задаче. Задача - Дано натуральное число &quot;N&quot;....

6
571 / 554 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
30.10.2012, 22:35 2
https://www.cyberforum.ru/cpp-... ost1321030
Оно?
0
Don't worry, be happy
16986 / 9864 / 1900
Регистрация: 27.09.2012
Сообщений: 24,462
Записей в блоге: 1
30.10.2012, 22:58 3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <math.h>
using namespace std;
 
void main()
{
    setlocale(LC_ALL, "");
    double x;
    cin>>x;
   x += x + 1;
   if( x > 1) {
   x = (1.8378770664093455 + log(x / 2.0) * x - x
     - (1.0 - 7.0 / (30.0 * x * x )) / ( 6.0 * x)) / 2.0 ;
   x = x * 0.43429448190325176; 
   x = pow((double)10, x); }
    cout<<"Факториал n = "<<x<<"\n";
     system("pause");
}
Нахождение факториала
0
5 / 5 / 3
Регистрация: 30.05.2012
Сообщений: 89
31.10.2012, 03:11  [ТС] 4
Croessmah, вы издеваетесь?)

Добавлено через 1 минуту
I.M., делает то что нужно идея та же что и у меня...
что если мне нужно вычислить 1000 таких факториалов за 1 секунду?
0
571 / 554 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
31.10.2012, 03:29 5
Попробуйте.
Если тема интересна, то она начинает обсуждаться с этого поста - https://www.cyberforum.ru/cpp-... ost1314219
и далее до поста с решением
0
Don't worry, be happy
16986 / 9864 / 1900
Регистрация: 27.09.2012
Сообщений: 24,462
Записей в блоге: 1
31.10.2012, 03:39 6
Цитата Сообщение от RESTY Посмотреть сообщение
Croessmah, вы издеваетесь?)
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
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;
 
 int Izdevatelstvo(const int a){
     double x=a;
    x += x + 1;
    if( x > 1) {
        x = (1.8378770664093455 + log(x / 2.0) * x - x
            - (1.0 - 7.0 / (30.0 * x * x )) / ( 6.0 * x)) / 2.0 ;
        x = x * 0.43429448190325176; 
        return static_cast<int>(x = pow((double)10, x)); 
    }
 }
 
void main()
{
    clock_t start;
    clock_t end;
    setlocale(LC_ALL, "");
     start = clock();
    for(int i=0;i<10000000;i++){
         Izdevatelstvo(30);
     }
      end = clock();
    cout<<"Функция Izdevatelstvo: "<<(double)(end - start)/CLOCKS_PER_SEC<<" сек.\n";
     cout<<Izdevatelstvo(100)<<"\n";
     system("pause");
}
У меня выполняется менее чем за секунду, для больших чисел, естественно происходит переполнение.
Что касается тысячи значений, то уловить с помощью clock'а не удается. Так как внутри нет циклов и рекурсии, то код не будет тормозить при увеличении числа, подаваемого в функцию

Добавлено через 7 минут
Правда вычисляет приближенно, погрешнисть при x=12 равна 1
0
5 / 5 / 3
Регистрация: 30.05.2012
Сообщений: 89
31.10.2012, 18:51  [ТС] 7
мне не нужен сам факторил мне нужна его последняя не нулевая цифра. И если я например введу n чисел (1<=n<=1000) то необходимо что бы этот алгоритм вывел все 1000 последних не нулевых цифр каждого из логарифмов за 1 сек в задание же написано.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.10.2012, 18:51

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Написать программу, которая распечатывает последнюю цифру заданного числа.
Задание: Написать программу, которая распечатывает последнюю цифру заданного числа. Помогите плиз)...

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

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

Для каждого столбца матрицы найти среднее арифметическое элементов, которые делятся нацело на последнюю цифру
1)программа для каждого столбца массива находит среднее арифметическое элементов, у которых...


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

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

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