PAT 甲级 1049 Counting Ones (30 分)(找规律,较难,想到了一点但没有深入考虑嫌麻烦)***

PAT 甲级 1049 Counting Ones (30 分)(找规律,较难,想到了一点但没有深入考虑嫌麻烦)***,第1张

概述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 be 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 (≤).

Output Specification:

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

Sample input:
12
Sample Output:
5

题意:

给定一个十进制正整数N,写下从1开始,到N的所有整数,然后数一下其中出现的所有“1”的个数。

题解:

一个最简单的方法来计算f(N),那就是从1开始遍历到N,将其中每一个数中含有“1”的个数加起来,自然就得到了从1到N所有“1”的个数的和。

但是这个算法的致命问题是效率,它的时间复杂度是

ON)×计算一个整数数字里面“1”的个数的复杂度 = ON * log2 N

如果给定的N比较大,则需要很长的运算时间才能得到计算结果。比如在笔者的机器上,如果给定N=100 000 000,则算出fN)大概需要40秒的时间,计算时间会随着N的增大而线性增长。

 

仔细分析这个问题,给定了N,似乎就可以通过分析“小于N的数在每一位上可能出现1的次数”之和来得到这个结果。让我们来分析一下对于一个特定的N,如何得到一个规律来分析在每一位上所有出现1的可能性,并求和得到最后的fN)。

先从一些简单的情况开始观察,看看能不能总结出什么规律。

 

先看1位数的情况。

如果= 3,那么从1到3的所有数字:1、2、3,只有个位数字上可能出现1,而且只出现1次,进一步可以发现如果N是个位数,如果N>=1,那么fN)都等于1,如果N=0,则fN)为0。

 

再看2位数的情况。

如果N=13,那么从1到13的所有数字:1、2、3、4、5、6、7、8、9、10、11、12、13,个位和十位的数字上都可能有1,我们可以将它们分开来考虑,个位出现1的次数有两次:1和11,十位出现1的次数有4次:10、11、12和13,所以fN)=2+4=6。要注意的是11这个数字在十位和个位都出现了1,但是11恰好在个位为1和十位为1中被计算了两次,所以不用特殊处理,是对的。再考虑N=23的情况,它和N=13有点不同,十位出现1的次数为10次,从10到19,个位出现1的次数为1、11和21,所以fN)=3+10=13。通过对两位数进行分析,我们发现,个位数出现1的次数不仅和个位数字有关,还和十位数有关:如果N的个位数大于等于1,则个位出现1的次数为十位数的数字加1;如果N的个位数为0,则个位出现1的次数等于十位数的数字。而十位数上出现1的次数不仅和十位数有关,还和个位数有关:如果十位数字等于1,则十位数上出现1的次数为个位数的数字加1;如果十位数大于1,则十位数上出现1的次数为10。

f(13) = 个位出现1的个数 + 十位出现1的个数 = 2 + 4 = 6;

f(23) = 个位出现1的个数 + 十位出现1的个数 = 3 + 10 = 13;

f(33) = 个位出现1的个数 + 十位出现1的个数 = 4 + 10 = 14;

f(93) = 个位出现1的个数 + 十位出现1的个数 = 10 + 10 = 20;

 

接着分析3位数。

如果N = 123:

个位出现1的个数为13:1,21,…,91,101,111,121

十位出现1的个数为20:10~19,110~119

百位出现1的个数为24:100~123

f(23)= 个位出现1的个数 + 十位出现1的个数 + 百位出现1的次数 = 13 + 20 + 24 = 57;

同理我们可以再分析4位数、5位数。读者朋友们可以写一写,总结一下各种情况有什么不同。

根据上面的一些尝试,下面我们推导出一般情况下,从N得到fN)的计算方法:

假设N=abcde,这里abcde分别是十进制数N的各个数位上的数字。如果要计算百位上出现1的次数,它将会受到三个因素的影响:百位上的数字,百位以下(低位)的数字,百位(更高位)以上的数字。

如果百位上的数字为0,则可以知道,百位上可能出现1的次数由更高位决定,比如12 013,则可以知道百位出现1的情况可能是100~199,1 100~1 199,2 100~2 199,…,11 100~11 199,一共有1 200个。也就是由更高位数字(12)决定,并且等于更高位数字(12)×当前位数(100)。

如果百位上的数字为1,则可以知道,百位上可能出现1的次数不仅受更高位影响,还受低位影响,也就是由更高位和低位共同决定。例如对于12 113,受更高位影响,百位出现1的情况是100~199,1 100~1 199,2 100~2 199,…,11 100~11 199,一共1 200个,和上面第一种情况一样,等于更高位数字(12)×当前位数(100)。但是它还受低位影响,百位出现1的情况是12 100~12 113,一共114个,等于低位数字(113)+1。

 

如果百位上数字大于1(即为2~9),则百位上可能出现1的次数也仅由更高位决定,比如12 213,则百位出现1的可能性为:100~199,1 100~1 199,2 100~2 199,…,11 100~11 199,12 100~12 199,一共有1 300个,并且等于更高位数字+1(12+1)×当前位数(100)。

 

AC代码:

#include<iostream>#include<algorithm>#include<vector>#include<queue>#include<map>#include<string>#include<cstring>using namespace std;int n;int num=0;int main(){    cin>>n;    int factor = 1;    int higher,lower,cur;//高位,低位,当前位    while(n/factor!=0){//依次取个、十、百、千……        higher = n/(factor*10);        cur=(n/factor)%10;        lower=n%factor;        if(cur==0){            num+=higher*factor;        }else if(cur==1){            num+=higher*factor+lower+1;        }else{            num+=higher*factor+factor;        }        factor = factor * 10;    }    cout<<num;    return 0;}
总结

以上是内存溢出为你收集整理的PAT 甲级 1049 Counting Ones (30 分)(找规律,较难,想到了一点但没有深入考虑嫌麻烦)***全部内容,希望文章能够帮你解决PAT 甲级 1049 Counting Ones (30 分)(找规律,较难,想到了一点但没有深入考虑嫌麻烦)***所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/1024255.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-23
下一篇 2022-05-23

发表评论

登录后才能评论

评论列表(0条)

保存