现在的位置: 首页 > 综合 > 正文

幸运数——庞果网

2012年02月10日 ⁄ 综合 ⁄ 共 6332字 ⁄ 字号 评论关闭

原题连接:http://hero.pongo.cn/OnlineCompiler/Index?ID=53&ExamID=51

题目详情

         如果一个数各个数位上的数字之和是质数,并且各个数位上的数字的平方和也是质数,则称它为幸运数。给定x,y,求x,y之间(包含x,y,即闭区间[x , y])有多少个幸运数。例如1到20之间有4个幸运数,它们是11,12,14,16,像因为1+1 = 2是质数,1^2 + 1^2 = 2也是质数等等。

         给定函数原型int luck(intx , int y),其中1<=x<=y<=1000000000,请完成函数,实现上述功能。

答题说明

         可额外编写其它的函数,然后lucky调用你编写的其它函数返回结果值;限时3s,程序运行时间超过3s即挑战失败。

 

         题目的关键在于效率。而提高效率的方法,一般来讲,以内存换效率,或者提高算法本身的性能。开始使用的是增加内存的方式,但是发现速度提高到2秒之后,就再也提高不了了。我认为,算法还不够好,于是从算法上着手,终于可以让程序运行在0.03秒之内(2.3GHz的CPU,惠普台式机,使用C++的结果)。下面说一下我的算法思路。

         这是一道搜索的题目,按照题中给出的数量级,大概要10亿以内,从而,如果按照自然数顺序搜索,想在3秒中获得结果,是非常困难的。为此,我们的搜索空间,绝对不是10亿个数。只要提炼出每个数字能决定幸运数的特征就可以了。

         而决定是否是幸运数的,是数字的每一位上的数。因此,我们只要找出0到9个数字的不同的组合,并求取组合的数量就可以了。

         基本的想法是:从个位数开始,有0到9共10中情况存在,那么,再加一位,两位数,则这十种情况分别增加一位数,共10 * 9种情况(第二位只考虑1到9),而且,这10 * 9种情况里边,必定有重复的(所谓重复,就是指这些情况的各个数位上的数字之和相等,并且各个数位上的数字的平方和也相等),而重复的情况,就可以和在一起继续添加一位。因为这些重复的情况,无论它们第几位数是什么,已经无法影响是否是幸运数。重申一遍,对是否是幸运数构成影响的是:各位数字和和各位数字的平方和。

         再解释一下,为什么第二位数的时候不把0也作为一种可能计算,因为,在计算第一位的时候,已经默认其它的位上全部为0,当然,也包括第二位为0。

         我们继续,第二位计算清楚了(多少种情况我没有具体算过,不过,肯定小于90),我们再添加一位,第三位也有1到9,共9中可能,这样,依次类推,只要我们统计出10位数字的可能情况数,就可以了。以下是我的代码,具体细节也有一定注释。

