首页 > 代码库 > The Counting Problem poj2282
The Counting Problem poj2282
/************************************************************************/ /* 递归问题: 给定一个区间,求其中所有0~9数字总计出现次数 思路: 设f(a),f(b)为各自从1开始到a,b中所有0~9数字总计出现次数。 则ans=f(b)-f(a-1);递归的话就是建立f(k)和f(10*k+x)的关系. 对于一个大数,先处理到末尾为0,然后再认为是从0开始10个10个数,数到这个数。 例如,f(2984)就先从2981数到2984(2,9,8各出现4次,1,2,3,4一次)然后 f(2980)可以和f(298)建立递推(实际的时候用f(297)更好一点)。 注意这里需要建立一个“乘子”,一开始为1,每次递推一层就*10,然后累加到0-9的记录上。 换句话说 逐位计算每个数字出现的个数 2984 先计算个位上的 2981 2982...2984 298各出现4次,1 2 3 4各一次 然后可以得知从1变化到2980 各位都各自变化了298次,对于2980 0的计算已经包含进来了,所以不用计算而298出现次数都再加一 然后个位上的不用管,看十位上的变为297 这时候乘子要变为之前的10倍 (若为10,那么从1到10每位各出现了1次,1再多一次,若做类似变化,10->1的时候会认为各位再多变了一次) 所以不用298 */ /************************************************************************/ #include <iostream> #include <string> using namespace std; int a,b; int ansa[10],ansb[10]; void count_digits(int s,int *ans,int times)// { int i,p,m; if(s<=0) return; m=s%10; p=s/10; for(i=1;i<=m;i++) ans[i]+=times;// while(p) { ans[ p%10 ]+=(m+1)*times; p/=10; } for(i=0;i<10;i++) ans[i]+=times*(s/10); count_digits((s/10)-1 ,ans,times*10); } int main() { int i,j; while(scanf("%d%d",&a,&b),a + b) { memset(ansb,0,sizeof(ansb)); memset(ansa,0,sizeof(ansa)); if (a >= b) { swap(a,b); } a --; if (b > a) { count_digits(b,ansb,1); count_digits(a,ansa,1); } for(i=0;i<10;i++) { printf("%d%c",ansb[i]-ansa[i],i==9?'\n':' '); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。