1. 用1、2、3、4、5这五个数字,用java写一个main函数,打印出所有不同的排列,如:51234、41235等。
public class TestQuestion {
static int[] bits = new int[] { 1, 2, 3, 4, 5 };
/**
* @param args
*/
public static void main(String[] args) {
sort("", bits);
}
private static void sort(String prefix, int[] a) {
if (a.length == 1) {
System.out.println(prefix + a[0]);
}
for (int i = 0; i < a.length; i++) {
sort(prefix + a[i], copy(a, i));
}
}
private static int[] copy(int[] a,int index){
int[] b = new int[a.length-1];
System.arraycopy(a, 0, b, 0, index);
System.arraycopy(a, index+1, b, index, a.length-index-1);
return b;
}
}
2. 对第一题增加难度,用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。
基本思路:
2-1. 把问题归结为图结构的遍历问题。图遍历思想:实际上6个数字就是六个结点,把六个结点连接成无向连通图,对于每一个结点求这个图形的遍历路径,所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2-2. 显然这个结果集还未达到题目的要求。从以下几个方面考虑:
2-2-1. 3,5不能相连:实际要求这个连通图的结点3,5之间不能连通, 可在构造图结构时就满足改条件,然后再遍历图。
2-2-2. 不能有重复: 考虑到有两个2,明显会存在重复结果,可以把结果集放在TreeSet中过滤重复结果
2-2-3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。
采用二维数组定义图结构,最后的代码是:
import java.util.Iterator;
import java.util.TreeSet;
public class TestQuestion {
private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};
private int n = b.length;
private boolean[] visited = new boolean[n];
private int[][] a = new int[n][n];
private String result = "";
private TreeSet set = new TreeSet();
public static void main(String[] args) {
new TestQuestion().start();
}
private void start() {
// Initial the map a[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;
// Begin to depth search.
for (int i = 0; i < n; i++) {
this.depthFirstSearch(i);
}
// Print result treeset.
Iterator it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();
// "4" can not be the third position.
if (string.indexOf("4") != 2) {
System.out.println(string);
}
}
}
private void depthFirstSearch(int startIndex) {
visited[startIndex] = true;
result = result + b[startIndex];
if (result.length() == n) {
// Filt the duplicate value.
set.add(result);
}
for(int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}
// restore the result value and visited value after listing a node.
result = result.substring(0, result.length() -1);
visited[startIndex] = false;
}
}
以上引用原址:http://www.blogjava.net/SongJunke/articles/101741.html
3. 递归思想。递归要抓住的关键是:(1)递归出口;(2)地推逐步向出口逼近。
3-1. 汉诺塔
这是递归的超经典的例子,几乎每本程序设计书上谈到递归都会介绍。具体情景不再赘述。以我上述的方法观之:
3-1-1. 递归的出口在于disk数为一的时候
3-1-2. 向出口逼近:如果不是一,是n ,则我们先挪动上面n-1块disk,等上面挪完,即递归返回的时候,我们挪动最底下的disk.
仅仅如此,一个貌似十分复杂的问题就解决了,因为挪动那n-1块disk的时候,会继续向上减少,直到disk的数量为一为止。下面给出代码:
import javax.swing.JOptionPane;
public class Hanoi{
private static final String DISK_B = "diskB";
private static final String DISK_C = "diskC";
private static final String DISK_A = "diskA";
static String from=DISK_A;
static String to=DISK_C;
static String mid=DISK_B;
public static void main(String[] args) {
String input=JOptionPane.showInputDialog("please input the number of the disks you want me move.");
int num=Integer.parseInt(input);
move(num,from,mid,to);
}
private static void move(int num, String from2, String mid2, String to2) {
if(num==1){
System.out.println("move disk 1 from "+from2+" to "+to2);
}
else {
move(num-1,from2,to2,mid2);
System.out.println("move disk "+num+" from "+from2+" to "+to2);
move(num-1,mid2,from2,to2);
}
}
}
3-2. 这是一个排列的例子,它所做的工作是将输入的一个字符串中的所有元素进行排序并输出,例如:你给出的参数是"abc" 则程序会输出:
abc
acb
bac
bca
cab
cba
分析:
3-2-1. 算法的出口在于:low=high也就是现在给出的排列元素只有一个时;
3-2-2. 算法的逼近过程:先确定排列的第一位元素,也就是循环中i所代表的元素,然后low+1开始减少排列元素,如此下去,直到low=high。(暂未调通)
public static void permute(String str) {
char[] strArray = str.toCharArray();
permute(strArray, 0, strArray.length - 1);
}
public static void permute(char[] list, int low, int high) {
int i;
if (low == high) {
String cout = "";
for (i = 0; i <= high; i++)
cout += list[i];
System.out.println(cout);
} else {
for (i = low; i <= high; i++) {
char temp = list[low];
list[low] = list[i];
list[i] = temp;
permute(list, low + 1, high);
temp = list[low];
list[low] = list[i];
list[i] = temp;
}
}
}
3-3. 这是一个组合的例子,与上述的例子相似,只是它所做的工作是,输出所给字符串中制定数目的元素的组合种类。
分析:
3-3-1. 程序出口在于n=1,此时只要输出目标数组的所有元素即可
3-3-2. 逼近过程,当n>1 的时候,我们先取第一个元素放入目标数组中,然后n-1,如此下去,最后出来。
import javax.swing.JOptionPane;
public class Combination {
/**
* @param args
*/
public static void main(String[] args) {
String input = JOptionPane.showInputDialog("please input your String: ");
String numString = JOptionPane.showInputDialog("please input the number of your Combination: ");
int num = Integer.parseInt(numString);
Combine(input, num);
}
private static void Combine(String input, int num) {
char[] a = input.toCharArray();
String b = "";
Combine(a, num, b, 0, a.length);
}
private static void Combine(char[] a, int num, String b, int low, int high) {
if (num == 0) {
System.out.println(b);
} else {
for (int i = low; i < a.length; i++) {
b += a[i];
Combine(a, num - 1, b, i+1, a.length);
b=b.substring(0, b.length()-1);
}
}
}
}
分享到:
相关推荐
Java实现的常见排序算法_IT/计算机_专业资料。本文较为完整得收录了常用的排序算法以及其他事例,讲解详细,值得收藏学习!
用Java实现几种常见的排序算法(经典收藏)
Java算法大全,收集了近100种Java常见算法代码实例,绝对值得收藏的Java源码资料,包括了各种算法的运用实例源码,尤其是编程新手,更需要这些算法资料。
个人收藏起来不错的东西,学习java需要的,我觉的不错,希望对大家有用。
java编写的轨迹纠偏算法,包含异常点检测、滤波平滑,以及代码使用示例和结果分析
基本的协同过滤推荐算法实现,包括数据集,以及算法的评价指标MAE的计算,数据集采用MovieLens中两个数据集进行测试
编程的几个经典算法,有C的,也有java的,值得收藏。
大神详解,这么详细的Java设计模式不收藏可惜了 设计模式是很多程序员总结出来的优秀实践。曾经在刚开始写项目的时候学习过设计模式,在开发过程中,也主动或者被动的使用过。现在写代码虽说不会特意明确在用哪种...
Java毕业设计基于用户的协同过滤算法实现的商品推荐系统源码+数据库(高分项目).zip该项目是个人高分毕业设计项目源码,已获导师指导认可通过,都经过严格调试,确保可以运行!放心下载使用。 Java毕业设计基于用户...
很好的数据结构及算法分析能力是学习Java的前提 本书绝对值得收藏
带标签的,java虚拟机中比较好的一本书,值得阅读与收藏 随着越来越多的第三方语言(Groovy、Scala、JRuby等)在Java虚拟机上运行,Java也俨然成为了一个充满活力的生态圈。《实战Java虚拟机——JVM故障诊断与性能...
用Java加密类实现常规的DES、RSA及SHA的加密算法,代码完整,收藏一下。
中国象棋算法独家收藏,人机对战,通过各种渠道很难总结出来的。。。希望对大家有所帮助。
Java数据结构和算法中文第二版,讲解全面深入,实用!!!值得收藏!
包括常见的java排序算法、非常值得收藏
很经典的java版数据结构与算法分析,清晰度不错,值得收藏!
3、用户操作行为:用户评分、收藏记录、浏览记录、观看时长、购买记录等操作行为; 混合推荐方法可以是先将数据进行聚类(用户聚类、项目聚类等),可进行多次聚类,聚类算法常用的有KMeans聚类、Canopy聚类、KMeans...
收藏一个Java环境的MD5字符串加密算法类代码,现在分享给大家,比较常用,用法简单,学习参考当然也可以啦。
1、[JAVA书籍400本,精心收藏].j2megame 2、j2me慢慢学教程 3、java2实用教程电子教案 4、java.2.编程21天自学通 5、java案例开发 6、java程序设计基础教程 7、java服务器高级编程 8、java面向对象应用程序...
Java c++通过des加密的结果不一样【已解决】 最近做了一个接口,需要和C++进行通讯,通讯的参数采用des加密,但调试的时候却发现同样的明文和密钥加密出来的结果却是不一样的。 收藏网络总结代码