追加内容:

         有网友问我说幸运数的原理没有看明白,其实,是我没有讲明白。我将思路梳理了一下,打算用下面的方式讲一下我的思路,希望我能把这个题的原理讲明白。

         我的解法的原理其实是分类。

         对于任意一个数x,假设它的各位和为P1,各位的平方和为P2。那么我们反过来想想,各位和是P1并且各位平方和是Q1的数,肯定不止x一个数,把这些数归为一类,或者叫分组,我们把这个类记为L(P1 , Q1)。

         分组的个数:我们要计算的数是1到10亿,第十亿个数肯定不是幸运数,那我们计算的最大数位999999999,共有九位,并且,它的各位和最大,为81,它的各位平方和也最大,为9乘以81,等于729。因此,分组的个数也能估计出来,肯定不大于729乘以81。所以我们会有分类:L(0 , 0),L(0 , 1),L(0 , 2)......L(81 , 729)。而对于每一个数,1,2,3,甚至10000,亦或是999999999,我们都能把它放到一个分组中,并且,每一个数,之能放到一个分组中。但一个分组中,却有若干个数。

         

         数的组成:每一个数,我们随便举个例子,拿1234来看,四位数是第四位数加上一个三位数构成的,那我们怎样把这个位数放到它应该在的类中去呢?其实,完全不需要考虑后边三位数是234还是342抑或是423,因为它们前边加上一个1,放到的是同一个分组。下面我们假设,前三位数都已经分组,也就是说,1位数已经分组,2位数也已经分组,3位数也已经分组。于是,由于234各位和是9,各位平方和是29,属于分组L(9 , 29),我们不管L(9,29)有多少个数,他的前边加上一个1,都要放到同一个分组,即分组L(10
, 30)。于是,分组L(10 , 30)(这个分组是前四位数组成的分组)的个数,需要加上L(9 , 29)(这个分组是前三位数组成的分组)。

         算法的流程:首先,我们需要计算一位数的分组,我们建立分组的队列,它们分别是L(0 , 0),L(1 , 1),L(2 , 4),L(3 , 9)...L(9 , 81)。每个队列的数量都是1。一位数就10个,这里包括0,因为,计算两位数的时候需要用到。其次,计算第二位,我们重新建立一个队列,这个队列里边保留有上一个队列的所有的分组。下面,我们需要加一位数,这位数只能从1开始,这是问题的关键。为什么只能从1呢?因为如果第二位数是0,那好,我们从第一位的分组中随便拿出一个分组来,比如还是1吧,那好了,看看我们新组成的数是多少,是01,这个数好熟悉吧,在数学中,它就是1,那么,我们有没有把这个数放到我们的分组中去呢?肯定已经放进去了。因为,这里保留了上一个队列的所有分组。于是,我觉得问题的关键可以这样解释:举个例子:如果你计算第四位的时候,你吧第四位置为0,那么,你这个四位数就是0×××,好吧,这个数在数学上,它就是×××,而所有的三位数,我们已经算过了啊,不能再计算一遍了。如果你想说,我的第三位也是0,那这个数是00××,显然,这是个两位数。我们同样算过了。我们再换个数,比如是10000×××,我们的第八位数是1,那么,这个数一定是在计算第八位的时候加上去的。我们去掉1,那么,剩下的是0000×××,这个数是个三位数,我们在计算三位数的时候加上去的,并且,在计算第八位的时候保留了下来。

         关键的问题解释了,希望我这段话能说明白问题。下面,计算三位数,依然保留之前的分组队列。三位数就是用之前的一位数(10+×构成三位数),或者两位数(1+××构成三位数)。将一位数两位数的队列再通过跟1到9组合,就形成了三位数的队列。以此类推,我们可以一直计算到9位数。

         于是,我们可以计算所有的一位数,进而可以计算所有的一位数+所有的两位数,进而可以计算所有的一位数+所有的两位数+所有的三位数,依次类推。更精确的表达是我们依次可以计算所有不大于9的数,进而可以计算所有不大于99的数,进而可以计算所有不大于999的数,等等。

         下面,我们计算区间[1 , x]之间的幸运数(莫急,一步一步来)。其实,区间[1 , x]之间的幸运数跟区间[0 , x]之间的幸运数一样多,因为0不是幸运数。好吧,我们可以计算[0 , x]之间的幸运数。这里依然要用一个技巧。直接举个例子,总觉得用实例说话,比较方便。比如,我们让x=987654321,计算区间[0 , 987654321],我们把区间划分一下吧[0 , 987654321] = [0 , 899999999]
+ [900000000 , 979999999] + [980000000 , 986999999] + [987000000 , 987599999] + [987600000 , 987649999] + [987650000 , 987653999] + [987654000 , 987654299] + [987654300 , 987654319] + [987654320 , 987654321],这个分组的规律,我想大家能看懂。啰嗦一下,就是固定x的前i位(i可以等于0,i小于x的位数),区间就是前i位加上全部是0的,到前i位,第i+1位减去1(又要注意:如果第i+1为是0
,则这个区间就不需要计算了),后边全部跟上9。

         为什么要这么计算呢?因为这样可以使用我的分组方法去计算幸运数的个数啊。[0 , x]幸运数的个数,就是所有区间幸运数的个数的和。下面看看如何计算这样的区间:依然是一个实例:比如上边的区间[987000000 , 987599999],该区间的所有数有个特点:987+××××××。那××××××又是那些数呢?观察一下,是[0 , 599999]。它,又是由第一位加上5位数组成的数,那好了,5位数可以是多少呢?可以是[0 , 99999]。这是所有的一位数+所有的二位数+所有的三位数+所有的四位数+所有的五位数。也就是所有不大于99999的数,我们可以分类了。于是,将这些分类和1到5组合,并加上前缀987,我们就能够计算出区间[987000000
, 987599999]有多少个幸运数了。

         幸运数的问题还没有解决。但是计算区间[x , y]的幸运数已经非常简单了。首先,我们可以计算区间[1 , x]中间的幸运数位N1个。我们也可以计算[1 , y]之间的幸运数为N2个。于是,区间[x , y]中幸运数的个数为N2 - N1,当然,如果x不是幸运数,则为N2 - N1,如果x也是幸运数,则为N2 - N1 + 1。

#include <string>
#include <stdio.h>
#include <cmath>
#include <iostream>
using namespace std;

//状态节点
struct Node{
    int num;
    int squ;
    int count;

    struct Node * next;

};

int dict[83][730]; // 状态节点

int squs[] = {0 , 1 , 4 , 9 , 16 , 25 , 36 , 49 , 64 , 81}; // 0-9数字平方

