задача создать функцию , которая принимает неотрицательное число, находит его факториал и возвращает сколько нулей на конце этого факториала [закрыт]
Закрыт. Этот вопрос необходимо уточнить или дополнить подробностями. Ответы на него в данный момент не принимаются.
Хотите улучшить этот вопрос? Добавьте больше подробностей и уточните проблему, отредактировав это сообщение.
Закрыт 1 год назад .
def factorial(n: int): a = 1 for i in range(1, n+1): a*=i return(a) def trailing_zeros(n: int) -> int: f = factorial(n) f_list=list(f) f_list.reverse() count=0 for i in range(f_list): if i ==0: count+=1 break return count Отслеживать
задан 2 фев 2022 в 14:18
21 7 7 бронзовых знаков
и в чем вопрос?
2 фев 2022 в 14:20
Вы не приняли ни одного ответа на свои вопросы.
2 фев 2022 в 14:35
Факториал можно найти функцией factorial() из модуля math. Если это нельзя использовать, то просто нужно перемножить числа от 1 до n, взяв за исключение, что 0!=1. Количество нулей можно просто посчитать циклом, в чем проблема?
– user457770
2 фев 2022 в 15:11
ежели вам нужен чистый питон, то так и скажите, а то другие люди стараются для вас, а вы даже не помечаете ответ как правильный
2 фев 2022 в 15:41
Вопрос в том что код не работает, задачка на степике, нужен чистый питон
2 фев 2022 в 15:45
4 ответа 4
Сортировка: Сброс на вариант по умолчанию
Вызовем вашу функцию factorial :
factorial(1) = 1 factorial(2) = 1 factorial(3) = 1 factorial(4) = 1 factorial(5) = 1 factorial(6) = 1 factorial(7) = 1 factorial(8) = 1 factorial(9) = 1 factorial(10) = 1 Очевидно функция factorial не считает факториал. Исправим ошибку и пойдём дальше. На этот раз вычислим trailing_zeros(1) :
Traceback (most recent call last): File "/home/sv/desk/stackoverflow/temp.py", line 19, in print(f'trailing_zeros() = ') File "/home/sv/desk/stackoverflow/temp.py", line 9, in trailing_zeros f_list=list(f) TypeError: 'int' object is not iterable Ошибка состоит в вызове функции list от числа. Это запрещено в Питоне.
Рекомендую вам запустить и привести в чувство вашу программу на компьютере прежде чем посылать в Степик на проверку.
P.S. Эта задача решается по-другому, без вычисления факториала.
Отслеживать
ответ дан 2 фев 2022 в 16:15
Stanislav Volodarskiy Stanislav Volodarskiy
29.7k 3 3 золотых знака 16 16 серебряных знаков 54 54 бронзовых знака
import math n = int(input()) result = sum(n // 5**i for i in range(1, int(math.log(n, 5))+1)) Отслеживать
ответ дан 2 фев 2022 в 16:56
19.5k 5 5 золотых знаков 22 22 серебряных знака 56 56 бронзовых знаков
Вариант 1: С использованием numpy и re.
Находим факториал и количество нулей в конце через re.search
import numpy as np import re def zeros(n: int): fact = np.math.factorial(n) return len(re.search('(0*)$', str(fact)).group(0)) Вариант 2 (Нашел у @CrazyElf): (добавил лишь нахождение факториала)
def end_zeros(n: int) -> int: num = np.math.factorial(n) return min((i for i,c in enumerate(str(num)[::-1], 0) if c != '0'), default=1) ссылка на его решение: ответ @CrazyElf
UPD. Вариант 3 (без использования библиотек):
P.S. Пришлось зарегистрироваться на сайте и поступить на курс (Этот ответ принимает система)
def factorial(n: int): a = 1 for i in range(1, n+1): a *=i return a def trailing_zeros(n: int) -> int: list_of = list(str(factorial(n))) count = 0 for i in list_of[::-1]: if i == '0': count += 1 else: break return count UPD 2. Вариант 4. (Вообще без нахождения факториала)
Суть в том, что нам можно не находить сам факториал числа n, чтобы знать сколько там нулей.
поэтому мы можем в функцию просто передать число, от которого нужно найти факториал и получить количество нулей, что при больших числах будет намного быстрее.
def factorial(n): count = 0 while n >=5: n //= 5 count += n return count Пятничный JS: единственно верный способ вычисления факториала
Вычисление факториала — одна из традиционных программистских задач для собеседований. Если вдруг кто забыл, факториал натурального числа N обозначается как N! и равняется произведению всех натуральных чисел от единицы до N включительно. Например, . Казалось бы, что тут сложного? Однако есть свои нюансы.
Например, сравним два самых распространённых способа вычисления факториала.
Через цикл
function factorial(n) < var result = 1; while(n)< result *= n--; >return result; > Через рекурсию
function factorial(n, result)< result = result || 1; if(!n)< return result; >else < return factorial(n-1, result*n); >> Многие скажут, что первый способ лучше, но это не так. Во-первых, циклы уже не в тренде, сейчас модно функциональное программирование. Во-вторых, чем больше людей используют второй способ, тем быстрее в основных джаваскриптовых движках появится оптимизация хвостовой рекурсии.
В любом случае, оба эти способа слишком примитивны, чтобы по ним судить о знаниях кандидата. А вот опытный разработчик на React.js уже может написать что-то в этом роде:
var React = require("react"); var Factorial = React.createClass( < render: function()< var result = this.props.result || 1, n = this.props.n; if(!n)< return >else < return result=/> > > >); module.exports = Factorial; Согласитесь, выглядит гораздо солиднее. Впрочем, невооружённым глазом видно, что это всего лишь вариант рекурсивного вычисления. Сходство станет ещё сильнее, если переписать Factorial как функциональный компонент. И, разумеется, я не стал бы писать этот хабрапост, если бы не был готов предложить нечто принципиально новое.
Начнём издалека
Какую из возможностей Javascript недолюбливают и недооценивают сильнее всего? Недолюбливают настолько, что про неё даже придумали специальную поговорку? Конечно же, это eval. Можно сказать, что eval — это тёмная сторона Силы. А как мы помним из фильмов Джорджа Лукаса, нет ничего более крутого и впечатляющего, чем тёмная сторона Силы, поэтому давайте попробуем ей овладеть.
Можно было бы запихнуть в строку какой-нибудь из методов, приведённых в начале поста, а затем передать эту строку в eval, но в этом не было бы новизны. Поставим задачу таким образом, чтобы сделать этот хак невозможным. Пусть у нас есть такой вот каркас:
function factorial(n) < var f = "это единственное место в коде, которое мы имеем право изменить"; f = f.replace("$", n); for(let i = 0; i < n; i++)< if(parseInt(f))< throw new Error("Cheaters are not allowed"); >f = eval(f); > return parseInt(f); > — и мы хотим, внеся изменения лишь в литерал строки f, сделать так, чтобы функция factorial взаправду вычисляла факториал. Вот задача, достойная истинного ситха.
Что-то это напоминает
Нам нужен код, который возвращает код, который возвращает код… Если забыть про конечную задачу — вычисление факториала, то есть одна хорошо известная штука, которая нам подойдёт. Эта штука называется квайн — программа, которая выводит свой собственный текст.
Про квайны на Хабре написано уже немало, потому я напомню лишь основные принципы квайностроительства. Чтобы сделать простейший квайн, нам нужно:
- Задать строку, которая содержит весь остальной текст программы.
- Подставить в эту строку её же саму
- Позаботиться об экранировании символов и прочих мелочах
- Вывести получившуюся строку
- .
- PROFIT
var o = < q: '\'', b: '\\', s: 'var o = ; console.log(Object.keys(o).reduce(function(a, k), o.s))' >; console.log(Object.keys(o).reduce(function(a, k), o.s)); В строке o.s содержится весь остальной код, а также специальные подстановочные последовательности, начинающиеся с подчёркивания. Страшное выражение внутри console.log заменяет каждую подстановочную последовательность на соответствующее свойство объекта o, что обеспечивает выполнение пунктов 2 и 3 хитрого плана по созданию квайна.
Лирическое отступление
Здесь меня могут поправить: товарищ, это не простейший квайн, а монстр какой-то. Простейший квайн на js выглядит так:
!function $()()Это правда, но не совсем. Такой квайн считается «читерским», поскольку он из тела функции получает доступ к её же тексту. Это почти то же самое, что прочитать с жёсткого диска файл с исходным кодом программы. Моветон, одним словом.
Скрещиваем ежа с ужом
Как же сделать так, чтобы наш квази-квайн модифицировал сам себя, а в результате превратился в одно-единственное число? Давайте забудем пока про вычисление факториала и постараемся просто написать строку, которая «схлопывается» через определённое количество eval’ов. Для этого нам понадобится:
- Некий счётчик
- Соответствующая ему подстановочная последовательность
- Место, где этот счётчик модифицируется
- Проверка того, завершён ли обратный отсчёт
var f = "var o = ; o.n--; " + "o.n ? Object.keys(o).reduce(function(a, k), o.s) : 0;'" + ">;" + "o.n--;" + "o.n ? Object.keys(o).reduce(function(a, k), o.s) : 0;" for(let i = 0; i
Обратите внимание на отсутствие return внутри строки: в нём нет необходимости, eval возвращает значение последнего выражения. Запустив этот код в консоли, можно c благоговением наблюдать, как с каждой итерацией цикла значение n уменьшается на 1. Если кто-то скажет, что для такого эффекта достаточно:
f.replace(/n: ([0-9]+)/, (_, n) => "n: " + (n - 1))— то у него нет чувства прекрасного.
После этого подготовительного этапа уже совсем нетрудно написать итоговую версию вычисления факториала. Просто добавляется ещё одна переменная и чуть усложняется строчка с изменением.
function factorial(n)< var f = "var o = ; o.r *= o.n--; " + "o.n ? Object.keys(o).reduce(function(a, k), o.s) : o.r;'" + ">;" + "o.r *= o.n--;" + "o.n ? Object.keys(o).reduce(function(a, k), o.s) : o.r;" f = f.replace("$", n); for(var i = 0; i < n; i++)< if(parseInt(f))< throw new Error("Cheaters are not allowed."); >f = eval(f); > return parseInt(f); > Теперь вы можете смело идти на собеседование.
Заключение
С живым кодом можно поиграться здесь. Как и в прошлой статье из рубрики «Пятничный JS» напоминаю: если вы сделаете что-нибудь подобное на продакшене, то попадёте в ад. С другой стороны, если вы сделаете это на собеседовании, то вам не дадут возможности сделать это на продакшене, и вы не попадёте в ад. Так что делайте это на собеседовании. Спасибо за внимание.
- Ненормальное программирование
- JavaScript
Вычисление факториала
Факториалом числа называют произведение всех натуральных чисел до него включительно. Например, факториал числа 5 равен произведению 1 * 2 * 3 * 4 * 5 = 120.
Формула нахождения факториала:
n! = 1 * 2 * … * n,
где n – это число, а n! – факториал этого числа.
Формулу можно представить в таком виде:
n! = 1 * … * (n-2) * (n-1) * n,
т. е. каждый предыдущий множитель меньше на единицу, чем последующий. Или в перевернутом виде, когда каждый следующий меньше предыдущего на единицу:
n! = n * (n-1) * (n-2) * … * 1,
Для вычисления факториала с помощью цикла можно использовать любую формулу. Для рекурсивного вычисления используется вторая.
Вычисление факториала с помощью циклов
С помощь цикла while :
n = int(input()) factorial = 1 while n > 1: factorial *= n n -= 1 print(factorial)
Вычисление факториала с помощью цикла for :
n = int(input()) factorial = 1 for i in range(2, n+1): factorial *= i print(factorial)
Нахождение факториала рекурсией
def fac(n): if n == 1: return 1 return fac(n - 1) * n print(fac(5))
Поток выполнения программы при n = 5:
- Вызов функции fac(5)
- fac(5) вызывает fac(4)
- fac(4) вызывает fac(3)
- fac(3) вызывает fac(2)
- fac(2) вызывает fac(1)
- fac(1) возвращает в fac(2) число 1
- fac(2) возвращает в fac(3) число 1 * 2, т. е. 2
- fac(3) возвращает в fac(4) число 2 * 3, т. е. 6
- fac(4) возвращает в fac(5) число 6 * 4, т. е. 24
- fac(5) возвращает число 24 * 5, т. е. 120 в основную ветку программы
- Число 120 выводится на экран
Функция factorial модуля math
Модуль math языка программирования Python содержит функцию factorial , принимающую в качестве аргумента неотрицательное целое число и возвращающую факториал этого числа:
>>> import math >>> math.factorial(4) 24
X Скрыть Наверх
Решение задач на Python
Вычисление факториала на C++
В данной статье рассматривается применение рекурсии в C++ на примере вычисления факториала целого числа. Для реализации приведенной ниже программы Вам понадобится среда разработки, которую можно скачать здесь или здесь.
Сначала определимся, что из себя представляет рекурсивная функция. Рекурсивной называется функция, которая возвращает значение самой себя, рассмотрим пример рекурсивной функции на примере программы, вычисляющей факториал целого числа
Создаем пустой проект в Visual Studio, добавляем файл исходного кода в проект, который мы назовем main.cpp.
Для начала напишем главную функцию программы и определим заголовочные файлы: