1统计数字问题
1.1 算法
设计思想
设书的页数为n由0,1,2...9组成的所有n位数。从n个0到n个9共有10^n个n
位数。在这10^n个n位数中,0,1,2.....9第个数字使用次数相同。f(n)满足如下递推式:f(n)
= n*10^(n-1)。通过这个方法算出0-9数字出现的次数,最后减去0的个数。
1.2 程序源码
import java.util.Scanner; public class Count { public static void main(String[] args) { int[] count=new int[10]; //建立一个数组,表示数字count[i]出现的次数 int[] f19={0,1,19,280,3700,46000,550000,6400000,73000000,820000000}; //f19[i]表示i位数里面,没有前导0时,数码i出现的次数,例如10-99 int[] f0={0, 1, 9, 180, 2700, 36000, 450000, 5400000, 63000000, 720000000}; //f0[i]表示i位数里面,没有前导0时,数码0出现的次数 int[] Next={0,1,20,300,4000,50000,600000,7000000,80000000,900000000}; //Next[i]表示为了计算i+1位数的各个数码出现的次数,需要知道i位数考虑前导0 时,各个数码出现的次数,例如00-99 int[] Num={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 }; //Num[i]表示i位数里一共有多少个数,例如2位数共100个,00-99 int i,j,k,sum=0; int page,temp; System.out.println("实验一 算法的分析基础"); System.out.println("题目:统计数字
问题"); Scanner reader=new Scanner(System.in); System.out.println("输入:"); page=reader.nextInt(); long startTime=System.nanoTime();//获取开始时间 while(page!=0){ temp=page; for(i=0;i<10;++i)
count[i]=0;
if(page>9)
count[0] -= 1;
while(temp!=0)//计算page的位数
{
++sum;
temp=temp/10;
}
for(i=1;i
count[0]+=f0[i];
j=1;
while(j<=9)
{
count[j]+=f19[i];
++j;
}
}
k=1;
while(sum!=0){
--sum;
temp=page/Num[sum];
if(k==1){//考虑到最高位为0时,不能进行统计
count[0] += (temp - 1)*Next[sum];
for(i=1; i {
count[i]+= (Num[sum] + (temp - 1)*Next[sum]);
}
for(i=temp;i<10; ++i)
{
count[i]+= (temp - 1)*Next[sum];
}
k = 0;
}
else{ //除了最高位以外的位为0时,需要进行统计
for(i=0; i {
count[i] += (Num[sum] + temp*Next[sum]);
}
for(i=temp; i<10; ++i)
{
count[i] += temp*Next[sum];
}
} count[temp] += page%Num[sum] + 1; page = page%Num[sum]; } long endTime=System.nanoTime();//获取结束时间 System.out.print("\n"); System.out.println("输出:"); for(i=0; i<10; ++i) System.out.println(count[i]); System.out.println("运行时间:"+(endTime-startTime)+"ns"); //获得程序运行的时间 } } }
1.3 实验结论(结果验证)
Input 1
Input 999 Input 9 Input 33 Input 99 Input 100 Input 1000000 Input 37281947 Input 26824326 Input 9432747
1.4 心得体会
通过老师的讲解和网上代码的参考才完成,自己写的程序运行总是出错, 只能到网上参考一下了。