`
nanjingjiangbiao_T
  • 浏览: 2587409 次
  • 来自: 深圳
文章分类
社区版块
存档分类
最新评论

用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列

 
阅读更多

用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连

这道笔试题相当的出名，我也有幸遇到了。确切的说这是一道算法题，像我这种离散，数据结构都半吊子的人实在拿它没撤，回来小发愤了一下，找到了多个不同的实现算法

第一个：

Java代码收藏代码
  1. packagecom.audition;
  2. //排序组合算法
  3. publicclassPermutationAlgo{
  4. privateintcount=0;
  6. publicvoidcalculate(){
  7. StringeleStr="122345";
  8. depthSearch(eleStr,"");
  9. System.out.println("符合条件的总结果数为:"+count+"条");
  10. }
  12. /**
  13. *@parameleStr-待分配字符组成的串
  14. *@paramrstStr-已分配字符组成的串
  15. */
  16. publicvoiddepthSearch(StringeleStr,StringrstStr){
  17. if(eleStr.length()==0){
  18. count++;
  19. System.out.println(rstStr);
  20. return;
  21. }
  22. for(inti=0;i<eleStr.length();i++){
  23. StringcurrEle=eleStr.substring(i,i+1);//取出当前位的值
  24. if(rstStr.length()==2&&"4".equals(currEle))continue;//剪掉第三位为4的分支
  25. if(rstStr.endsWith("3")&&"5".equals(currEle))continue;//剪掉"35"相连的分支
  26. if(rstStr.endsWith("5")&&"3".equals(currEle))continue;//剪掉"53"相连的分支
  27. if(eleStr.substring(0,i).indexOf(currEle)!=-1)continue;//剪掉同一位上字符重复的分支(此题即剪掉重复的2)
  28. depthSearch(eleStr.substring(0,i)+eleStr.substring(i+1),rstStr+currEle);//用剩余的合法串继续递归
  29. }
  30. }
  32. publicstaticvoidmain(String[]args){
  33. newPermutationAlgo().calculate();
  34. }
  35. }

第二个

Java代码收藏代码
  1. packagecom.audition;
  3. publicclassPermutationAlgo2{
  4. privatestaticintcount=0;
  5. publicstaticvoidmain(String[]args){
  6. //本题的思路是先用1,3,4,5进行全排列
  7. //后边再将另外两个2往里插入，并判断是否符合要求
  8. int[]arr={1,3,4,5};
  9. printCom(arr,0);
  10. System.out.printf("符合要求的排列共有%d种",count);
  11. }
  13. publicstaticvoidprintCom(int[]arr,intindex){
  14. if(index==arr.length-1){
  15. insertTwo(arr,0);
  16. return;
  17. }
  18. printCom(arr,index+1);
  19. for(inti=index+1;i<arr.length;i++){
  20. arr[index]^=arr[i];
  21. arr[i]^=arr[index];
  22. arr[index]^=arr[i];
  23. printCom(arr,index+1);
  24. arr[index]^=arr[i];
  25. arr[i]^=arr[index];
  26. arr[index]^=arr[i];
  27. }
  28. }
  30. //将2在符合要求的情况下插入数组
  31. privatestaticvoidinsertTwo(int[]arr,intindex){
  32. if(index==arr.length+1)
  33. return;
  34. for(inti=index+1;i<arr.length+2;i++){
  35. int[]tar=newint[arr.length+2];
  36. tar[i]=2;
  37. tar[index]=2;
  38. innerInsert(arr,tar);
  39. }
  40. insertTwo(arr,index+1);
  41. }
  43. privatestaticvoidinnerInsert(int[]arr,int[]tar){
  44. intindex=0;
  45. intindexArr=0;
  46. while(index<tar.length){
  47. if(tar[index]==0){
  48. if((index>0&&tar[index-1]+arr[indexArr]==8)
  49. ||(index==2&&arr[indexArr]==4))
  50. return;
  51. tar[index]=arr[indexArr++];
  52. }
  53. index++;
  54. }
  55. count++;
  56. System.out.printf("[%d]",count);
  57. for(inti=0;i<tar.length;i++){
  58. System.out.print(tar[i]+"");
  59. }
  60. if(count%5==0){
  61. System.out.println();
  62. }
  63. }
  65. }

第三个

Java代码收藏代码
  1. packagecom.audition;
  3. /**
  4. *用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"
  5. *不能相连。
  6. *
  7. *
  8. *@authorAdministrator
  9. *
  10. */
  11. publicclassPermutationAlgo3{
  12. privateint[]numbers=newint[]{1,2,2,3,4,5};
  13. publicintn;
  14. privateStringlastResult="";
  16. privatebooleanvalidate(Strings){
  17. if(s.compareTo(lastResult)<=0)
  18. returnfalse;
  19. if(s.charAt(2)=='4')
  20. returnfalse;
  21. if(s.indexOf("35")>=0||s.indexOf("53")>=0)
  22. returnfalse;
  23. returntrue;
  24. }
  26. publicvoidlist(Stringindex,Stringresult){
  27. for(inti=0;i<numbers.length;i++){
  28. if(index.indexOf(i+48)<0){
  29. Strings=result+String.valueOf(numbers[i]);
  30. if(s.length()==numbers.length){
  31. if(validate(s)){
  32. System.out.println(s);
  33. lastResult=s;
  34. n++;
  35. }
  36. break;
  37. }
  38. list(index+String.valueOf(i),s);
  39. }
  40. }
  41. }
  44. publicstaticvoidmain(String[]args){
  45. PermutationAlgo3algo3=newPermutationAlgo3();
  46. algo3.list("","");
  47. System.out.println("总数："+algo3.n);
  48. }
  49. }

用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连

这道笔试题相当的出名，我也有幸遇到了。确切的说这是一道算法题，像我这种离散，数据结构都半吊子的人实在拿它没撤，回来小发愤了一下，找到了多个不同的实现算法

第一个：

Java代码收藏代码
  1. packagecom.audition;
  2. //排序组合算法
  3. publicclassPermutationAlgo{
  4. privateintcount=0;
  6. publicvoidcalculate(){
  7. StringeleStr="122345";
  8. depthSearch(eleStr,"");
  9. System.out.println("符合条件的总结果数为:"+count+"条");
  10. }
  12. /**
  13. *@parameleStr-待分配字符组成的串
  14. *@paramrstStr-已分配字符组成的串
  15. */
  16. publicvoiddepthSearch(StringeleStr,StringrstStr){
  17. if(eleStr.length()==0){
  18. count++;
  19. System.out.println(rstStr);
  20. return;
  21. }
  22. for(inti=0;i<eleStr.length();i++){
  23. StringcurrEle=eleStr.substring(i,i+1);//取出当前位的值
  24. if(rstStr.length()==2&&"4".equals(currEle))continue;//剪掉第三位为4的分支
  25. if(rstStr.endsWith("3")&&"5".equals(currEle))continue;//剪掉"35"相连的分支
  26. if(rstStr.endsWith("5")&&"3".equals(currEle))continue;//剪掉"53"相连的分支
  27. if(eleStr.substring(0,i).indexOf(currEle)!=-1)continue;//剪掉同一位上字符重复的分支(此题即剪掉重复的2)
  28. depthSearch(eleStr.substring(0,i)+eleStr.substring(i+1),rstStr+currEle);//用剩余的合法串继续递归
  29. }
  30. }
  32. publicstaticvoidmain(String[]args){
  33. newPermutationAlgo().calculate();
  34. }
  35. }

第二个

Java代码收藏代码
  1. packagecom.audition;
  3. publicclassPermutationAlgo2{
  4. privatestaticintcount=0;
  5. publicstaticvoidmain(String[]args){
  6. //本题的思路是先用1,3,4,5进行全排列
  7. //后边再将另外两个2往里插入，并判断是否符合要求
  8. int[]arr={1,3,4,5};
  9. printCom(arr,0);
  10. System.out.printf("符合要求的排列共有%d种",count);
  11. }
  13. publicstaticvoidprintCom(int[]arr,intindex){
  14. if(index==arr.length-1){
  15. insertTwo(arr,0);
  16. return;
  17. }
  18. printCom(arr,index+1);
  19. for(inti=index+1;i<arr.length;i++){
  20. arr[index]^=arr[i];
  21. arr[i]^=arr[index];
  22. arr[index]^=arr[i];
  23. printCom(arr,index+1);
  24. arr[index]^=arr[i];
  25. arr[i]^=arr[index];
  26. arr[index]^=arr[i];
  27. }
  28. }
  30. //将2在符合要求的情况下插入数组
  31. privatestaticvoidinsertTwo(int[]arr,intindex){
  32. if(index==arr.length+1)
  33. return;
  34. for(inti=index+1;i<arr.length+2;i++){
  35. int[]tar=newint[arr.length+2];
  36. tar[i]=2;
  37. tar[index]=2;
  38. innerInsert(arr,tar);
  39. }
  40. insertTwo(arr,index+1);
  41. }
  43. privatestaticvoidinnerInsert(int[]arr,int[]tar){
  44. intindex=0;
  45. intindexArr=0;
  46. while(index<tar.length){
  47. if(tar[index]==0){
  48. if((index>0&&tar[index-1]+arr[indexArr]==8)
  49. ||(index==2&&arr[indexArr]==4))
  50. return;
  51. tar[index]=arr[indexArr++];
  52. }
  53. index++;
  54. }
  55. count++;
  56. System.out.printf("[%d]",count);
  57. for(inti=0;i<tar.length;i++){
  58. System.out.print(tar[i]+"");
  59. }
  60. if(count%5==0){
  61. System.out.println();
  62. }
  63. }
  65. }

第三个

Java代码收藏代码
  1. packagecom.audition;
  3. /**
  4. *用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"
  5. *不能相连。
  6. *
  7. *
  8. *@authorAdministrator
  9. *
  10. */
  11. publicclassPermutationAlgo3{
  12. privateint[]numbers=newint[]{1,2,2,3,4,5};
  13. publicintn;
  14. privateStringlastResult="";
  16. privatebooleanvalidate(Strings){
  17. if(s.compareTo(lastResult)<=0)
  18. returnfalse;
  19. if(s.charAt(2)=='4')
  20. returnfalse;
  21. if(s.indexOf("35")>=0||s.indexOf("53")>=0)
  22. returnfalse;
  23. returntrue;
  24. }
  26. publicvoidlist(Stringindex,Stringresult){
  27. for(inti=0;i<numbers.length;i++){
  28. if(index.indexOf(i+48)<0){
  29. Strings=result+String.valueOf(numbers[i]);
  30. if(s.length()==numbers.length){
  31. if(validate(s)){
  32. System.out.println(s);
  33. lastResult=s;
  34. n++;
  35. }
  36. break;
  37. }
  38. list(index+String.valueOf(i),s);
  39. }
  40. }
  41. }
  44. publicstaticvoidmain(String[]args){
  45. PermutationAlgo3algo3=newPermutationAlgo3();
  46. algo3.list("","");
  47. System.out.println("总数："+algo3.n);
  48. }
  49. }
分享到：
| java中日期比较大小
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    编写一个java应用程序

    用户从键盘输入一个1-9999之间的数，程序将判断这个数是几位数，并判断这个数是否回文数。回文数是指将数含有的数字逆序排列后得到的数和原数相同，例如12121,4224,6778776等都是回文数。 1）程序具有判断用户的输入...

    java源码包2

    2个目标文件，FTP的目标是：（1）提高文件的共享性（计算机程序和/或数据），（2）鼓励间接地（通过程序）使用远程计算机，（3）保护用户因主机之间的文件存储系统导致的变化，（4）为了可靠和高效地传输，虽然用户...

    蓝点被必做的算法经典题java.c/c++

    【程序29】：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。 【程序30】写一个方法，用二分查找法判断任意整数在...

    java源码包4

    2个目标文件，FTP的目标是：（1）提高文件的共享性（计算机程序和/或数据），（2）鼓励间接地（通过程序）使用远程计算机，（3）保护用户因主机之间的文件存储系统导致的变化，（4）为了可靠和高效地传输，虽然用户...

    java源码包3

    2个目标文件，FTP的目标是：（1）提高文件的共享性（计算机程序和/或数据），（2）鼓励间接地（通过程序）使用远程计算机，（3）保护用户因主机之间的文件存储系统导致的变化，（4）为了可靠和高效地传输，虽然用户...

    成百上千个Java 源码DEMO 4(1-4是独立压缩包)

    凯撒加密解密程序 1个目标文件 1、程序结构化，用函数分别实现 2、对文件的加密，解密输出到文件 利用随机函数抽取幸运数字 简单 EJB的真实世界模型（源代码） 15个目标文件 摘要:Java源码,初学实例,基于EJB的真实...

    java源码包---java 源码 大量 实例

    2个目标文件，FTP的目标是：（1）提高文件的共享性（计算机程序和/或数据），（2）鼓励间接地（通过程序）使用远程计算机，（3）保护用户因主机之间的文件存储系统导致的变化，（4）为了可靠和高效地传输，虽然用户...

    成百上千个Java 源码DEMO 3(1-4是独立压缩包)

    凯撒加密解密程序 1个目标文件 1、程序结构化，用函数分别实现 2、对文件的加密，解密输出到文件 利用随机函数抽取幸运数字 简单 EJB的真实世界模型（源代码） 15个目标文件 摘要:Java源码,初学实例,基于EJB的真实...

    JAVA上百实例源码以及开源项目

    2个目标文件，FTP的目标是：（1）提高文件的共享性（计算机程序和/或数据），（2）鼓励间接地（通过程序）使用远程计算机，（3）保护用户因主机之间的文件存储系统导致的变化，（4）为了可靠和高效地传输，虽然用户...

    java 经典习题.doc

    题目：打印出所有的"水仙花数"，所谓"水仙花数"是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个"水仙花数"，因为153=1的三次方＋5的三次方＋3的三次方。 1.程序分析：利用for循环控制100-999个数，...

    JAVA上百实例源码以及开源项目源代码

    2个目标文件，FTP的目标是：（1）提高文件的共享性（计算机程序和/或数据），（2）鼓励间接地（通过程序）使用远程计算机，（3）保护用户因主机之间的文件存储系统导致的变化，（4）为了可靠和高效地传输，虽然用户...

    Java经典编程题（附答案）

    题目：打印出所有的"水仙花数"，所谓"水仙花数"是指一个三位数，其各位数字立方和等于该数本身。例如： 153是一个"水仙花数"，因为153=1的三次方＋5的三次方＋3的三次方。 1.程序分析：利用for循环控制100-999个...

    java面试题

    84.9. 题目1：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连. 117 84.10. 写一个方法，实现字符串的反转，如：输入...

    跟我学Java面向对象程序设计技术及应用——应用冒泡排序算法实现数组元素排序的Java程序实现示例.pdf

    杨教授工作室，版权所有，盗版必究， 3/29 页 3 2、在工程项目创建的对话框中输入项目名称 JavaDemo，并选择项目存放的目录路径 3、点击对话框中的完成（Finish）按钮，将创建出一个空的 Java 应用程序项目 杨教授...

    java应用软件程序设计

    这里边包括：第1章 Java图形用户界面编程 1 实例1 布局管理 2 实例2 设计软件启动界面 9 实例3 实现多色窗口 11 实例4 切分窗口 13 实例5 丰富多彩的按钮 15 实例6 在窗口中显示背景图 16 实例...

    黑马入学考试试题

    4、有五个学生，每个学生有3门课（语文、数学、英语）的成绩，写一个程序接收从键盘输入学生的信息，输入格式为：name,30,30,30（姓名，三门课成绩），然后把输入的学生信息按总分从高到低的顺序写入到一个名称"stu....

    易语言程序免安装版下载

    　静态编译后的易语言EXE/DLL之间不能再共享譬如窗口、窗口组件等类似资源，对于已经静态连接到一个EXE/DLL中的支持库，该支持库中的数据或资源将不能再被其它EXE/DLL中所使用的同名支持库访问。这是因为代码被分别...

    网管教程 从入门到精通软件篇.txt

    INT：中间代码，当一个源程序经过语法检查后编译产生一个可执行代码 IOF：Findit文档 IQY：Microsoft Internet查询文件 ISO：根据ISD 9660有关CD-ROM文件系统标准列出CD-ROM上的文件 ISP：X-Internet签字文件 ...

    精髓Oralcle讲课笔记

    ------------------------/组函数(共5个)：将多个条件组合到一起最后只产生一个数据------min() max() avg() sum() count()----------------------------/ 51、select count(*) from emp; --求出表中一共有多少条...

Magicbox
Global site tag (gtag.js) - Google Analytics