c# - 1到100亿之间有多少个数字包含14

Question

我试过这段代码，但它花了很长时间，我无法得到结果

    public long getCounter([FromBody]object req)
    {
        JObject param = Utility.GetRequestParameter(req);
        long input = long.Parse(param["input"].ToString());
        long counter = 0;
        for (long i = 14; i <= input; i++)
        {
            string s = i.ToString();
            if (s.Contains("14"))
            {
                counter += 1;
            }
        }
        return counter;
    }

请帮忙

Answer 1

我们可以检查所有 < 10^10 的非负数。每个这样的数字都可以用 10 位数字的序列表示(允许有前导零)。

14有多少个数

动态编程解决方案。让我们找出以特定数字结尾并包含(或不包含)子序列 14 的特定长度的序列数:

F(len, digit, 0)是以digit结尾且不包含14的长度为len的序列数， F(len, digit, 1) 是包含 14 的此类序列的数量。最初 F(0, 0, 0) = 1。结果是所有 F(10, digit, 1) 的总和。

可使用的 C++ 代码:https://ideone.com/2aS17v .答案好像是 872348501。

数字包含 14 的次数有多少

首先，让我们将 14 放在序列的末尾:

????????14

每个“？”可以用 0 到 9 之间的任何数字代替。因此，在末尾包含 14 的区间中有 10^8 个数字。然后考虑 ????????14?, ??????14??, ..., 14?????? ?? 数字。 14 个序列有 9 个可能的位置。答案是 10^8 * 9 = 90000000。

---

[由马修沃森添加]

这是 C++ 实现的 C# 版本；它运行不到 100 毫秒:

using System;

namespace Demo
{
    public static class Program
    {
        public static void Main(string[] args)
        {
            const int M = 10;
            int[,,] f = new int [M + 1, 10, 2];

            f[0, 0, 0] = 1;

            for (int len = 1; len <= M; ++len)
            {
                for (int d = 0; d <= 9; ++d)
                {
                    for (int j = 0; j <= 9; ++j)
                    {
                        f[len,d,0] += f[len - 1,j,0];
                        f[len,d,1] += f[len - 1,j,1];
                    }
                }
                f[len,4,0] -= f[len - 1,1,0];
                f[len,4,1] += f[len - 1,1,0];
            }

            int sum = 0;

            for (int i = 0; i <= 9; ++i)
                sum += f[M,i,1];

            Console.WriteLine(sum); // 872,348,501
        }
    }
}