前言
本文主要給大家介紹了關于利用Java快速查找21位花朵數的相關內容，分享出來供大家參考學習，下面話不多說了，來一起看看詳細的介紹吧。
以前備賽的時候遇到的算法題，求所有21位花朵數，分享一下，供大家參考，效率已經很高了。
示例代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
|
package com.jianggujin;import java.math.BigInteger;import java.util.ArrayList;import java.util.List;/** * 水仙花數 * * @author jianggujin * */public class NarcissusNumber{ /** * 記錄10的0~N次方 */ private BigInteger[] powerOf10; /** * 記錄0到9中任意數字i的N次方乘以i出現的次數j的結果（i^N*j） */ private BigInteger[][] preTable1; /** * 記錄離PreTable中對應數最近的10的k次方 */ private int[][] preTable2; /** * 記錄0到9中每個數出現的次數 */ private int[] selected = new int[10]; /** * 記錄水仙花數的位數 */ private int length; /** * 記錄水仙花數 */ private List<BigInteger> results; /** * 記錄當前的進制 */ private int numberSystem = 10; /** * @param n * 水仙花數的位數 */ private NarcissusNumber(int n) { powerOf10 = new BigInteger[n + 1]; powerOf10[0] = BigInteger.ONE; length = n; results = new ArrayList<BigInteger>(); // 初始化powerPowerOf10 for (int i = 1; i <= n; i++) { powerOf10[i] = powerOf10[i - 1].multiply(BigInteger.TEN); } preTable1 = new BigInteger[numberSystem][n + 1]; preTable2 = new int[numberSystem][n + 1]; // preTable[i][j] 0-i的N次方出現0-j次的值 for (int i = 0; i < numberSystem; i++) { for (int j = 0; j <= n; j++) { preTable1[i][j] = new BigInteger(new Integer(i).toString()).pow(n) .multiply(new BigInteger(new Integer(j).toString())); for (int k = n; k >= 0; k--) { if (powerOf10[k].compareTo(preTable1[i][j]) < 0) { preTable2[i][j] = k; break; } } } } } public static List<BigInteger> search(int num) { NarcissusNumber narcissusNumber = new NarcissusNumber(num); narcissusNumber.search(narcissusNumber.numberSystem - 1, BigInteger.ZERO, narcissusNumber.length); return narcissusNumber.getResults(); } /** * @param currentIndex * 記錄當前正在選擇的數字(0~9) * @param sum * 記錄當前值（如選了3個9、2個8 就是9^N*3+8^N*2） * @param remainCount * 記錄還可選擇多少數 */ private void search(int currentIndex, BigInteger sum, int remainCount) { if (sum.compareTo(powerOf10[length]) >= 0) { return; } if (remainCount == 0) { // 沒數可選時 if (sum.compareTo(powerOf10[length - 1]) > 0 && check(sum)) { results.add(sum); } return; } if (!preCheck(currentIndex, sum, remainCount)) { return; } if (sum.add(preTable1[currentIndex][remainCount]).compareTo(powerOf10[length - 1]) < 0)// 見結束條件2 { return; } if (currentIndex == 0) { // 選到0這個數時的處理 selected[0] = remainCount; search(-1, sum, 0); } else { for (int i = 0; i <= remainCount; i++) { // 窮舉所選數可能出現的情況 selected[currentIndex] = i; search(currentIndex - 1, sum.add(preTable1[currentIndex][i]), remainCount - i); } } // 到這里說明所選數currentIndex的所有情況都遍歷了 selected[currentIndex] = 0; } /** * @param currentIndex * 記錄當前正在選擇的數字(0~9) * @param sum * 記錄當前值（如選了3個9、2個8 就是9^N*3+8^N*2） * @param remainCount * 記錄還可選擇多少數 * @return 如果當前值符合條件返回true */ private boolean preCheck(int currentIndex, BigInteger sum, int remainCount) { if (sum.compareTo(preTable1[currentIndex][remainCount]) < 0)// 判斷當前值是否小于PreTable中對應元素的值 { return true;// 說明還有很多數沒選 } BigInteger max = sum.add(preTable1[currentIndex][remainCount]);// 當前情況的最大值 max = max.divide(powerOf10[preTable2[currentIndex][remainCount]]);// 取前面一部分比較 sum = sum.divide(powerOf10[preTable2[currentIndex][remainCount]]); while (!max.equals(sum)) { // 檢驗sum和max首部是否有相同的部分 max = max.divide(BigInteger.TEN); sum = sum.divide(BigInteger.TEN); } if (max.equals(BigInteger.ZERO))// 無相同部分 { return true; } int[] counter = getCounter(max); for (int i = 9; i > currentIndex; i--) { if (counter[i] > selected[i])// 見結束條件3 { return false; } } for (int i = 0; i <= currentIndex; i++) { remainCount -= counter[i]; } return remainCount >= 0;// 見結束條件4 } /** * 檢查sum是否是花朵數 * * @param sum * 記錄當前值（如選了3個9、2個8 就是9^N*3+8^N*2） * @return 如果sum存在于所選集合中返回true */ private boolean check(BigInteger sum) { int[] counter = getCounter(sum); for (int i = 0; i < numberSystem; i++) { if (selected[i] != counter[i]) { return false; } } return true; } /** * @param value * 需要檢驗的數 * @return 返回value中0到9出現的次數的集合 */ private int[] getCounter(BigInteger value) { int[] counter = new int[numberSystem]; char[] sumChar = value.toString().toCharArray(); for (int i = 0; i < sumChar.length; i++) { counter[sumChar[i] - '0']++; } return counter; } /** * 獲得結果 * * @return */ public List<BigInteger> getResults() { return results; } public static void main(String[] args) { int num = 21; System.err.println("正在求解" + num + "位花朵數"); long time = System.nanoTime(); List<BigInteger> results = NarcissusNumber.search(num); time = System.nanoTime() - time; System.err.println("求解時間:\t" + time / 1000000000.0 + "s"); System.err.println("求解結果:\t" + results); }} |
運行查看結果：
正在求解21位花朵數
求解時間: 0.327537257s
求解結果: [128468643043731391252, 449177399146038697307]
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對服務器之家的支持。
原文鏈接：http://blog.csdn.net/jianggujin/article/details/53544720
