当前位置：首页 > article >正文

C#，聚会数（相遇数，Rencontres Number）的算法与源代码

article 2024/9/27 17:27:27

1 相遇数

相遇数（Rencontres Number，partial derangement numbers）是指部分扰动的数量，或与独立对象的r相遇的置换数（即具有固定点的独立对象的置换数）。

看不通。懂的朋友给解释一下哈。

2 源程序

using System;

namespace Legalsoft.Truffer.Algorithm
{
   public static partial class Number_Sequence
   {
       private static int Rencontres_Number_Binomial_Coeff(int n, int k)
       {
           if (k == 0 || k == n)
           {
               return 1;
           }
           return Rencontres_Number_Binomial_Coeff(n - 1, k - 1) + Rencontres_Number_Binomial_Coeff(n - 1, k);
       }

       public static int Rencontres_Number(int n, int m)
       {
           if (n == 0 && m == 0)
           {
               return 1;
           }
           if (n == 1 && m == 0)
           {
               return 0;
           }
           if (m == 0)
           {
               return (n - 1) * (Rencontres_Number(n - 1, 0) + Rencontres_Number(n - 2, 0));
           }
           return Rencontres_Number_Binomial_Coeff(n, m) * Rencontres_Number(n - m, 0);
       }

       private static int[,] Rencontres_Number_Binomial_Coeff_Second(int n, int k)
       {
           int[,] Coeff = new int[MAX, MAX];
           for (int i = 0; i <= n; i++)
           {
               for (int j = 0; j <= Math.Min(i, k); j++)
               {
                   if (j == 0 || j == i)
                   {
                       Coeff[i, j] = 1;
                   }
                   else
                   {
                       Coeff[i, j] = Coeff[i - 1, j - 1] + Coeff[i - 1, j];
                   }
               }
           }
           return Coeff;
       }

       public static int Rencontres_Number_Second(int n, int m)
       {
           int[,] Coeff = Rencontres_Number_Binomial_Coeff_Second(n, m);
           int[,] dp = new int[n + 1, m + 1];
           for (int i = 0; i <= n; i++)
           {
               for (int j = 0; j <= m; j++)
               {
                   if (j <= i)
                   {
                       if (i == 0 && j == 0)
                       {
                           dp[i, j] = 1;
                       }
                       else if (i == 1 && j == 0)
                       {
                           dp[i, j] = 0;
                       }
                       else if (j == 0)
                       {
                           dp[i, j] = (i - 1) * (dp[i - 1, 0] + dp[i - 2, 0]);
                       }
                       else
                       {
                           dp[i, j] = Coeff[i, j] * dp[i - j, 0];
                       }
                   }
               }
           }
           return dp[n, m];
       }
   }
}

——————————————————————————

POWER BY TRUFFER.CN 50018.COM

3 代码格式

using System;

namespace Legalsoft.Truffer.Algorithm
{
    public static partial class Number_Sequence
    {
        private static int Rencontres_Number_Binomial_Coeff(int n, int k)
        {
            if (k == 0 || k == n)
            {
                return 1;
            }
            return Rencontres_Number_Binomial_Coeff(n - 1, k - 1) + Rencontres_Number_Binomial_Coeff(n - 1, k);
        }
        
        public static int Rencontres_Number(int n, int m)
        {
            if (n == 0 && m == 0)
            {
                return 1;
            }
            if (n == 1 && m == 0)
            {
                return 0;
            }
            if (m == 0)
            {
                return (n - 1) * (Rencontres_Number(n - 1, 0) + Rencontres_Number(n - 2, 0));
            }
            return Rencontres_Number_Binomial_Coeff(n, m) * Rencontres_Number(n - m, 0);
        }

        private static int[,] Rencontres_Number_Binomial_Coeff_Second(int n, int k)
        {
            int[,] Coeff = new int[MAX, MAX];
            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= Math.Min(i, k); j++)
                {
                    if (j == 0 || j == i)
                    {
                        Coeff[i, j] = 1;
                    }
                    else
                    {
                        Coeff[i, j] = Coeff[i - 1, j - 1] + Coeff[i - 1, j];
                    }
                }
            }
            return Coeff;
        }

        public static int Rencontres_Number_Second(int n, int m)
        {
            int[,] Coeff = Rencontres_Number_Binomial_Coeff_Second(n, m);
            int[,] dp = new int[n + 1, m + 1];
            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= m; j++)
                {
                    if (j <= i)
                    {
                        if (i == 0 && j == 0)
                        {
                            dp[i, j] = 1;
                        }
                        else if (i == 1 && j == 0)
                        {
                            dp[i, j] = 0;
                        }
                        else if (j == 0)
                        {
                            dp[i, j] = (i - 1) * (dp[i - 1, 0] + dp[i - 2, 0]);
                        }
                        else
                        {
                            dp[i, j] = Coeff[i, j] * dp[i - j, 0];
                        }
                    }
                }
            }
            return dp[n, m];
        }
    }
}

查看全文

http://www.kler.cn/news/232534.html