shenyu
- 浏览: 122540 次
- 性别:
- 来自: 上海
-
文章列表
背包问题有许多种形式，最简单的背包问题形式：现在有一堆石头，(比如重量为2,6,8,10)，一个背包中可以装指定的重量（比如14）的石头，请问背包中可以放入的石头的组合。
代码中假设石头是个源数组，背包是目标数组。
算法中使用分治的想法将此问题递归为两个小范围的问题。
针对第n个石头，背包问题可以分解为两种组合的何：含第n个石头的背包的组合，与不含n个石头的背包的组合，
1.假设含第n个石头，背包问题变为，针对剩下的石头求得总重量减去第n个石头的重量的背包问题。
2.不含n个石头，背包问题变为针对剩下的石头求得总重量的背包问题。
class Bag {
public static void m ...
- 2008-05-14 00:10
- 浏览 4811
- 评论(0)
汉诺塔问题。
这里顺便可以求出一共需要搬运的次数。
以下是汉诺塔问题的解法：
class Hanoi {
public static void main(String[] args) {
int times = hanoi(3,'a','b','c');
System.out.println("一共搬运" + times + "次");
}
//from: 搬运的起点， to：搬运的目标地，middle： 临时中转地
private static int hanoi(int level, char from, char to, char ...
计算幂，n^m，其中n为底数，m为幂
当m取值比较大时如果采用m个n相乘的办法，计算显得冗长。
可以采用以下方法重新组织算法：
n^m == n^((m/2) * 2)
n^m == (n^(m/2))^2
假设如果可以求得temp = n^(m/2),则n^m = temp * temp
这里采用了递归的做法，将n^m问题转换成为n^(m/2)的问题,将近减少了一半运算量。
特殊情况是m不是偶数的情况，这种状况下：
temp = n^(m/2)
n^m = temp * temp * n （多乘一次就可以解决这个问题）
时间代价从原来的O(m) 变成了 O(log m)，再这种情况下 ...
二分法查找是建立在针对有序数组的查找，这里使用的是递归的算法，算法本身比较简单，这里就不再叙述。
二分法查找的时间效率为O(log n)
代码如下：
class BinarySearch {
public static void main(String[] args) {
int[] a = {2,3,4,5,6,7,8,9,10,13,17,18,24,56,78};
System.out.println(search(a,5));
}
private static int search(int[] a, int key) {
return search(a,0,a.len ...
用递归算法求得阶乘。
阶乘用迭代可以更有效的求得。这里只是演示递归的算法。
下面是代码。
1. class Factorial {
2. public static void main(String[] args) {
3. for(int i=1; i<10; i++) System.out.print(getNext(i) + " ");
4. System.out.println();
5. }
6.
7. public static int ...
- 2008-05-10 15:45
- 浏览 1977
- 评论(0)
现在游戏规则如下：
500个小孩首尾相连拉成一个圆圈，从第0个小孩起，依次报数，每当数到3，该小孩退出圈，下一个小孩接着从1开始报数。如此下去圈中的小孩越来越少，求最后一个小孩是哪一个。
代码采用两种方法解决这个问题。
代码如下：
class Children {
public static void main(String[] args) {
play2();
play1();
}
public static void play1() { //算法一
boolean[] a = new boolean[500]; //false表示在圈子里面
int count = ...
- 2008-05-09 00:39
- 浏览 1853
- 评论(1)
堆排序的时间效率与快速排序
相同，也为O(n * log n)。空间上没有使用多余的空间。
基于数组堆的相关定义算法见Heap 堆
排序基于以下假设：
如果一个节点的两个子堆是正确，可以通过下降trickleDown使得堆恢复正常。
一个无序数组的n/2～n的数字可以看成为没有子堆的正确的堆。
对从n/2-1 至 0的元素依次调用trickleDown,可以将一个无序数组组中成一个正确的堆
只有一个节点的堆是个正确的堆
移除总是移除最大的元素，且每次移除后数组的从后向前多增加自由位置，可以将刚移除的数据放入其中。
Node为辅助类，key表示 ...
- 2008-05-08 08:34
- 浏览 1752
- 评论(2)
基数排序是种与众不同的排序方法，它不是基于比较和交换。其理论时间效率是O(n)。基数排序的基本想法是将每个数字按照一定的基数拆分，然后根据每一位将数据反复排序。
例如： 代排序数组:{7,3,1,5,4} 基数:2用基数表示源排序数组:{111,011,001,101,100}首先按照第0位（从右边数起）,根据0位是0,还是1将数组中数据放入0队列或1队列中，然后再将数据从两个队列中取出，这样便完成了对0位的排序。 此时数组变成了{100,111,011,001,101}然后在按照此算法对第1位操作： 此时数组变成了{100,001,101,111,011}然后在按照此算 ...
快速排序是通用排序中（针对内存中）最为流行的算法，其时间效率为O(n * log n)。
其关键算法是基于划分的排序。
划分只将数组中任意一个元素作为枢纽值，经过交换，使得数组中排列成所有小于枢纽的数值都在枢纽左边，而 ...
- 2008-05-06 00:39
- 浏览 1457
- 评论(0)
插入排序
对基本有序的数组效果非常好，但是对于通常情况则表现一般。假设最小的数字在最右边，升序排序时，这个数则要经过n次交换比较换到最左边。希尔排序则是对插入排序的很好的修正。而且在希尔排序很少出现最坏状况。
希尔排序通过对数组 以一定间隔相隔的位置 进行插入排序，以达到让数据快速出现在它应该出现的位置的周围，使数组逐步接近基本有序。随着间隔的减少，数组越来越接近基本有序，最后间隔为1时，变成标准的插入排序。
数据的间隔有多种算法，一般要求间隔序列之间互质，此处使用Kunth序列：h = h * 3 + 1
希尔排序的时间效率很难从理论上证明，实验表明大约是O(n^(3/2)) ~ O(n^(7 ...
- 2008-05-05 00:17
- 浏览 1631
- 评论(0)
归并排序的时间效率为O(n * log n)
算法假设两个已有序的数组，将其归并成一个有序的数组（见merge函数)。算法将数组分为前后两部分，对这两部分递归调用归并排序，然后将这两部分再合并。
算法的空间效率不高，需要多耗费一倍的空间。
class Merge {
public static void main(String[] args) {
int[] a = {3,2,5,2,0,6,3,7};
sort(a,0,a.length);
print(a);
}
public static void sort(int[] a, int p1, int p3) {
if ...
插入排序算法比冒泡
和选择
略微复杂些，但效率好些。
插入排序总是假设指定位置的左边的数组是有序的，而后将指定位置的值插入左边的有序数组。
指定的位置从下标1开始，每次循环递增1，直到数组结束。
插入排序的比较次数与交换次数的时间效率均为O(n^2)，确切的说是O(n^2 / 4)，比冒泡排序快一倍。
对于一个基本有序数组，由于内循环基本都是空循环，插入排序的效率接近O(n)，但对于完全逆序数组，插入排序的效率与冒泡相同。因此插入排序对于
基本有序，或反复排序的数组比较有利，实是上插入排序常常用于其他排序的首尾工作，其他排序只要排到基本有序即可，比如快速排序。
下面是代码。
class Inse ...
红黑树是一种二叉平衡树搜索树，相关背景知识此处不再叙述。
节点与关键值之间的关系与普通二叉树
一致，只是在插入时要保证红黑规则，如果插入过程中违反了红黑规则，树则会通过自我调整，改变树的结构和节点的颜色 ...
冒泡排序的算法此处不在叙述。冒泡排序比较与交换的时间效率都是O(n^2)。
下面提供冒泡排序的Java代码。代码足够简单，没有加注释。
class Bubble {
public static void main(String[] args) {
int[] a = {6,3,2,6,3,2,9,7};
sort(a);
print(a);
}
private static void print(int [] a) {
for(int i: a) System.out.print(i + " &q ...
- 2008-04-28 22:00
- 浏览 2215
- 评论(2)
三角数字是这样一组数字：1 3 6 10 15 21 28 36 45......
其中第n个数字等于n-1个数字的值加上n。
此处用递归算法求三角数字。（要求得该数字不一定要使用递归，迭代来的效率更高一些）
下面是代码：
class Triangle {
public static void main(String[] args) {
for(int i=1; i<10; i++) System.out.print(getNext(i) + " ");
System.out.println();
}
priva ...
- 2008-04-27 19:47
- 浏览 2375
- 评论(0)