原题连接: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 //提示:自动阅卷结束唯一标识,请勿删除或增加。