1

数日前、就職の面接があり、C 言語を使用して 1 から 10000 までの 2 または 5 の倍数の合計を計算する方法を尋ねられました。これは私がしました：

int mult2_5()
{
     int i, sum=0;
     for(i = 1; i <= 10000; i++)
        if(i % 2 == 0 || i % 5 == 0)
          sum += i;
     return sum;  
}

これよりも高速な実装だったのだろうか？

4

5 に答える 5

5

モジュラス演算子は非効率的です。より高速な実装は次のようになります。

int multiply2_5(int max)
{
  int i, x2 = 0,x5 = 0,x10 = 0;

  for(i = 2; i < max; i+=2)    x2 += i;    // Store all multiples of 2   O(max/2)
  for(i = 5; i < max; i+=5)    x5 += i;    //  Store all multiples of 3  O(max/5)
  for(i = 10; i < max; i+=10)  x10 += i;   //   Store all multiples 10;  O(max/10)

  return x2+x5-x10;
}

このソリューションでは、10 の倍数を取り出す必要がありました。これは、2 と 5 の倍数が 10 であるため、2 番目のループでは、最初のループで既に追加された 10 の倍数が追加されるためです。3 つのループを組み合わせると、O(8/10 最大) になります。

別のより良い解決策は、数学的アプローチを取る場合です。

この 2 + 4 + 6 + 8 ... 10000 と 5 + 10 + 15 +20 + ... 10000 のようなすべての数値を合計しようとしています。これは 2 * (1 + 2 + 3 + 4 + … + 5000) と 5 * (1 + 2 + 3 + 4 + ... + 2000) の場合、「n」個の自然数の和は (n * (n + 1)) ( source ) なので、次のように一定の時間：

int multiply2_5(int max)
{
    // x = 2 + 4 + 6 + ... = 2 * (1 + 2 + 3 +...)
    // y = 5 + 10 + 15 + ... = 5 * (1 + 2 + 3 +...)
    // The sun of n natural numbers is sn = (n (n + 1)) / 2
   int x2 = max/ 2;                      // 2 * ( 1 +2 + 3 … max/2)
   int x5 = max /5;                      // 5 * ( 1 +2 + 3 … max/5)
   int x10 = max/ 10;                  
   int sn2 = 0.5 * (x2 * (x2+1));        // (n * (n + 1)) / 2
   int sn5 = 0.5 * (x5 * (x5+1)); 
   int sn10 = 0.5 * (x10 * (x10+1));
   return (2*sn2) + (5 *sn5) - (10*sn10);
}
于 2012-11-20T00:28:30.573 に答える
2

それが「より速い」という意味であれば、最初に紙の上でそれを解決してください。

$2\sum_{1<=2k<=10000}k + 5\sum_{1<=5k<=10000} - 10\sum_{1<=10k<=10000}k$

申し訳ありませんが、私のSO方程式-fuは弱いです...とにかく、このルートは、紙の上でほとんど処理できるものを提供します:いくつかのステップを減らした後、5000 * 6001

int
mult2_5(void)
{
    return 5000*6001;
}

プロジェクト オイラーの問題 1は非常によく似ています。これに対する解決策を投稿した人はたくさんいます。

于 2012-11-20T01:15:44.050 に答える
2

以前の回答で述べたように、関連する倍数を明示的にループする方が、ループごとに残りをテストするよりも優れています。ただし、10 の倍数を計算して減算する必要はありません。5 から始めて 10 ずつ進めるだけで、すべてをスキップできます。

int multiply2_5b(int max)
{
  int i, x2 = 0,x5 = 0;

  for (i = 2; i < max; i += 2)    x2 += i;    // Sum all multiples of 2   
  for (i = 5; i < max; i += 10)   x5 += i;    // Sum all odd multiples of 5

  return x2 + x5;
}
于 2012-11-20T01:26:41.070 に答える
1

これは、数学を使用して行うことができます。2 * sum(1 to 5000) + 5 * sum(1 to 2000) - 10 * sum(1 to 1000). 練習問題として残されている、off-by-one エラーのようなもの。

于 2012-11-20T04:00:10.450 に答える
0

35 (2 + 4 + 5 + 6 + 8 + 10 の合計) で始まる単純なループを 60 のステップで実行することにより、純粋で単純な乗算にほぼ到達しました。次のくじを取る 例: 12 + 14 + 15 + 16 + 18 + 20 など for(int i=35;i<5976;i=i+60) { sum=sum+i } 5976 は 5975 が最後であることに由来しますつまり、このループは 100 回実行され、最初のターンで合計が 35 増加し、残りの 99 回で合計が 60 増加することがわかります。これは、単純な乗算などに還元できるようになりました。

于 2012-11-20T03:57:14.140 に答える