1 哥伦布数（Golomb Number）

哥伦布数（Golomb Number）是一个自然数的非减量序列，使得n在序列中正好出现G（n）次。前几个15的G（n）值为：1 2 2 3 3 4 4 4 5 5 5 6 6 6 6

计算结果：

2 源程序，文本格式

using System;

namespace Legalsoft.Truffer.Algorithm
{
    /// <summary>
    /// 哥伦布数（Golomb Number）
    /// 哥伦布数（Golomb Number）是一个自然数的非减量序列，使得n在序列中正好出现G（n）次。
    /// 前几个15的G（n）值为：1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
    /// </summary>
    public static partial class Number_Sequence
    {
        /// <summary>
        /// 哥伦布数（Golomb Number）的原始（递归）算法
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int Golomb_Number(int n)
        {
            if (n == 1)
            {
                return 1;
            }
            return 1 + Golomb_Number(n - Golomb_Number(Golomb_Number(n - 1)));
        }

        /// <summary>
        /// 哥伦布数（Golomb Number）的改进（非递归）算法
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int Golomb_Number_Second(int n)
        {
            int[] dp = new int[n + 1];
            dp[1] = 1;
            for (int i = 2; i <= n; i++)
            {
                dp[i] = 1 + dp[i - dp[dp[i - 1]]];
            }
            return dp[n];
        }
    }
}

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

POWER BY TRUFFER.CN

3 代码格式

using System;

namespace Legalsoft.Truffer.Algorithm
{
    /// <summary>
    /// 哥伦布数（Golomb Number）
    /// 哥伦布数（Golomb Number）是一个自然数的非减量序列，使得n在序列中正好出现G（n）次。
    /// 前几个15的G（n）值为：1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
    /// </summary>
    public static partial class Number_Sequence
    {
        /// <summary>
        /// 哥伦布数（Golomb Number）的原始（递归）算法
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int Golomb_Number(int n)
        {
            if (n == 1)
            {
                return 1;
            }
            return 1 + Golomb_Number(n - Golomb_Number(Golomb_Number(n - 1)));
        }

        /// <summary>
        /// 哥伦布数（Golomb Number）的改进（非递归）算法
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int Golomb_Number_Second(int n)
        {
            int[] dp = new int[n + 1];
            dp[1] = 1;
            for (int i = 2; i <= n; i++)
            {
                dp[i] = 1 + dp[i - dp[dp[i - 1]]];
            }
            return dp[n];
        }
    }
}