当前位置: 代码迷 >> 综合 >> 数字1的数量 51Nod - 1009
  详细解决方案

数字1的数量 51Nod - 1009

热度:70   发布时间:2023-12-12 14:20:20.0

## 题目 ##

给定一个十进制正整数N,写下从1开始,到N的所有正数,计算出其中出现所有1的个数。
例如:n = 12,包含了5个1。1,10,12共包含3个1,11包含2个1,总共5个1。

Input
输入N(1 <= N <= 10^9)

Output
输出包含1的个数

Sample Input
12

Sample Output
5

题意分析:这个题呢,刚开始我也没有写出来,应为思维被固化了,总是在想 “有几个1”,想通过排列组合来解决,但是发现很复杂,要考虑的方面很多,最后看了看解题思路。原来要把寻找“有几个1” 变成 寻找“每一位上面有几个含有1的数字”,然后把每一位上面含有1的数字的个数,加起来就可以了。思路很简单,接下来还要分析每一位上面含有1的数字的个数。总体来说有三种情况(假设数字n为:a5a4a3a2a1a0, 下面我们先针对 a2 进行分析):
《1》a2 == 0
这时候呢,a2前面剩下的高位,只有在 【0, a5a4a3-1】这个范围内,才会让a2出现1的情况,该为含有1的数的个数为:(a5a4a3-1 - 0 + 1) * (10的i次方),(这里i是2)。
《2》a2 > 1
这个情况和上面等于0的情况类似,只是高位的数字不用减一就可以满足出现1的情况了高位范围是:【0,a5a4a3】,该位含有1的数字的个数为:(a5a4a3 - 0 + 1) * (10的i次方),(这里i是2)。
《3》a2 == 1
这个情况相对来说要特殊一点,前面两种都是只用考虑高位数字即可,这种情况还要考虑低位数字,应为1刚好是处于0和大于1的数字之间,所以要在第一种情况的基础之上还要加上低位数字的个数,加上:a1a0 + 1

另外可能我的方法可能不是很好,还需要考虑该为数字是不是最高位的问题,当最高位== 1 的时候,只需要加上低位的数字即可,如a4a3a2a1a0 + 1; 如果最高位大于1,那么就直接加上(10的i次方)这里的i表示5。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;int Shift(int *arr, int n)//将数字n的每一位放到数组当中,并返回位长
{int index = 0;while (n){arr[index++] = n % 10;n /= 10;}return index;
}int demo(int *arr, int s, int e, int mark)//计算数据
{int sum = 0;for (int i = e; i >= s; i--){if (mark == i)sum = sum * 10 + arr[i] - 1;else sum = sum * 10 + arr[i];}return sum;
}int fact(int n)// 返回10的n次方
{int area = 1;for (int i = 0; i < n; i++)area *= 10;return area;
}int main()
{int n;int arr[15];LL one_num = 0;int len = 0;scanf("%d", &n);memset(arr, 0, sizeof(arr));len = Shift(arr, n);for (int i = 0; i < len-1; i++){if (arr[i] == 0){one_num += (demo(arr, i+1, len-1, i+1) + 1) * fact(i);}else if (arr[i] == 1){one_num += (demo(arr, i+1, len-1, i+1) + 1) * fact(i) + demo(arr, 0, i-1, -1) + 1;}else if (arr[i] > 1){one_num += (demo(arr,i+1,len-1,-1) + 1) * fact(i);}}//最高位特判if (arr[len-1] == 1)one_num += demo(arr, 0, len-1-1, -1) + 1;else if (arr[len-1] > 1)one_num += fact(len-1);printf("%d\n", one_num);return 0;
}