c# - Project Euler 1 :Find the sum of all the multiples of 3 or 5 below 1000, 适用于 10 个数字,但不适用于 1000 个数字

标签 c# algorithm math sum

<分区>

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

所以我决定尝试解决 Euler 站点上的一些问题,以提高编程水平。在尝试解决第一个问题时,我编写了一个快速代码来计算总和,它适用于 10 个数字,但对于 1000 个数字,它向我显示了答案:166833,这是错误的,我在这里找不到问题。如果有人可以给我提示以改进我的算法,那么它就会起作用。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Multiplies_of_3_and_5
{
  class Program
  {
    static void Main(string[] args)
    {            
        int[] array = new int[7000];

        for (int j = 0; j<array.Length ;j++)
        {
            array[j] = j + 1;
        }

        int n = 1;
        int z = 1;
        int numbers = 0;

        for (int i = 0; i<999; i++)
        {
            if (array[i] == 3 * n )
            {
                n++;                    
                numbers += array[i];
            }

            else if (array[i] == 5 * z)
            {
                z++;
                numbers += array[i];
            }                                                           
        }
        Console.WriteLine(string.Join(" ", numbers));
        Console.ReadLine();
      }
   }
}

最佳答案

想法计数 3 秒、5 秒并扣除 15 秒,因为它们都在两者中,但只需要计数一次。

int maxNum = 999;
int num3s = maxNum/3; // rounded down 333
int num5s = maxNum/5; // rounded down 199

int num15s = maxNum/15; // rounded down 66

知道有多少仍然不能告诉我们总和。毕达哥拉斯来拯救。

sum3s = 3+6+9+12+15 (=45)
sum5s = 5+10+15     (=30) 
sum15s = 15         (=15)

平均值 = (最大值+最小值)/2

如果 3、5 或 15 的个数为奇数,则平均数为偶数。或者有一个偶数,在这种情况下/2 和 even 相互抵消。

所以我们得到

sumXs = (min+max)*numXs

在上面的例子中我们得到

sum3s = (3+15)/2*5 = 45
sum5s = (5+15)/2*3 = 30
sum15s = (15+15)/2*1 = 15


int sum = sum3s+sum5s-sum15s = 60;

另一个例子11

sum = (3+9)/2*3 + (5+10)/2*2 - 0 = 33

最后是 3 和 5 的和,直到 999

sum = (3+999)/2*333 + (5+995)/2*199 - (15+990)/2*66
    = 501*333 + 500*199 - (1005)*66/2 
    = 501*333 + 500*199 - 1005*33 
    =  166833 +   99500 -   33165
    =  233168

这也是程序的结果。

关于c# - Project Euler 1 :Find the sum of all the multiples of 3 or 5 below 1000, 适用于 10 个数字,但不适用于 1000 个数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47320171/

相关文章:

mysql - 不同自定义 View 的记录计数

c# - 为我的计算寻找数学函数(算术级数)

math - 将多项式曲线转换为贝塞尔曲线控制点

c# - 验证文本框中的日期

c# - 如何在unity3d中加载一个html网页

c# - 实现 Microsoft AspNet Identity IUserLockoutStore

每个用户的 c# 策略模式

algorithm - 合并排序的伪代码是如何工作的?

algorithm - 重复模式中的整数分解

c++ - Photoshop如何将两张图片融合在一起?