求1到2008080808之间含有数字7的个数总和? 其实没那么复杂

在CSDN上看到的题..看到很多人的算法都挺复杂的..

从小的数字看起..10里有1个100是10的10倍.但是100里还有70-79都是..所以就是 1*9+10=19个
那么1000就是  (1*9+10)*9+100
10000就是  ((1*9+10)*9+100)*9+1000嗯.是麻烦.所以要把公式提炼出来把这个算术式分析一下。就可以得到公式
这个东西算出来就是9*9*9+810+900+1000=9的三次方*10的0次方+9的2次方*10的一次方 + 9的1次方*10的2次方+9的0次方*10的3次方
                                                                  (9*9*9)              (810)                                (900)                           (1000)

如果把  求1到2008080808之间含有数字7的个数总和?  简化为求 10000以内的含有数字7的数的应该这样9的3次方*10的0次方 + 9的2次方*10的1次方 + 9的1次方*10的2次方  +  9的0次方+10的3次方
其实就是要求N位数的含有某数字的个数先求出N为数的最小数a然后计算a以内有多少个acount=9的n-2次方*10的0次方 + .... + 9的0次方*10的n-2次方.
然后用该整数除以a得到该整数是a的b倍..再用b*acount.得出该整数减去该整数除以a的余数包含的所有包含该数字的数的数量依次类推..

这个可以一直做下去。 2008080808 = 2000000000  先求出 2000000000 包含的个数  8000000  再求8000000内包含的个数      800   ...        8  ...

(改天附上程序实现)

一下是程序实现:

package org.phyeas.demo;

public class Main {

public static void main(String[] args) {

System.out.println(lookUpForHasNumber(2008080808 , 7));

}

/**

* 查找从从1到end含有数字hasNumber的个数

* @param end

* 结束

* @param hasNumber

* 含有某数字

* @return

public static int lookUpForHasNumber(long end, int hasNumber) {

int count = 0;

long less = getLess(end);

while (less > 10) {

int n = (int) Math.log10(less);

long bei = end / less;

int tempCount = 0;

for (int i = n - 1, j = 0; i >= 0; i--, j++) {

tempCount += Math.pow(9, i) * Math.pow(10, j);

}

if (bei >= 1) {

if (bei > hasNumber) {

tempCount = (int) ((int) (tempCount * (bei - 1)) + less);

} else if (bei == hasNumber) {

tempCount = (int) (tempCount * bei) + 1;

} else {

tempCount = (int) (tempCount * bei);

}

count += tempCount;

end = end - less * bei;

less = getLess(end);

}

if (less > hasNumber) {

count = count + 1;

}

// System.out.println("count=" + count);

return count;

}

/**

* 获取与这个数字位数相同的最小数

* @param number

* @return

public static long getLess(long number) {

if (number > 10) {

String str = String.valueOf(number);

StringBuffer nStr = new StringBuffer("1");

for (int i = 1; i < str.length(); i++) {

nStr.append("0");

}

return Long.parseLong(nStr.toString());

}

return number;

}

最后结果:1229473242

posted on 2008-06-18 23:11 phyeas 阅读(384) 评论(1) 编辑收藏

常用链接

留言簿(2)

随笔档案

文章分类

文章档案

相册

搜索

最新评论

阅读排行榜

评论排行榜


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻知识库 C++博客博问管理