Вывести последнюю ненулевую цифру факториала

@Reb0ot · Регистрация: 11.09.2021

Студворк — интернет-сервис помощи студентам

Алгоритм работает неправильно на числах 15, 25 и т.д. В остальном всё нормально

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
using namespace std;
 
int main()
{
  int n;
  unsigned long res = 1;
    cin >> n;
    for(int i = 2; i <= n; ++i)
    {
        res *= i;
        while(res % 10 == 0)
            res /= 10;
        res %= 10;
    }
    cout << res;
}

@zayats80888 · 01.03.2024, 12:15

Не по теме:

Сообщение от hi51

Есть Скрип непонятный поможешь разобратся?

Суставы проверь, возможно они скрипят.

@KSergey9 · 01.03.2024, 13:03

Только что ж тема была

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

Один ВУЗ?

@TheCalligrapher · 02.03.2024, 02:41

Сообщение от Reb0ot

Алгоритм работает неправильно на числах 15, 25 и т.д.

Почему не работает такой наивный алгоритм - понятно. Сохранение лишь последней ненулевой цифры факториала приведет к сбою, когда умножение этой цифры на очередное число даст 0 в конце. После этого нам понадобится не последняя, а предпоследняя цифра результата. А вот именно ее мы к этому моменту уже потеряли.

Однако чисто из любопытства возникает вопрос: а что если мы будем хранить не только последнюю ненулевую цифру факториала, а несколько последних ненулевых цифр? Например, для хранения двух последних цифр факториала реализацию ТС можно модифицировать так

C++
1
2
3
4
5
6
7
8
9
10
11
12
unsigned ldf(unsigned n)
{
  unsigned long long f = 1;
  for (unsigned i = 2; i <= n; ++i)
  {
     f *= i;
     for (; f % 10 == 0; f /= 10);
     f = f % 100; // сохраняем две цифры факториала
  }
 
  return f % 10; // результат
}

Сколько сохраняется последних ненулевых цифр зависит от делителя в строке 8.

Понятно, что сколько бы цифр бы мы ни хранили, в какой-то момент возникнет ситуация, когда после очередного умножения окажется, что все цифры обнулились и нам нужна следующая старшая цифра, которую мы не можем определить корректно. То есть такая реализация обязательно рано или поздно даст сбой (для какого-то числа n, содержащего фактор "5 в какой-то степени"). Но чем больше ненулевых цифр факториала мы будем сохранять, тем для больших значений n такая реализация сможет давать правильный ответ.

Вот мне было интересно, как далеко можно зайти для разных делителей 10^k в строке 8. Понятно, что использовать делитель больше 10¹⁰ или 10¹¹ смысла нет - будет переполняться умножение в строке 6. Результаты моего натурного эксперимента таковы:

Code
1
2
3
4
5
6
7
8
9
10
Fail 1 at 15: 3 != 8
Fail 2 at 25: 9 != 4
Fail 3 at 375: 7 != 2
Fail 4 at 3125: 5 != 2
Fail 5 at 9375: 3 != 8
Fail 6 at 78125: 5 != 8
Fail 7 at 78125: 3 != 8
Fail 8 at 1953125: 7 != 2
Fail 9 at 1953125: 7 != 2
Fail 10 at 9765625: 9 != 4

"Fail <k>" говорит, на каком числе n сломалось вычисление для делителя 10^k. "Fail 1" - это , разумеется, исходный вариант ТС, который ломается уже на n=15.

---

Хотя ясно, что натурный эксперимент можно было и не проводить. Количество двоек в факториале растет намного быстрее, чем количество пятерок. Поэтому для больших n можно ожидать, что если делитель в строке 8 равен 10^k, то как только n станет равно 5^k, то произойдет то самое обнуление всех хранимых нами последних цифр факториала и вычисления "сломаются". Это мы и видим в моих результатах сверху.

Отсюда можно предположить, если я ничего не упускаю, что для того, чтобы такой полулобовой/наивный подход сработал для всего диапазона 32-битного unsigned int, нам нужно хранить 13-14 последних ненулевых цифр факториала (5¹³ меньше 2³², а 5¹⁴ - больше). При этом во избежание переполнения в строке 6 нам понадобится 128-битное умножение.

Для GCC с его __uint128_t

C++
1
2
3
4
5
6
7
8
9
10
11
12
unsigned ldf(unsigned n)
{
  __uint128_t f = 1;
  for (unsigned i = 2; i <= n; ++i)
  {
     f *= i;
     for (; f % 10 == 0; f /= 10);
     f %= 10'000'000'000'000; // сохраняем 13 цифр
  }
    
  return f % 10;
}

@TheCalligrapher · 03.03.2024, 02:26

Дождался

Code
1
Fail 11 at 146484375: 7 != 2

При делителе 10¹¹ функция дает первый ошибочный ответ на 146484375 = 3 * 5¹¹. Т.е. есть еще какой-то дополнительный эффект (он виден выше и для делителей поменьше), который продлевает жизнь этому подходу в три раза.

@TheCalligrapher · 22.03.2024, 02:52

Сообщение от _Ivana

C++
1
2
3
4
5
6
7
8
9
10
11
int f(int n) {
    int r = 1, d2 = 0, d5 = 0;
    for(int i=2; i<=n; i++) {
        int j = i;
        while (j%2 == 0 && j > 1) { j /= 2; d2++; }
        while (j%5 == 0 && j > 1) { j /= 5; d5++; }
        r = (r*j)%10;
    }
    for(int i=0; i<(d2-d5); i++) r = (r*2)%10;
    return r;
}

Вместо циклического деления на 2 - std::countr_zero (С++20). Вместо циклического умножения на 2 - простая зависимость последней цифры степени двойки от показателя степени:

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
unsigned f(unsigned n) 
{
  unsigned r = 1, d2 = 0, d5 = 0;
 
  for (unsigned i = 2; i <= n; ++i) 
  {
    unsigned j = i;
 
    unsigned jd2 = std::countr_zero(j);
    d2 += jd2;
    j >>= jd2;
    assert(j % 2 != 0);
 
    for (; j % 5 == 0; j /= 5, ++d5);
    assert(j % 5 != 0);
 
    r = (unsigned long long) r * j % 10;
  }
 
  assert(d2 >= d5);
  unsigned n2 = d2 - d5;
  if (n2 > 0)
    r = (unsigned long long) r * "\x2\x4\x8\x6"[(n2 - 1) % 4] % 10;
 
  return r;
}

@Royal_X · 22.03.2024, 09:38

Не по теме:

zayats80888, YMMD

@повар1 · 22.03.2024, 13:01

Сообщение от TheCalligrapher

а что если мы будем хранить не только последнюю ненулевую цифру факториала, а несколько последних ненулевых цифр?

нет необходимости: пусть допустим надо знать 17! расчитаем произведения 1*2*3*4*5=120 6*7*8*9*10=30240
11*12*13*14*15=360360 и 16*17=272. Мы расчитали произведения где последний множитель кратный 5 и произведение где последний множитель не кратен 5. Берем последние цифры результата произведений отличные от нуля и считаем 2*4*6*2=96. проверяем по таблице факториалов 17!=355687428096000355687428096000 что нам и требовалось получить. Алгоритм до 100! работает правильно дальше не проверял.

@TheCalligrapher · 22.03.2024, 19:01

Сообщение от повар1

нет необходимости: пусть допустим надо знать 17! расчитаем произведения 1*2*3*4*5=120 6*7*8*9*10=30240
11*12*13*14*15=360360 и 16*17=272. Мы расчитали произведения где последний множитель кратный 5 и произведение где последний множитель не кратен 5. Берем последние цифры результата произведений отличные от нуля и считаем 2*4*6*2=96. проверяем по таблице факториалов 17!=355687428096000355687428096000 что нам и требовалось получить.