// 判断是否为素数
bool isPrime(int n){
    if(n < 2){
        return false;
    }else{
        int sqr = (int)sqrt(n * 1.0);
        for(int i = 2 ; i <= sqr ; ++i){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }

}

bool primes[730];

// 素数表是否已经初始化
bool primesInited = false;
//初始化素数分布表
void initIsPrime(){
    for(int i = 0 ; i < 730 ; ++i){
        primes[i] = isPrime(i);
    }
        
    primesInited = true;
        
}

//
int calPartPartialCount(int onset , int square , int n , int time){

    if(n < 1 || time < 1){
        
        return 0;
    }

    int count = 0;
    if(!primesInited){
        initIsPrime();
    }

    int i = 0;
    int j = 0 , k = 0;
        
    //初始化状态节点分布矩阵
    for(i = 0 ; i < 83 ; ++i){
        for(j = 0 ; j < 730 ; ++j){
            dict[i][j] = 0;
        }
            
    }

    Node * root = new Node();// 个位数0的节点
    root -> num = 0;
    root -> squ = 0;
    root -> count = 1;
    root -> next = NULL;

    dict[0][0] = 1; // 0节点所对应的的列表

    Node * tail = NULL;
    tail = root; // 只有一个节点尾部等于首部

    Node * p = NULL;

    // 初始化1-9的节点
    for(i = 1 ; i < 10 ; ++i){
        p = new Node();
        p -> num = i;
        p -> squ = squs[i];
        p -> count = 1;
        p -> next = NULL;
        //想链表中增加节点
        tail -> next = p; // 尾部节点增加下一节点
        tail = p;

        dict[p -> num][p -> squ] = 1;

    }

    int size = 0;
    int num = 0;
    int squ = 0;
    p = NULL;

    time = time - 1;
    Node * current = NULL; // 当前遍历的最后节点
    Node * pNew = NULL; // 新节点
    for(j = 0 ; j < time ; ++j){
        current = tail;
        p = root;

        while(p != current -> next){

            for(i = 1 ; i < 10 ; ++i){
                num = p -> num + i;
                squ = p -> squ + squs[i];
                if(dict[num][squ] == 0){
                    pNew = new Node();
                    pNew -> num = num;
                    pNew -> squ = squ;
                    pNew -> count = p -> count;
                    pNew -> next = NULL;

                    dict[num][squ] = p -> count;

                    tail -> next = pNew; // 将新节点加入到链表中
                    tail = pNew;

                }else{
                    dict[num][squ] += p -> count;
                }

            } // for(i = 1 ; i < 10 ; ++i)

            p = p -> next; // 节点后移

        } // while(p != current)

        p = root;
        while(p != NULL){
            p -> count = dict[p -> num][p -> squ];
            p = p -> next;
        }

    } // for(j = 0 ; j < time ; ++j)

    p = root;
    while(p != NULL){
        for(i = 0 ; i < n ; ++i){
            if(primes[p -> num + onset + i] && 
                primes[p -> squ + square + squs[i]]){
                    count += p -> count;
            }

        }

        p = p -> next;
    }

    return count;

} // int calPartPartialCount(int onset , int square , int n , int time)

// 计算小于x的所有数字钟幸运数的个数
int countLuckNumber(int x){
    int count = 0;
        
    if(x >= 1000000000){ // 不超过1000000000
        x = 999999999;            
    }
        
    int number[9];
    int i= 0;
    for(i = 8 ; i > -1 ; --i){
        number[i] = x % 10;
        x = x/10;            
    }
        
    int onset = 0;
    int square = 0;
        
    for(i = 0 ; i < 9 ; ++i){

        count += calPartPartialCount(onset , square , number[i] , 8 - i);

        onset += number[i];
        square += squs[number[i]];
                        
    }
    
    onset = 0;
    square = 0;
    for(i = 0 ; i < 8 ; ++i){
        onset += number[i];
        square += squs[number[i]];

    }

    for(i = 0 ; i <= number[8] ; ++i){
        if(primes[onset + i] && 
            primes[square + squs[i]]){
                count ++;
        }
    }

    return count;
}

int lucky(int x,int y) {
    int count = 0;
        
    count = countLuckNumber(y) - countLuckNumber(x);
        
    int sum = 0;
    int squares = 0;
    int digit = 0;

    for(int i = 0 ; i < 9 ; ++i){
        digit = x % 10;
        x = x /10;
        sum += digit;
        squares += squs[digit];
    }
    if(primes[sum] && primes[squares]){
        count ++;
    }

    return count;
}



//start 提示:自动阅卷起始唯一标识,请勿删除或增加。
int main()
{   
    //main函数方便你自行测试,可不用完成
} 
//end //提示:自动阅卷结束唯一标识,请勿删除或增加。

【上篇】
【下篇】

抱歉!评论已关闭.