`
蔡华江
  • 浏览: 107642 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

一道算法题

    博客分类：
  • JAVA
算法thread百度多线程IDEA 
阅读更多

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

 

[原题]

        http://www.iteye.com/problems/50018

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

 

[解决思路]

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

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

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

	private int[] countArray = new int[10]; // 个数列表
	private int[] countSumArray = new int[10]; // 个数总数
	private BigInteger[] sumArray = new BigInteger[10];// 值总数
	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画过图，有粗制滥造之嫌，请勿怪了。。。

 

[代码实现] 

import java.math.BigInteger;
import java.util.Hashtable;

public class Main {

    private static final int SIZE = 21;
    private int[] countArray = new int[10]; // 个数列表
    private int[] countSumArray = new int[10]; // 个数总数
    private BigInteger[] sumArray = new BigInteger[10];// 值总数
    private int offset = 0;// 浮标

    /**
     * 设置当前浮标对应的个数，个数的总数，值总数
     *
     * @param num
     *            个数
     */
    private void setValue(int num) {
        countArray[offset] = num;
        if (offset == 0) {
            countSumArray[offset] = num;
            sumArray[offset] = p(9 - offset).multiply(n(num));
        } else {
            countSumArray[offset] = countSumArray[offset - 1] + num;
            sumArray[offset] = sumArray[offset - 1].add(p(9 - offset).multiply(n(num)));
        }
    }

    /**
     * 检验当前数据是否匹配
     *
     * @return
     */
    private boolean checkPersentArray() {
        BigInteger minVal = sumArray[offset];// 当前已存在值
        BigInteger maxVal = sumArray[offset].add(p(9 - offset).multiply(n(SIZE - countSumArray[offset])));// 当前已存在值+可能存在的最大值
        // 最小值匹配
        if (minVal.compareTo(MAX) > 0) {
            return false;
        }
        // 最大值匹配
        if (maxVal.compareTo(MIN) < 0) {
            return false;
        }
        String minStr = minVal.compareTo(MIN) > 0 ? minVal.toString() : MIN.toString();
        String maxStr = maxVal.compareTo(MAX) < 0 ? maxVal.toString() : MAX.toString();
        // 找到最小值与最大值间首部相同的部分
        int[] sameCountArray = new int[10];
        for (int i = 0; i < SIZE; i++) {
            char c;
            if ((c = minStr.charAt(i)) == maxStr.charAt(i)) {
                sameCountArray[c - '0'] = sameCountArray[c - '0'] + 1;
            } else {
                break;
            }
        }
        // 判断如果相同部分有数据大于现在已记录的位数，返回false
        for (int i = 0; i <= offset; i++) {
            if (countArray[i] < sameCountArray[9 - i]) {
                return false;
            }
        }
        // 如果当前值的总数为SIZE位，那么判断该值是不是需要查找的值
        if (countSumArray[offset] == SIZE) {
            String sumStr = sumArray[offset].toString();
            BigInteger sum = ZERO;
            for (int i = 0; i < sumStr.length(); i++) {
                sum = sum.add(p(sumStr.charAt(i) - '0'));
            }
            return sum.compareTo(sumArray[offset]) == 0;
        }
        return true;
    }

    /**
     * 退出循环，打印
     *
     * @return
     */
    private void success() {
        System.out.println("find a match number:" + sumArray[offset]);
    }

    /**
     * 将浮标指向下一位数
     *
     * @return
     */
    private void next() {
        offset++;
        setValue(SIZE - countSumArray[offset - 1]);
    }

    /**
     *
     * 回退浮标，找到最近的浮标，并减一
     *
     * @return
     */
    private boolean back() {
        // 回退浮标，找到最近的浮标，并减一
        if (countArray[offset] == 0) {
            while (countArray[offset] == 0) {
                if (offset > 0) {
                    offset--;
                } else {
                    return true;
                }
            }
        }
        if (offset > 0) {
            setValue(countArray[offset] - 1);
            return false;
        } else {
            return true;
        }
    }

    /**
     * 测试程序
     *
     * @param startValue
     *            测试匹配数中包含9的个数
     * @param startTime
     *            程序启动时间
     */
    private void test(int startValue, long startTime) {
        // 设置9的个数
        offset = 0;
        setValue(startValue);
        while (true) {
            if (checkPersentArray()) {// 检查当前提交数据是否匹配
                // 匹配且总数正好为SIZE的位数，那么就是求解的值
                if (countSumArray[offset] == SIZE) {
                    success();
                }
                // 总数不为SIZE，且当前值不在第10位（即不等于0）
                if (offset != 9) {
                    next();
                    continue;
                }
                // 总数不为SIZE，且当前值在第10位。
                if (back()) {
                    break;
                }
            } else {
                if (back()) {
                    break;
                }
            }
        }

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

    /**
     * 主函数
     */
    public static void main(String[] args) {
        final long startTime = System.currentTimeMillis(); 
            int s = MAX.divide(p(9)).intValue();
            for (int i = 0; i <= s; i++) {
//            new Main().test(i, startTime);
            // 启动十个线程同时运算
            final int startValue = i;
            new Thread(new Runnable() {

                public void run() {
                    new Main().test(startValue, startTime);
                }
            }).start();
        }
    }
    private static final BigInteger ZERO = new BigInteger("0");
    private static final BigInteger MIN;
    private static final BigInteger MAX;

    /**
     * 0-SIZE间的BigInteger
     */
    private static final BigInteger n(int i) {
        return (BigInteger) ht.get("n_" + i);
    }

    /**
     * 0-9的次方的BigInteger
     */
    private static final BigInteger p(int i) {
        return (BigInteger) ht.get("p_" + i);
    }
    /**
     * 用于缓存BigInteger数据，并初始化0-SIZE间的BigInteger和0-9的次方的BigInteger
     */
    private static Hashtable<String, Object> ht = new Hashtable<String, Object>();

    static {
        int s = SIZE < 10 ? 10 : SIZE;
        for (int i = 0; i <= s; i++) {
            ht.put("n_" + i, new BigInteger(String.valueOf(i)));
        }
        for (int i = 0; i <= 10; i++) {
            ht.put("p_" + i, new BigInteger(String.valueOf(i)).pow(SIZE));
        }
        MIN = n(10).pow(SIZE - 1);
        MAX = n(10).pow(SIZE).subtract(n(1));
    }
} 

 

[结论]

        运算结果如下：

Thread[Thread-0,5,main] End,Spend time 0s
Thread[Thread-9,5,main] End,Spend time 0s
Thread[Thread-5,5,main] End,Spend time 0s
Thread[Thread-8,5,main] End,Spend time 0s
find a match number:449177399146038697307
Thread[Thread-4,5,main] End,Spend time 1s
Thread[Thread-7,5,main] End,Spend time 1s
Thread[Thread-6,5,main] End,Spend time 1s
Thread[Thread-3,5,main] End,Spend time 2s
find a match number:128468643043731391252
Thread[Thread-2,5,main] End,Spend time 3s
Thread[Thread-1,5,main] End,Spend time 3s
分享到：
| 第15届问答大赛获奖感言
评论
41 楼 myfoot 2011-05-01  
看了newZai的描述，有点意思了
40 楼 myfoot 2011-05-01  
不怎么看得懂
39 楼 newzai 2011-04-29  
这个一定要排序，否则时间复杂度很高。包含2道排序。
1. 把每个数的按照每一个位的大小，重新排序，例如 323456 排序后为 654332(必须保存排序之前的原始值。
2. 把整个集合的所有数进行从小到大或者从大到小的排序。
3. 过滤不符合要求的值，也就是N位数的每个位的N次方只和大于N位数的最大值或者小于其最小值的过滤掉，由于之前排序了，因此可以使用二分算法快速的过滤 不符合要求的数。
4.对剩下的数遍历，每个计算并验证。对每个数的计算时，如果前面的M(M < N)位的N次方之和 已经大于本数，则立刻放弃。类似于 布尔运算的短路规则 一样。不同的数，通过第1步排序后的值可能相同。把排序后的数值称为 V，排序之前的值称为R。每个V都有一个R队列，对R队列进行从大到小的排序。计算时，如果前面M位的N次方只和大于R队列的最大值，则可全部跳过。否则知道计算完N个。如果其值小于R队列的最小值，也可以跳过。如果结果值在R队列的最大和最小范围之间，则一一比较是否有相等的。此时只能有一个是与该值相等的，找到一个即可。
38 楼 x1387420 2010-09-20  
因为水仙花数就是每个数的出现次数的21次方之和。


这句话的原意应该是---水仙花数就是0^21*出现次数+1^21*出现次数+。。。。+9^21*出现次数

对吗？你的描述应该更清晰点，按你的描述有点看不懂。
37 楼 蔡华江 2010-09-20  
SongChaoBin 写道
你的代码很强悍...上次你的回答我不很明了，我并没回溯，只是加一个简单的判定条件if（offset==9），然后就可以用8代替9了，这是小事。
我有个基本问题没明白，还请指点！
最基本的就是你是如何遍历完从10的20次方到全9的二十一位数的遍历？...
通过分析，我觉得你是以countArray[0],countArray[1],一直到countArray[9]的和为恒定的Size为条件，逐次改变countArray[0]到countArray[9]的大小，来完成遍历的，但那样遍历的次数依旧很大啊...对于next（）方法不好理解！

我没有遍历每个数，只是遍历每个数的可能出现次数。
因为水仙花数就是每个数的出现次数的21次方之和。
这个数远远小于一个21位数，其大小就是将21个数插入10位的列中的可能次数，
即C（10，21）。
并且，在其中对大量可能性做了过滤处理，很多数还没计算就直接处理掉了。
所以要汇总计算的数据是很少的。

next()方法并不是要找到一个水仙花数，而是说下一个可能成立的数据。这个数不一定有21位，可能只有其中的部分信息，只要成立，就继续判断。
36 楼 SongChaoBin 2010-09-19  
你的代码很强悍...上次你的回答我不很明了，我并没回溯，只是加一个简单的判定条件if（offset==9），然后就可以用8代替9了，这是小事。
我有个基本问题没明白，还请指点！
最基本的就是你是如何遍历完从10的20次方到全9的二十一位数的遍历？...
通过分析，我觉得你是以countArray[0],countArray[1],一直到countArray[9]的和为恒定的Size为条件，逐次改变countArray[0]到countArray[9]的大小，来完成遍历的，但那样遍历的次数依旧很大啊...对于next（）方法不好理解！
35 楼 changedi 2010-09-19  
大于60位的自然数无水仙花数，最大的水仙花数是39位数，见《水仙花数的计算机解法》这一篇paper，此文统计了所有自然数中的88个水仙花数。
感兴趣的可以参看一下这篇论文里用到的算法。
楼主的方法和论文中的有相同之处，但是文章给出了证明过程。
34 楼 sunting_bcwl 2010-09-18  
33 楼 0704681032 2010-09-18  
  楼主真的很牛啊
32 楼 蔡华江 2010-09-17  
offset是一个浮标，表示你当前所判断的是0的个数。
这是一个全局的值。

而minVal与maxVal是局部值，仅用来判断当前的数组是否合法。
脱离了这个函数在进行是否回溯的判定上是没有什么作用的。
31 楼 SongChaoBin 2010-09-17  
但我觉得可以稍微修改下，当offset为9时maxVal=minVal不就行了？
30 楼 蔡华江 2010-09-17  
ocaso1987@gmail.com
29 楼 1927105 2010-09-17  
LZ，
msn多少的加下我：
shipengyan@qq.com
28 楼 蔡华江 2010-09-17  
1927105 写道
我还是不明白，MAX / 9^21 个9的问题，为什么从这个角度考虑啊？

int s = SIZE < 10 ? 10 : SIZE;
for (int i = 0; i <= s; i++)
{
ht.put("n_" + i, new BigInteger(String.valueOf(i)));
}
这段我也不太明白


主要思路我不是很清楚，，郁闷


这一个已经说过了，见20楼
第二个意思就是说，在缓存中存储1-SIZE的BigInteger形式。
n1->BigInteger  1
...
但是最少要存储0-10这几位
27 楼 1927105 2010-09-17  
我还是不明白，MAX / 9^21 个9的问题，为什么从这个角度考虑啊？

int s = SIZE < 10 ? 10 : SIZE;
for (int i = 0; i <= s; i++)
{
ht.put("n_" + i, new BigInteger(String.valueOf(i)));
}
这段我也不太明白


主要思路我不是很清楚，，郁闷
26 楼 蔡华江 2010-09-17  
推荐个贴子
http://www.iteye.com/topic/609049
25 楼 agao1985 2010-09-17  
蔡华江 写道
娘的，是那里看到的说水仙花数最高位为34位，我就发现39位上还有两个解,
40位上没了。
注：百度害死人哟

人家说的是理论上嘛。。。。~支持百度，和谐万岁
24 楼 1927105 2010-09-17  
继续学习中，，，
23 楼 蔡华江 2010-09-17  
SongChaoBin 写道
BigInteger maxVal = sumArray[offset].add(p(9 - offset).multiply(n(SIZE - countSumArray[offset])));// 当前已存在值+可能存在的最大值
我感觉这句不太对啊，sumArray[offset]应该是相应个数的9-offset的21次方的和，那么在此条件下，最大值应该只能是 BigInteger maxVal = sumArray[offset].add(p(8 - offset).multiply(n(SIZE - countSumArray[offset])));
不知对不对？

你是对的!

但是这里放8是不行的,要考虑数据在最后位时,是没有后继值的..
当然放9不会影响到程序结果.
22 楼 SongChaoBin 2010-09-16  
BigInteger maxVal = sumArray[offset].add(p(9 - offset).multiply(n(SIZE - countSumArray[offset])));// 当前已存在值+可能存在的最大值
我感觉这句不太对啊，sumArray[offset]应该是相应个数的9-offset的21次方的和，那么在此条件下，最大值应该只能是 BigInteger maxVal = sumArray[offset].add(p(8 - offset).multiply(n(SIZE - countSumArray[offset])));
不知对不对？
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics