编程求n的阶乘 n 这个数有多少个09

来源：蜘蛛抓取(WebSpider) 时间：2016-12-11 14:50 标签： 编程求n的阶乘
&编程之美&计算0到N中包含数字1的个数[转]
有这样一个函数f(n),对于任意正整数n,它表示从 0 到
n 之间出现“1”的个数,比如 f(1) = 1, f(13) = 6,请列出从 1 到
中所有的 f(n) =
n 的n, 要求准确快速.
相信很多人都能立刻得出以下的解法：
&&for(n:N)
&&&&&&&&&&判断n包含1的个数；
&&&&&&&&&&累加计数器；
这是最直接的解法，但遗憾的是，时间复杂程度为O(N*logN)。因为还需要循环判断当前的n的各位数，该判断的时间复杂程度为O(logN)。
接下来就应该思考效率更高的解法了。说实话，这道题让我想起另外一道简单的算法题：
N为正整数，计算从1到N的整数和。
很多人都采用了循环求解。然后利用初等数学知识就知道S=N*(N+1)/2，所以用O(1)的时间就可以处理。
再回到本道题目，同理应该去寻找到结果R与N之间的映射关系。
分析如下：
假设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] =
当a[1]=1时，c[1] =
当a[1]&1时，c[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);
编程之美之1的数目
&&&309views
给定一个十进制正整数 N，写下从
1 开始，到 N 的所有整数，
然后数一下其中出现的所有“1”的个数。
N= 2，写下
1，2。这样只出现了 1 个“1”。
N= 12，我们会写下 1, 2,
3, 4, 5, 6, 7, 8, 9, 10, 11, 12。这样，1的个数是 5。
写一个函数f(N)
返回1到N之间出现的“1”的个数,比如f(12)=5。
这个问题看上去并不是一个困难的问题，因为不需要太多的思考，大家都能找到一个最简单的方法来计算
f（N），那就
是从1开始遍历到N,将其中每一个数中含有“1”的个数加起来，
自然就得到了从1到N所有“1”的个数的和.C语言实现如下:
int&Count1(int&n)
&&&&int&iNum=0;
&&&&while(n!=0)
&&&&&&&&iNum+=(n==1)?1:0;
&&&&&&&&n/=10;
&&&&&&&&&&&&&&
&&&&return&iN
int&Count2(int&n)
&&&&int&iCount=0;
&&&&for(int&i=0;i&=n;i++)
&&&&&&&&iCount+=Count1(i);
&&&&return&iC&
int&main()
&&&&&int&x;
&&&&&scanf("%d",&x);
&&&&&printf("%d",Count2(x));
&&&&&return&0;
但是这个算法的致命问题是效率，它的时间复杂度是O（N）&计算一个整数数字里面“1”的个数的复杂度
= O（N *log2 N）,如果给定的 N
比较大，则需要很长的运算时间才能得到计算结果。我试着输入,一共用了大概12秒,貌似有点长,不够比作者说的40S快多了,作者的电脑有点旧…….-
&编程之美&先从一些简单的情况开始观察:
如果N是一位数,可以确定f(N)=1
如过是二位数,如果
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，所以 f（N）=2+4=6。要注意的是 11 这个数字在十位和个位都出现了 1， 但是 11 恰好在个位为 1 和十位为 1
中被计算了两次，所以不用特殊处理，是对的。再考虑 N=23 的情况，它和 N=13 有点不同，十位出现 1 的次数为 10 次，从
10 到 19，个位出现 1 的次数为 1、11 和 21，所以f（N）=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 =
接着分析 3
个位出现 1 的个数为 13：1,
11, 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 位数、
位数。&&&根据上面的一些尝试，下面我们推导出一般情况下，从
f（N）的计算方法：&假设 N=abcde，这里 a、b、c、d、e 分别是十进制数 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
个，等于低位数字（123）+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）。通过上面的归纳和总结，我们可以写出如下的更高效算法来
int&Sumls(int&n)
&&&&int&iCount=0,iFactor=1,iLowerNum=0,iCurrNum=0,iHigherNum=0;
&&&&while(n/iFactor!=0)
&&&&&&&&iLowerNum=n-(n/iFactor)*iF
&&&&&&&&iCurrNum=(n/iFactor);
&&&&&&&&iHigherNum=n/(iFactor*10);
&&&&&&&&switch(iCurrNum)
&&&&&&&&&&&&case&0:
&&&&&&&&&&&&&&&&iCount+=iHigherNum*iF
&&&&&&&&&&&&&&&&
&&&&&&&&&&&&case&1:
&&&&&&&&&&&&&&&&iCount+=iHigherNum*iFactor+iLowerNum+1;
&&&&&&&&&&&&&&&&
&&&&&&&&&&&&default:
&&&&&&&&&&&&&&&&iCount+=(iHigherNum+1)*iF
&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&iFactor*=10;
&&&&return&iC&
int&main()
&&&&int&x;
&&&&scanf("%d",&x);&&&
&&&&printf("%d",Sumls(x));
&&&&return&0;
我试着输入瞬间就显示出结果了,编程之美说效率至少提高了40000倍…
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。【图文】09_N进制编程_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
09_N进制编程
上传于||暂无简介
大小：781.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢c语言编程问题,计算出从n 个不同元素中取出m 个元素(m≤n)的排列数｡有道题需要这个函数,百度了好久,也没有找到合适的代码,而且好多都看不明白.还请高人给个算法,并且加上注释,好的话追加分数.
不是很理解你的问题,给举个例子.
C(5,3)=10。
这咱们都知道，我需要的是用程序实现这个。
int c(int n, int m)
if(m=n） return 1;
int res=1;
int fin=m;
for(int i=0;i<i++,n--)
for(int j=0;j<j++,m--)
res=res/m;
为您推荐：
其他类似问题
扫描下载二维码

我要回帖

更多关于 编程求n的阶乘 的文章

 

随机推荐