概述
这类问题在n较小的情况 下可以一一遍历,但是在数较大的情况下,会使效率降低,
这时就要使用高效算法,判断在某种情况下的数的个数依次从高位向低位推,在某位
时会可能会受到高位或者低位的影响,这时就是以特例将循环写出。
例如,求1--n的n个数中0-9这是个数字出现的次数问题
#include<stdio.h>
#include<string.h>
int fun(int a,int x)
{
int i,sum=1;
for(i=0;i<x;i++)
sum*=a;
return sum;
}
int main()
{
int a[10],sum[10],i,j,num,cout,num1;
while(scanf("%d",&num)==1) //数组a用来存放输入的是的每一位
{
memset(sum,0,sizeof(sum));
i=0; num1=num;
while(num1!=0)
{
a[i++]=num1%10;
num1/=10;
}
cout=--i; //一共有cout+1位数,此时占用数组0-cout位
for(j=0;j<a[cout];j++)
{
sum[j]+=fun(10,cout);
}
if(j!=0)
sum[j]+=num%fun(10,cout)+1;
for(i=cout-1;i>=0;i--) //循环对每位数进行操作
{
for(j=0;j<a[i];j++)
{
sum[j]+=(num/fun(10,i+1)+1)*fun(10,i);
}
sum[j]+=num/fun(10,i+1)*fun(10,i)+num%fun(10,i)+1;
for(j=j+1 ;j<10;j++)
sum[j]+=num/fun(10,i+1)*fun(10,i);
}
for(i=cout;i>=0;i--)
sum[0]-=fun(10,i);
//显示每个数的个数
for(i=0;i<10;i++)
printf("sum[%d]=%dn",i,sum[i]);
}
return 0;
}
最后
以上就是暴躁紫菜为你收集整理的求1-n中的某个数的出现次数的全部内容,希望文章能够帮你解决求1-n中的某个数的出现次数所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复