引言 我们可以把{1,2,3,4,…,n}的n!个全排列按照字典序从小到大列出，例如对n=3而言，我们可以得到： 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 现在给出{1,2,3,4,…,n}的一个全排列，问这个全排列按字典序是第几小的？ 逆康托展开 设p[0],p[1],…,p[n-1]是{1,2,…,n}的一个全排列。 令c[k]表示比p[k],p[k+1],…,p[n-1]小的{p[k],p[k+1],…,p[n-1]}的全排列的个数。 则c[0]+1便是我们要求的。 比p[k],p[k+1],…,p[n-1]小的全排列有两种类型，第一种是第一位小于p[k]的，第二种是第一位等于p[k]的，对于
引言 如果一个自然数的每位数字的立方之和等于这个数本身，则称这个数为水仙花数。比如0,1,153。 寻找某个范围类的水仙花数的任务经常作为编程教学的练习题出现，现在我想做的是寻找全部的水仙花数。 水仙花数有有穷的 注意到，任何一个[math]n[/math]位的水仙花数[math]x=\sum_{k=0}^{k=n-1}{a_k{10^k}}[/math]，根据定义，都有[math]x=a_0^3+a_1^3+\ldots+a_{n-1}^3\leq9^3+9^3+\ldots+9^3=n9^3[/math]，另一方面，由于[math]x[/math]是一个[math]n[/math]位数，所以必然有[math]x\geq10^{n-1}[/math]，这样我们便得到： [math]n9^3\
问题 设[math]S=x_1y_1+x_2y_2+\ldots +x_ny_n[/math]，其中[math]x_1,x2,\ldots ,x_n[/math]和[math]y_1,y_2,\ldots ,y_n[/math]分别是两个正实数序列，各自有[math]n[/math]个元素。 证明： 在这两个序列的所有排列中，当两个系列都排序（非降序排序）时，[math]S[/math]取最大值。 在这两个序列的所有排列中，当一个序列排成非降序，另一个序列排成非升序时，[math]S[/math]取最小值。 证明 不失一般性，这里只证明问题(1)，问题(2)类似。 假设[math]x_1,x2,\ldots ,x_n[/math]和[math]y_1,y_2,\ldots ,y_n[/math]都已按不降序排列
问题 在黑板上写数字1,2,…,2n，其中n是奇数，从中挑出两个数j和k，在黑板上写|j-k|并擦掉j和k。继续这个过程，直到黑板上只写一个整数为止。证明：这个整数必为奇数。 证明 假设现在黑板上有[math]x[/math]个奇数和[math]y[/math]个偶数，我们任意挑出两个数[math]j,k[/math]。 如果这两个数都为奇数，那么[math]|j-k|[/math]为偶数，那么在写上新数并擦掉旧数后，黑板上将有[math]x-2[/math]个奇数，[math]y+1[/math]个偶数。 如果这两个数都为偶数，那么[math]|j-k|[/math]为偶数，那么在写上新数并擦掉旧数后，黑板上将有[ma
引言 初中生便可以做出[math]\sqrt2[/math]是无理数的证明，而我们都知道[math]\sqrt3[/math]，[math]\sqrt5[/math]是无理数，一般的，对于正整数[math]n[/math]，我们都默认[math]\sqrt{n}[/math]是无理数，除了那些特别的被称为完全平方数的正整数，比如1,4,9,16,25。现在要求对这个默认的假设做出证明。 问题 [math]n[/math]是一个不是完全平方数的正整数，求证[math]\sqrt{n}[/math]是无理数。 证明 我们知道完全平方数的算术平方根是整数，而非完全平方整数的平方根如果是有理数，那么一定是分数，所以要证明原命题，我们只需要证
问题简述 给出十进制整数N和B （0<=N<=220，1<B<=800），求N!在B进制表示下的位数与末尾0的个数。 分析 一个数[math]x[/math]在[math]B[/math]进制下的位数等于： [math]1+\lfloor log_{B}x \rfloor[/math] 考虑到[math]N!=1\cdot2\cdot3\cdot4\cdot\ldots\cdotN[/math]，所以其位数可以分解为： [math]1+\lfloor \sum_{i=1}^{N}{log_{B}i} \rfloor[/math] 任意进制下阶乘末尾零的求法，与求十进制下N!末尾零的求法[1]是相似的。 在十进制下，一个数末尾的零对应于它可以被因数分解为多少个10，同样的，一个B进制数的末尾
问题简述 一些数在某些进制下可能具有“轮换乘法”性质，这是说这个数与某乘数相乘的结果等于将这个数的末位移动到首位。 下面是两个例子： 179487 * 4 = 717948，这是十进制下的例子。 17 * 4 = 71 ，这是九进制下的例子。 现在给出进制B，乘数N在B进制下的末尾D，以及另一个乘数M （0<=M<B），求满足“轮换乘法”性质的乘数N的最小位数。（B进制下） 分析 假设我们的乘数有n位，从低位到高位分别为d[0],d[1],…,d[n-1]，我们让它与m相乘，结果如下表所示： d[n-1] d[n-2] … d[2] d[1] d[0] &nbs
问题简述 给出一组N(0<=N<=10000)，求N!的最右边的非零数字。比如5!=120，那么答案就为2。 分析 我们用f[n]保存n!的末几位非零数，然后进行递推求解。先看看只保存一位是否可以，要通过f[n-1]求解n，如果nf[n-1]末尾没有0，那么显然f[n]就等于nf[n-1]的最末位，这是因为乘积的最末位只由乘数的最末位决定，但是当nf[n-1]有一个尾0的时候就行不通了，因为要得知f[n]，也就是要得知n!的最末非零数，我们需要知道乘数的末两位，而f[n-1]只保存了末一位。如果f[n]保存末两位，则当nf[n-1]有两个尾0时便行不通了，而由于n最大为10000，
计算N!的末尾有多少个0是一个经典的问题，其解法蕴含了数论问题中的一种基本思路。 我们将N!做质因子分解：[math]N!=2^{X}3^{Y}5^{Z}\ldots[/math] N!中的末尾0个数实际就是乘积为10的个数，而10=2*5，所以末尾0个数就是N!分解式中2和5的对数，我们知道偶数的个数远多于5的倍数的个数，所以2肯定是够用的，所以末尾0个数就等于分解式中5的个数。 所以： [math]ZERO(N!)=\lfloor\frac{N}{5}\rfloor+\lfloor\frac{N}{25}\rfloor+\lfloor\frac{N}{125}\rfloor+\ldots[/math] © 2012, Aikilis. 版权所有. 转载请注明出自http://aikil
问题简述 给出Z,I,M和L，每个都最大是一个四位数。现在不断执行L=(ZL+I) MOD M，我们知道从某一次开始会得到以前出现过的数，这样就形成了一个环，问这个环的长度是多少。 分析 特别需要注意的是，环不一定是从第一个L开始的。 用c表示已经生成了多少个数，用一个标记数组map[i]来记录i是否出现过，用len[i]记录i第一次出现时产生了多少个不同的数（包括i ),然后不断生成L，直到发现map[L]为真，也就是L已经出现过，这时c-len[L]+1就是环的长度。 代码 #include <stdio.h> #include <math.h> #define N (10000) int main()