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

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

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

Студворк — интернет-сервис помощи студентам
Факториалом натурального числа 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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
30.10.2012, 22:28
Ответы с готовыми решениями:

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

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

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

9
 Аватар для I.M.
576 / 559 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
30.10.2012, 22:35
https://www.cyberforum.ru/cpp-... ost1321030
Оно?
0
Неэпический
 Аватар для Croessmah
18146 / 10730 / 2066
Регистрация: 27.09.2012
Сообщений: 27,030
Записей в блоге: 1
30.10.2012, 22:58
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  [ТС]
Croessmah, вы издеваетесь?)

Добавлено через 1 минуту
I.M., делает то что нужно идея та же что и у меня...
что если мне нужно вычислить 1000 таких факториалов за 1 секунду?
0
 Аватар для I.M.
576 / 559 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
31.10.2012, 03:29
Попробуйте.
Если тема интересна, то она начинает обсуждаться с этого поста - https://www.cyberforum.ru/cpp-... ost1314219
и далее до поста с решением
0
Неэпический
 Аватар для Croessmah
18146 / 10730 / 2066
Регистрация: 27.09.2012
Сообщений: 27,030
Записей в блоге: 1
31.10.2012, 03:39
Цитата Сообщение от 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  [ТС]
мне не нужен сам факторил мне нужна его последняя не нулевая цифра. И если я например введу n чисел (1<=n<=1000) то необходимо что бы этот алгоритм вывел все 1000 последних не нулевых цифр каждого из логарифмов за 1 сек в задание же написано.
0
0 / 0 / 0
Регистрация: 20.04.2022
Сообщений: 2
17.07.2022, 16:49
#include <iostream>
using namespace std;
int main()
{
int n; cin >> n;
int m = 0;
int f = 1;
for (int i = 1; i <= n; ++i) {
int x = i;
while (x % 2 == 0)
x /= 2, ++m;
while (x % 5 == 0)
x /= 5, --m;
f=f * x % 10;
}
for(int i = 0; i < m; ++i)
f = f * 2 %10;
cout<<f<<endl;
}
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,532
Записей в блоге: 1
20.07.2022, 01:34
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
#include <iostream>
using namespace std;
int main() {
    int f = 1;
    int two_counter = 0;
    int N; cin>>N;
    for (int i = 2; i <= N; ++i) {
        int multiplier = i;
        while (multiplier % 5 == 0) {
            multiplier /= 5;
            --two_counter;
        }
        while (multiplier % 2 == 0) {
            multiplier /= 2;
            ++two_counter;
        }
        f = f*multiplier % 10;
        cout <<"i:"<< i<< ", f:" << f << ", m:" << multiplier<< ", c:" << two_counter << " " << endl;
    }
    while(two_counter--)
        f = f * 2 % 10;
    cout << "f:" << f << endl;
    return 0;
}
Добавлено через 4 минуты
Alex802862, вот какой смысл поднимать старые темы? Я ожидаал, что автору RESTY нужно решение и нужна помощь!
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12937 / 6804 / 1821
Регистрация: 18.10.2014
Сообщений: 17,219
20.07.2022, 09:20
Цитата Сообщение от RESTY Посмотреть сообщение
мне не нужен сам факторил мне нужна его последняя не нулевая цифра.
Тема "на сколько нулей оканчивается факториал" тут муслилась вдоль и поперек уже много раз.

Определить на сколько нулей оканчивается n!

Цитата Сообщение от RESTY Посмотреть сообщение
находить последнюю отличную от нуля цифру в числе N!
А, видимо я не совсем правильно понял задание. Интересует не только (и не столько) позиция цифры, а именно само значение этой цифры, так?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
20.07.2022, 09:20
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Новые блоги и статьи
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Символьное дифференцирование
igorrr37 13.02.2026
/ * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru