Вычисление факториала 20-битного числа

@Jen948 · Регистрация: 27.10.2013

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

Здравствуйте.
Дано 20-битное беззнаковое целое число.
Нужно узнать количество знаков и количество нулей его факториала в N системе счисления.

Задача сводится к нахождению факториала 20-битного числа.
Есть ли в C++ какой-то тип "больших" данных, который сможет вместить результат?
Сторонние библиотеки подключать нельзя

@ForEveR · 27.10.2014, 11:11

Jen948, Если стороннее нельзя - писать свою библиотеку для работы с длинными числами. На форуме была куча тем, используйте поиск.

Байт · 27.10.2014, 11:18

Подсчитать количество нулей можно и не вычисляя факториала. Для этого нужно только подсчитать количество пятерок в разложении на множители всех чисел до данного N (ибо двоек хватит всегда)
Количесво знаков тоже можно подсчитать, как сумму логарифмов по основании 10

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

Есть ли в C++ какой-то тип "больших" данных, который сможет вместить результат?

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

@Jen948 · 27.10.2014, 20:10 **[ТС]**

Сообщение от Байт

Подсчитать количество нулей можно и не вычисляя факториала. Для этого нужно только подсчитать количество пятерок в разложении на множители всех чисел до данного N (ибо двоек хватит всегда)
Количесво знаков тоже можно подсчитать, как сумму логарифмов по основании 10

Спасибо.. А можно ли распространить это свойство на системы счисления, отличные от 10?
В моем случае от 1 до 800.

То есть задано число в десятичной системе, нужно узнать кол-во нулей и общее число знаков его факториала в N системе

Байт · 28.10.2014, 11:36

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

То есть задано число в десятичной системе, нужно узнать кол-во нулей и общее число знаков его факториала в N системе

Общее количество знаков - легко. Просто сумма логарифмов по основанию N
А вот с нулями... Тут видимо, для каждого числа по разному...Если N - простое - тоже все просто
А в общем случае подумать надо

@Somebody · 28.10.2014, 11:42

Тут полноценная длинная арифметика даже и не нужна. Если 64-битный тип есть, то это будет умножение длинного на короткое.

@_Ivana · 28.10.2014, 11:42

Рискну предположить, что как с основанием 10 мы целочисленно делим на 5 и суммируем результаты пока не кончится число, так и в системе с любым другим основание - факторизуем основание и прогоняем описанную процедуру для максимального простого из элементов факторизации,

Сообщение от Байт

(ибо двоек хватит всегда)

Байт · 28.10.2014, 11:52

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

Тут полноценная длинная арифметика даже и не нужна.

Согласен.
Но хочу добавить, что по моим наблюдениям каждый уважающий себя (или собирающийся уважать в будущем) программист в начале своей карьеры обязательно создает свой вариант длинной арифметики.

@_Ivana · 28.10.2014, 12:02

А те, кому повезло больше, вообще реализуют ее тривиально прямо на ассемблере с использованием флага переноса регистра состояния, и потом удрученно смотрят на ограниченную систему базовых типов С/С++ и других языков высокого уровня...

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@Jen948 8 / 8 / 2 Регистрация: 27.10.2013 Сообщений: 207

	Вычисление факториала 20-битного числа 27.10.2014, 11:00. Показов 1973. Ответов 8 Метки нет (Все метки) Здравствуйте. Дано 20-битное беззнаковое целое число. Нужно узнать количество знаков и количество нулей его факториала в N системе счисления. Задача сводится к нахождению факториала 20-битного числа. Есть ли в C++ какой-то тип "больших" данных, который сможет вместить результат? Сторонние библиотеки подключать нельзя 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	27.10.2014, 11:11
	Jen948, Если стороннее нельзя - писать свою библиотеку для работы с длинными числами. На форуме была куча тем, используйте поиск. 0

@Somebody 2838 / 1647 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	28.10.2014, 11:42
	Тут полноценная длинная арифметика даже и не нужна. Если 64-битный тип есть, то это будет умножение длинного на короткое. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	28.10.2014, 12:02
	А те, кому повезло больше, вообще реализуют ее тривиально прямо на ассемблере с использованием флага переноса регистра состояния, и потом удрученно смотрят на ограниченную систему базовых типов С/С++ и других языков высокого уровня... 0