Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.57/56: Рейтинг темы: голосов - 56, средняя оценка - 4.57
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 100
1

Найти количество нулей в конце записи факториала числа

10.11.2015, 00:33. Просмотров 11050. Ответов 25
Метки нет (Все метки)

Найти количество нулей в конце записи факториала числа n. Подскажет, кто алгоритм? Или хотя бы в какую сторону копать? Если приведете пример кода, буду безмерно благодарен!
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.11.2015, 00:33
Ответы с готовыми решениями:

Найти количество нулей в конце записи факториала N
Найти количество нулей в конце записи факториала числа n

Определить количество нулей в цифровой записи числа, кроме нулей в младших разрядах
Дано натуральное число N (N > 9). Определить количество нулей в цифровой записи числа, кроме нулей...

Определить количество нулей в цифровой записи числа, кроме нулей в младших разрядах
#include <iostream> #include<conio.h> main() { setlocale(LC_ALL, "Russian"); int N,digit = 0;...

Определить количество нулей в цифровой записи числа, кроме нулей в младших разрядах (Pascal -> С++)
Var i: longint; N: integer; begin write('input Nomber, pleeeaaase: '); readln(i); N:= 0;...

25
492 / 374 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
10.11.2015, 00:39 2
Цитата Сообщение от EdHaker Посмотреть сообщение
Подскажет, кто алгоритм?
если по простому, то найти факториал, а потом с заду делить по модулю на 10 и считать сколько нулей
0
492 / 374 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
10.11.2015, 00:56 3
Цитата Сообщение от _Valera_ Посмотреть сообщение
если по простому,
а если по сложному, хотя могу ошибаться.
http://www.habit.ru/33/348.html
видно что на каждые пять элементов факториала к концу прибавляется один ноль, но каждые 25 два, и того не надо ничего считать, достаточно лишь доказать эту теорию и все делается в один шаг.

Могу быть не прав!
0
Эксперт С++
8225 / 3813 / 826
Регистрация: 15.11.2014
Сообщений: 8,661
10.11.2015, 01:09 4
Цитата Сообщение от EdHaker Посмотреть сообщение
Если приведете пример кода, буду безмерно благодарен!
не благодари.

http://rextester.com/IRCK37249
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
#include <iostream>
 
template<int N> struct factorial
{ 
    enum{ value = N * factorial<N - 1>::value };
};
template<> struct factorial<1>
{
    enum{ value = 1 };
};
 
template<int N, bool Z = (N!=0 && N%10==0) > 
struct zeroCount
{
    enum { value = 1 + zeroCount<N/10>::value };
};
 
template<int N> 
struct zeroCount<N, false>
{
    enum { value = 0 };
};
 
int main()
{
    std::cout << "Hello, world!\n";
 
    const size_t n = 10;
    enum { value = factorial<n>::value     };
    enum { zeros = zeroCount<value>::value };
 
    std::cout << "factorial("<<n<<") = " << value << '\n'
        << "in number of " << value << " " 
            << zeros << " values of zero\n";
}
0
Dimension
579 / 447 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
10.11.2015, 01:21 5
Цитата Сообщение от hoggy Посмотреть сообщение
не благодари.
было бы за что ,при n=13 произойдет переполнение и ваш код работать не будет ,лучше использовать вариант Валеры
0
492 / 374 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
10.11.2015, 01:29 6
hoggy, может мне кто то объяснить зачем enum понатыкан? Это вобще читабильно?!

Добавлено через 5 минут
Цитата Сообщение от _Valera_ Посмотреть сообщение
а если по сложному, хотя могу ошибаться.
http://www.habit.ru/33/348.html
видно что на каждые пять элементов факториала к концу прибавляется один ноль, но каждые 25 два, и того не надо ничего считать, достаточно лишь доказать эту теорию и все делается в один шаг.
Могу быть не прав!
Откуда ноль берется: при умножении четного числа(а начиная с факториал 5 у нас все числа четные) на 5 или на число в конце с нулем - всегда получим число у которого в конце ноль, вот и "добавляется" ноль.
почему на каждые 25 добавляется 2 нуля пока не знаю.
0
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
10.11.2015, 01:32 7
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
#include <iostream>
 
using namespace std;
 
