first blog编程之美-----计算1的个数

时间:2021-06-05 06:11:46
根据以下总结写出以下程序,总结来源于网上
感想:得硬着头皮找规律
#include
 
int count1(int n)
{
        int i=1;
        int count=0,after=0,before=0,cur=0;
        while(n/i)
        {
                after = n%i;
                before=n/(10*i);
                cur = n/i;
                // printf("%d %d %d\n",before,cur,after);
                if(cur < 1){
                        count+=(before*i);
                } else if(i==1){
                        count+=(before*i+after+1);
                } else{
                        count+=((before+1)*i);
                }
                i*=10;
        }
        return count;
 
}
 
 
 
int main(int argc,char*argv[])
{
        printf("%d\n",count1(atoi(argv[1])));
        return 0;
}
 
 

假设N,我们要计算百位上出现1的次数,将由三部分决定:百位上的数字,百位以上的数字,百位一下的数字。

如果百位上的数字为0,则百位上出现1的次数仅由更高位决定,比如12013,百位出现1的情况为100~199,1100~1199,2100~2199,…,11100~11199,共1200个。等于更高位数字乘以当前位数,即12 * 100。

如果百位上的数字大于1,则百位上出现1的次数仅由更高位决定,比如12213,百位出现1的情况为100~199,1100~1199,2100~2199,…,11100~11199,12100~12199共1300个。等于更高位数字加1乘以当前位数,即(12 + 1)*100。

        如果百位上的数字为1,则百位上出现1的次数不仅受更高位影响,还受低位影响。例如12113,受高位影响出现1的情况:100~199,1100~1199,2100~2199,…,11100~11199,共1200个,但它还受低位影响,出现1的情况是12100~12113,共114个,等于低位数字113+1。