-1

問題: 2520 は、1 から 10 までの各数字で割り切れる最小の数です。

1 から 20 までのすべての数で割り切れる最小の正の数は?

そこで、プロジェクト euler で演習 5 を実行しようとして、次のコードを作成しました。

#include <stdio.h>
#define TRUE 1
#define FALSE 0

int main () {
   int n, fnd = FALSE, count, i; 

   for (i = 1; fnd == FALSE; i++) {       
      count = 0;
      for (n = 1; n <= 20; n++) {
         count += i % n;
      }
      printf ("testing %d, count was: %d\n", i, count);
      if (count == 0) {
         fnd = TRUE;
         printf ("%d\n", i); 
      }
   }
   return 0;
}

私のアプローチは正しいと信じています。1 から 20 で割り切れる数を確実に見つけることができます。私のアプローチは正しいですか？はいの場合、それを行う別の方法はありますか？これを解決する別の方法は考えられません。ヒントをいただければ幸いです。前もって感謝します。

編集：皆さんからのアドバイスに基づいて、私はそれを理解しました、どうもありがとうございました！したがって、これは依然として強引ですが、最後の数値に 1 を追加する代わりに、1 から 10 の最小公倍数である 2520 を追加します。したがって、2520 の倍数の剰余の合計を 11 から20 は 0 でした。2520 は既に 1 から 10 で割り切れるので、11 から 20 で割るだけで済みました。

#include <stdio.h>
#define TRUE 1
#define FALSE 0

int main () {
   int n, fnd = FALSE, count, i; 

   for (i = 2520; fnd == FALSE; i = i + 2520) {       
      count = 0;
      for (n = 11; n <= 20; n++) {
         count += i % n;
      }
      printf ("testing %d, count was: %d\n", i, count);
      if (count == 0 && i != 0) {
         fnd = TRUE;
         printf ("%d\n", i); 
      }
   }
   return 0;
}

どうもありがとうございます。あなたの助けなしには解決できません :) PS: 10 秒未満で計算できるようになりました。

4

7 に答える 7

3

あなたのアプローチは力ずくの解決策であるため、時間がかかりすぎています。少し賢くなる必要があります。

あなたへの私のヒントはこれです:ある数が別の数で割り切れるとはどういう意味ですか? または、特定の数を下回るすべての数ですか？数の素因数に共通点はありますか? 割り切れる可能性に関するウィキペディアのページは、良い出発点になるはずです。

于 2012-05-06T18:34:21.457 に答える
3

ヒント: 「最小公倍数」を調べる必要があります。

次のヒント:

  1. 答えは、1、2、3、...、20 の最小公倍数 (LCM) です。
  2. n 個の数値の最小公倍数は、連続して見つけることができます。LCM(1, 2) = xの場合、LCM(1, 2, 3) = LCM( x , 3); LCM(1, 2, 3) = yの場合、 LCM(1, 2, 3, 4) = LCM( y , 4) などよりも. したがって、任意の 2 つの数値の LCM を見つける方法を知っていれば十分です。
  3. 2 つの数値の最小公倍数を見つけるには、次の式を使用できます: LCM( p , q ) = pq /GCD( p , q )、ここで、GCD は最大公約数です。
  4. GCD を見つけるには、よく知られた Euclid のアルゴリズムがあります (おそらく、地球上で最初の重要なアルゴリズムです)。
于 2012-05-06T18:36:33.070 に答える
1

2から20までの各数の素因数を計算することから始めるべきだと思います。目的の数は1から20までの各数で割り切れる必要があるため、それらの数の各素因数でも割り切れる必要があります。

さらに、素因数の多重度を追跡することが重要です。たとえば、4 = 2 * 2であるため、必要な数は2*2で割り切れる必要があります。

于 2012-05-06T19:05:56.030 に答える
0

Python 3 ですぐに焼き上げたもの:

primary_list = []
for i in range(2, 4097):
    j = i
    k = 2
    delta_list = primary_list[0:]
    alpha_list = []
    while j > 1:
        if j % k == 0:
            j /= k
            alpha_list.append(k)
            k = 2
        else:
            k += 1
    for i in alpha_list:
        try:
            delta_list.remove(i)
        except:
            primary_list.append(i)
final_number = 1
for i in primary_list:
    final_number *= i
print(final_number)

これは、低速のマシンでわずか数秒で計算されます。Python は抽象数を扱うのに非常に適しています。仕事に最適なツール。

アルゴリズムは比較的単純です。数値の倍数を格納する基本リストprimary_listがあります。次に、計算したい数値の範囲を推定するループが来ます。一時変数jを、簡単に分割、分割、および征服できる数値として使用します。2から始まる除数としてkを使用します。delta_listはprimary_listのメインの作業コピーであり、必要な " logic "だけが残るまで番号を次々と分解します。次に、これらの番号をプライマリ リストに追加します。

1: 1
2: 2 1
3: 3 1
4: 2 2 1
5: 5 1
6: 2 3 1
7: 7 1
8: 2 2 2 1
9: 3 3 1
10: 2 5 1

最終的な数値は、primary_listにある数値を乗算することで見つかります。
1 * 2 * 3 * 2 * 5 * 7 * 2 * 3 = 2520

前述のように、Python は数値を扱うのが_本当に_得意です。仕事に最適なツールです。そのため、Euler の演習では、C、Erlang、Go、D、またはその他の動的/静的言語の代わりに使用する必要があります。

于 2012-05-06T19:41:03.310 に答える
0

上記のコメントについてのいくつかの考え、

@ pg190 は、「実際には、1 から 20 までの素数、つまり 2、3、5、7、11、13、17、19 で割り切れる必要があるだけです」と言っています。9699690 を取り、1 ～ 20 のすべての値で除算しません。

これは良い解決策かもしれませんので、

与えられた数値セット [1-20]

最小公倍数は次のように計算できます。

元。数字 2,6,9 の場合

素数のかけ算で表せ 2 2

6 2 3

9 3 3

LCM = 各素数の最高べき乗の倍数。= 2*3^2 = 18

これは、各数値を素数乗算として表現し、この計算を行うことによって、手元の問題に対して行うことができます。

于 2013-08-18T23:34:28.087 に答える
0

Cを使用して解決しました。以下がアルゴリズムです！

#include <stdio.h>
#include <stdio.h>
int main()
{
 int i;
 int count;
 for(i=21;i>0;i++)
  {  count = 0;
  for( int j=2;j<21;j++)
 {
  if (i%j!=0)
  break;
  count++;
  } 
  if (count==19)
  break;
   }

 printf("%d\n",i);
 return 0;
   }
于 2013-03-09T19:40:03.083 に答える