为学日益，为道日损
2011年11月03日 04:40
最近听港大数据结构课，于是想动手实现一些最基本的算法。深度优先跟广度优先是最基本的遍历算法，实现的时候还是会有一些小的错误。
比如删除队列中的元素，出现段错误因为：
head -> next = head -> next -> next;
free(head -> next)
以及遍历链表时无法得到最后一个元素
while(tmp -> next != NULL)
都是一些细节没有处理好，以后写程序要注意了……
附上两个程序的图
BFS：
C语言程序可在GitHub下载：https://github.com/jia1546/BFS
DFS：
C语言程序可在GitHub下载：https://github.com/jia1546/DFS
2011年11月02日 02:44
折腾了好久，始终没有在网上找到解决问题的办法，偶然发现了这篇文章，心中的郁闷终于消除
http://www.cnblogs.com/ghj1976/archive/2011/01/26/1945476.html
可是U盘只读，需要使用sudo才能修改文件，怎样让U盘可读写呢？晚上回去问超哥吧……
接下来解决Ubuntu用不了wifi 的问题，它也折腾我好久了，每次去实验室还得专门找一台电脑上网，然后在笔记本上写程序，很不方便。
PS: 每次需要手动挂载，很不方便，下了usb管理工具，mountmanager可以自动挂载，方便多了
2011年10月28日 02:40
港大CS一年级data structure的作业，模拟“画鬼脚”游戏，编码测试花了三个小时，总算可以交差。在网上搜了下，发现这个简单游戏背后有着不简单的数学原理。
1. 游戏规则
画鬼脚又称画线抽签。是几个人需要用抽签来决定事物或工作的分配时，最简便的方式。进行时只需要一个能够画线的地方或物品就足够了，人数决定了竖线的条数。
在竖线的一端分别写上参与人，将需分配的事物或工作分成与人数的同等分后分别写在另一端。然后在每两个竖线相隔的区域，每个人任意的画上横线。每个人画横线的条数一般不限，但横线间不可交叉且横线不可横跨穿过两个间隔。
从写有自己名字的竖线一端开始，向另一端前进。每当遇上横线时，则沿着横线转弯走向另一根竖线，到达竖线后继续向前最终到达另一端，而这一端所写的事物便是你所抽到的事物。
2. 数学现象
当游戏结束时总是会出现1:1的对应关系，不会有多个人对应同一物品也不会有物品没有人对应。重要的是这个性质在任意条横线情况下均成立
3. 重要性质
a) 排列性
整个游戏过程会将一串输入元素排列变为另一串顺序不同的输出元素的排列
b) 周期性
可以将游戏过程看作对输入元素的变换M，则在对输入元素重复进行有限次变换后，输出元素排列会与输入元素排列相同。即 
c) 可逆性
对任意变换M，存在变换
，使得M = 
d) 等价性
将输入序列变为同一输出序列的变换M的个数是无无限的，它们之间是等价的。那么如何寻找最小数目横线的变换呢？可以参考：http://en.wikipedia.org/wiki/Ghost_Leg
4. 游戏过程模拟
因为添加的横线距离顶端的高度不能相同，可以用链表结构来组织数据，然后设计链表上的游戏算法，整个过程也就显得清晰简单了。C代码可以从GitHub上下载: https://github.com/jia1546/ghostleg
2011年10月26日 20:48
If you want to know more about Linux Commands, refer to the following URLs:
http://www.computerhope.com/unix/overview.htm
2011年10月24日 03:05
问题描述： 输入一组整数，求出这组数字子序列和中最大值
Jon Bentley’s在《编程珠玑》中给出的算法如下：
input: an array of integers
output: largest sum of contiguous integers in the given array A
Algorithm:
total = 0 // sum of contiguous integers
maxNow = 0 // the max sum up to the current position
for each element A[i] in the given array A
do total = max(total + A[i], total)
maxNow = max(maxNow, total)
output maxNow
time complexity : O(n)
这个算法最核心的思想在于：如果a[i]是负数那么它不可能代表最有序列的起点，因为任何包含a[i]的作为起点的子序列都可以通过用a[i+1]作为起点来改进。类似的有，任何的负的子序列不可能是最优子序列的前缀
但是这个算法存在问题：如果所有整数都是负数，则输出0，显然不对，这个情况下最大序列和应为数组中所有负数的最大值，所以修改原来的算法，加入判断。详细的C代码如下：
C代码如下：
#include <stdio.h>
#include <stdlib.h>
long long max(long a, long b)
{
long long result;
result = a > b ? a : b;
return result;
}
int main()
{
int n, i;
long long *array;
long long maxNow, total;
long long maxEle, allNegative;
while(scanf("%d", &n) != EOF)
{
array = (long long *) malloc(sizeof(long long) * n);
for(i=0; i<n; i++)
scanf("%lld", array+i);
maxNow = 0;
total = 0;
allNegative = 1;
maxEle = array[0];
for(i=0; i<n; i++)
{
total= max(total+array[i] , 0);
maxNow = max(maxNow, total);
maxEle = max(maxEle, array[i]);
if(array[i] >= 0)
allNegative = 0;
}
if(allNegative)
printf("%lld\n", maxEle);
else
printf("%lld\n", maxNow);
}
return 0;
}
2011年10月24日 01:01
1.问题描述：n个人（编号1~n)，从1开始报数，报到m的退出，剩下的人继续从1开始报数。按顺序输出列者编号
模拟过程，使用循环链表或者数组，但是链表便于删除，效率更高。使用循环链表的C代码如下:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int value;
struct node *next;
};
typedef struct node list;
int main()
{
int n, m;
int i;
while(scanf("%d%d", &n, &m) != EOF)
{
list *head, *tmp, *pre;
head = (list*)malloc(sizeof(list));
head -> value = 1;
head -> next = NULL;
tmp = head;
for(i=2; i<=n; i++)
{
list *node = (list*)malloc(sizeof(list));
node -> value = i;
node -> next =NULL;
tmp -> next = node;
tmp = node;
}
tmp -> next = head; //link the last to the head
pre = tmp;
tmp = head;
while(tmp -> next != tmp)
{
for(i=1; i<m; i++)
{
pre = tmp;
tmp = tmp -> next;
}
//delete the node to which tmp point to
pre -> next = tmp -> next;
printf("%d ", tmp -> value);
free(tmp);
tmp = pre -> next;
}
printf("%d\n", tmp -> value);
free(tmp);
}
return 0;
}
另一种方法是使用数学方法计算，C代码如下：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, m;
int i , p;
int *array, counter;
while(scanf("%d%d", &n, &m) != EOF)
{
i = 0;
array = (int*)malloc(sizeof(int)*n);
counter = 0;
while(++i <= n)
{
p = i * m;
while(p > n)
p = p - n + (p - n -1)/(m - 1);
array[counter] = p;
counter++;
}
if(counter == 1)
printf("%d\n", array[0]);
else
{
for(i=0; i<counter-1; i++)
printf("%d ", array[i]);
printf("%d\n", array[i]);
}
free(array);
}
return 0;
}
两种方法的时间复杂度都是O(n)
2011年10月21日 16:58
#include <stdio.h>
#include <stdlib.h>
int partition(int *array, int p, int r)
{
int x, i, j;
int tmp;
x = array[r];
i = p - 1;
for(j=p; j<=r-1; j++)
{
if(array[j] <= x)
{
i++;
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
tmp = array[r];
array[r] = array[i+1];
array[i+1] = tmp;
return i+1;
}
void quickSort(int *array, int p, int r)
{
int q;
if(p < r)
{
q = partition(array, p, r);
quickSort(array, p, q-1);
quickSort(array, q+1, r);
}
}
int main()
{
int *array, n;
int i;
while(scanf("%d",&n) != EOF)
{
array = (int*)malloc(sizeof(int)*n);
for(i=0; i<n; i++)
scanf("%d", array+i);
quickSort(array, 0, n-1);
for(i=0; i<n; i++)
printf("%d ", array[i]);
printf("\n");
}
return 0;
}
2011年10月21日 03:26
虽然知道算法的基本原理，还是动手写写吧。
代码如下：
#include <stdio.h>
#include <stdlib.h>
void MaxHeapfy(int *array, int i, int heapSize)
{
int l, r ;
int temp, largest;
l = 2 * i;
r = 2 * i + 1;
if(l <= heapSize && array[l] > array[i])
largest = l;
else
largest = i;
if(r <= heapSize && array[r] > array[largest])
largest = r;
if(largest != i)
{
temp = array[i];
array[i] = array[largest];
array[largest] = temp;
MaxHeapfy(array, largest, heapSize);
}
}
void BuildMaxHeap(int* array, int n)
{
int heapSize = n;
int i;
for(i=n/2; i>=1; i--)
MaxHeapfy(array, i, heapSize);
}
void HeapSort(int *array, int n)
{
int temp;
int heapSize = n;
int i;
BuildMaxHeap(array, n);
for(i=n; i>=2; i--)
{
temp = array[1];
array[1] = array[i];
array[i] = temp;
heapSize--;
MaxHeapfy(array, 1, heapSize);
}
}
int main()
{
int *array;
int n;
int i;
while(scanf("%d",&n) != EOF)
{
array = (int*)malloc(sizeof(int)*(n+1)); //the index starts from 1
for(i=1; i<=n; i++)
scanf("%d",array+i);
HeapSort(array, n);
for(i=1; i<=n; i++)
printf("%d ", array[i]);
printf("\n");
}
return 0;
}
PS：喜欢上Scribes Text Editor，虽然没有Vim, Emacs那般强大，但写写小程序够用了，之前试过很多编辑器，发现不是很简便，终于找到一个喜欢的了……
2011年10月20日 20:49
这道题源于华为校园招聘的机试题，想了很久没有好的解法，google之后发现Manacher's Algorithm可以达到O(n)的复杂度。
这篇文章讲得比较详细：http://www.felix021.com/blog/read.php?2040
C代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 1000000
int min(int a, int b)
{
int result;
result = a > b ? b : a;
return result;
}
int main()
{
char input[MAXSIZE], str[MAXSIZE];
char *result;
int p[MAXSIZE];
int i, j;
int mx, id;
int maxlen;
int pos;
str[0] = '$';
str[1] = '#';
while(gets(input))
{
memset(p, 0, sizeof(p));
mx = 0;
id = 0;
j = 2;
for(i=0; i<strlen(input); i++)
{
str[j] = input[i];
j++;
str[j] = '#';
j++;
}
str[j] = '\0';
for(i=1; i<strlen(str); i++)
{
p[i] = mx > i ? min(str[2*id-1], mx-i) : 1;
while(str[i+p[i]] == str[i-p[i]])
p[i]++;
if(i+p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
maxlen = 0;
pos = 0;
for(i=1; i<strlen(str); i++)
if(p[i] > maxlen)
{
maxlen = p[i];
pos = i;
}
result = (char*) malloc(sizeof(char)*(maxlen));
j = 0;
for(i=pos-(maxlen-1); i<=pos+(maxlen-1); i++)
{
if(str[i] != '#')
{
result[j] = str[i];
j++;
}
}
result[j] = '\0';
printf("length of the longest palindrome is %d\n", maxlen-1);
printf("Palindrome is %s\n", result);
}
return 0;
}
总结:
1. 在字符串中插入'#', 将奇数与偶数长度的回文串统一考虑
2. 使用数组记录已求回文的最右边界，降低时间复杂度到O(n)
2011年10月17日 01:43
给定一个字符串，由小写字母升序排列，且各不相同，输出这个字符串的全排列(字典序)，这个程序会超过一秒，主要是生成全排列部分的算法有问题不能做到输出有序，生成全排列之后不得不使用快速排序，因而会超时。更优化的算法进行中……
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 7
int counter = 0;
char array[1000][MAXSIZE];
int compare(const void *s1, const void *s2)
{
char *a, *b;
a = (char*)s1;
b = (char*)s2;
return strcmp(a, b);
}
void arrange(char *s, int start, int end)
{
int i;
char tmp;
if(start == end)
{
strcpy(array[counter], s);
counter++;
}
else
{
for(i=start; i<end; i++)
{
tmp = s[start];
s[start] = s[i];
s[i] = tmp;
arrange(s, start+1, end);
tmp = s[start];
s[start] = s[i];
s[i] = tmp;
}
}
}
int main()
{
char str[MAXSIZE];
int i;
while(scanf("%s",str) != EOF)
{
counter = 0;
arrange(str, 0, strlen(str));
qsort((void*)array, counter, sizeof(char[MAXSIZE]),compare);
//printf("counter = %d\n",counter);
for(i=0; i<counter; i++)
printf("%s\n",array[i]);
}
return 0;
}