集合A是个整数集｛1,2,...,n},定义集合B为从A中随机抽取n个数(每次抽取之后放回),求集合B中包含1的概率.因为每次抽取之后放回,所有A中所有数字被抽取的概率一样,任何一个元素都可能被抽取0,1,...,n 次.
求它的反面,也就是不包含1.也就是每次都抽不到1,所以是[（n-1）/n]^n,包含1的概率就是1-[（n-1）/n]^n
为您推荐：
其他类似问题
扫描下载二维码算法的时间复杂度是如何减少的
服务器君一共花费了90.272 ms进行了3次数据库查询，努力地为您提供了这个页面。
试试阅读模式？希望听取您的建议
给定一个十进制整数N，求出从1到N的所有整数中出现"1"的个数。
例如：N=2，1,2出现了1个"1"。
N=12，1,2,3,4,5,6,7,8,9,10,11,12。出现了5个"1"。
最直接的方法就是从1开始遍历到N，将其中每一个数中含有"1"的个数加起来，就得到了问题的解。
public long CountOne3(long n)
long i = 0,j = 1;
long count = 0;
for (i = 0; i &= i++)
while (j != 0)
if (j % 10 == 1)
j = j / 10;
此方法简单，容易理解，但它的问题是效率，时间复杂度为O（N * lgN），N比较大的时候，需要耗费很长的时间。
我们重新分析下这个问题，对于任意一个个位数n，只要n>=1,它就包含一个"1"；n&1，即n=0时，则包含的"1"的个数为0。于是我们考虑用分治的思想将任意一个n位数不断缩小规模***成许多个个位数，这样求解就很方便。
但是，我们该如何降低规模？仔细分析，我们会发现，任意一个n位数中"1"的个位可以***为两个n-1位数中"1"的个数的和加上一个与最高位数相关的常数C。例如，f(12) = f(10 - 1) + f(12 - 10) + 3,其中3是表示最高位为1的数字个数，这里就是10,11,12；f(132)=f(100 -1) + f(132 - 100) + 33，33代表最高位为1的数字的个数，这里就是100~132；f(232) = 2*f(100 - 1) + f(32) + 100，因为232大于199，所以它包括了所有最高位为1的数字即100~199，共100个。
综上，我们分析得出，最后加的常数C只跟最高位n1是否为1有关，当最高位为1时，常数C为原数字N去掉最高位后剩下的数字+1，当最高位为1时，常数C为10bit，其中bit为N的位数-1，如N=12时，bit=1，N=232时，bit=2。
于是，我们可以列出递归方程如下：
if(n1 == 1)
f(n) = f(10bit-1) + f(n - 10bit)
+ n - 10bit+ 1;
f(n) = n1*f(10bit-1) + f(n - n1*10bit) + 10bit;
递归的出口条件为：
if(1&n&10)
else if (n == 0) return 0;
基于此，编写如下代码：
public long CountOne(long n)
long count = 0;
if (n == 0)
count = 0;
else if (n > 1 && n & 10)
long highest =//表示最高位的数字
int bit = 0;
while (highest >= 10)
highest = highest / 10;
int weight = (int)Math.Pow(10, bit);//代表最高位的权重，即最高位一个1代表的大小
if (highest == 1)
count = CountOne(weight - 1)
+ CountOne(n - weight)
+ n - weight + 1;
count = highest * CountOne(weight - 1)
+ CountOne(n - highest * weight)
此算法的优点是不用遍历1~N就可以得到f(N)。经过我测试，此算法的运算速度比解法一快了许多许多，数字在1010内时，算法都可以在毫秒级内结束，而解法一在计算109时，时间超过了5分钟。但此算法有一个显著的缺点就是当数字超过1010时会导致堆栈溢出，无法计算。
还有就是，我尝试了许久也没有计算出此算法的时间复杂度到底是多少，似乎是O（lg2N），我并不确定，希望知道的高手能给予解答。
解法二告诉我们1~ N中"1"的个数跟最高位有关，那我们换个角度思考，给定一个N，我们分析1~N中的数在每一位上出现1的次数的和，看看每一位上"1"出现的个数的和由什么决定。
1位数的情况：在解法二中已经分析过，大于等于1的时候，有1个，小于1就没有。
2位数的情况：N=13,个位数出现的1的次数为2，分别为1和11，十位数出现1的次数为4，分别为10,11,12,13，所以f(N) = 2+4。N=23,个位数出现的1的次数为3，分别为1，11，21，十位数出现1的次数为10，分别为10~19，f(N)=3+10。
由此我们发现，个位数出现1的次数不仅和个位数有关，和十位数也有关，如果个位数大于等于1，则个位数出现1的次数为十位数的数字加1；如果个位数为0，个位数出现1的次数等于十位数数字。而十位数上出现1的次数也不仅和十位数相关，也和个位数相关：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1，假如十位数大于1，则十位数上出现1的次数为10。
3位数的情况：
N=123，个位出现1的个数为13:1,11,21，…，91,101,111,121。十位出现1的个数为20:10~19,110~119。百位出现1的个数为24:100~123。
我们可以继续分析4位数，5位数，推导出下面一般情况： 假设N，我们要计算百位上出现1的次数，将由三部分决定：百位上的数字，百位以上的数字，百位一下的数字。
如果百位上的数字为0，则百位上出现1的次数仅由更高位决定，比如12013，百位出现1的情况为100~199,00~2199，…，，共1200个。等于更高位数字乘以当前位数，即12 * 100。
如果百位上的数字大于1，则百位上出现1的次数仅由更高位决定，比如12213，百位出现1的情况为100~199,00~2199，…，，共1300个。等于更高位数字加1乘以当前位数，即（12 + 1）*100。
如果百位上的数字为1，则百位上出现1的次数不仅受更高位影响，还受低位影响。例如12113，受高位影响出现1的情况：100~199,00~2199，…，，共1200个，但它还受低位影响，出现1的情况是，共114个，等于低位数字113+1。
综合以上分析，写出如下代码：
public long CountOne2(long n)
long count = 0;
long i = 1;
long current = 0,after = 0,before = 0;
while((n / i) != 0)
current = (n / i) % 10;
before = n / (i * 10);
after = n - (n / i) *
if (current > 1)
count = count + (before + 1) *
else if (current == 0)
count = count + before *
else if(current == 1)
count = count + before * i + after + 1;
i = i * 10;
此算法的时间复杂度仅为O(lgN)，且没有递归保存现场的消耗和堆栈溢出的问题。
本文地址：，欢迎访问原出处。
不打个分吗？
转载随意，但请带上本文地址：
如果你认为这篇文章值得更多人阅读，欢迎使用下面的分享功能。
小提示：您可以按快捷键 Ctrl + D，或点此 。
大家都在看
阅读一百本计算机著作吧，少年
吴军 (作者)
近一百多年来，总有一些公司很幸运地、有意识或无意识地站在技术革命的浪尖之上。在长达十年甚至几十年的时间里，它们代表着科技的浪潮，直到下一波浪潮的来临。从19世纪末算起，AT&T公司、IBM公司、苹果公司、英特尔公司、微软公司、思科公司、雅虎公司和Google公司都先后被幸运地推到了浪尖。虽然，它们来自不同的领域，中间有些已经衰落或正在衰落，但是它们都极度辉煌过。吴军的这本《浪潮之巅》系统地介绍了这些公司成功的本质原因及科技工业一百多年的发展。在这些公司兴衰的背后，有着它必然的规律。《浪潮之巅》不仅讲述科技工业的历史，更重在揭示它的规律性。
扫一扫，在手机上阅读
栏目最新博文
19,766 views
13,750 views
14,770 views
15,426 views
14,882 views
14,854 views
10,075 views
9,605 views
12,268 views
12,281 views
栏目博文推荐
5,793 views
6,490 views
13,750 views
5,526 views
14,854 views
4,249 views
3,939 views
12,808 views
10,075 views
11,591 views
学习的本质是为了解决问题。
1,179 views
关于网站与作者
互联网信息太多太杂，各互联网公司不断推送娱乐花边新闻，SNS，微博不断转移我们的注意力。但是，我们的时间和精力却是有限的。这里是互联网浩瀚的海洋中的一座宁静与美丽的小岛，供开发者歇息与静心潜心修炼（愿景）。
“Veda”的本义是知识、启示，希望这里能为开发者提供充足的技术资料。
我的电子邮件gonnsai(，腾讯微博：，欢迎与我联系。在1-9中最多能排出多少个数,使得这些数中没有一个数是另一个数的整数倍
暗刃骑士丹
为您推荐：
其他类似问题
扫描下载二维码