时间戳

首页 > 解决方案 > C# 查找一串数字中每个可被 3 整除的数字

c# - C# 查找一串数字中每个可被 3 整除的数字

问题描述

这是我在这里的第一篇文章，我是 C# 新手，我的代码有一些问题。

class Program
{
    static void Main(string[] args)
    {
        #region FindAllNumbersDivisibleBy3
        Console.Write("Enter a string of numbers: ");
        string Nums = Console.ReadLine();          
        List<long> arr = new List<long>(); 
     
        for (int i = 0; i < Nums.Length; i++)
        {
            for(int j = Nums.Length - 1; j >= i; j--)
            {
                try
                {
                    string substring = Nums.Substring(i, j);                      
                    if (Convert.ToInt64(substring) % 3 == 0)
                    {
                        arr.Add(Convert.ToInt64(substring));                                                    
                    }
                }
                catch (Exception e)
                {
                    Console.WriteLine(e.Message);
                }
               
            }
        }
        Console.WriteLine("The following numbers are divisble by 3: ");
        for (int i = 0; i < arr.Count; i++)
        {
            Console.WriteLine(arr[i]);
        }
        
        Console.ReadLine();
        #endregion
    }
}

问题如下：给了我一系列数字，可能太大且效率低而无法存储为整数，因此建议使用字符串，并且您必须找到每个数字都可以被三整除。那可能是整个字符串，或者一些子字符串，或者只是个位数等。我从 catch 异常中得到一些转换错误，以及关于一些长度参数的其他东西，我真的不明白问题出在哪里. for 循环的参数也可能有一些错误，但就我而言，问题始于 try 块。抱歉，如果这是一个非常愚蠢的问题，我还在上高中，所以我还不太擅长编程。提前谢谢你的帮助。

标签： c#

解决方案

这仍然容易受到溢出的影响，但确实需要很长的字符串才能达到这一点：

class Program
{
    static void Main(string[] args)
    {
        Console.Write("Enter a string of numbers: ");
        string Nums = Console.ReadLine();          
        Console.WriteLine("The following numbers are divisble by 3: ");

        foreach(var result in DivisibleByThree(Nums))
        {
            Console.WriteLine(result);
        }
        
        Console.ReadKey(true);
    }

    public static IEnumerable<string> DivisibleByThree(string input)
    {
        for (int i = 0; i < input.Length; i++)
        {
            for(int j = input.Length; j > i; j--)
            {
                string segment = input.Substring(i, j-i);                      
                if (SumOfDigits(segment) % 3 == 0)
                {
                    yield return segment;                                                    
                }
            }
        }
    }

    public static int SumOfDigits(string digits)
    {
        return digits.Where(c => char.IsDigit(c)).Select(c => c-'0').Sum();
    }
}

在这里看到它的工作：

https://dotnetfiddle.net/KacyAD

而且由于有人建议递归，我认为尝试一下会很有趣。我没有达到我想要的程度（删除两个循环并使用递归作为唯一的重复机制），但这确实有效：

public static IEnumerable<string> DivisibleByThree(string input)
{
    if (input.Length > 1)
    {
       foreach(var item in DivisibleByThree(input.Substring(0, input.Length-1))) 
       {
           yield return item;
       }
    }
    while(input.Length > 0)
    {
        if ( SumOfDigits(input) % 3 == 0) yield return input;
        input = input.Substring(1);
    }
}

但这就是无聊的递归。从纯粹的性能角度来看，它仍然花费大量时间对相同的数字序列求和。可能有一种方法可以使用递归来保留每个递归调用的先前工作，这样可以显着加快运行速度。

也就是说，不是从一个大字符串开始并逐步检查更小的段，而是从小字符串开始，并且每次检查都添加仅附加数字的总和：

public static IEnumerable<string> DivisibleByThree(string input)
{
    for(int i = input.Length - 1; i>=0; i--)
    {
        foreach(var item in DivisibleByThreeR(input.Substring(i, input.Length - i), 0, 0, 0)) yield return item;
    }
}

public static IEnumerable<string> DivisibleByThreeR(string input, int startPos, int nextPos, int sum)
{
    sum += input[nextPos] - '0';
    if (sum % 3 == 0) yield return input.Substring(startPos, nextPos - startPos + 1);
    if (++nextPos < input.Length) 
    {
        foreach (var item in DivisibleByThreeR(input, startPos, nextPos, sum)) yield return item;
    }
}

我不确定这是否真的更快。除了获得正确的结果之外，我根本没有进行基准测试或测试。事实上，我怀疑迭代器会吃掉对纯循环版本的任何改进。

还有一种方法可以将外部方法中的循环也移动到递归函数中，从而进一步优化。但这是一个很好的练习。

如果其他人想玩，这是我最后的小提琴：

https://dotnetfiddle.net/dGFWNx

推荐阅读