Не совсем понимаю, что именно вы хотели сказать.

Во-первых, правильный подход к решению задачи уже приведен _Ivana в сообщении #13. Я привел существенно более эффективную реализацию этого подхода в #25. Цель моего сообщения #23, на которое вы отвечали - это не какие-то "необходимости", а лишь разобрать ошибку исходного "наивного" подхода ТС и то, как его можно попытаться "спасти".

Во-вторых, касательно только что предложенного вами варианта. Напомню, что главная проблема, из-за которой эту задача не может быт решена "в лоб" - это разрушение результата из-за арифметических переполнений. Каким образом вы в вашем варианте предлагаете "рассчитывать произведения где последний множитель кратный 5" тогда, когда сомножители станут большими? Как вы предлагаете бороться с переполнением при вычислении произведения пяти последовательных больших чисел? Разумеется, правильно вычислить последнюю цифру такого произведения пяти можно, но сделать это, наверное, лучше всего именно тем же самым подходом, что и в сообщении #13. И в конечном итоге получится то же самое. То есть я не понимаю, что именно вы пытаетесь предложить.

Сообщение от повар1

Алгоритм до 100! работает правильно дальше не проверял.

Вот вот...

Как я уже сказал в сообщении #23, до 100! (точнее, до 374!) отработает вот такая простенькая бесхитростная реализация

C++
1
2
3
4
5
6
7
8
9
10
11
12
unsigned ldf(unsigned n)
{
  unsigned long long f = 1;
  for (unsigned i = 2; i <= n; ++i)
  {
     f *= i;
     for (; f % 10 == 0; f /= 10);
     f = f % 1000; // сохраняем три цифры факториала
  }
 
  return f % 10; // результат
}

То есть это фактически вариант ТС лишь с незначительным исправлением.

@pechka_ne_sed · 22.03.2024, 19:13

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
inline int factorial(int n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}
 
int main() {
    int n = 0;
 
    std::cin >> n;
 
    n = factorial(n);
 
    int remainder = 0;
 
    while ((remainder = n % 10) == 0) {
        n /= 10;   
    }
 
    std::cout << remainder << std::endl;
}

@TheCalligrapher · 22.03.2024, 19:18

Сообщение от pechka_ne_sed

std::cout << remainder << std::endl;

https://coliru.stacked-crooked... f8d04a6686
Последняя цифра 17! равна -4, %username%... ¯\_(ツ)_/¯

@pechka_ne_sed · 22.03.2024, 19:23

TheCalligrapher, кривой алгоритм + переполнение. Модераторы, удалите мое "решение"

Новые блоги и статьи Все статьи Все блоги /
Учебный мини "цифровой двойник" = (Сервер = Java + Flask_питон )+(3D = Гугловскаая 4T nvideo + google colab) +( WMS = Odoo на Docker) anaschu 07.07.2026 Увидел в требованиях к вакансии создателя имитационных моделей связку (REst + Api + WMS + Anylogic + питон + 3D Nvideo), и решил посмотреть, что это такое. Из этого всего я работал более менее. . .	Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .
Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .

@KSergey9 631 / 526 / 104 Регистрация: 05.08.2022 Сообщений: 2,810
	01.03.2024, 13:03
	Только что ж тема была Добавлено через 28 секунд Нахождение факториала: для заданного N найти последнюю отличную от нуля цифру Один ВУЗ? 0

@Royal_X
	22.03.2024, 09:38
	Не по теме: zayats80888, YMMD 0

@pechka_ne_sed 27 / 24 / 4 Регистрация: 20.11.2023 Сообщений: 131
	22.03.2024, 19:23
	TheCalligrapher, кривой алгоритм + переполнение. Модераторы, удалите мое "решение" 0