Рубрики

Двойной факториал

Двойной факториал неотрицательного целого числа n является произведением всех целых чисел от 1 до n, имеющих одинаковую четность (нечетную или четную) с n. Это также называется полуфакториалом числа и обозначается как !! , Например, двойной факториал 9 равен 9 * 7 * 5 * 3 * 1, что составляет 945. Обратите внимание, что следствием этого определения является 0 !! = 1

Примеры:

Input: 6
Output: 48
Note that 6*4*2 = 48

Input: 7
Output: 105
Note that 7*5*3 = 105

Для четного n двойной факториал равен:

Для нечетного n двойной факториал равен:

Рекурсивное решение:
Двойной факториал можно рассчитать по следующей рекурсивной формуле.

  n!! = n * (n-2)!!
  n!! = 1 if n = 0 or n = 1 

Ниже приводится реализация двойного факториала.

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;

}

Джава

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));

    }

}

  
// Этот код предоставлен anuj_67.

python3

# функция, чтобы найти двойной
# факториал заданного числа

def doublefactorial(n):

  

    if (n == 0 or n == 1):

        return 1;

    return n * doublefactorial(n - 2);

  
Код водителя

print("Double factorial is"

       doublefactorial(5));

  
# Этот код добавлен
# от Smitha

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));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP-код для
// Двойной факториал

  
// возврат функции
// двойной факториал

function doublefactorial($n)

{

    if ($n == 0 || $n==1)

    return 1;

    return $n * doublefactorial($n - 2);

}

  

    // Код драйвера

    echo "Double factorial is "

            doublefactorial(5);

  
// Этот код предоставлен Ajit.
?>


Выход:

Double factorial is 15

Итеративное решение:
Двойной факториал также может быть вычислен итеративно, поскольку рекурсия может быть дорогостоящей для больших чисел.

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));

    }

}

  
// Этот код предоставлен Anuj_67

python3

# 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));

  
# Этот код предоставлен mits

C #

// 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));

    }

}

  
// Этот код предоставлен Anuj_67

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);

  
// Этот код предоставлен anuj_67.
?>


Выход:

Double factorial is 15

Временная сложность указанных решений составляет O (n).

Важные моменты :

  1. Двойной факториал и факториал связаны с использованием приведенной ниже формулы.
    Note : n!! means double factorial.
    If n is even, i.e., n = 2k
       n!! = 2kk!
    Else (n = 2k + 1)
       n!! = (2k)! / 2kk! 
    
  2. Двойной факториал часто используется в комбинаторике. Обратитесь к вики для получения списка приложений. Примером приложения является подсчет совершенных совпадений полного графа K n + 1 для нечетного n.

Ссылки:
https://en.wikipedia.org/wiki/Double_factorial

Эта статья предоставлена Рахул Агравал . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Двойной факториал

0.00 (0%) 0 votes