文件名称：排列数问题
文件大小：602KB
文件格式：PPT
更新时间：2015-12-03 16:28:48
字典排列数字
对于一个m位整数，我们可以把0到n之间的n+1个整数从小到大这样来排列： 000......0 ............. 199......9 200......0 299......9 ......... 这样一直排到自然数n。对于从0到199......9这个区间来说，抛去最高位的数字不看，其低m-1位恰好 就是m-1个0到m-1个9共10^(m-1)个数。利用原著中的递推公式，在这个区间里，每个数字出现的次数 （不包括最高位数字）为(m-1)*10^(m-2)。假设n的最高位数字是x，那么在n之间上述所说的区间共有 x个。那么每个数字出现的次数x倍就可以统计完这些区间。再看最高位数字的情况，显然0到x-1这些 数字在最高位上再现的次数为10^(m-1)，因为一个区间长度为10^(m-1)。而x在最高位上出现次数就是 n^(m-1)+1了。接下来对n^(m-1)，即n去掉最高位后的那个数字再继续重复上面的方法。直到 个位，就可以完成题目要求了。 比如，对于一个数字34567，我们可以这样来计算从1到34567之间所有数字中每个数字出现的次数： 从0到9999，这个区间的每个数字的出现次数可以使用原著中给出的递推公式，即每个数字出现4000次。 从10000到19999，中间除去万位的1不算，又是一个从0000到9999的排列，这样的话，从0到34567之间 的这样的区间共有3个。所以从00000到29999之间除万位外每个数字出现次数为3*4000次。然后再统计 万位数字，每个区间长度为10000，所以0,1,2在万位上各出现10000次。而3则出现4567+1=4568次。 之后，抛掉万位数字，对于4567，再使用上面的方法计算，一直计算到个位即可。 import java.io.BufferedWriter; import java.io.FileWriter; import java.io.IOException; public class Arirgmetic { public static void main(String [] args) { long startTime = System.nanoTime(); int iTest; String fileName = "COUNT0.IN"; iTest = ReadFromFile.readFileByChars(fileName); Arith r = new Arith (); r.Arith(iTest); } }