|
00世纪来移动Brahma塔。卢卡斯最初的难题则是更实际的。它需要2^8-1=255步，较快的话只需要4分钟。
河内塔递归是出现在各种各样的应用程序典型的一个。在发现封闭列表对于兴趣就像Tn，我们通过3个阶段：
1 观察最小的案例。这给予我们洞察力已经帮助我们在第2第三3阶段。
2 发现和证明一个数学表达式对于大量实例。对于河内塔，这是一个允许我们计算对于任何n的Tn的递归。
3 发现和证明一个封闭列表从我们的数学表达式中。对于河内塔，这就是一个递归的解决方案。
第三阶段是将贯穿于本书的精神。事实上，我们将频繁的略过第1和第2阶段，因为数学表达式讲被当成一个起点。但是即使那样，我们也将在问题之下通过所有的3个阶段来入手。
我们关于河内塔的分析引导出了正确的结果，但它被要求了一个“归纳的跳跃”；我们信赖于答案的一个幸运的猜想。本书的主要目标之一就是去解释一个人怎样解决递归问题而不需要惊人的洞察力。例如，我们将看到（1.1）中的递归可以被简化，通过等式两边加1：
T0+1=1;
Tn+1=2Tn-1+2, for n >0.
现在我们假设Un=Tn+1,因此有
U0=1;
Un=2Un-1+1, for n >0.
这很容易地发现对于这个递归的解决方案仅仅是Un=2^n，因此Tn=2^n-1。即使一个计算就可以发现它。
三、冒泡排序算法的运作如下： 比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 C实现
#include
#define LENGTH 8
int main() {
int i,j,temp,number[LENGTH]={95,45,15,78,84,51,24,12};
for(i=0;i
for(j=0;j
if(number[j]>number[j+1]) {
temp=number[j];
number[j]=number[j+1];
number[j+1]=temp;
} //if end
for(i=0;i
puts("");
} //main end
C++实现
#include
#define LENGTH 8
using namespace std;
int main() {
int temp,number[LENGTH]={95,45,15,78,84,51,24,12};
for(int i=0;i
for(int j=0;j
if(number[j]>number[j+1]) {
temp=number[j];
number[j]=number[j+1];
number[j+1]=temp;
} //if end
for(int i=0;i
cout<
} //main end
Java实现
public class BubbleSort {
public static void main(String[] args) {
int[] number={95,45,15,78,84,51,24,12};
int temp=0;
for(int i=0;i
for(int j=0;j
if(number[j]>number[j+1]) {
temp=number[j];
number[j]=number[j+1];
number[j+1]=temp;
} //if end
for(int i=0;i
System.out.println();
} //main end
} //BubbleSort end
Ruby实现
def bubbleSort(array)
return array if array.size <2
(array.size-2).downto(0) do |i|
(0..i).each do |j|
array[j],array[j+1]=array[j+1],array[j] if array[j]>=array[j+1]
end
end
return array
end
java script实现
function bubbleSort(arr){
var i=arr.length, j;
var tempExchangVal;
while(i>0){
for(j=0;j
if(arr[j]>arr[j+1]){
tempExchangVal = arr[j];
arr[j]=arr[j+1];
arr[j+1]=tempExchangVal;
}
}
i--;
}
return arr;
}
var arr = [3,2,4,9,1,5,7,6,8];
var arrSorted = bubbleSort(arr);
console.log(arrSorted);
alert(arrSorted);
C#实现
///
/// 冒泡排序O(n^2)
///
///
待排序数组
static void BubbleSort(int[] intArray)
{
int temp = 0;//存储临时变量
for (int i = 0; i < intArray.Length; i++)
{
for (int j = i - 1; j >= 0; j--)
{
if (intArray[j + 1] < intArray[j])
{
temp = intArray[j + 1];
intArray[j + 1] = intArray[j];
intArray[j] = temp;
}
}
}
}
PHP实现
function bubble_sort($arr) {
$n=count($arr);
for($i=0;$i<$n-1;$i++){
for($j=$i+1;$j<$n;$j++) {
if($arr[$j]<$arr[$i]) {
$temp=$arr[$i];
$arr[$i]=$arr[$j];
$arr[$j]=$temp;
}
}
}
return $arr;
}
Python实现
def bubble(List):
for j in range(len(List)-1,0,-1):
for i in range(0,j):
if List[i]>List[i+1]:List[i],List[i+1]=List[i+1],List[i]
return List
鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序or快乐小时排序是冒泡排序的一种变形。此演算法与冒泡排序的不同之处在于排序是以双向在序列中进行排序。
Java实现
/** * 鸡尾酒排序法 * * @param a * 指定整型数组 */
public void sort(int[] a) {
//需要来回a,length/2趟
for (int i = 0; i < a.length / 2; i++) {
//类冒泡，交换最大值至右端
for (int j = i; 1 + j < a.length - i; j++)
if (a[j] > a[1 + j])
Arr.swap(a, j, 1 + j);
//类冒泡，交换最小值至左端
for (int j = a.length - i - 1; j > i; j--)
if (a[j - 1] > a[j])
Arr.swap(a, j - 1, j);
}
}
四、奇偶排序，或
奇偶换位排序，或
砖排序，是一种相对简单的排序算法，最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序。
该算法中，通过比较数组中相邻的（奇-偶）位置数字对，如果该奇偶对是错误的顺序（第一 |