2 u011963627 u011963627 于 2013.09.10 20:52 提问

求助一道c语言题啊,很急啊

众所周知,琪露诺(チルノ,Cirno)是幻想郷 (げんそうきょう)中首屈一指的天才,可以说⑨就是她的代名词。
然而如今,她遇到了一个和⑨有关的难题。你能帮助她么?
题目是这样的,给出两个数 a 和 b (0 <= a <= b <= 10^10000),求 a 到 b 之间(包括a和b)的数字中,有多少个数字是包含9的(例如 19,910 等都是包含9的数字)。
输入
第一行为一个数字 T (0 < T <= 100) 表示数据组数。
之后的 T 行,每行包含两个数 a 和 b (0 <= a <= b <= 10^10000)。
输出
对每组数据输入,输出一个数字,表示 a 到 b 之间的数字中(包括a和b),有多少个数字是包含9的。(注意:答案可能很大)
测试输入
期待的输出
时间限制
内存限制
额外进程

测试用例 1 以文本方式显示
1. 1↵
2. 0 9↵ 1. 1↵

这是我的作法不对啊
#include"stdio.h"
int mul(int a,int d,int l)
{int i;
for (i = 0; i < l; i++)

{

a[i] = a[i] * d;

}

for (i = 0; i < l; i++)

{

a[i + 1] += a[i] / 1000000;

a[i] = a[i]%1000000;

}
if(a[l]!=0)
l++;
return l;

}
int plus(int *x, int *y,int l)

{

int i;

for (i = 0; i < l; i++)

{

x[i] += y[i];

if (x[i] >= 1000000)

{

x[i + 1]++;

x[i] -= 1000000;

}

}
if(x[l]!=0)
l++;
return l;
}
int minus(int *x, int *y, int *z,int l)

{

int i;

for (i = 0; i {
z[i] += x[i] - y[i];
if (z[i] {
z[i + 1]--;
z[i] += 1000000;
}
}
while(l>0&&z[l-1]==0)
{
l--;
}
return l;
}

main()
{
int a[100]={0},b[100]={0},c[100]={0},d[100]={0};
int e[100]={0},f[100]={0},g[100]={0},h[100]={0};
int flag=1,pda9=1,pdb9=1,i,j,T;
int lena=1,lenc=1,lend=1,lene=1,lenf=1,leng=1,lenh=1;
char ch;
scanf("%d\n",&T);/
输入的行数*/
for(i=0;i<T;i++)
{
for(;;)/*如果遇到\n,退出循环*/
{ ch=getchar();
if(ch=='\n') break;
if(ch==' ') { flag=0;continue;}/*遇到空格表明该计算小的数含9个数了*/

     if(flag==1)
    { b[0]=ch-'0'; 
     lenc=mul(c,10,lenc);lenc=plus(c,b,lenc);/*先乘以10再加读入的数,lenc是所得数的位数*/         
     if(ch=='9') pda9=0;/*接下来计算含9的个数,做标记分两种情况*/ 
     if(pda9==0) lena=mul(a,9,lena);
     if(pda9==1) {lena=mul(a,9,lena);lena=plus(a,b,lena);}  

    }

    if(flag==0) /*计算大的数含9个数*/
     {
      b[0]=ch-'0'; /*将b转换为整形,只有一位,后面要被加*/ 
      lend=mul(d,10,lend);lend=plus(d,b,lend);/*lend是所得位数*/ 
      if(ch=='9') pdb9=0;/*同上*/ 
      if(pdb9==0) lene=mul(e,9,lene);
      if(pdb9==1){lene=mul(e,9,lene);plus(e,b,lene);} 
     } 

    }

 lenf=minus(c,a,f,lenc); /*f是小的数里面含的9的个数,f=c-a*/  
 leng=minus(d,e,g,lend);/*g是大的数里面含的9的个数,g=d-e*/
 if(pdb9==0) {b[0]=1;leng=plus(g,b,leng);}   /*遇到9,大的数里面含的9个数要加1*/

 lenh=minus(g,f,h,leng);
 for(j=lenh-1;j>=0;j++)
 printf("%d",h[j]);


 }

}

1个回答

czp1001
czp1001   2013.12.26 20:29
已采纳

我没有时间详细看你的代码,这里给出这类题的解题思路。
1)遍历
从最小的值到最大的值遍历,将其中含1的个数加起来,这样就得到答案。但这样最大的缺点是效率不高,因为复杂度O(N*lgN). 另外,f(N,M) = f(1,M)-f(1,N-1).
2) 发现规律
假设求f(1,N).
f(1,125) = 个位数出现9个数 + 十位数出现9的个数 + 百位出现的9的个数。

Csdn user default icon
上传中...
上传图片
插入图片