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;
}