1. 原题： https://www.patest.cn/contests/pat-a-practise/1049
2. 思路：
题意：
输出从1~N之间的所有整数中含有1的总个数。
思路：
数学逻辑题。需要枚举，归纳出规律。不易想出来。
首先，从1直接数的方法有些傻，抛弃掉。
那么如何处理呢？
不妨站在全局进行思考，我们无法准确知道1会出现在哪一位。
那为何我们不从每一位出现1的次数进行累加不就是总次数呢。
okay， 那么我们需要归纳每一位出现1的次数是多少。
假设我们现在计算百位上为1的次数。比如一个数12033.
1. 若当前位cur = 0， 显然若百位为1，只与高位有关。
比如 100~199, 1100~1199, 总数为12*100。
即高位*位权。
2. cur = 1, 如12133.显然除了高位，还与低位有关。即12100~12133，
低位有关时的总个数为 低位数+1.
3. cur > 1, 如12233. 显然与低位无关了，与高位及当前位有关，
但可以把当前位累计到高位上，即 总个数为 （高位+1）*位权。
以上就是一个规律的展示。
3. 源码（已AC）：
#include<iostream>
using namespace std;
int main(void)
{
//freopen("in.txt", "r", stdin);
int N, sum = 0;
cin >> N;
int wgt = 1;//位权初始1，表示从个位开始
while (N / wgt != 0)
{
int left = N / (wgt * 10);//表示高位数
int cur = N / wgt % 10;//当前位值
int right = N % wgt;//低位数值
if (cur == 0)//三种情况
sum += left * wgt;
else if (cur == 1)
sum += left * wgt + right + 1;
else
sum += (left + 1) * wgt;
wgt *= 10;//位权增加
}
cout << sum << endl;
return 0;
}参考自：
http://m.blog.csdn.net/article/details?id=38846057
转载请注明原文地址: https://ju.6miu.com/read-662353.html
