UC知道c++记数器
来源：百度知道 编辑：UC知道 时间：2024/09/28 12:21:02
一本书的页数为N。页码从1开始编起，请你求出全部页码中，用了多少个0,1,2,…..,9.其中一个页码不含多余的0，如N＝1234时第五页不是005，只是5。
输入：一个正常数N（N小于10的9次方），表示总的页码。
输出：共十行，第K行为数字K-1的个数。
下面是我写的程序
#include<iostream>
using namespace std;
main()
{
int n,i,p;
while(scanf("%d",&n))
{
int a[10]={0,0};
for(i=1;i<=n;i++)
{
p=i;
do
{
switch(p%10)
{
case 0:a[0]++;break;
case 1:a[1]++;break;
case 2:a[2]++;break;
case 3:a[3]++;break;
case 4:a[4]++;break;
case 5:a[5]++;break;
case 6:a[6]++;break;
case 7:a[7]++;break;
case 8:a[8]++;break;
case 9:a[9]++;break;
}
p=p/10;
} while(p!=0);
}
for(i=0;i<10;i++)
printf("%d\n",a[i]);
}
return 0;
}
在OJ上运行后超时了，就差一点，规定1000ms，这个是1015ms.
哪位高手能帮忙改一下，或者有什么其它更好的办法可以解决，万分感谢！！！！！！！！
输入：一个正常数N（N小于10的9次方），表示总的页码。
输出：共十行，第K行为数字K-1的个数。
下面是我写的程序
#include<iostream>
using namespace std;
main()
{
int n,i,p;
while(scanf("%d",&n))
{
int a[10]={0,0};
for(i=1;i<=n;i++)
{
p=i;
do
{
switch(p%10)
{
case 0:a[0]++;break;
case 1:a[1]++;break;
case 2:a[2]++;break;
case 3:a[3]++;break;
case 4:a[4]++;break;
case 5:a[5]++;break;
case 6:a[6]++;break;
case 7:a[7]++;break;
case 8:a[8]++;break;
case 9:a[9]++;break;
}
p=p/10;
} while(p!=0);
}
for(i=0;i<10;i++)
printf("%d\n",a[i]);
}
return 0;
}
在OJ上运行后超时了，就差一点，规定1000ms，这个是1015ms.
哪位高手能帮忙改一下，或者有什么其它更好的办法可以解决，万分感谢！！！！！！！！
您好超时的原因是您使用了比较繁琐的算法，
其实每个数字出现都是有规律的
不难分析：
比如n为25
各位0-9整体循环了2次，最后1-5又单独出现了一次
所以您应该用一个变量base存所有数字出现的基数；a[0]-a[9]存放0-9比基数多出的次数
算法主干
int a[10]=0;
int i;
int p=n; int base=0;
while(p>0){
base+=(p-p%10)/10;
for(i=0;i<10;i++){
if(p%10>=i)a[i]++;
}
p/=10;
}
for(i=0;i<10;i++){
a[i]+=bass;
printf("%d\n",a[i]);
}
1015只是说这个时间已经大于1000，所以不再进行处理了，你这个算法肯定不对的，想想规律，这题不难。具体做法就不解答了，既然是做oj的，就应该自己思考，好好加油。
建议看看，王晓东的算法设计与分析