0

我已经浏览了我的代码，并试图让它尽可能高效。如果不冻结我的盒子，我仍然无法让这个程序一直运行。我让它在没有冻结的情况下运行的最长时间约为 2 小时。我不敢相信这没有在这么长的时间内执行。

是我的电脑有问题，还是这种解决这个问题的蛮力方法效率低下。

在将来编写方法时，有哪些方法可以避免这种类型的低效率？

private void Form1_Load(object sender, EventArgs e)
    {
        ArrayList listOfAbundantNumbers = new ArrayList();
        ArrayList listOfSums = new ArrayList();
        long total = 0;

        for (int i = 1; i < 20162; i++)
        {
            if (isAbundandt(i))
            {
                listOfAbundantNumbers.Add(i);
            }
            total+=i;
        }

        for (int i = 1; i < listOfAbundantNumbers.Count; i++)
        {
            for (int a = 0; a < listOfAbundantNumbers.Count; a++)
            {
                long temp1 = Convert.ToInt64(listOfAbundantNumbers[i]);
                long temp2 = Convert.ToInt64(listOfAbundantNumbers[a]);
                long num = temp1 + temp2;
                if(listOfSums.Contains(num) == false)
                {
                    listOfSums.Add(num);
                }
            }
        }

        for (int i = 1; i < listOfAbundantNumbers.Count; i++)
        {
            long temp1 = Convert.ToInt64(listOfAbundantNumbers[i]);
            total -= temp1;
        }

        printLn(total + "");
    }

    private ArrayList divisorList(long input)
    {
        ArrayList divisors = new ArrayList();
        for (long i = 2; i < Math.Round(Math.Sqrt(input),0,0); i++)
        {
            long temp = input % i;
            if (temp == 0)
            {
                divisors.Add(i);
                divisors.Add(input / i);
            }
        }
        return divisors;
    }

    private Boolean isAbundandt(long input)
    {
        long sum = 0;
        ArrayList divisor = divisorList(input);

        for (int i = 0; i < divisor.Count; i++)
        {
            long temp1 = Convert.ToInt64(divisor[i]);
            sum += temp1;
        }
        sum++;

        if (sum > input)
        {
            return true;
        }
        return false;
    }
4

1 回答 1

0

避免使用ArrayList，更喜欢通用集合，例如List<Int64>因为您的转换可能非常昂贵。

您的程序中有一部分位于O(n^3)中。它可以很容易地减少到O(n^2)。只需替换以下代码（O(n)因为List<T>.Contains）：

if(listOfSums.Contains(num) == false)
{
    listOfSums.Add(num);
}

经过：

listOfSums.Add(num);

where listOfSumsis a HashSet<Int64>(它曾经有一个没有重复的集合)。

此外，您可以将填充 的时间减少listOfSums2 倍，只需注意如果交换i和a，则sum是相同的，那么只有两个组合中的一个被添加到listOfSums.

您可以更换：

for (int i = 1; i < listOfAbundantNumbers.Count; i++)
    for (int a = 0; a < listOfAbundantNumbers.Count; a++)

经过;

for (int i = 1; i < listOfAbundantNumbers.Count; i++)
    for (int a = 0; a <= i; a++)

最终代码是：

private static void Main()
{
    List<Int64> listOfAbundantNumbers = new List<Int64>();
    HashSet<Int64> listOfSums = new HashSet<Int64>();
    long total = 0;

    for (int i = 1; i < 20162; i++)
    {
        if (isAbundandt(i))
        {
            listOfAbundantNumbers.Add(i);
        }
        total += i;
    }

    for (int i = 0; i < listOfAbundantNumbers.Count; i++)
        for (int a = 0; a <= i; a++)
        {
            long temp1 = Convert.ToInt64(listOfAbundantNumbers[i]);
            long temp2 = Convert.ToInt64(listOfAbundantNumbers[a]);
            long num = temp1 + temp2;
            listOfSums.Add(num);
        }

    for (int i = 1; i < listOfAbundantNumbers.Count; i++)
    {
        long temp1 = Convert.ToInt64(listOfAbundantNumbers[i]);
        total -= temp1;
    }

    Console.WriteLine(total + "");
}

private static List<Int64> divisorList(long input)
{
    List<Int64> divisors = new List<Int64>();
    for (long i = 2; i < Math.Round(Math.Sqrt(input), 0, 0); i++)
    {
        long temp = input % i;
        if (temp == 0)
        {
            divisors.Add(i);
            divisors.Add(input / i);
        }
    }
    return divisors;
}

private static Boolean isAbundandt(long input)
{
    long sum = 0;
    List<Int64> divisor = divisorList(input);

    for (int i = 0; i < divisor.Count; i++)
    {
        long temp1 = divisor[i];
        sum += temp1;
    }
    sum++;

    if (sum > input)
    {
        return true;
    }
    return false;
}
于 2013-07-25T18:57:59.060 回答