teratail
回答率
85.48%
質問するログイン新規登録
トップJavaに関する質問2つのn桁の数字の積から作られる最大の回文数を求めたい

編集履歴

回答編集履歴

2

間違いの修正

2018/08/12 12:56

投稿

opyon
opyon

スコア1009

test CHANGED
@@ -2,14 +2,14 @@
2
2
 
3
3
  ---
4
4
 
5
- - 下一桁9,3,1のみ大きいものから配列に格納する
6
-
7
5
  - ループ範囲の桁を半分にする
8
6
 
9
7
  　　変更前：999999>>>900000　
10
8
 
11
9
  　　変更後：999999>>>999000　
12
10
 
11
+ - 1つ目の発見が最大数と仮定し、そこで処理中断することで大幅に改善
12
+
13
13
 
14
14
 
15
15
  ---
@@ -18,9 +18,53 @@
18
18
 
19
19
  ---
20
20
 
21
+ 最終結果 91 * 99 = 9009
22
+
23
+ 2桁 1ms
24
+
25
+
26
+
27
+ 最終結果 913 * 993 = 906609
28
+
29
+ 3桁 0ms
30
+
31
+
32
+
33
+ 最終結果 9901 * 9999 = 99000099
34
+
35
+ 4桁 1ms
36
+
37
+
38
+
39
+ 最終結果 99681 * 99979 = 9966006699
40
+
41
+ 5桁 1ms
42
+
43
+
44
+
45
+ 最終結果 999001 * 999999 = 999000000999
46
+
47
+ 6桁 6ms
48
+
49
+
50
+
51
+ 最終結果 9997647 * 9998017 = 99956644665999
52
+
53
+ 7桁 66ms
54
+
55
+
56
+
57
+ 最終結果 99990001 * 99999999 = 9999000000009999
58
+
21
- 8桁までは約1秒
59
+ 8桁 249ms
60
+
61
+
62
+
22
-
63
+ 最終結果 999920317 * 999980347 = 999900665566009999
64
+
23
- 9桁で約100秒
65
+ 9桁 20197ms
66
+
67
+
24
68
 
25
69
 
26
70
 
@@ -40,7 +84,7 @@
40
84
 
41
85
  ```java
42
86
 
43
- for (int i = 9; i <= 9; i++) {
87
+ for (int i = 2; i <= 9; i++) {
44
88
 
45
89
 
46
90
 
@@ -50,30 +94,6 @@
50
94
 
51
95
  func((long) i);
52
96
 
53
-
54
-
55
- // func((long)2);//0ms
56
-
57
- // func((long)3);//1ms
58
-
59
- // func((long)4);//1ms
60
-
61
- // func((long)5);//23ms
62
-
63
- // func((long)6);//18ms
64
-
65
- // func((long)7);//1,058ms
66
-
67
- // func((long)8);//994ms
68
-
69
- // func((long)9);//101,748ms
70
-
71
-
72
-
73
- //最終経過 999920317 * 999980347 = 999900665566009999
74
-
75
- //9桁 101748ms
76
-
77
97
 
78
98
 
79
99
  long end = System.currentTimeMillis();
@@ -90,6 +110,8 @@
90
110
 
91
111
  ```java
92
112
 
