JAVA程序归递算法求解汉诺塔问题_CMS教程

首先你需要有下面这两个意识：

1一个函数对于其它函数来说相当于一个盒子，他封装了其中的内容，其它函数只知道给它参数，然后得到它的结果。就好比一个做蛋糕的商店：我们只需要知道给钱，它就会给蛋糕。而我们不需要理解他们是怎么做出来的这个蛋糕。

2调用的过程，就相当于上面例子中我们去买蛋糕的过程。谁说自己不能买自己店里的蛋糕呢？比如你是做蛋糕的，难道你不能买自己店里的蛋糕吗？函数的自我调用（递归？）也是这么回事情。

对于hanoi类里面，两个核心函数：

move（char getme, char purone):

这个函数的功能是：把getme最上面的盘子移动到purone位置，比如

move('A','B')就是把A柱子最上面那个盘子移动到B柱子的最上面。

hanoi(int n,char one,char two,char three）：

这个函数的功能是：现在在柱子one上一共有n个盘子，这个函数能够通过two把它移动到three上面。

现在你了解了这两个函数设计的初衷，ok，我们来分别实现每个函数。

public void move(char getme,char purone)

{//请联系上面写的这个函数的功能来看：

c=c+1;//我们每移动一步，就计数一次

Systemoutprintln(getme+"-->"+putone+"搬盘次数为："+c);

//这行使用输出来表明移动过了（事实上hanoi就是要让你详细说明移动过程，所谓“说明”，就是打印出每次的移动，那这里我们就把这次移动打印出来，这个没有任何问题吧？这个函数就是要把移动这件事情说出来，明白？

}

public void hanoi(int n,char one,char two,char three)

{//请回忆hanoi函数的功能，是要把one柱子上的前n个放到three柱子上：

if(n==1) //如果n==1,那也就是要把one柱子上最上面的那个移到three上面了，这就是move函数的作用，对吧？那就直接调用move(one,three)

move(one,three);

else{

//如果n>1的话，那我们该怎么办？

分为三个步骤：

1先想办法把one主子上的前n-1个移动到柱子two上

2然后把one柱子上的第n个移动到柱子three上。

3然后想办法把two柱子上的n-1个移动到three上。

对吧？现在你注意到第1步和第3步是不是就是hanoi这个函数的功能能够实现的呢？回答显然是肯定的，下面就是这三步。

hanoi(n-1,one,three,two); //把one柱子上的n-1个通过three移动到two上。

move(one,three); //把one主子上最上面那个（注意，上面一步已经把前n-1个移动到two上面了，one柱现在最上的那个就是第N个）

hanoi(n-1,two,one,three);//把two柱子上的n-1个移动到three柱子上。

}

解释到这里，main函数里面的调用应该也就很明白了吧？

ahanoi(m,'A','B','C')；

把'A'柱子上的m个盘子通过'B'柱子全部移动到'C'上面的步骤。

解释起来很容易，想得多了也就慢慢明白了，最难的是如何设计一个递归出来。这个和数学里面的递推公式很相似（事实上其来源就是递推公式），想必你肯定知道递增函数把？ An = An-1 + 5（A0 = 0 );这个条件能够唯一确定一个数列。

那现在你把它写成函数呢？

int A(int n) {

if(n == 0) {

return 0;

} else {

return A(n -1) + 5;

}

调用A(n)就能返回An的值。明白？

多想想，多练练，大家都是这么过来的：）祝好运

// 大概看了一下, 发现所需人力没说明什么用,在本题中处于什么条件

// 只说思路要去买饭, 懒得写code

// 1 定义一个Task 属性开始时间结束时间人力

// 2 将5个任务放到一个集合中 tasks = List<Task>

// 3 循环输出,第一次拿Task1的endTime与下一个Task的startTime比较,如果小则count计数+1

// 并将Task1的endTime = (下一个Task的endTime)

// 这写一下吧

Date endTime = null;

int count = 0;

for(Task task: tasks){ // 第一种情况第一个任务他参与, 第二种情况他从第二个任务参与

endTime = taskEndTime;

for(Task task: tasks){

if(endTime<taskStartTime){

count++;

endTime = taskEndTime;

}

count即为最大任务数;

// 可能有更优方式, 懒得想了;

import javaio;

public class Test

{

@param args

public static void main(String[] args) throws IOException

{

// TODO Auto-generated method stub

BufferedReader br=new BufferedReader(new InputStreamReader(Systemin));

String str=brreadLine();

Systemoutprintln("请输入要查询的单词");

String s=brreadLine();

int count=0;

int m=0;

int begin=-1;

int end=-1;

while(true)

{

if(slength()==1)

{

begin=strindexOf(s);

if(m==0)

{

Systemoutprintln("第一次出现在"+begin+"字节处");

}

m++;

end=begin;

}

else

{

begin=strindexOf(ssubstring(0,1));

if(m==0)

{

Systemoutprintln("第一次出现在"+begin+"字节处");

}

end=strindexOf(ssubstring(slength()-1));

}

if(begin==-1||end==-1)

{

break;

}

if(sequals(strsubSequence(begin, end+1)))

{

count++;

str=strsubstring(end+1);

}

else

{

str=strsubstring(end+1);

}

Systemoutprintln("单词"+s+"出现了"+count+"次");

}

2015年5月27日下午5:13:48

@author season

public class SecurityByKey {

securityByKey TODO 对数字 num 每一个位数进行加key 对10 取余的加密

@param num

需要被加密的三位整数

@param key

每一位数加上多少

@return String 返回加密之后的字符串

public String securityByKey(int num, int key) {

StringBuffer newNum = new StringBuffer();

while (num > 0) {// 取出从尾数开始每一位数,并求出+7 ,对10取余(从尾数开始,那么真正的是反转过来的)

int temp = num % 10;

temp += 7;

newNumappend(temp % 10);

num = num / 10;

}

newNumreverse();// 将字符串倒转

return new String(newNum);

}

public static void main(String[] args) {

SecurityByKey byKey = new SecurityByKey();

Systemoutprintln(byKeysecurityByKey(123, 7));

}

package image;

import javautilArrays;

10个排序

@author yugi

public class AllSrots

{

直接选择排序

private static void directChooseSort ( int[] array )

{

for ( int i = 0; i < arraylength; i++ )

{

int index = i;

for ( int j = i + 1; j < arraylength; j++ )

{

if (array[index] > array[j])

{

index = j;

}

if (i != index)

{

int temp = array[i];

array[i] = array[index];

array[index] = temp;

}

堆排序

private static void heapSort ( int[] array, int start, int len )

{

int pos = ( len - 1 ) / 2;

for ( int i = pos; i >= 0; i-- )

{

int tmp = array[start + i];

int index = i 2 + 1;

while (index < len)

{

if (index + 1 < len && array[start + index] < array[start + index + 1]) // 从小到大

{

index += 1;

}

if (tmp < array[start + index]) // 从小到大

{

array[start + i] = array[start + index];

i = index;

index = i 2 + 1;

}

else

{

break;

}

array[start + i] = tmp;

}

for ( int i = 0; i < len; i++ )

{

int temp = array[start];

array[start] = array[start + len - 1 - i];

array[start + len - 1 - i] = temp;

// 再一次

int post = 0;

int tmp = array[start + post];

int index = 2 post + 1;

while (index < len - 1 - i)

{

if (index + 1 < len - 1 - i && array[start + index] < array[start + index + 1]) // 从小到大

{

index += 1;

}

if (tmp < array[start + index]) // 从小到大

{

array[start + post] = array[start + index];

post = index;

index = post 2 + 1;

}

else

{

break;

}

array[start + post] = tmp;

}

冒泡排序

private static void bubbleSort ( int[] array )

{

for ( int i = 0; i < arraylength; i++ )

{

for ( int j = i + 1; j < arraylength; j++ )

{

if (array[i] > array[j])

{

int temp = array[i];

array[i] = array[j];

array[j] = temp;

}

快速排序

private static void quickSort ( int[] array, int start, int end )

{

if (start < end)

{

int key = array[start];

int i = start;

for ( int j = start + 1; j < end + 1; j++ )

{

if (key > array[j])

{

int temp = array[j];

array[j] = array[i + 1];

array[i + 1] = temp;

i++;

}

array[start] = array[i];

array[i] = key;

quickSort (array, start, i - 1);

quickSort (array, i + 1, end);

}

直接插入排序

private static void directInsertSort ( int[] array )

{

for ( int i = 1; i < arraylength; i++ )

{

int j;

int temp = array[i];

for ( j = i; j > 0; j-- )

{

if (array[j - 1] > temp)

{

array[j] = array[j - 1];

}

else

{

break;

}

array[j] = temp;

}

折半插入排序

private static void binaryInsertSort ( int[] array )

{

for ( int i = 1; i < arraylength; i++ )

{

// if (array[i] > array[i - 1]) // 从大到小

if (array[i] < array[i - 1]) // 从小到大

{

int tmp = array[i];

int low = 0;

int high = i - 1;

while (low <= high)

{

int mid = ( low + high ) >>> 1;

// if (array[mid] > tmp) // 从大到小

if (array[mid] < tmp)// 从小到大

{

low = mid + 1;

}

else

{

high = mid - 1;

}

for ( int j = i; j > low; j-- )

{

array[j] = array[j - 1];

}

array[low] = tmp;

}

希尔排序

private static void shellSort ( int[] array, int start, int len )

{

int power = 1;

while (( power + 1 ) 2 < len)

{

power = ( power + 1 ) 2 - 1;

}

for ( int k = power; k >= 1; k = ( k + 1 ) / 2 - 1 )

{

for ( int i = 0; i < k; i++ )

{

if (len - i <= 1)

{

break;

}

int tmp;

for ( int j = start + i + k; j < start + len; j += k )

{

tmp = array[j];

int m = j;

for ( ; m > start + i; m -= k )

{

if (array[m - k] > tmp) // 从小到大

{

array[m] = array[m - k];

}

else

{

break;

}

array[m] = tmp;

}

归并排序

private static void mergeSort ( int[] array, int start, int end, int[] tempArray )

{

if (end <= start)

{

return;

}

int middle = ( start + end ) / 2;

mergeSort (array, start, middle, tempArray);

mergeSort (array, middle + 1, end, tempArray);

int k = 0, leftIndex = 0, rightIndex = end - start;

Systemarraycopy (array, start, tempArray, 0, middle - start + 1);

for ( int i = 0; i < end - middle; i++ )

{

tempArray[end - start - i] = array[middle + i + 1];

}

while (k < end - start + 1)

{

if (tempArray[rightIndex] > tempArray[leftIndex]) // 从小到大

{

array[k + start] = tempArray[leftIndex++];

}

else

{

array[k + start] = tempArray[rightIndex--];

}

k++;

}

桶式排序

private static void bucketSort ( int[] array, int min, int max )

{

int[] tmp = new int[arraylength];

int[] buckets = new int[max - min];

for ( int i = 0; i < arraylength; i++ )

{

buckets[array[i] - min]++;

}

// 从小到大

// for ( int i = 1; i < max - min; i++ )

// {

// buckets[i] = buckets[i] + buckets[i - 1];

// }

// 从大到小

for ( int i = max - min - 1; i > 0; i-- )

{

buckets[i - 1] = buckets[i] + buckets[i - 1];

}

Systemarraycopy (array, 0, tmp, 0, arraylength);

for ( int k = arraylength - 1; k >= 0; k-- )

{

array[--buckets[tmp[k] - min]] = tmp[k];

}

基数排序

private static void radixSort ( int[] array, int from, int radix, int d )

{

int len = arraylength;

int[] temporary = new int[len];

int[] count = new int[radix];

int R = 1;

for ( int i = 0; i < d; i++ )

{

Systemarraycopy (array, from, temporary, 0, len);

Arraysfill (count, 0);

for ( int k = 0; k < len; k++ )

{

int subkey = ( temporary[k] / R ) % radix;

count[subkey]++;

}

// 从小到大

// for ( int j = 1; j < radix; j++ )

// {

// count[j] = count[j] + count[j - 1];

// }

// 从大到小

for ( int j = 1; j < radix; j++ )

{

count[j - 1] = count[j] + count[j - 1];

}

for ( int m = len - 1; m >= 0; m-- )

{

int subkey = ( temporary[m] / R ) % radix;

--count[subkey];

array[from + count[subkey]] = temporary[m];

}

R = radix;

}

public static void main ( String[] args )

{

int[] array = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };

directChooseSort (array);