求助一个求整数1到n中数字1的个数的程序

Violet_fei 2011-10-23 07:55:40

例：1个13中1的个数是6个。菜鸟求思路。

...全文

653 17 打赏收藏转发到动态举报

写回复

用AI写文章

17 条回复

切换为时间正序

请发表友善的回复…

发表回复

AndyZhang 2011-10-24

打赏
举报

给个解释巨清晰的吧，看来大学学的概率与统计没有白学啊。

最清晰直观的做法，就是遍历这N个数，便利N个数中的数位，累计求出1出现的次数；至于所谓的递归，没去看，也懒得去看；这里，我们先分析下这些阿拉伯数字的规律，然后根据出现1的概率来进行求解：
(1) 当n=9时，我们考虑0,1,2...9(共10个数字)，我们不难得出结论：字符'0','1'...'9'出现的概率个占1/10(即0.1);
(2) 当n=99时，我们考虑0,1,2...99(共100个数字)，十位上，'1'出现的概率个占1/10;个位上，'1'出现的概率也为1/10, 于是1出现的次数=0.1*100 + 0.1 * 100 = 20;
(3) 当n=100000000时，我们考虑0,1,2...100000000(共100000001个数字)，最高位上，'1'只可能出现1次;其余各位上，'1'出现的概率各占1/10, 于是1出现的次数=1 + (0.1*8) * 100000000 = 80000001;

当然，上面都是列举的最简单的例子，但我们不难看出，'1'的出现概率的确是存在规律的。下面我们来看更复杂的例子('0','1'...'9'，下面统称为阿拉伯数字符)：设n=XYZ(其中X、Z表示零个或多个阿拉伯数字符，Y为一个阿拉伯数字)，这样XYZ就可以表示任意数字了，例如n=5可以表示为：X=Z="",Y=5；n=123456可以表示成:X="",Y=1,Z=23456或X=12345,Y=6,Z=""等6种方式。
这里我取这种表达方式，是为了从Y上得出一个通用的统计字符出现概率的计算方法。Y为一个阿拉伯数字，所以其只能取0,1...9中的一个数字，其存在如下三种可能：
(1) Y<1
(2) Y=1
(3) Y>1

以n=123Y45(X=123，Y在百位上，可以任意取值，Z=45)来分别讨论上面的三种情况：
(1) Y<1：(此时Y只能取0值了)，我们可以把区间[0..n]中的n+1个数分成两段区间来分析，[000000..122999]，即[000000..122999]，即[000000...(X-1)999]，
[123000..123045]，即[X000..XYZ]，
其中第一段区间中Y位(百位)上，共(X * Pow(10, Length(Z)+1))个数字，出现'1'的概率占1/10，而第二段区间中，Y位上出现'1'的概率为0，因此可以得出结论：Y<1时，'1'在该位上出现的数量=0.1 * (X * Pow(10, Length(Z)+1))；

(2) Y=1：(此时Y只能取1值了)，我们可以把区间[0..n]中的n+1个数分成三段区间来分析，[000000..122999]，即[000000..122999]，同(1)，Y位上出现'1'的概率为1/10；
[123000..123099]，即[X000..X099]，同(1)，Y为上出现'1'的概率为0；
[123100..123145]，即[XY00..XYZ]，Y上出现'1'的概念为1，此区间工(Z+1)个数字
因此可以得出结论：Y=1时，'1'在该位上出现的数量=0.1 * (X * Pow(10, Length(Z)+1)) + (Z + 1)；

(3) Y>1：(此时Y只能取2..9中的任意一个值了)，我们可以把区间[0..n]中的n+1个数分成四段区间来分析，
[000000..122999]，即[000000..(X-1)999]，同(1)，Y位上出现'1'的概率为1/10；
[123000..123099]，即[X000..X099]，同(1)，Y位上出现'1'的概率为0；
[123100..123199]，即[X100..X199]，Y上出现'1'的概念为1，此区间共Pow(10, Length(Z))个数字；
[123200..123Y45]，即[X200..XYZ]，此时Y恒大于0，Y位上出现'1'的概率为0；
因此可以得出结论：Y>1时，'1'在该位上出现的数量=0.1 * (X * Pow(10, Length(Z)+1)) + Pow(10, Length(Z))；

通过对上面3种情况的分析，我们可以看出，对于任意给定的整数n，我们都可以拆分成XYZ形式，并计算出Y位上'1'出现的数量；将Y从最高向最低位(个位)移动，可以计算出每位上'1'出现的数量，累计求和即为原题中要求的结果。

AndyZhang 2011-10-24

打赏
举报

假设N表示为a[n]a[n-1]...a[1]，其中a[i](1<=i<=n)表示N的各位数上的数字。

c[i]表示从整数1到整数a[i]...a[1]中包含数字1的个数。

x[i]表示从整数1到10^i - 1中包含数字1的个数，例如，x[1]表示从1到9的个数，结果为1；x[2]表示从1到99的个数，结果为20；

当a[1]=0时，c[1] = 0;

当a[1]=1时，c[1] = 1;

当a[1]>1时，c[1] = 1;

当a[2]=1时，c[2] = a[1] +1+ c[1] + x[1];

当a[2]>1时，c[2] = a[2]*x[1]+c[1]+10;

当a[3]=1时，c[3] = a[2]*a[1] +1+ c[2] + x[2];

当a[3]>1时，c[3] = a[3]*x[2]+c[2]+10^2;

......

以此类推

