2字典序问题
1.1 算法
设计思想
对于以字母i开头,长度为k的升序字符串,假设其个数为f(i,k),又假设长 度为k的升序字符串总个数为g(k),则g(k)与f(i,k)存在一个函数关系,即g (k)=f(1,k)+f(2,k)+f(3,k)+ … +f(27-k,k)。而f(i,k)也存在一条公 式:f(i,k)=f(i+1,k-1)+f(i+2,k-1)+ … +f(28-k,k-1),因此f(i,k) 的计算可以通过一个递归来实现,只要能求出g(k)和f(i,k),便可使用上述的解 题思路对任何升序字符串进行求解。
1.2 程序源码
import java.io.*; import java.util.Scanner; import java.text.SimpleDateFormat; import java.util.Date; public class Dictionary { //将输入的字符串转化为字符数组 private char[] converse(String input){ if(input.length()<1||input.length()>6){ return null; } char[]chars=input.toCharArray(); for(int i=chars.length-1;i>0;i--){ if(chars[i]
return c-'a'+1; } //f(i,k)计算以编号为i的字母开头,长度为k的升序字符串个数 private int f(int i,int k){ int sum=0; if(k==1){ return 1; } for(int j=i+1;j<=28-k;j++){ sum+=f(j,k-1); } return sum; } //g(k)用于计算长度为k的字符串组合数 private int g(int k){ int sum=0; for(int i=1;i<=27-k;i++){ sum+=f(i,k); } return sum; }
//计算编号的主方法,参数为待求升序字符串 public int getOrder(String input){ int order=0; char[] chars; if((chars=converse(input))==null){ return -1; } int len=chars.length; //求长度小于待求字符串的所有组合个数 for(int k=1;k order+=g(k); } //求长度等于len,首字母小于待求字符串首字母的组合个数 for(int i=1;i public static void main(String[]args){ System.out.println("实验一 算法的分析基础"); System.out.print("\n"); System.out.println("题目:统计数字问题"); System.out.println(":李勇 System.out.print("\n"); //计时开始的时候 long startTime = System.nanoTime(); Dictionary dr=new Dictionary(); int num = 0; String input[] = null; int order[]; :1007092105");
try{ //打开指定路径下文件 FileReader in=new FileReader ("ENCODE.IN"); BufferedReader a= new BufferedReader(in);
num = Integer.parseInt(a.readLine()); input= new String[num+1]; for(int i=0;i<=num;i++){ input[i]=a.readLine(); } a.close(); in.close();
order = new int[num]; for(int i = 0; i ("本次程序运行耗时 " + (endTime-startTime)/1000 + " us" );
SimpleDateFormat time = new SimpleDateFormat (" yyyy-MM-dd HH:mm:ss");//设置日期格式 System.out.println(time.format(new Date())); } catch(IOException e){ System.out.println(e); } }
1.3 实验结论(结果验证)
1.4 心得体会
}