PythonTip >> 博文 >> python

【算法21】从1到n的正数中1的出现次数

zihua 2014-01-20 23:01:59 点击: 844 | 收藏


【题   目】输入一个整数n,求从1到n这n个正数中,1出现的次数。例如:输入12,出现一的数字有1,10,11,12共有5个1,则输出5.

【思 路1】几乎所有的算法题目都有很直观容易想到的方法,当然这类方法的效率通常都不是很好,然而解决问题是第一要义。所以还是从最容易想到的入手。我们可以遍历从1到n的每一个数字k,对于k我们计算出它其中包含的1的个数,方法其实很简单,只需要分别判断个位,十位,百位,千位等的每一位是否为1,然后用计数器记录就OK了。这种思路很简单,我们很容易就可以写出如下的代码:

1 #include<iostream>

2 #include<string>

3 using namespace std;

4

5 //返回任意一个整数k中包含的1的个数

6 int NumbersOf1s(unsigned int k)

7 {

8 int cnt = 0;

9 while(k)

10 {

11 //该位是1,计数器就加1;

12 if(k % 10 == 1)

13 cnt++;

14

15 k = k / 10;

16 }

17

18 return cnt;

19 }

20

21 //返回从1到n的n个整数中所包含的1的个数

22 int NumbersOf1sFrom1ToN(unsigned int n)

23 {

24 if(n < 0)

25 return 0;

26

27 int count = 0;

28 for(int i = 1;i <= n;i++)

29 {

30 count += NumbersOf1s(i);

31 }

32

33 return count;

34 }

35

36 int main()

37 {

38 cout<<"Please Enter the number N:"<<endl;

39 unsigned int number = 0;

40 cin>>number;

41

42 cout<<"The Numbers of 1 From 1 to N is:"<<endl;

43 cout<<NumbersOf1sFrom1ToN(number)<<endl;

44

45 return 0;

46 }

运行结果如下:

【思 路2】上述算法的效率不是很好,尤其对于n非常大的情况,这种算法花费的时间很长。其实我们并不需要对于每一个数字计算出它包含的1的个数,我们可以逐位考虑,所有1的个数等于个位上1的个数+十位上1的个数+百位上1的个数+千位上1的个数+。。。接下来的问题,就是如何求解这些位上1的个数?

首先,我们有如下比较容易得到的结论,0-9中1的个数是1个,0-99中十位(10-19)上1的个数是10,0-999中百位上(100-199)上1的个数是100,以此类推。为什么需要这些数字,我们经过简单罗列,很容易发现:个位上1的个数,实际上和这个数字包含多少个10有关,因为对于个位来说,总是从0-9循环,十位上1的个数,实际上和这个数字包含多少个100有关,因为每包含1个100,就有0-99的循环,而0-99中十位上的1是10个;那么关系究竟是什么呢?我们看下面的例子来理解:

对于数字123:

123/10=12,包含12个10,每个10包含1个1(个位1)所以个位共包含12*1=12个1;余数的情况后面单独讨论;

123/100(或者12/10)=1,包含1个100,每个100包含10个1(十位1),所以十位共包含1*10=10个1;余数的情况后面单独讨论;

123/1000(或者1/10)=0,包含0个1000,每个1000包含100个1(百位1),所以百位共包含0*100=0个1;余数的情况后面单独讨论;

现在考虑余数的两种情况:

(1)余数大于1的情况:

数个位时,余数3大于1;所以个位上1的个数要+1;

数十位时,余数2大于1;因为增加了100-120之间(10-19)的数字即110-119,所以十位上1的个数要+10;

(2)余数等于1的情况:

数百位时,余数等于1;我们应该增加100-123这24个数字中百位上的1,共计24个;

在上面的计算中我们发现123/1000=0包含0个1000,所以百位包含0*100个1,这是常规的情况,实际上由于百位为1,从100到n(123)中还应增加:123-100+1个1.

总结上面的情况:就是对于每一位(个位,十位,百位),我们计算他们“通常”情况下(即该数字包含多少个10,100,1000乘以对应的1的个数)包含的1的个数+该位上余数大于1(等于1)的情况下包含的1的个数 = 该位上1的总个数,所有的位遍历,求和,就OK了。根据这种思路我们可以得到如下的代码:

1 #include<iostream>

2 #include<string>

3 using namespace std;

4

5 int NumbersOf1sFrom1ToN(unsigned int n)

6 {

7 int currentN = n;

8

9 //计数器

10 int cnt = 0;

11

12 //商,计算该数字包含多少个10,100,1000等

13 int quotient = 0;

14

15 //余数,计算除去“整”的包含,剩下的数字包含的1的个数

16 int remainder = 0;

17

18 //每一轮循环中的权重,分别记录10,100,1000中包含多少个位1,十位1,百位1;

19 int mult = 1;

20

21 while(currentN)

22 {

23 quotient = currentN / 10;

24 remainder = currentN % 10;

25

26 //包含多少个10,100,1000,乘以对应的数量的个位1,十位1,百位1

27 cnt += quotient * mult;

28

29 //余数大于1,多加一个该轮下的权重

30 if(remainder > 1)

31 {

32 cnt += mult;

33 }

34 //余数等于1

35 else if(remainder == 1)

36 {

37 cnt += n - currentN * mult + 1;

38 }

39

40

41 currentN = currentN / 10;

42 mult *= 10;

43 }

44

45 return cnt;

46 }

47

48 int main()

49 {

50 cout<<"please enter the number N:"<<endl;

51 unsigned int number = 0;

52 cin>>number;

53

54 cout<<"the number of 1s From 1 to N is:"<<endl;

55 cout<<NumbersOf1sFrom1ToN(number)<<endl;

56

57 return 0;

58 }

原文链接:http://www.wumii.com/item/CSysvSvq

作者:zihua | 分类: python | 标签: python | 阅读: 844 | 发布于: 2014-01-20 23时 |