博文
编程珠矶学习笔记（5）--两分搜索算法（折半查找算法）(2009-10-19 22:22:00)
摘要：个人原创，转载请注明出处，谢谢！
一、目的
input: 有序序列
output: 查找结果，如果为-1则未找到目标
constrain: 使用两分法进行查找，使查找时间复杂度为O(logn)
二、 算法原理
两分搜索算法是一种理解比较简单，但执行效率却十分高的算法。可以用循环的方式来实现，也可以用递归的方式来实现。算法原理如图:
通过不断的改变l和u的值来接近要查找的目标值（40）
m = ( 0 + 13 ) / 2 = 6 result: l = 0, u = m – 1 = 5
m = ( 0 + 5 ) / 2 = 2 result: l = m + 1 = 3, u = 5
m = ( 3 + 5 ) / 2 = 4 result: l = 3 , u = m – 1 = 3
三、代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 1000000
typedef int DataType;
DataType x[MAXN];
int n = 0;
int binarysearch (DataType t)
{ int l, u, m;
l = 0;
u = n-1;
while (l <= u) {
m = (l + u) / 2;
......
编程珠矶学习笔记（4）--挤压法查找变位词(2009-10-19 22:20:00)
摘要：个人原创，转载请注明出处，谢谢！
一、 目的
如示例：
input: 单词文件
output: 同位词归类文件
constrain: 归类所有为同位词的单词
何为同位词：单词字母相同，但字母的顺序不同:
pans 和snap是同位词
pots 、stop和tops是同位词，还有这些：
二、算法原理
如果我们输入如下单词序列，并期望对该序列进行同位词归类：
第一步：对每个单词进行签名。如这些单词：
我们使用每个单词的字母序列（按字母顺序进行排列）作为它的个人签名，如pans的签名是 anps，这样我们可以得到上图右侧的签名序列。
第二步：对签名序列进行排序。如下图：
通过对签名序列进行排序后，大家可以发现同位词聚在了一起，我们只需要将具有相同签名的单词合并在一起即可。
第三步：对排序后的签名序列进行挤压：
这样我们通过三步即完成了同位词的查找过程，实现代码其实很简单，但其算法思想给人眼前一亮的感觉。
三、代码
Sign.c:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORDMAX 100
int charcomp (char *x, char *y)
{ return *x - *y;
}
int main()
{ char word[WORDMAX], sig[WORDMAX];
while (scanf("%s", word) != EOF) {
strcpy......
编程珠矶学习笔记（3）--反转旋转（手摇法实现旋转）(2009-10-19 22:19:00)
摘要：个人原创，转载请注明出处，谢谢！
一、目的
如示例：
input: n = 10, rotdist = 5 (移动前5个元素到数组尾), x[] = {1,2,3,4,5,6,7,8,9,10}
output: x[6,7,8,9,10,1,2,3,4,5]
constrain: 使用尽可能少的额外内存
可通过手揺法来实现旋转，其原理如下图：
准备：两手上下平放，左手在上，右手在下，手面圴冲自己，此时规定十个手指从上到下分别代表1,2,3,4,5,6,7,8,9,10
第一步：将左手反转，手背冲自己，拇指此时冲地面：
第二步：将右手也反转，手背冲自己，拇指此时冲地面：
第三步：将两个手同是反转，手面冲自己，与准备动作的区别是，现在右手在上左在下，观察手指上的数字会发现，此时已经达到了移位的目的(6,7,8,9,10,1,2,3,4,5)：
这就是本算法的原理，通过三次反转(手摇三次)来实现旋转的目的。为了易于说明原理，本例采用了10个元素，移动5个的要求（必竟人就10个手指嘛），但对于其它任何要求，本算法也适用。
二、代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 10000000
int x[MAXN];
int rotdist, n;
void reverse(int i, int j)
{ int t;
while (i < j) {
t = x[i]; x[i] = x[j]; x[j] = t;
i++;
&n......
编程珠矶学习笔记（2）--移位旋转(2009-10-19 22:13:00)
摘要：个人原创，转载请注明出处，谢谢！
一、代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 10000000
int x[MAXN];
int rotdist, n;
int gcd(int i, int j)
{ int t;
while (i != 0) {
if (j >= i)
j -= i;
else {
t = i; i = j; j = t;
}
}
return j;
}
void jugglerot(int rotdist, int n)
{ &nb......
编程珠矶学习笔记（10）--查找最大和（扫描算法O(n)）(2009-10-19 12:12:00)
摘要：
个人原创，转载请注明出处，谢谢！
一、目的
input: n个元素的数组；
output: 在数组中查找相邻数的最大和；
constrain: 如最大和为负数，则最大和为0，即一个也不选。
二、算法原理
算法从数组的最左端x[0]开始，一直扫描到最右端x[n-1]，记下所碰到过的最大和，初始最大和为0。实际通过一个一个的增加元素来判断哪个子数组的和最大，抛弃小的和，留下大的和，最终得到最大和。就像我们看一排队伍中哪个人最高，我们从队伍的开头走起，发现一个比前面个子高的，就记下他来，然后往后走，又发现一个个子更高的，那就记下这个，忘掉之前的，再继续向后走，最终走到头，即可知道这个队伍中谁个子最高。和本算法唯一区别是，本算法不是求某个数最大，而是求哪几个连续数的和最大。如下图：
三、代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 10000000
int n;
float x[MAXN];
void sprinkle()
{
int i;
for (i = 0; i < n; i++) {
x[i] = 1 - 2*( (float) rand()/RAND_MAX);
}
}
float get_max_sum ()
{ int i;
float maxsofar = 0, maxendinghere = 0;
for (i = 0; i < n; i++) {
maxendinghere += x[i];
if (maxendinghere &l......
编程珠矶学习笔记（1）--位排序(2009-10-12 22:55:00)
摘要：个人原创，转载请注明出处，谢谢！
一、代码
#include <stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
inline void set_bit(int i)
{
a[i>>SHIFT] |= (1<<(i & MASK));
}
inline void clear_bit(int i)
{
a[i>>SHIFT] &= ~(1<<(i & MASK));
}
inline int test_bit(int i)
{
return a[i>>SHIFT] & (1<<(i & MASK));
}
int main()
{ int i;
for (i = 0; i < N; i++) {
clear_bit(i);
}
while (scanf("%d", &i) != EOF)
......