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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
RESTY
5 / 5 / 0
Регистрация: 30.05.2012
Сообщений: 89
#1

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

30.10.2012, 22:28. Просмотров 1889. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.10.2012, 22:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нахождение факториала: для заданного N найти последнюю отличную от нуля цифру (C++):

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

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

Найти последнюю цифру a^b - C++
В input.txt лежат а и b-число и степень. В output.txt нужно вывести последнюю цифру a^b. a и b не превышают 10000. Должно быть...

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

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

Найти первую и последнюю цифры заданного числа; найти сумму цифр заданного числа - C++
Помогите решить в С++ 2.1 Дано натуральное число: − найти первую и последнюю цифры числа; − верно ли, что сумма цифр данного числа...

6
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
30.10.2012, 22:35 #2
http://www.cyberforum.ru/cpp-experts...ml#post1321030
Оно?
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 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
RESTY
5 / 5 / 0
Регистрация: 30.05.2012
Сообщений: 89
31.10.2012, 03:11  [ТС] #4
Croessmah, вы издеваетесь?)

Добавлено через 1 минуту
I.M., делает то что нужно идея та же что и у меня...
что если мне нужно вычислить 1000 таких факториалов за 1 секунду?
0
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
31.10.2012, 03:29 #5
Попробуйте.
Если тема интересна, то она начинает обсуждаться с этого поста - http://www.cyberforum.ru/cpp-experts...ml#post1314219
и далее до поста с решением
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 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
RESTY
5 / 5 / 0
Регистрация: 30.05.2012
Сообщений: 89
31.10.2012, 18:51  [ТС] #7
мне не нужен сам факторил мне нужна его последняя не нулевая цифра. И если я например введу n чисел (1<=n<=1000) то необходимо что бы этот алгоритм вывел все 1000 последних не нулевых цифр каждого из логарифмов за 1 сек в задание же написано.
0
31.10.2012, 18:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2012, 18:51
Привет! Вот еще темы с ответами:

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

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

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

Найти первую цифру заданного натурального числа - C++
Дано натуральное число n, найти первую цифру числа n. (c++) ?


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

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

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