博文
“快速排序算法”问题的分而治之算法(2007-09-30 21:40:00)
摘要：/* 标题：<<系统设计师>>应试编程实例-[分治法程序设计] 作者：成晓旭 时间：2002年09月18日(21:43:00-22:03:00) 实现“快速排序算法”问题的分而治之算法函数*/#include "stdio.h"#include "stdlib.h"
//:============================“快速排序算法”问题的分而治之算法===========================/* 时间：2002年09月18日(21:43:00-22:03:00) 实现“快速排序算法”问题的分而治之算法函数 问题描述: 用分治法的思想实现快速排序算法。 编程思想: 快速排序算法的基本思想本身就是分治法。通过分割，将无序序列分成两部分， 其中前一部分的元素值都小于后一部分的元素值。然后每一部分再各自递归进行上 述过程，直到每一部分的长度为1为止。 首先，在序列的第一个，中间一个，最后一个元素中选取中项，设为p[middle], 并作temp = p[middle](保存中项); 其次，将序列中的第一个元素移到p[middle]的位置上； 然后，设两个指针i,j分别指向将排序序列的第一个元素和最后一个元素； 重复以上两步，直到i = j为止； 最后，将array[i] = temp(将tmep移到array[i])。*/#define MAXN 20
void Carve_up(int array[],int number,int *m){ int i,j,k,middle,temp; i = 0; j = number - 1; k = (i + j) / 2; //在下标i,j,k的数组元素......
S/P先生数学谜题"算法分析及源代码(2007-05-09 21:41:00)
摘要：S、P先生数学谜题：
设有两个自然数X、Y，2<=X<=Y<=99,S先生知道这两个数的和S，P先生知道这两个数的积 P ，他们二人进行了如下对话：
S：我确信你不知道这两个数是什么，但我也不知道。
P: 一听你说这句话，我就知道这两个数是什么了。
S: 我也是，现在我也知道了。
现在你能通过他们的会话推断出这两个数是什么吗？（当然，S和P先生都是非常聪明的）
S、P先生数学谜题的思路：
首先已声明2<=x<=y<=99，且x，y都是自然数。
1、S先生说：“我不知道这两个数。”，这就可知S决不是：
4(=2+2)；5(=2+3)；197(=98+99)；198(=99+99)。
把这些S的不可能的值及其对应的X，Y的组合存储到数组US[]中。
2、S先生说：“我确定你也不知道这两个数。”，这就可知P决不是：
（1） 两端的数之积，如4(=2*2)；6(=2*3)；8=(2*4)；10(=2*5)；。。。
9801（=99*99）；9702（=98*99）；9604（=98*98）。
（2） 素数或者素数之积，如5，7，11，。。。25（=5*5），35（=5*7）。
把这些P的不可能的值及其对应的X，Y的组合存储到数组UP[]中。
UP共有2981个元素，它们是：
UP={4 5 6 7。。。4316 4327 4331 。。。9781 9787 9791 9801}
那么可以根据这些X，Y的组合求出对应的S（=X+Y）来，把它们加入到数组US[]中。这样一来，S的数又可以排除一些了。
比如6(=2+4)；7(=2+5)；...10(=5+5);...。
如此一来，就可以初步总结出S可能的数的集合：
&n......
最大值堆排序算法实现(2007-05-09 17:22:00)
摘要：// max-heap sort in c++// 最大值堆排序算法实现//作者：Andyhou
#include <iostream>using namespace std;
//建立比较类。class initCompare{public: static bool it(int x,int y) { return x<y; } static bool gt(int x,int y) { return x>y; } static bool eq(int x,int y) { return x==y; }};//Max-heap class template <class Elem,class Compare>class maxheap{private: Elem* Heap; int size; int n; void siftdown(int); void swap(Elem A[],int,int);public: maxheap(Elem* h,int num,int max) { Heap=h; n=num; size=max; buildHeap(); } int heapsize() const { return n; } bool isL......
台阶问题 (2007-05-02 21:59:00)
摘要：
台阶问题
某人上楼梯,他一步可以迈一个台阶,两个台阶或三个台阶,共有n个台阶,编程输出他所有可能上法.如:有4个台阶,输出应是:1 1 1 11 1 21 2 11 32 1 12 23 1
/* stair.c
The problem of stair
Copyright By Jimmy, 2002.11 All Rights Reserved.*/
#define STAIR_NUM 5int total=0;int index;int que[STAIR_NUM];
void outputstep(){ int i; for(i=0;i<index;i++) printf("-%d",que[i]);
printf("-\n");}
void step(int n){ if (n==0) { total++; printf("---------the NO.%d&......
用队列实现的带度数的后根次序恢复树(2007-05-02 21:57:00)
摘要：
用队列实现的带度数的后根次序恢复树
算法思想：
从左向右扫描数组，每遇到一个结点都进队列，当结点度数degree不为0时，则从队列中出degree个结点作为其子结
点，由于是先进先出，出队列的顺序正好是从左到右的子树顺序。
但要注意，出队列的结点应是队列中最后的degree个，所以要不断进行出队列、入队列操作直到找到正确的子结点。
//queue.cpp#include"iostream.h"#include"math.h"class BinNode{public: BinNode(char e) { left=NULL; right=NULL; elem=e; } char elem; BinNode* left; BinNode* right;};class Queue{public: BinNode* *listarray; int size; int front; int rear;// int queuenum; Queue(int n) { size=n; front=rear=0; listarray=new BinNode*[size]; } ~Queue() { delete [] listarray; } bool isEmpty......
并归排序算法和优化后的算法(2007-05-02 21:49:00)
摘要：// merge sort in C++// 并归排序算法和优化后的算法//作者：Andyhou#include <iostream>using namespace std;
const int THRESHOLD=9;class intCompare{public: static bool it(int x,int y) { return x<y; } static bool gt(int x,int y) { return x>y; } static bool eq(int x,int y) { return x==y; }};
template<class Elem,class Compare>class Merge{private: Elem* array; int arraySize; void inssort(Elem A[],int n); void swap(Elem A[],int i,int j);public: void mergesort1(Elem A[],Elem temp[],int left,int right); void mergesort2(Elem A[],Elem temp[],int left,int right); void print(Elem A[],int n);};
template<cla......
内部排序算法比较(2007-05-02 16:44:00)
摘要：排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较．
问题分析和总体设计
ADT OrderableList{数据对象：D={ai| ai∈IntegerSet，i=1，2，…，n，n≥0}数据关系：R1={〈ai-1，ai〉|ai-1， ai∈D， i=1，2，…，n}基本操作：InitList(n)操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d，isInverseOrser)操作结果：随机打乱BubbleSort( )操作结果：进行起泡排序InserSort( )操作结果：进行插入排序SelectSort( )操作结果：进行选择排序QuickSort( )操作结果：进行快速排序HeapSort( )操作结果：进行堆排序ListTraverse(visit( ))操作结果：依次对L种的每个元素调用函数visit( )}ADT OrderableList
待排序表的元素的关键字为整数.用正序，逆序和不同乱序程度的不同数据做测试比较，对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息，用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕，要求列表现是比较结果.要求对结果进行分析.
详细设计1、起泡排序算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好
bubblesort(struct rec r[]，int n){int i，j;struct rec w;unsigned long int compare=0，move=0;for(i=1;i<=n-1;i++)for(j=n;j>=i+1;j--){if(r[j].key<r[j-1].key){w=r[j];r[j]=r[j-1];r[j-1]=w;move=move+3;}compare++;}printf("BubbleSort compare= %ld，move= %ld"，compar......
一种极为有趣算法 摇头丸排序法 (2007-05-01 07:56:00)
摘要：普通的冒泡排序法,在一次循环中,只把最小的元素排到数组的顶部,而摇头丸排序法则在一次循环中,把最小元素排到顶部,并把最大的元素排到底部.下面是实现代码: #include <iostream>
using namespace std;
template <class T> void Swap( T &t1, T &t2 ) { T temp; temp = t1; t1 = t2; t2 = temp; }
int iArray[10] = { 8, 4, 3, 6, 2, 9, 1, 7, 0, 5 };
void Display( int a[], int iSize ) { for ( int i = 0; i < iSize; ++i ) cout << a[i]; cout << endl; }
void Sort( int a[], int iSize ) { int i,j; int temp = 0; int iIndexMax;
for ( i = 0; i < iSize; ++i ) { iIndexMax = iSize - i - 1;
for ( j = iSize - i - 1; j > i; --j ) { if ( a[j] < a[j-1] ) //把最小元素排到顶部 Swap( a[j], a[j-1] ); if ( a[j] > a[iIndexMax] ) //把最大元素排到底部 iIndexMax = j; } Swap( a[iSize - i - 1], a[iIndexMax] ); Display( a, iSize ); } }
int main() { Display( iArray, 10 ); Sort( iArray, 10 ); Display( iArray, 10 ); return 0; }
整个算法,就像把最小元素和最大元素摇到数组的两头
可是它的时间代价为多少呢,它是否比冒泡排序法更快呢?
转http://bbs.csai.cn/......
《栈的计数》问题的算法分析(2007-04-29 13:00:00)
摘要：
问题转述：
求一列共n辆的火车按顺序通过一个栈所产生的排列总数。
分析：
这一类组合计数题目显然不能用搜索的方法把所有可能的移动方案都穷举出来再统计总数──这样做时间复杂度极大。这道题与经典的HANOI问题很相似，所以应当根据问题本身的性质，利用组合数学的原理，将原问题转化为递归形式，找到计算总数的递归方程，再进行计算。
摘要：
算法一
算法二
算法三
算法
递推
递推
Catalan数
时间复杂度
O(n2)
O(n2)
O(n)
空间复杂度
O(n)
O(n2)
O(1)
算法一：
我们不妨直接设n辆火车产生的排列总数为f(n)。看看能不能找到一些规律。 如图,n列火车通过栈,起始车头在车列最前端。经过移动后,车头处在了第a+1位,车头前有a辆车,车头后有b辆车(a>=0,b>=0)。则n=a+b+1,b=n-a-1。
若要达到上述移动目的,步骤为:
(1) 将车头进栈;
(2) 将车头后a辆车依次通过栈，移至轨道另一端；
(3) 将车头出栈，则车头恰好排在第a+1位；
(4) 将轨道右端剩余b辆车依次通过栈，移至轨道另一端；
不难证明，移动方案仅此一种。问题是每个步骤又有许多种不同的移动方法。显然步骤（1）（3）各只有一种移动方法。仔细观察步骤（2）（4）。我们前面定义了“n辆火车依次通过栈产生的排列总数为f(n)”，而步骤（2）恰恰是这个问题的子问题。即步骤二可写为“将a辆火车依次通过栈”，根据前面定义，其移动方案总数为f(a)。同理，步骤(4)的移动方法总数为f(b)。
根据乘法原理，要完成上述工作：
总的方法数tot=步骤(1)的方法数*步骤(2)的方法数*步骤(3)的方法数*步骤(4)的方法数
=1* f(a) * 1* f(b)
=f(a) * f(b)
=f(a) * f(n-a-1) (因为b=n-a-1)
我们目前已求......
排列组合问题的通用算法(2007-04-29 12:37:00)
摘要：尽管排列组合是生活中经常遇到的问题，可在程序设计时，不深入思考或者经验不足都让人无从下手。由于排列组合问题总是先取组合再排列，并且单纯的排列问题相对简单，所以本文仅对组合问题的实现进行详细讨论。以在n个数中选取m(0<m<=n)个数为例，问题可分解为：1. 首先从n个数中选取编号最大的数，然后在剩下的n-1个数里面选取m-1个数，直到从n-(m-1)个数中选取1个数为止。2. 从n个数中选取编号次小的一个数，继续执行1步，直到当前可选编号最大的数为m。很明显，上述方法是一个递归的过程，也就是说用递归的方法可以很干净利索地求得所有组合。下面是递归方法的实现：/// 求从数组a[1..n]中任选m个元素的所有组合。/// a[1..n]表示候选集，m表示一个组合的元素个数。/// b[1..M]用来存储当前组合中的元素, 常量M表示一个组合中元素的个数。void combine( int a[], int n, int m, int b[], const int M ){ for(int i=n; i>=m; i--) // 注意这里的循环范围 { b[m-1] = i - 1; if (m > 1) combine(a,i-1,m-1,b,M); else // m == 1, 输出一个组合 { for(int j=M-1; j>=0; j--) cout << a[b[j]] << " "; cout << endl; } }}
因为递归程序均可以通过引入栈，用回溯转化为相应的非递归程序，所以组合问题又可以用回溯的方法来解决。为了便于理解，我们可以把组合问题化归为图的路径遍历问题，在n个数中选取m个数的所有组合，相当于在一个这样的图中（下面以从1,2,3,4中任选3个数为例说......