前言
本文主要给大家介绍了关于利用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