当a[i]=1时，c[i] = a[i-1]*...*a[1] +1+ c[i-1]+x[i-1];

当a[i]>1时，c[i] = a[i]x[i-1]+c[i-1]+10^(i-1);



public static int search(int _n)      

{      

    int N = _n/10;      

    int a1 = _n%10,a2;      

    int x = 1;   

    int ten = 10;   

    int c = a1 == 0?0:1;   

    while(N > 0)      

    {      

        a2 = N%10;   

        if(a2 == 0);   

        else if(a2 == 1)c = a1 + 1 + x + c;      

        else c = a2*x + c + ten;      

        a1 = 10*a1 + a2;        

        N /=10;      

        x = 10*x + ten;   

        ten *= 10;    

    }      

    return c;      

}

AndyZhang 2011-10-24

打赏
举报

不是要O(1)的算法吗？

proorck6 2011-10-24

打赏
举报

把数字打印到一个数组里（或文件里）
sprintf(s,"%d",n);
然后在字符串s中求1的个数。
sscanf(s,"%",&x);
if(x=='1'){count++;}
大概就是这样。
代码你再调调。

小清新爱大光明 2011-10-24

打赏
举报

#include <iostream>
using namespace std;

long Count1(long n)
{
long nNum = 0;

while(0 != n)
{
nNum += (1 == n%10 ? 1:0);
n /= 10;
}

return nNum;
}

int main()
{
long n,iNum = 0;
cout<<"input n: ";
cin>>n;

while(n)
{
iNum += Count1(n);
n--;
}

cout<<iNum<<endl;

return 0;
}

qq120848369 2011-10-24

打赏
举报

自己看编程之美，上边真的有。

Violet_fei 2011-10-23

打赏
举报

谢谢指点
[Quote=引用 4 楼 tujiaw 的回复:]
C/C++ code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int GetOneCount(int x)
{
char szNum[32] = {0};

itoa(x, szNum, 10);
int nCount = strlen(szNum);
int ……
[/Quote]

Violet_fei 2011-10-23

打赏
举报

谢谢指点
[Quote=引用 3 楼 pathuang68 的回复:]
参考：

C/C++ code

#include <iostream>
using namespace std;

int func(int x)
{
int countx = 0;
while (x)
{
countx++;
x=x&(x-1);
}
return countx;
}……
[/Quote]

Violet_fei 2011-10-23

打赏
举报

没看过，最近才开始攻编程，谢指点。
[Quote=引用 6 楼 jietoulangren 的回复:]
LZ看过《编程之美》没？这是其中一道
《编程之美》是微软的面试题
[/Quote]

孤独小剑 2011-10-23

打赏
举报

两外2楼和4楼应该那种思路应该是穷举法能算出来答案，3楼是求一个数二进制表示的时候1的个数好像和本题提问的答案不一样。

Violet_fei 2011-10-23

打赏
举报

厉害，啥时候我能随手写出这个呢。
[Quote=引用 2 楼 keiy 的回复:]
随手写一个,供参考

C/C++ code

#include <stdio.h>
#include <stdlib.h>
int count1(int n)
{
int ct=0;
while(n>0)
{
if (n%10==1)
ct++;
n/=10;
}
return ct;
}
int mai……
[/Quote]

JieTouLangRen 2011-10-23

打赏
举报

LZ看过《编程之美》没？这是其中一道
《编程之美》是微软的面试题

孤独小剑 2011-10-23

打赏
举报

我觉得这个问题应该是有规律的，找到规律在变成能降低很多复杂度。
首先对这个例子14来说，可以这样拆分：十位是1的情况各位有0、1、2、3四个情况的四个数（因为其组成的数还是要小于等于13），各位是1的情况，其十位有0、1两种情况的两个数，所以答案为4+2=6个。可以按照这种思路找其他的数然后总结规律，应该可以找到一个更节省复杂度的算法来计算答案。

ningto.com 2011-10-23

打赏
举报



#include <stdio.h>

#include <stdlib.h>

#include <string.h>



int GetOneCount(int x)

{

	char szNum[32] = {0};



	itoa(x, szNum, 10);

	int nCount = strlen(szNum);

	int nRet = 0;



	while (nCount--)

	{

		if (x % 10 == 1)

		{

			nRet++;

		}

		x /= 10;

	}



	return nRet;

}



int main(int argc, char *argv[])

{

	int nEnd = 13;

	int nSum = 0;



	for (int i = 1; i <= nEnd; i++)

	{

		nSum += GetOneCount(i);

	}



	printf("1的个数（1~%d）：%d\n", nEnd, nSum);



	return 0;

}

pathuang68 2011-10-23

打赏
举报

参考：



#include <iostream>

using namespace std;



int func(int x)

{

    int countx = 0;

    while (x)

    {

        countx++;

        x=x&(x-1);

    }

    return countx;

}



int main()

{

	int n = 0;

	cin >> n;



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

	{

		cout << i << "的二进制中，1的个数为：\t" << func(i) << endl;

	}

    return 0;

}

柯本 2011-10-23

打赏
举报

随手写一个,供参考



#include <stdio.h>

#include <stdlib.h>

int count1(int n)

{

 int ct=0;

 while(n>0)

   {

      if (n%10==1)

        ct++;

      n/=10;

   }

  return ct;

}

int main()

{

   int i,n,ct=0;

   printf("Please input a number:\n");

   scanf("%d",&n);

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

     ct+=count1(i);

   printf("%d\n",ct);

   system("pause");

        return 0;

}

//---------------------------------------------------------------------------