21次方

admin 管理员组

文章数量: 1086866

21次方

原文地址：

一道算法题

文章分类:Java编程

经楼下朋友提醒，我这个算法求出的正好是21位水仙花数。于是我对其进行了稍微的修订，使得其支持任意位数的水仙花数求值，效果还不错，理论上的水仙花最大数为34位(我算了下，至少到39位还有解)，我的求解花了半分多钟，而21位数的求解只化了2秒多。

 

[原题]

        

写道

一个21位的整数,它的各个位数的21次方的和加起来等于它本身. 要求:程序在三分钟内完成,Java语言实现.

 

[解决思路]

        这个我最初的思路也是想找出其中是否有数学规律，无奈大学数学就混过来的，只能穷举解决了。

        虽然是穷举，但是不同的实现，效果也不一样，如果要从100000000000000000000穷举到999999999999999999999，我想肯定麻烦大了。

        这里我主要是换个思路，穷举这个数中的每个位置上的数字的总数。从一开始，我们假设共有该数中存在9个9，我们将这个数的信息存到几个特定的数组中去：

Java代码  

1.  private int[] countArray = new int[10]; // 个数列表  

2.  private int[] countSumArray = new int[10]; // 个数总数  

3.  private BigInteger[] sumArray = new BigInteger[10];// 值总数  

4.  private int offset = 0;// 浮标  

        countArray记录依次从9到0每个数的个数，countSumArray是countArray中的各个数与其之前所有数的个数的总和(即countSumArray[n]=countSumArray[n-1]+countNum)，sumArray是当前数的总值(即sumArray[n]=sumArray[n-1]+num)。offset是浮标，即当前判定的数的位置       

        我们对该个数进行判断，9个9后面还有12位数，那么9个9最小就是9个9的平方+12个0的平方，最大是9个9的平方+12个8的平方。我们从以下三个方面来判断：

        1. 最小值不大于999999999999999999999

        2. 最大值不小于100000000000000000000

        3. 最大值与最小值从首部是否相同的部分，如777700000000000000000与777799999999999999999，存在7777相同的部分，如果该相同的部分中有某个数的个数大于offset中相同的值的个数，那么该值也判定为失败

        还有一个很重要的判断就是，如果countSumArray中对应的offset中的值为21，那么即所有的位数都有值，那么直接判定如果该值=其各个位置上的数的21次方之和，如果不等返回失败，反之，这个数就是要求的数。

 

        总体判断如上所述，如果失败我们即查询下一个数next()，countSumArray[offset]=21，那么就是查到头了，就返回查找back()。

        用到了几个技巧，就是将BigInteger的运算结果直接存储到hashtable中去，可以节约大量运算时间。题中给予了4分钟的时间，以为很需要一段时间，就设置了多线程，后来发现，不使用多线程也只要花费2秒种，多线程的意义也就不复存在了。

 

        应楼下朋友要求，贴图描述解题思路，很少画图，更没用Dia画过图，有粗制滥造之嫌，请勿怪了。。。

 

[代码实现]

Java代码  

1.  import java.math.BigInteger;  

2.  import java.util.Hashtable;  

3.    

