日期:2014-05-20 浏览次数:20812 次
import java.math.BigInteger; import java.util.Arrays; public class Flower { private static int num = 21; private static BigInteger[] table = new BigInteger[10]; private static int[] nums; public static void main(String[] args) { long time = System.currentTimeMillis(); for (int i = 0; i < 10; i++) table[i] = BigInteger.valueOf(i).pow(num); nums = new int[num]; find(nums, 0, 0); time = System.currentTimeMillis() - time; System.out.println(time / 1000.0 + "s"); } public static void find(int[] nums, int level, int num) { nums[level] = num; if (level == nums.length - 1) { BigInteger big = sum(nums); int[] temp = getArray(big); if (check(nums, temp)) System.out.println(big); return; } for (int i = num; i < 10; i++) find(nums, level + 1, i); } public static boolean check(int[] a1, int[] a2) { if (a1.length != a2.length) return false; Arrays.sort(Arrays.copyOf(a1, a1.length)); Arrays.sort(a2); return Arrays.equals(a1, a2); } public static BigInteger sum(int[] nums) { BigInteger sum = BigInteger.ZERO; for (int i = 0; i < nums.length; i++) sum = sum.add(table[nums[i]]); return sum; } public static int[] getArray(BigInteger big) { String s = String.valueOf(big); char[] ch = s.toCharArray(); int[] res = new int[ch.length]; for (int i = 0; i < ch.length; i++) res[i] = ch[i] - '0'; return res; } }
------解决方案--------------------
import java.math.BigInteger; import java.util.Arrays; public class Narcissistic { private static BigInteger[] table = new BigInteger[10]; public static void main(String[] args) { long time = System.nanoTime(); find(31); time = System.nanoTime() - time; System.out.println(time / 1000000000.0 + "s"); } public static void find(int n) { for (int i = 0; i < 10; i++) table[i] = BigInteger.valueOf(i).pow(n); int[] nums = new int[n]; int index = 0; int num = 0; BigInteger sum = BigInteger.ZERO; BigInteger MIN = BigInteger.TEN.pow(n - 1); BigInteger MAX = BigInteger.TEN.pow(n).subtract(BigInteger.ONE); while (true) { if (index < nums.length && num < 10) { BigInteger temp = sum.add(table[num]); if (temp.compareTo(MAX) < 0) { nums[index] = num; index++; sum = temp; continue; } } else if (index >= nums.length && sum.compareTo(MIN) > 0) { int[] temp = getArray(sum); if (check(nums, true, temp, false)) System.out.println(sum); } else if (index <= 0) { break; } index--; num = nums[index]; sum = sum.subtract(table[num]); num++; } } public static boolean check(int[] a1, boolean copy1, int[] a2, boolean copy2) { if (a1.length != a2.length) return false; if (copy1) a1 = a1.clone(); if (copy2) a2 = a2.clone(); Arrays.sort(a1); Arrays.sort(a2); return Arrays.equals(a1, a2); } public static int[] getArray(BigInteger big) { String s = String.valueOf(big); int length = s.length(); int[] res = new int[length]; for (int i = 0; i < length; i++) res[i] = s.charAt(i) - '0'; return res; } }