广工顾国生软件算法作业.docVIP

评定等级 算法作业 学生学院____ ____________ 专业班级___ _____ 学 号____ ________ 学生姓名____ ____________ 指导教师____顾国生____________ 2011 年 11 月 1、Johnson-Trotter算法 1.1关于Johnson-Trotter的介绍 Johnson-Trotter算法又称为字典序法，对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。 [注意] 一个全排列可看做一个字符串，字符串可有前缀、后缀…..n】的所有排列的列表。 1.3实验分析 字典序如下： 　　设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn 　　1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pipi+1} 　　2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pipj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者） 　　3）对换pi，pk 　　4）再将pj+1......pk-1pkpk+1......pn倒转得到排列p=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。package JohnsonTrotter; import java.io.*; import java.util.*; class JohnsonTrotter2{ public static void main(String args[])throws IOException { System.out.println(输入n：); BufferedReader in = new BufferedReader(new InputStreamReader(System.in));//设置输入缓冲流来加快运算速度 String s; int n=0; while((s = (in.readLine()).trim())== null ||s.length()==0) { System.out.println(请输入非空的字符串); if(s.length()=1) break; } try { n=Integer.parseInt(s); } catch(Exception e){ System.out.println(e.toString()); s=null; } int []li=new int[n+1]; int []ji=new int[n+1]; li[0]=n; for(int i=1;i=n;i++) { System.out.println(第+i+个数为：); in = new BufferedReader(new InputStreamReader(System.in)); int m=0; while((s = (in.readLine()).trim())== null ||s.length()==0) { System.out.println(请输入非空的字符串); if(s.length()=1) break; } try { m=Integer.parseInt(s); } catch(Exception e){ System.out.println(e.toString()); s=null; } li[i]=m; } int sum=1; for(int j=1;j=n;j++) ji[j]=li[n-j+1]; //开始全排列 int index=-1; int min=-1; int flag=-1; int minShu=-1; int count=0; JohnsonTrotter2 hh=new JohnsonTrotter2(); for(int f