首页 > 代码库 > 求1~n直接1出现的次数

求1~n直接1出现的次数

2024-07-26 07:35:36   220人阅读

参考前人的统计思想：分别统计个、十、百、、、亿等第N位上1出现的次数。

如ABCDE，在统计D位1出现的次数时，用D做分割符，ABC为Before，E为After。

分情况考虑：(n为D的length-1)

当D = 0 时，count = Before * 10^n ;

当D = 1 时，count = Before * 10^n + After;

当D > 1 时，count = (Before + 1)*10^n; 

例如：

　　19X8

统计X上1的次数：

1）X = 0 ，即1908 X为1的数有001x~181x，x取0~9则19为Before，8为After

此时count = 19 * 10^1 ;

2）X = 1 ，即1918 X为1的数有001x~181x，x取0~9；另外，1910~1918，则19为Before，8为After

此时count = 19 * 10^1 + (8 + 1);

3）X > 1 ，如1928 X为1的数有001x~191x，x取0~9则19为Before，8为After

此时count = (19 + 1) * 10^1 ;

特别当X在最左端时Before 为 0，最右端时After 为0 

#include <stdio.h>int Count1(int n){    int count = 0,//1出现总次数    bitCount = 0,//某位1出现次数    base = 1,//基数    before = n,after = 0,  //从最右开始，则Before = n，After = 0    bitN = 0;//第N位数    while(before)//向左移，还有数时循环    {        after = n % base;        before = n / (base * 10);        bitN = (n / base) % 10;        if(bitN > 1)        {            bitCount = (before + 1) * base;        }        else if(bitN == 0)        {            bitCount = (before) * base;        }        else        {            bitCount = (before) * base + (after + 1);        }        base *= 10;        count += bitCount;    }    return count;}int main() {   int n = 121;   printf("%d\n",Count1(n));   return 0;}

 

求1~n直接1出现的次数


联系
我们