teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

2

バグ修正とコメント添削

2018/08/15 15:26

投稿

opyon
opyon

スコア1009

answer CHANGED
@@ -5,60 +5,87 @@
5
5
  ---
6
6
 
7
7
  ```java
8
- static void func2(int num) {
8
+ public static void main(String[] args) {
9
+ long start = System.currentTimeMillis();
9
10
 
10
- int n = 0; //n //n個目(の三角数)
11
- int n1 = 0; //n+1 //n+1
11
+ func(500);
12
- int t = 0; //triangle //三角数
13
- int d = 0; //divisors //三角数の約数の個数
14
12
 
13
+ long end = System.currentTimeMillis();
14
+ System.out.println((end - start) + "ms");
15
+ }
16
+
17
+ static void func(int num) {
18
+
19
+ int n = 0; //自然数n
20
+ int t = 0; //n番目の三角数(総和)
21
+
22
+ //約数の個数の性質「互いに素なaとbについて、
23
+ //a*bの約数の個数は、aの約数の個数×bの約数の個数に等しい」
24
+ //nとn+1は互いに素なのでnかn+1のどちらかが偶数になる
25
+
26
+ int x = 0; //(偶数奇数で分けて偶数の方を2で割る)
27
+ int y = 0; //(偶数奇数で分けて偶数の方を2で割る)
28
+ int d = 0; //分けて計算した約数の個数を掛けた総数
29
+
15
30
  while (d < num) {
16
31
 
32
+ //自然数n
17
33
  n++;
18
34
 
19
- n1 = n + 1;
35
+ //三角数の公式
36
+ //n(n+1)/2
20
37
 
21
- t = n * n1 / 2; //三角数の公式 n(n+1)/2
38
+ //n 1 2 3 4 5 6 7 8 9 10
39
+ //三角数 1 3 6 10 15 21 28 36 45 55
40
+ //約数  1 2 4 4 4 4 6 9 6 4
22
41
 
23
- //「nとn+1のうち、偶数を2で割ったもの」
24
- // 奇数偶数で分けて計算して掛ける
42
+ //偶数奇数判定
25
43
  if (n % 2 == 0) {
26
- d = getDivisors(n / 2) * getDivisors(n1);
44
+ x = n / 2;
45
+ y = n + 1;
27
46
  } else {
47
+ x = n;
28
- d = getDivisors(n) * getDivisors(n1 / 2);
48
+ y = (n + 1) / 2;
29
49
  }
50
+
51
+ //個別に約数の個数を求め掛け合わせて総数を求める
52
+ d = getD(x) * getD(y);
30
53
  }
31
- System.out.println("n:" + n + " t:" + t + " d:" + d);
32
- System.out.println("Answer:" + t);
33
54
 
55
+ //ログ出力用
56
+ t = n * (n + 1) / 2;
57
+
58
+ System.out.print("last n:" + (n));
59
+ System.out.print(" t:" + t);
60
+ System.out.print(" d:" + d);
61
+ System.out.println();
62
+ System.out.println("Ans:" + t);
34
63
  }
35
64
 
36
- //三角数の約数の個数を求める
65
+ //約数の個数を求める
37
- //範囲は三角数の平方根まで
38
- //三角数が平方数の場合は+1する
39
- static int getDivisors(int triangle) {
66
+ static int getD(final int t) {
40
67
 
41
- int divisors = 0;
68
+ int d = 0;
42
- int rootT = (int) Math.sqrt(triangle);
43
69
 
70
+ final int rootT = (int) Math.sqrt(t);
71
+
44
72
  for (int i = 1; i <= rootT; i++) {
45
- if (triangle % i == 0) {
73
+ if (t % i == 0) {
46
- divisors++;
74
+ d++;
47
75
  }
48
76
  }
49
- divisors = divisors * 2;
50
77
 
78
+ d *= 2;
79
+
51
- if (triangle == rootT * rootT) {
80
+ if (t == rootT * rootT) {
52
- divisors++;
81
+ d--;
53
82
  }
83
+
54
- return divisors;
84
+ return d;
55
85
  }
56
-
57
86
  ```
58
87
  出力結果
59
88
  ---
60
- n:12375 t:76576500 d:576
89
+ last n:12375 t:76576500 d:576
61
- Answer:76576500
90
+ Ans:76576500
62
- 7ms
91
+ 0ms
63
-
64
- (307ms※平方根までの処理を実装前の結果)

1

未実装の修正を追加

2018/08/15 15:25

投稿

opyon
opyon

スコア1009

answer CHANGED
@@ -1,49 +1,64 @@
1
1
  頂いたアドバイスで作り直したところ、かなり改善できました。
2
2
  ありがとうございました。
3
+ ※追加で平方根の処理を実装したところ更に改善できました。
3
4
 
4
5
  ---
5
6
 
6
7
  ```java
7
8
  static void func2(int num) {
8
-
9
+
9
10
  int n = 0; //n //n個目(の三角数)
10
- int n1= 0; //n+1
11
+ int n1 = 0; //n+1 //n+1
11
12
  int t = 0; //triangle //三角数
12
- int d = 0; //divisors //三角数の約数の個数
13
+ int d = 0; //divisors //三角数の約数の個数
13
-
14
- while(d < num) {
15
14
 
15
+ while (d < num) {
16
+
16
17
  n++;
17
18
 
18
- n1 = n+1;
19
+ n1 = n + 1;
19
-
20
+
20
- t = n*n1/2; //三角数の公式 n(n+1)/2
21
+ t = n * n1 / 2; //三角数の公式 n(n+1)/2
21
-
22
+
22
23
  //「nとn+1のうち、偶数を2で割ったもの」
23
24
  // 奇数偶数で分けて計算して掛ける
24
- if(n % 2 == 0) {
25
+ if (n % 2 == 0) {
25
- d = getDivisors(n/2) * getDivisors(n1) ;
26
+ d = getDivisors(n / 2) * getDivisors(n1);
26
27
  } else {
27
- d = getDivisors(n) * getDivisors(n1/2) ;
28
+ d = getDivisors(n) * getDivisors(n1 / 2);
28
29
  }
29
30
  }
30
- System.out.println("n:"+n+" t:"+t+" d:"+d );
31
+ System.out.println("n:" + n + " t:" + t + " d:" + d);
32
+ System.out.println("Answer:" + t);
33
+
31
34
  }
32
-
35
+
33
- //約数の個数を求める
36
+ //三角数の約数の個数を求める
37
+ //範囲は三角数の平方根まで
38
+ //三角数が平方数の場合は+1する
34
39
  static int getDivisors(int triangle) {
35
-
40
+
36
41
  int divisors = 0;
42
+ int rootT = (int) Math.sqrt(triangle);
43
+
37
- for (int i = 1; i <= triangle; i++) {
44
+ for (int i = 1; i <= rootT; i++) {
38
45
  if (triangle % i == 0) {
39
46
  divisors++;
40
47
  }
41
48
  }
49
+ divisors = divisors * 2;
50
+
51
+ if (triangle == rootT * rootT) {
52
+ divisors++;
53
+ }
42
54
  return divisors;
43
55
  }
56
+
44
57
  ```
45
58
  出力結果
46
59
  ---
47
60
  n:12375 t:76576500 d:576
48
61
  Answer:76576500
49
- 307ms
62
+ 7ms
63
+
64
+ (307ms※平方根までの処理を実装前の結果)