typedef long long li;
int main() {
        li n;
        cin >> n;
        li p2 = 0, p5 = 0;
    li val = 1;
    for(int i = 0; i < 60; i++) {
        val *= 2;
        li cnt = n / val;
        p2 += cnt;
        if(cnt == 0) break;
    }
 
    val = 1;
    for(int i = 0; i < 60; i++) {
        val *= 5;
        li cnt = n / val;
        p5 += cnt;
        if(cnt == 0) break;
    }
 
    cout << min(p2, p5) << endl;
        return 0;
}
0
2572 / 2188 / 233
Регистрация: 03.07.2012
Сообщений: 7,896
Записей в блоге: 1
10.11.2015, 01:35 8
Цитата Сообщение от _Valera_ Посмотреть сообщение
почему на каждые 25 добавляется 2 нуля пока не знаю.
Потому, что 25=52. Соответственно, 125 добавляет три нуля, 625 четыре и т.д...
2
Эксперт PHP
2711 / 2367 / 1107
Регистрация: 14.05.2014
Сообщений: 6,763
Записей в блоге: 1
10.11.2015, 01:39 9
Цитата Сообщение от _Valera_ Посмотреть сообщение
а начиная с факториал 5 у нас все числа четные
именно с 5? или все же с 2?
1
492 / 374 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
10.11.2015, 01:55 10
Цитата Сообщение от zer0mail Посмотреть сообщение
Потому, что 25=52. Соответственно, 125 добавляет три нуля, 625 четыре и т.д..
почти, каждые 25 это 25, 50 ,75, 100 ,125 и тд Я почти нашел закономерность, сейчас докажу ее и выложу

Добавлено через 28 секунд
Цитата Сообщение от Kerry_Jr Посмотреть сообщение
именно с 5? или все же с 2?
я имел в веду что бы еще и на ноль кончалось)

Добавлено через 10 минут
есть число х и оговорим то что число которое кончается на ноль при делении на число с концом 5 или ноль - отнимет один ноль от делимого. Тогда:

х * 25 == х * 100/4 (два нуля)
х * 50 == х * 100/2 (два нуля)
х * 100 == х * 100/1 (два нуля)

для других чисел:

х * 10 == 100/10 (один ноль )
х * 5 == 100/20 (один ноль )
х * 20 == 100/5 (один ноль )
х * 15 == (100/20)*3 (один ноль )

Думаю так...

Не математически конечно, но выглядит вполне логично.
0
165 / 68 / 17
Регистрация: 22.03.2011
Сообщений: 196
10.11.2015, 02:02 11
Цитата Сообщение от _Valera_ Посмотреть сообщение
может мне кто то объяснить зачем enum понатыкан? Это вобще читабильно?!
ignorance is bliss
1
492 / 374 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
10.11.2015, 02:04 12
х - кончается на ноль
0
_Ivana
10.11.2015, 02:39
  #13

Не по теме:

Пора уже, как в известном анекдоте, нумеровать подобные баянные задачки :)

0
492 / 374 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
10.11.2015, 03:15 14
C++
1
2
3
4
5
6
for(int i = 1; i<= 100;++i)
    {
        int res = 0;
        res = i/5 + (i - (i % 25) )/25;
        cout<<i<<"   "<<res<<endl;
    }
0
4453 / 2072 / 263
Регистрация: 01.03.2013
Сообщений: 5,508
Записей в блоге: 22
10.11.2015, 03:33 15
Лучший ответ Сообщение было отмечено Ilot как решение

Решение

C++
1
int f(int n) {return n ? n/5 + f(n/5) : 0;}
0
492 / 374 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
10.11.2015, 03:39 16
Цитата Сообщение от _Ivana Посмотреть сообщение
int f(int n) {return n ? n/5 + f(n/5) : 0;}
зачем рекурсия? в один шаг решает :
Цитата Сообщение от _Valera_ Посмотреть сообщение
C++
1
2
3
4
5
6
for(int i = 1; i<= 100;++i)
    {
        int res = 0;
        res = i/5 + (i - (i % 25) )/25;
        cout<<i<<"   "<<res<<endl;
    }
это я 100 тестов провел
0
4453 / 2072 / 263
Регистрация: 01.03.2013
Сообщений: 5,508
Записей в блоге: 22
10.11.2015, 03:41 17
Затем что не решает. И больше 100 тоже числа бывают, внезапно.
0
492 / 374 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
10.11.2015, 03:44 18
Цитата Сообщение от _Ivana Посмотреть сообщение
Затем что не решает. И больше 100 тоже числа бывают, внезапно.
введи хоть миллион, решает, на основе алгоритма который я описал выше

Добавлено через 1 минуту
Цитата Сообщение от _Ivana Посмотреть сообщение
И больше 100 тоже числа бывают, внезапно.
это для 100! факториал вобще то
0
_Ivana
10.11.2015, 03:46
  #19

Не по теме:

_Valera_, я рад за ваши открытия, но вы выглядите смешно. За сим отписываюсь от диалога.

0
492 / 374 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
10.11.2015, 03:58 20
Цитата Сообщение от _Ivana Посмотреть сообщение
_Valera_, я рад за ваши открытия, но вы выглядите смешно. За сим отписываюсь от диалога.
причем тут открытия? Хотя ладно, этот диалог не имеет смысла.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.11.2015, 03:58

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

Количество нулей в записи числа
Помогите пожалуйста написать эдакое... Дано натуральное число n. Подсчитать количество нулей в...

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

Найти все натуральные числа, меньшие N, в записи которых содержаться K подряд идущих нулей
помогите решить!

Найти количество цифр в десятичной записи числа
На C++ нужны программки Дано число N, 1: Найти количество цифр в десятичной записи числа 2:...


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

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

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