プロジェクトオイラー 問題1
問題はこちら↓
※アルゴリズムの段階でとても簡略化していることが多々あるので、なるべく丁寧に書きますが、おかしいところがあったら教えていただけると嬉しいです!
<アルゴリズム>
(愚直な方法)
1から999まで1ずつ上げながら、その数字が3もしくは5で割り切れるものを
見つけて和を表す変数sumに足していく。(1~999までの数字を1つずつ見ているので愚直)
(もう少し工夫する方法)
1~999の数字のうち、3の倍数のものと、5の倍数のものを和を表す変数sumに足していく。3と5の倍数である15の倍数の数は、2回足されているので、sumから引いていく。
(愚直な方法)
<ソースコード>
#include <stdio.h> #include <time.h> int main(void){ int sum = 0;//求める和を入れる変数 clock_t start_clock, end_clock; start_clock = clock(); // 計測開始 for(int i = 1; i < 1000; i++){ if(i % 3 == 0 || i % 5 == 0) sum += i; } end_clock = clock(); // 計測終了 printf("求める和は%dです。\n", sum); printf("経過時間は%f秒\n", (double)(end_clock - start_clock) / CLOCKS_PER_SEC); return 0; }
<実行結果>
求める和は233168です。
経過時間は0.000000秒
(工夫した方法)
<ソースコード>
#include <stdio.h> #include <time.h> int main(void){ int sum = 0;//求める和を入れる変数 clock_t start_clock, end_clock; start_clock = clock(); // 計測開始 for(int i = 1; 3 * i < 1000; i++){ sum += 3 * i; } for(int i = 1; 5 * i < 1000; i++){ sum += 5 * i; } for(int i = 1; 15 * i < 1000; i++){ sum -= 15 * i; } end_clock = clock(); // 計測終了 printf("求める和は%dです。\n", sum); printf("経過時間は%f秒\n", (double)(end_clock - start_clock) / CLOCKS_PER_SEC); return 0; }
<実行結果>
求める和は233168です。
経過時間は0.000000秒
計測時間が小さいので、計測部分を10000回などの大きな回数ループさせ、そのループ回数で割ることで、1ループあたりの計測時間が計測できるが、今回は特に大きな差が見られないことがわかるし、比較回数は工夫した方が少ないこともわかると思うので省略します。