github 地址：https://github.com/iofu728/PAT-A-by-iofu728 难度：☆☆★ 关键词：递归，数学问题

# 题目

1049.Counting Ones (30) The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive N (<=230).

Output Specification:

For each test case, print the number of 1’s in one line.

Sample Input: 12 Sample Output: 5

# 大意

给一个正整数 n，输出小于 n 带 1 数的个数。

# 思路

1. 一看到这问题，第一反应是 n 大起来，遍历的复杂度可能吃不消。 想的思路是如果首位为 1，则个数F(n)=F(n-1)+C(n-1) 首位若大于 1，则F(n)=A（n-1）*（C(n)-C(n-1)-1）+F(n-1). 其中 C 为原始数组，A 为 n 位前的含 1 个数数组，F 为所求的数组 n 位前的含 1 数数组
2. 后来看见一个算法，很优美。用了 left，now，right 三个数来控制问题，分别表示当前位左侧，当前位，当前位右侧。 从个位开始遍历： 若当前位为0，则temp+=left*bit；若当前位为1，则temp+=left*bit+right+1;若当前位为其他，则temp+=(left+1)*bit;

# code

#include <iostream>
int main() {
  int n, left = 0, now = 1, right = 0, temp = 0, bit = 1;
  scanf("%d", &n);
  while (n / bit) {
    left = n / (bit * 10);
    now = (n / bit) % 10;
    right = n % bit;
    if (!now) {
      temp += left * bit;
    } else if (now == 1) {
      temp += left * bit + right + 1;
    } else {
      temp += (left + 1) * bit;
    }
    bit *= 10;
  }
  printf("%d", temp);
  return 0;
}