| 起名问题 |
|
 |
|
|
起名问题 求敲七（题的名字）算法（C++）
人气：
【字体：大 中 小】
发布时间：2006-04-12 12:42:20
>>>>>>>>提问
题目描述：
大家都爱敲七，我也来敲一回。
如果一个数能被7整除，或者它含有数字7，那么说这个数字与7有关。现在给出整数N(1<=N<=300)，请你求出从0到10^N-1有多少个数与7有关。当然，0是7的倍数，所以0也算与7有关的数。
输入：
本题有多组数据，每组一行，为一个整数N。
输出：
每行一个整数，为从0到10^N-1的与7有关的数的个数。
由于数据太大如果直接搜估计搜个100年就能出结果。。。哪位高人有好办法解决。详细说明算法有程序当然更好(C++或者Pascal）
时间限制是1S- -
休 闲 宝 贝 网
>>>>>>>>休闲宝贝网回答：
不会。。。。
我只会这样算，
比如说n = 3;
即0 到999
先找7的倍数
999 / 7 得到142
带7的数
由于是 n=3,所以最高是三位
则有三种情况：个位是7，十位是7，还有百位是7（要求只能有一个7出现在数中）
个位是7，则前面还有两位：百位，十位
则选择方案有9*9种（当百位为0则就是一个二位数，百位十位都为0，就是一个一位数，就可以把个，十，百三种情况都包括了，哦耶！！当然，这时百位和十位不能有任何一个为7）
同样的，十位是7的话，百位和个位有9*9种选择。
百位是7的时候也是一样。。。
所以直接就可以算出来是 n * 9*9……*9（n-1个9）。
再说有两位同时为7的，这两位是百，十，个位的有序组合，有三种情况，百+十，十+个，百+个
这个时候有3*9种情况。
……当多于三位，以此类推。不会太复杂。
最后是三个都位7，明显只有一个呗。
最后还有一个很恐怖的问题。。。。当一个数又是7的倍数，又包含7。。。这个。。。。努力思考中。。
----------------------------------------------------------
想了半天之后，我突然发现一个很严重的问题，10^300次方~~~这东西完全没法没法用内置类型来表达嘛~~~
那我的算法，完全就不可行了。。。除非你新建一个类，能表达这么大的数，其行为又和内置类型相似~~
想想。。。是不是应该用string来表达这些数呢~~~
然后加一个容器~~~
先将能被7整除的数找出来，再在这些string里面，利用find方法找7，找到就排除。。。。
这样做的话，好像时间复杂度又没怎么减少啊。。。
郁闷了。。。。
反正我就能想到这么多了。。。你自己看着吧。。
≡
查看、发表评论 ≡
|
|
