My version of the recursive solution, in one line:
dfact = lambda n: (n <= 0) or n * dfact(n-2)
However, it is also interesting to note that the double factorial can be expressed in terms of the “normal” factorial. For odd numbers,
n!! = (2*k)! / (2**k * k!)
where k = (n+1)/2. For even arguments n=2k, although this is not consistent with a generalization to complex arguments, the expression is simpler,
n!! = (2k)!! = 2*k * k!.
All this means that you can write code using the factorial function from the standard math library, which is always nice:
import math
fact = math.factorial
def dfact(n):
if n % 2 == 1:
k = (n+1)/2
return fact(2*k) / (2**k * fact(k))
else:
return 2**k * fact(k)
Now, this code is obviously not very efficient for large n, but it is quite instructive. More importantly, since we are dealing with standard factorials now, it is a very good starting point for optimizations when dealing with really large numbers. You try to use logarithms or gamma functions to get approximate double factorials for large numbers.
Напишите функцию, которая будет принимать число num и возвращать его двойной факториал. Математическая формула двойного факториала следующая.
Если num — четное число:
num !! = num (num - 2)(num - 4)(num - 6) ... (4)(2)
Если num — нечетное число:
num !! = num (num - 2)(num - 4)(num - 6) ... (3)(1)
Если num = 0 или num = -1, тогда num !! = 1.
Примечания
- Исходим из того, что
numбудет больше или равно -1. - Двойной факториал — не то же самое, что умноженный на 2.
- Попробуйте решить при помощи рекурсии.
Примеры
double_factorial(0) ➞ 1 double_factorial(2) ➞ 2 double_factorial(9) ➞ 945 # 9*7*5*3*1 = 945 double_factorial(14) ➞ 645120
Варианты решения
def double_factorial(n):
return 1 if n < 2 else n * double_factorial(n - 2)
def double_factorial(num):
if num in (0, 1) or num < 0:
return 1
return num * double_factorial(num - 2)
Как вы делаете двойной факториал в питоне?
Я застрял на этом вопросе в течение очень долгого времени. Мне удалось сделать один рекурсивный факториал.
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
Двойной факториал Для четного целого числа n двойной факториал представляет собой произведение всех четных положительных целых чисел, меньших или равных n. Для нечетного целого числа p двойной факториал представляет собой произведение всех нечетных положительных целых чисел, меньших или равных p.
Если n четно, то n!! = n*(n - 2)*(n - 4)*(n - 6)* ... *4*2
Если р нечетно, то p!! = p*(p - 2)*(p - 4)*(p - 6)* ... *3*1
Но я понятия не имею, как сделать двойной факториал. Любая помощь?
person
python learner
schedule
19.01.2011
source
источник
Ответы (10)
Разве это не то же самое, что факториал с другим конечным условием и другим параметром для рекурсивного вызова?
def doublefactorial(n):
if n <= 0:
return 1
else:
return n * doublefactorial(n-2)
Если n четное, то он остановится, когда n == 0. Если n нечетное, то оно остановится, когда n == -1.
person
CanSpice
schedule
19.01.2011
Проблема здесь в том, что двойной факториал определен для отрицательных действительных чисел (-1)!! = 1, (-3)!! = -1 (даже отрицательные целые числа (такие как -2, -4,…) должны иметь решение как +/- inf), так что… что-то плохо пахнет во всех решениях для отрицательных чисел. Если кто-то хочет определить двойной факториал для всех вещественных чисел, эти решения не работают. Решение состоит в том, чтобы определить двойной факториал с помощью гамма-функции.
import scipy.special as sp
from numpy import pi
def dfact(x):
n = (x + 1.)/2.
return 2.**n * sp.gamma(n + 0.5)/(pi**(0.5))
Оно работает! 😀
person
Eduardo Alberto Duarte Lacerda
schedule
21.04.2016
Начиная с Python 3.8, мы можем использовать функцию prod из < модуль href=”https://docs.python.org/3.8/library/math.html” rel=”nofollow noreferrer”>math, который вычисляет произведение всех элементов в итерируемом объекте, что в нашем случае это range(n, 0, -2):
import math
math.prod(range(n, 0, -2))
Обратите внимание, что это также обрабатывает случай n = 0, и в этом случае результат равен 1.
person
Xavier Guihot
schedule
14.02.2019
Моя версия рекурсивного решения в одну строку:
dfact = lambda n: (n <= 0) or n * dfact(n-2)
Однако также интересно отметить, что двойной факториал можно выразить через «нормальный» факториал. Для нечетных чисел,
n!! = (2*k)! / (2**k * k!)
где k = (n+1)/2. Для четных аргументов n=2k, хотя это и не согласуется с обобщением на сложные аргументы, выражение проще,
n!! = (2k)!! = 2*k * k!.
Все это означает, что вы можете писать код с помощью функции factorial из стандартной математической библиотеки, что всегда приятно:
import math
fact = math.factorial
def dfact(n):
if n % 2 == 1:
k = (n+1)/2
return fact(2*k) / (2**k * fact(k))
else:
return 2**k * fact(k)
Теперь этот код, очевидно, не очень эффективен для больших n, но он весьма поучителен. Что еще более важно, поскольку сейчас мы имеем дело со стандартными факториалами, это очень хорошая отправная точка для оптимизации при работе с действительно большими числами. Вы пытаетесь использовать логарифмы или гамма-функции, чтобы получить приблизительные двойные факториалы для больших чисел.
person
Karol
schedule
23.04.2014
def doublefactorial(n):
if n in (0, 1):
return 1
else:
return n * doublefactorial(n-2)
должен сделать это.
person
Lennart Regebro
schedule
19.01.2011
def double_fact(number):
if number==0 or number==1:
return 1
else:
return number*double_fact(number-2)
Я думаю, это должно сработать для вас.
person
Tauquir
schedule
19.01.2011
Надеюсь, я правильно понял, но будет ли это работать
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n-2)
person
Navi
schedule
19.01.2011
reduce(lambda x,y: y*x, range(n,1,-2))
Это в основном то же самое, что и простая итеративная версия:
x = n
for y in range(n-2, 1, -2):
x*=y
Очевидно, вы также можете сделать это рекурсивно, но в чем смысл? Примеры такого рода, реализованные с использованием рекурсии, хороши при использовании всех рекурсивных языков, но с императивным языком простые инструменты, такие как рекурсия, всегда выглядят более сложными, чем необходимо, в то время как рекурсия может быть реальным упрощением при работе с фундаментально рекурсивными структурами, такими как деревья.
person
kriss
schedule
19.01.2011
def doublefactorial(n):
if n <= 0:
return 1
else:
return n * doublefactorial(n-2)
Это должно сработать. Если я не понимаю
person
LoveAndCoding
schedule
19.01.2011
In the previous article, we have discussed Python Program for Product of Maximum in First array and Minimum in Second
Factorial:
The product of all positive integers less than or equal to n is the factorial of a non-negative integer n, denoted by n! in mathematics:
n! = n * (n – 1) *(n – 2) * . . . . . . . . . . 3 * 2 * 1.
4 != 4 * 3 * 2 *1=24
Double Factorial:
The product of all the integers from 1 to n with the same parity (odd or even) as n is the double factorial of a non-negative integer n. It is also known as a number’s semi factorial and is denoted by!!.
For example, the double factorial of 7 is 7*5*3*1 = 105
It is worth noting that as a result of this definition, 0!! = 1.
The double factorial for even number ‘n’ is:
The double factorial for odd number ‘n’ is:
Given a number ‘n’ and the task is to find the double factorial of a given number.
Examples:
Example 1:
Input:
Given number = 5
Output:
The double factorial of a given number{ 5 } = 15
Example 2:
Input:
Given number = 10
Output:
The double factorial of a given number{ 10 } = 3840
Below are the ways to find the double factorial of a given number.
- Using For Loop (Static Input)
- Using For loop (User Input)
Method #1: Using For Loop (Static Input)
Approach:
- Give the number as static input and store it in a variable.
- Take a variable, initialize it with the value ‘1’, and store it in another variable say ‘c’.
- Loop from the given number to 0 in decreasing order with the stepsize of -2 using the for loop.
- Inside the loop multiply the above initialized variable c with the iterator value and store it in the same variable ‘c’.
- Print the double factorial of a given number.
- The Exit of the Program.
Below is the implementation:
# Give the number as static input and store it in a variable.
numbr = 8
# Take a variable, initialize it with the value '1', and store it in another
# variable say 'c'.
c = 1
# Loop from the given number to 0 in decreasing order with the stepsize of -2
# using the for loop.
for i in range(numbr, 0, -2):
# Inside the loop multiply the above initialized variable c with the iterator value
# and store it in the same variable 'c'.
c *= i
# Print the double factorial of a given number.
print("The double factorial of a given number{", numbr, "} = ", c)
Output:
The double factorial of a given number{ 8 } = 384
Method #2: Using For loop (User Input)
Approach:
- Give the number as user input using the int(input()) function and store it in a variable.
- Take a variable, initialize it with the value ‘1’, and store it in another variable say ‘c’.
- Loop from the given number to 0 in decreasing order with the stepsize of -2 using the for loop.
- Inside the loop multiply the above initialized variable c with the iterator value and store it in the same variable ‘c’.
- Print the double factorial of a given number.
- The Exit of the Program.
Below is the implementation:
# Give the number as user input using the int(input()) function and store it in a variable.
numbr = int(input("Enter a random number = "))
# Take a variable, initialize it with the value '1', and store it in another
# variable say 'c'.
c = 1
# Loop from the given number to 0 in decreasing order with the stepsize of -2
# using the for loop.
for i in range(numbr, 0, -2):
# Inside the loop multiply the above initialized variable c with the iterator value
# and store it in the same variable 'c'.
c *= i
# Print the double factorial of a given number.
print("The double factorial of a given number{", numbr, "} = ", c)
Output:
Enter a random number = 7
The double factorial of a given number{ 7 } = 105
Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.
- Python Program to Print a Deck of Cards in Python
- Python Program to Multiply each Element of a List by a Number
- Python Program to Print all Twin Primes less than N
- Python Program to Enter Basic Salary and Calculate Gross Salary of an Employee
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Double factorial of a non-negative integer n, is the product of all the integers from 1 to n that have the same parity (odd or even) as n. It is also called as semifactorial of a number and is denoted by !!. For example, double factorial of 9 is 9*7*5*3*1 which is 945. Note that, a consequence of this definition is 0!! = 1.
Examples:
Input: 6 Output: 48 Note that 6*4*2 = 48 Input: 7 Output: 105 Note that 7*5*3 = 105
For even n, the double factorial is:
For odd n, the double factorial is:
Recursive Solution:
Double factorial can be calculated using following recursive formula.
n!! = n * (n-2)!! n!! = 1 if n = 0 or n = 1
Following is the implementation of double factorial.
C++
#include<stdio.h>
unsigned int doublefactorial(unsigned int n)
{
if (n == 0 || n==1)
return 1;
return n*doublefactorial(n-2);
}
int main()
{
printf("Double factorial is %d", doublefactorial(5));
return 0;
}
Java
import java.io.*;
class GFG {
static long doublefactorial(long n)
{
if (n == 0 || n==1)
return 1;
return n * doublefactorial(n - 2);
}
static public void main (String[] args)
{
System.out.println("Double factorial"
+ " is " + doublefactorial(5));
}
}
Python3
def doublefactorial(n):
if (n == 0 or n == 1):
return 1;
return n * doublefactorial(n - 2);
print("Double factorial is",
doublefactorial(5));
C#
using System;
class GFG {
static uint doublefactorial(uint n)
{
if (n == 0 || n==1)
return 1;
return n * doublefactorial(n - 2);
}
static public void Main ()
{
Console.WriteLine("Double factorial"
+ " is " + doublefactorial(5));
}
}
PHP
<?php
function doublefactorial($n)
{
if ($n == 0 || $n==1)
return 1;
return $n * doublefactorial($n - 2);
}
echo "Double factorial is ",
doublefactorial(5);
?>
Javascript
<script>
function doublefactorial(n)
{
if (n == 0 || n==1)
return 1;
return n * doublefactorial(n - 2);
}
document.write("Double factorial"
+ " is " + doublefactorial(5));
</script>
Output:
Double factorial is 15
Iterative Solution:
Double factorial can also be calculated iteratively as recursion can be costly for large numbers.
C++
#include<stdio.h>
unsigned int doublefactorial(unsigned int n)
{
int res = 1;
for (int i=n; i>=0; i=i-2)
{
if (i==0 || i==1)
return res;
else
res *= i;
}
}
int main()
{
printf("Double factorial is %d", doublefactorial(5));
return 0;
}
Java
import java .io.*;
class GFG {
static int doublefactorial(int n)
{
int res = 1;
for (int i = n; i >= 0; i = i-2)
{
if (i == 0 || i == 1)
return res;
else
res *= i;
}
return res;
}
public static void main(String[] args)
{
System.out.println("Double factorial"
+ " is " + doublefactorial(5));
}
}
Python3
def doublefactorial(n):
res = 1;
for i in range(n, -1, -2):
if(i == 0 or i == 1):
return res;
else:
res *= i;
print("Double factorial is",
doublefactorial(5));
C#
using System;
class GFG {
static int doublefactorial(int n)
{
int res = 1;
for (int i = n; i >= 0; i = i-2)
{
if (i == 0 || i == 1)
return res;
else
res *= i;
}
return res;
}
static void Main()
{
Console.Write("Double factorial"
+ " is " + doublefactorial(5));
}
}
PHP
<?php
function doublefactorial( $n)
{
$res = 1;
for ($i = $n; $i >= 0; $i = $i - 2)
{
if ($i == 0 or $i == 1)
return $res;
else
$res *= $i;
}
}
echo "Double factorial is ", doublefactorial(5);
?>
Javascript
<script>
function doublefactorial(n)
{
let res = 1;
for (let i = n; i >= 0; i = i-2)
{
if (i == 0 || i == 1)
return res;
else
res *= i;
}
return res;
}
document.write("Double factorial" + " is "
+ doublefactorial(5));
</script>
Output:
Double factorial is 15
Time complexity: O(n).
Auxiliary Space: O(1) since using constant space
Important Points :
- Double factorial and factorial are related using below formula.
Note : n!! means double factorial. If n is even, i.e., n = 2k n!! = 2kk! Else (n = 2k + 1) n!! = (2k)! / 2kk!
2.Double factorial is frequently used in combinatorics. Refer wiki for list of applications. An example application is count of perfect matchings of a complete graph Kn+1 for odd n.
References:
https://en.wikipedia.org/wiki/Double_factorial
This article is contributed by Rahul Agrawal. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Last Updated :
11 Jul, 2022
Like Article
Save Article