4.  public class Main {  

5.    

6.      private static final int SIZE = 21;  

7.      private int[] countArray = new int[10]; // 个数列表  

8.      private int[] countSumArray = new int[10]; // 个数总数  

9.      private BigInteger[] sumArray = new BigInteger[10];// 值总数  

10.     private int offset = 0;// 浮标  

11.   

12.     /** 

13.      * 设置当前浮标对应的个数，个数的总数，值总数 

14.      * 

15.      * @param num 

16.      *            个数 

17.      */  

18.     private void setValue(int num) {  

19.         countArray[offset] = num;  

20.         if (offset == 0) {  

21.             countSumArray[offset] = num;  

22.             sumArray[offset] = p(9 - offset).multiply(n(num));  

23.         } else {  

24.             countSumArray[offset] = countSumArray[offset - 1] + num;  

25.             sumArray[offset] = sumArray[offset - 1].add(p(9 - offset).multiply(n(num)));  

26.         }  

27.     }  

28.   

29.     /** 

30.      * 检验当前数据是否匹配 

31.      * 

32.      * @return 

33.      */  

34.     private boolean checkPersentArray() {  

35.         BigInteger minVal = sumArray[offset];// 当前已存在值  

36.         BigInteger maxVal = sumArray[offset].add(p(9 - offset).multiply(n(SIZE - countSumArray[offset])));// 当前已存在值+可能存在的最大值  

37.         // 最小值匹配  

38.         if (minVal.compareTo(MAX) > 0) {  

39.             return false;  

40.         }  

41.         // 最大值匹配  

42.         if (maxVal.compareTo(MIN) < 0) {  

43.             return false;  

44.         }  

45.         String minStr = minVal.compareTo(MIN) > 0 ? minVal.toString() : MIN.toString();  

46.         String maxStr = maxVal.compareTo(MAX) < 0 ? maxVal.toString() : MAX.toString();  

47.         // 找到最小值与最大值间首部相同的部分  

48.         int[] sameCountArray = new int[10];  

49.         for (int i = 0; i < SIZE; i++) {  

50.             char c;  

51.             if ((c = minStr.charAt(i)) == maxStr.charAt(i)) {  

52.                 sameCountArray[c - '0'] = sameCountArray[c - '0'] + 1;  

53.             } else {  

54.                 break;  

55.             }  

56.         }  

57.         // 判断如果相同部分有数据大于现在已记录的位数，返回false  

58.         for (int i = 0; i <= offset; i++) {  

59.             if (countArray[i] < sameCountArray[9 - i]) {  

60.                 return false;  

61.             }  

62.         }  

63.         // 如果当前值的总数为SIZE位，那么判断该值是不是需要查找的值  

64.         if (countSumArray[offset] == SIZE) {  

65.             String sumStr = sumArray[offset].toString();  

66.             BigInteger sum = ZERO;  

67.             for (int i = 0; i < sumStr.length(); i++) {  

68.                 sum = sum.add(p(sumStr.charAt(i) - '0'));  

69.             }  

70.             return sum.compareTo(sumArray[offset]) == 0;  

71.         }  

72.         return true;  

73.     }  

74.   

75.     /** 

76.      * 退出循环，打印 

77.      * 

78.      * @return 

79.      */  

80.     private void success() {  

81.         System.out.println("find a match number:" + sumArray[offset]);  

82.     }  

83.   

84.     /** 

85.      * 将浮标指向下一位数 

86.      * 

87.      * @return 

88.      */  

89.     private void next() {  

90.         offset++;  

91.         setValue(SIZE - countSumArray[offset - 1]);  

92.     }  

93.   

94.     /** 

95.      * 

96.      * 回退浮标，找到最近的浮标，并减一 

97.      * 

98.      * @return 

99.      */  

100.     private boolean back() {  

101.         // 回退浮标，找到最近的浮标，并减一  

102.         if (countArray[offset] == 0) {  

103.             while (countArray[offset] == 0) {  

104.                 if (offset > 0) {  

105.                     offset--;  

106.                 } else {  

107.                     return true;  

108.                 }  

109.             }  

110.         }  

111.         if (offset > 0) {  

112.             setValue(countArray[offset] - 1);  

113.             return false;  

114.         } else {  

115.             return true;  

116.         }  

117.     }  

118.   

119.     /** 

120.      * 测试程序 

121.      * 

122.      * @param startValue 

123.      *            测试匹配数中包含9的个数 

124.      * @param startTime 

125.      *            程序启动时间 

126.      */  

127.     private void test(int startValue, long startTime) {  

128.         // 设置9的个数  

129.         offset = 0;  

130.         setValue(startValue);  

131.         while (true) {  

132.             if (checkPersentArray()) {// 检查当前提交数据是否匹配  

133.                 // 匹配且总数正好为SIZE的位数，那么就是求解的值  

134.                 if (countSumArray[offset] == SIZE) {  

135.                     success();  

136.                 }  

137.                 // 总数不为SIZE，且当前值不在第10位（即不等于0）  

138.                 if (offset != 9) {  

139.                     next();  

140.                     continue;  

141.                 }  

142.                 // 总数不为SIZE，且当前值在第10位。  

143.                 if (back()) {  

144.                     break;  

145.                 }  

146.             } else {  

147.                 if (back()) {  

148.                     break;  

149.                 }  

150.             }  

151.         }  

152.   

153.         System.out.println(Thread.currentThread() + " End,Spend time " + (System.currentTimeMillis() - startTime) / 1000 + "s");  

154.     }  

155.   

156.     /** 

157.      * 主函数 

158.      */  

159.     public static void main(String[] args) {  

160.         final long startTime = System.currentTimeMillis();   

161.             int s = MAX.divide(p(9)).intValue();  

162.             for (int i = 0; i <= s; i++) {  

163. //            new Main().test(i, startTime);  

164.             // 启动十个线程同时运算  

165.             final int startValue = i;  

166.             new Thread(new Runnable() {  

167.   

168.                 public void run() {  

169.                     new Main().test(startValue, startTime);  

170.                 }  

171.             }).start();  

172.         }  

173.     }  

174.     private static final BigInteger ZERO = new BigInteger("0");  

175.     private static final BigInteger MIN;  

176.     private static final BigInteger MAX;  

177.   

178.     /** 

179.      * 0-SIZE间的BigInteger 

180.      */  

181.     private static final BigInteger n(int i) {  

182.         return (BigInteger) ht.get("n_" + i);  

183.     }  

184.   

185.     /** 

186.      * 0-9的次方的BigInteger 

187.      */  

188.     private static final BigInteger p(int i) {  

189.         return (BigInteger) ht.get("p_" + i);  

190.     }  

191.     /** 

192.      * 用于缓存BigInteger数据，并初始化0-SIZE间的BigInteger和0-9的次方的BigInteger 

193.      */  

194.     private static Hashtable<String, Object> ht = new Hashtable<String, Object>();  

195.   

196.     static {  

197.         int s = SIZE < 10 ? 10 : SIZE;  

198.         for (int i = 0; i <= s; i++) {  

199.             ht.put("n_" + i, new BigInteger(String.valueOf(i)));  

200.         }  

201.         for (int i = 0; i <= 10; i++) {  

202.             ht.put("p_" + i, new BigInteger(String.valueOf(i)).pow(SIZE));  

203.         }  

204.         MIN = n(10).pow(SIZE - 1);  

205.         MAX = n(10).pow(SIZE).subtract(n(1));  

206.     }  

207. }   

 

[结论]

        运算结果如下：

Console代码  

1.  Thread[Thread-0,5,main] End,Spend time 0s  

2.  Thread[Thread-9,5,main] End,Spend time 0s  

3.  Thread[Thread-5,5,main] End,Spend time 0s  

4.  Thread[Thread-8,5,main] End,Spend time 0s  

5.  find a match number:449177399146038697307  

6.  Thread[Thread-4,5,main] End,Spend time 1s  

7.  Thread[Thread-7,5,main] End,Spend time 1s  

8.  Thread[Thread-6,5,main] End,Spend time 1s  

9.  Thread[Thread-3,5,main] End,Spend time 2s  

10. find a match number:128468643043731391252  

11. Thread[Thread-2,5,main] End,Spend time 3s  

12. Thread[Thread-1,5,main] End,Spend time 3s  

 

本文标签： 21次方