Другие языки программирования и технологии
Факториалы больших чисел и действия с ними
Кто может помочь понять, что надо сделать чтобы решить 300!/(100!*100!*100!). Понимаю, что 100! из знаменателя сокращается на первые 100 множителей из 300!. Но остаются в числителе множители от 101 до 300, четные из них найдут свою пару из разложения знаменателя, но что-то должно же быть попроще. С программированием не знакома, оперирую только математическими знаниями.
Магома Магомедов
1 862
Первый шаг на пути оптимизации — занести все числа в массив.
Сформируем 2 таких, в одном сохраним числа от 2 до 100, утроив их. В другом от 2 до 300.
Далее предлагаем программе вытаскивать числа из первого массива ради умножения, а далее проверять, делится ли уже существующее значение на первый элемент второго массива.
И прикрытия от возможных проблем:
Что, если в делимой части числа закончатся раньше? Ответ: тогда только проверяем на деление.
Что, если раньше кончатся числа в делителе? Тогда только умножаем.
Могу попробовать реализовать, если это практическое задание.
Сформируем 2 таких, в одном сохраним числа от 2 до 100, утроив их. В другом от 2 до 300.
Далее предлагаем программе вытаскивать числа из первого массива ради умножения, а далее проверять, делится ли уже существующее значение на первый элемент второго массива.
И прикрытия от возможных проблем:
Что, если в делимой части числа закончатся раньше? Ответ: тогда только проверяем на деление.
Что, если раньше кончатся числа в делителе? Тогда только умножаем.
Могу попробовать реализовать, если это практическое задание.
Игорь Лотков
___код для python, важна табуляция, которую сайт не сохранит.
Магома Магомедов
Спасибо большое. Может и прав Евгений Высочин, что это не мое. Но проблема в том, что я способна на многое, кроме варки борща. Преподавала физическую химию, имею ученую степень, занимаюсь репетиторством. Ученик сдавал МАТЕМАТИКУ в ВШЭ. Все решил кроме этой задачи. И мне самой очень интересно стало как решить ее, зная лишь школьную программу по математике. Дело может в самом задании. В нем надо определить максимальное целое неотрицательное число р, при котором данное выражение с факториалами делится на 6^р. Если не пожалеть времени, можно решить самым примитивным образом. Но здесь должно быть что-то математическое. Спасибо за участие в моей проблеме. Мне действительно не место в сообществе программистов. Suum cuique.
Проще всего напрямую вычислить. На PascalABC.NET:
var p,q:biginteger;
begin
p:=1; q:=1;
for var i:=1 to 300 do p*=i;
for var i:=1 to 100 do q*=i;
writeln(p/(q*q*q))
end.
Результат
376523493564631064367712071965768747782444205128669798396168767743500485766630075466163294008566118208045715304490994009624725072511252178400
Или на калькуляторе из Интернета для работы с большими числами
3.765234935646310643677120719657687477824442051286697983961687677435004857666300754661632940085661182080457153044909940096247250725112521784e+140
var p,q:biginteger;
begin
p:=1; q:=1;
for var i:=1 to 300 do p*=i;
for var i:=1 to 100 do q*=i;
writeln(p/(q*q*q))
end.
Результат
376523493564631064367712071965768747782444205128669798396168767743500485766630075466163294008566118208045715304490994009624725072511252178400
Или на калькуляторе из Интернета для работы с большими числами
3.765234935646310643677120719657687477824442051286697983961687677435004857666300754661632940085661182080457153044909940096247250725112521784e+140
Дмитрий Шалимов
69 519
300!/(100!*100!*100!) = (101 * 102 * ...200) * (201 * 202 * ...300) / (100! * 100!)
________
(101 * 102 * ...* 199 * 200) / (1 * 2 * 3 * ...* 99 * 100)
= (101 / 1) * (102 / 2) * (103 / 3) * ...* (200 / 100)
= (200 / 100) * (198 / 99) * (196 / 98) * (194 / 97) * (102 / 51) * остальное
= 2 * 50 * остальное
= 100 * (199 * 197 * 195 * .. * 101) / (1 * 2 * ...* 49 * 50)
(то же самое для 201-300)
Вроде дальше некуда сокращать...
Можно еще пятерки сократить для (195 / 50) * (185 * 45), но легче уж циклом досчитать. Количество операций примерно вдвое сократилось.
________
(101 * 102 * ...* 199 * 200) / (1 * 2 * 3 * ...* 99 * 100)
= (101 / 1) * (102 / 2) * (103 / 3) * ...* (200 / 100)
= (200 / 100) * (198 / 99) * (196 / 98) * (194 / 97) * (102 / 51) * остальное
= 2 * 50 * остальное
= 100 * (199 * 197 * 195 * .. * 101) / (1 * 2 * ...* 49 * 50)
(то же самое для 201-300)
Вроде дальше некуда сокращать...
Можно еще пятерки сократить для (195 / 50) * (185 * 45), но легче уж циклом досчитать. Количество операций примерно вдвое сократилось.
Безумный Пушистик
62 360
Не твоё это. Иди вари борщ! :)
Дуся Макаревич
37 945
А что надо-то - просто значение получить? Тогда можно зайти в командную оболочку Питона и набрать:
from math import factorial as f
print(f(300)/f(100)**3)
И тут же появится ответ:
3.7652349356463108е+140
from math import factorial as f
print(f(300)/f(100)**3)
И тут же появится ответ:
3.7652349356463108е+140
Сергей Гура
28 648
Похожие вопросы
- как посчитать 365! (С++) Нужен алгоритм вычисления факториала больших чисел.
- Факториал парных чисел в С++ (VS 2010)
- На сколько нулей оканчивается факториал заданного числа
- Написать на Турбо прологе программу вычисляющую факториал заданного числа
- информатика. вычислите факториал натурального числа n.
- Требуется калькулятор для очень больших чисел, очень больших. Есть такой?
- C++ long double большие числа при умножении искажаются
- Паскаль ДОЛГО считывает КОД с большими числами
- Delphi Как сложить два очень больших числа?
- Паскаль. Цикл While. Определить остаток от деления большего числа а на меньшее число b, не используя стандартные функции