113
+
114
+
93
115
  static void func(long num) {
94
116
 
95
117
 
@@ -104,9 +126,9 @@
104
126
 
105
127
  //ループ範囲最大数：3桁例：999999
106
128
 
107
- final long startMax = (long) Math.pow(10, num) - 1;
129
+ final long iMax = (long) Math.pow(10, num) - 1;
108
-
109
-
130
+
131
+
110
132
 
111
133
  //ループ範囲最小数：3桁例：999000
112
134
 
@@ -114,129 +136,67 @@
114
136
 
115
137
  //※暫定的に半分にしてみる
116
138
 
117
- final long iMin = startMax - (long) Math.pow(10, num - num / 2) + 1;
118
-
119
-
120
-
121
- //下一桁9,1,3のみ回文数を作成
122
-
123
- //※開始から発見が近いことがほとんどなので
124
-
125
- //※暫定的に51個としておく
126
-
127
- //※（桁が増えると正確では無いかも）
128
-
129
- long[] iMax = new long[51];
130
-
131
-
132
-
133
- int tmp = 0;
134
-
135
- for (int i = 0; i < iMax.length; i=i+3) {
136
-
137
- iMax[i] = startMax - tmp * 10;
138
-
139
- iMax[i + 1] = startMax - tmp * 10 - 6;
140
-
141
- iMax[i + 2] = startMax - tmp * 10 - 8;
142
-
143
- tmp++;
144
-
145
- }
146
-
147
-
148
-
149
- for (int n = 0; n < iMax.length; n++) {
150
-
151
-
152
-
153
- for (long i = iMax[n]; i >= iMin; i--) {
154
-
155
-
156
-
157
- //回文数範囲：999999>>>900009
158
-
159
-
160
-
161
- //2 99 93 91
162
-
163
- //3 90
164
-
165
-
166
-
167
- //3 999 993 991 989 983 981
168
-
169
- //30 909 903 901
170
-
171
-
172
-
173
- //4 9999 9993 9991 9989 9983 9981
174
-
175
- //30 9909 9903 9901
176
-
177
- //300 9009 9003 9001 9009 9003 9001
178
-
179
-
180
-
181
- //※全件対象の最大まで配列を確保すると配列数が10倍づつ増えるので
182
-
183
- //※暫定的に100個としておく
184
-
185
-
186
-
187
- //回文数生成
188
-
189
- final long pd = getPalindrome(i);
190
-
191
-
192
-
193
- //3桁の整数B：ループ範囲：i>>>最小値√回分数
194
-
195
- long jMax = iMax[n];
196
-
197
- long jMin = (long) Math.sqrt(pd);
198
-
199
-
200
-
201
- for (long j = jMax; j >= jMin; j--) {
202
-
203
-
204
-
205
- //整数で割り切れ且つ3桁の整数
206
-
207
- if (pd % j == 0 && pd / j < j) {
208
-
209
-
210
-
211
- //暫定最大数として更新
212
-
213
- if (maxS < pd) {
214
-
215
-
216
-
217
- maxA = (int) (pd / j);
218
-
219
- maxB = (int) j;
220
-
221
- maxS = pd;
222
-
223
- break;
224
-
225
- }
139
+
140
+
141
+ final long iMin = iMax - (long) Math.pow(10, num - (num * 50 / 100)) + 1;
142
+
143
+
144
+
145
+ for (long i = iMax; i >= iMin; i--) {
146
+
147
+
148
+
149
+ //回文数生成
150
+
151
+ final long pd = getPalindrome(i);
152
+
153
+
154
+
155
+ //3桁の整数B：ループ範囲：i>>>最小値√回分数
156
+
157
+ long jMax = iMax;
158
+
159
+ long jMin = (long) Math.sqrt(pd);
160
+
161
+
162
+
163
+ for (long j = jMax; j >= jMin; j--) {
164
+
165
+
166
+
167
+ //整数で割り切れ且つ3桁の整数
168
+
169
+ if (pd % j == 0 && pd / j < j) {
170
+
171
+
172
+
173
+ //最初の発見が最大数と仮定する
174
+
175
+ if (maxS < pd) {
176
+
177
+
178
+
179
+ maxA = (int) (pd / j);
180
+
181
+ maxB = (int) j;
182
+
183
+ maxS = pd;
184
+
185
+ System.out.println("最終結果 " + maxA + " * " + maxB + " = " + maxS);
186
+
187
+
188
+
189
+ //発見と同時に処理中断で大幅に改善
190
+
191
+ return;
226
192
 
227
193
  }
228
194
 
195
+ }
196
+
229
- } //j
197
+ } //j
230
-
198
+
231
- } //i
199
+ } //i
232
-
233
- } //n
234
-
235
-
236
-
237
- System.out.println("最終経過 " + maxA + " * " + maxB + " = " + maxS);
238
-
239
-
240
200
 
241
201
  }
242
202
 
@@ -256,8 +216,6 @@
256
216
 
257
217
  }
258
218
 
259
- }
260
-
261
219
 
262
220
 
263
221
  ```

1

間違いがあったので修正

2018/08/12 12:56

投稿

opyon
opyon

スコア1009

test CHANGED
@@ -122,21 +122,25 @@
122
122
 
123
123
  //※開始から発見が近いことがほとんどなので
124
124
 
125
- //※暫定的に100個としておく
125
+ //※暫定的に51個としておく
126
126
 
127
127
  //※（桁が増えると正確では無いかも）
128
128
 
129
- long[] iMax = new long[100];
129
+ long[] iMax = new long[51];
130
+
131
+
132
+
130
-
133
+ int tmp = 0;
131
-
132
-
134
+
133
- for (int i = 0; i < 3; i++) {
135
+ for (int i = 0; i < iMax.length; i=i+3) {
134
-
136
+
135
- iMax[i] = startMax - i * 10;
137
+ iMax[i] = startMax - tmp * 10;
136
-
138
+
137
- iMax[i + 1] = startMax - i * 10 - 6;
139
+ iMax[i + 1] = startMax - tmp * 10 - 6;
138
-
140
+
139
- iMax[i + 2] = startMax - i * 10 - 8;
141
+ iMax[i + 2] = startMax - tmp * 10 - 8;
142
+
143
+ tmp++;
140
144
 
141
145
  }
142
146