做了一个好玩的梦

2010/08/31

       过去的几天中，给十台机器装上了fedora 12, 又装了必要的软件。昨天晚上，我梦到我把一个同学的运行windows的机器装上了ubuntu，装完之后，我还感觉害怕，很害怕很害怕，因为这人的机器里可能有重要的东西或者说这同学可能不习惯用ubuntu。直到醒来之前，还感觉害怕，害怕这位同学和我吵架。醒了之后，才发现这是一个梦。
       哎，都过去一年半了，我居然会梦到这个人，悲剧！或许是对这个人的所做所为感觉恶心吧，一直感觉恶心。我不应该这样，不应该啊不应该。我把关于这个人的记忆放在这里，但愿就放下了，但愿大脑里永远不会有了，就在这里吧。卑鄙是卑鄙者的通行证，高尚是高尚者的墓志铭。厚黑是厚黑者的通行证，薄白是薄白者的墓志铭。

Posted in 活着2 条评论

一道题（转化为图）

2010/08/31

原文：

      You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < · · · < an , where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an ), which is your destination.
    You’d ideally like to travel 200 miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is (200 − x)^2 . You want to plan your trip so as to minimize the total penalty—that is, the sum, over all travel days, of the daily penalties.
大意：

      你将要进行一次长途旅行。旅行起点标记为0英里。沿途有n个hotel，它们的位置分别是a1 < a2 <……< an，ai是从出发点测量的结果。只能停在hotel里，但可以选择停在哪个hotel。目标是停在an。
      理想的情况是每天行进200英里，但这也许是不可能的（取决于hotel之间的距离）。如果每天行进x英里，penalty是(200-x)的平方。你为旅行做计划，使得总penalty最小。

      ai既代表第i个hotel，又代表第i个hotel到起点的距离。

解法：

我们把hotel a1…an放在一条直线上，从左到右依次排列。任意一对hotel(ai, aj), i<j，有一条弧。这条弧表示：某一天，从ai行进到了aj。这条弧的代价是(200-(aj-ai))的平方。这样，我们得到一个有向无环图。问题转化求这个有向无环图中节点a1到节点an的最短路径。

Posted in 笔试面试2 条评论

生成全排列

2010/08/27
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

/*
CSDN上说是迅雷招人的题。
字符串长度为N，生成N个字符的全排列，就是生成1个字符加上N－1个字符的全排列。
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
 
void myswap(char *p, int i, int j)
{
	char c = p[i];
	p[i] = p[j];
	p[j] = c;
}
 
void generate(char *p, int start, int len)
{
	if(start==len) 
	{
		printf("%s\n", p);
		return ;
	}
	int i = 0;
	for(i=0; i<len-start; i++)
	{
		myswap(p, start, i+start);
		generate(p, start+1, len);
		myswap(p, start, i+start);
	}
}
 
 
 
void myswap1(char *p, char *q)
{
	char c = *p;
	*p = *q;
	*q = c;
}
void generate1(char *str, char *p ,int len)
{
	if(len == 0)
	{
		printf("%s\n", str);
		return;
	}
 
	int i=0;
	for(i=0; i<len; i++)
	{
		myswap1(p, p+i);
                generate1(str, p+1, len-1);	
		myswap1(p, p+i);
	}
}
 
void foo(const char *str)
{
	int len = strlen(str);
	char *p = (char *) malloc (len+1);
	if(p==NULL) exit(1);
	memcpy(p, str, len+1);
	generate(p, 0, len);
        //generate1(p, p, len);//这个好像更好一些	
	free(p);
}
 
 
 
int main()
{
	char *str = "abcde";
	foo(str);
	return 0;
}

Posted in C/C++9 条评论

N皇后

2010/08/26
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N 8
 
int count = 0;
 
void print(int (*a)[N])
{
	count ++;
	int i = 0;
	int j = 0;
	for(i=0; i<N; i++)
	{
		for(j=0; j<N; j++)
			printf(" %d", a[i][j]);
		printf("\n");
	}
	printf("\n\n");
}
 
//在a[i][j]处放一个皇后
void set(int (*a)[N], int i, int j)
{
	a[i][j] = 1;
}
 
//判断a[i][j]是否有皇后
int is_set(int (*a)[N], int i, int j)
{
	return a[i][j] == 1;
}
 
//清除a[i][j]处的皇后
void clear(int (*a)[N], int i, int j)
{
	a[i][j] = 0;
}
 
//判断a[i][j]处的皇后是否与其他皇后冲突
int conflict(int (*a)[N], int i, int j)
{
	int row = i;
	int colum = j;
	for(--i, --j; i>=0 && j>=0; i--, j--) // 斜对角
		if(is_set(a, i, j)) return 1;
 
	i = row;
        j = colum;
	for(--i, ++j; i>=0 && j<=N-1; i--, j++) // 斜对角
		if(is_set(a, i, j)) return 1;
 
	i = row;
	j = colum;
	for(--i; i>=0; i--)                     // 同一列
		if(is_set(a, i, j)) return 1;
 
	return 0;
}
void queen(int (*a)[N], int i)
{
	if(i == N)  // 如果已经放了N个皇后，打印并返回 
	{
		print(a);
		return;
	}
 
	int j = 0;
	for(j=0; j<N; j++)  // 放第i（0 ~ N-1）个皇后，每个位置都试。
	{
		set(a, i, j);
		if(!conflict(a, i, j)) 
			queen(a, i+1);
		clear(a, i, j);
	}
}
int main()
{
	int a[N][N];
	memset(a, 0, sizeof(a));
	queen(a, 0);
	printf("%d\n", count);
	return 0;
}

Posted in C/C++4 条评论

打印个螺旋方阵

2010/08/25
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

/*
1	2	3	4	5	6	
20	21	22	23	24	7	
19	32	33	34	25	8	
18	31	36	35	26	9	
17	30	29	28	27	10	
16	15	14	13	12	11	
*/
#include <stdio.h>
#include <stdlib.h>
 
void generate(int **M, int x1, int y1, int x2, int y2, int x)
{
	if(x1>x2) return;
	int i, j;
	for(i=x1, j=y1; j<y2; j++)
        	M[i][j] = x++;
        for(i=x1, j=y2; i<x2; i++)
        	M[i][j] = x++;
	for(i=x2, j=y2; j>y1; j--)
        	M[i][j] = x++;
	for(i=x2, j=y1; i>x1; i--)
        	M[i][j] = x++;
	generate(M, x1+1, y1+1, x2-1, y2-1, x);
}
 
void print(int **M, int n)
{
	int i, j;
	for(i=0; i<n; i++)
	{
		for(j =0; j<n; j++)
		{
			printf("%d	", M[i][j]);
		}
		printf("\n");
	}
 
}
 
void matrix(int n)
{
	int **M = (int **) malloc(n*sizeof(int *));
	int i = 0;
	for(i=0; i<n; ++i)
		M[i] = (int *) malloc (n*sizeof(int));
 
	generate(M, 0, 0, n-1, n-1, 1);
	print(M, n);
 
	for(i=0; i<n; ++i)
		free(M[i]);
	free(M);
}
 
 
int main()
{
	matrix(4);
	return 0;
}

Posted in 未分类2 条评论

堆排序

2010/08/24
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
#define INCCAPACITY 100  
 
typedef int ElemType;
struct heap_operation; //前向声明
 
typedef struct Heap    //堆结构
{
	int capacity;  //容量
	int size;      //现有元素数量
	ElemType *data;  //指针，指向数组
        struct heap_operation *heap_op; // 操作函数
}Heap;
 
typedef struct heap_operation  //里面有一堆函数指针，类似于C＋＋的虚表
{
	void (*init_heap)(Heap *heap, ElemType *_data, int capacity, int size);
	void (*build_heap)(Heap *heap);
	ElemType (*get_min)(Heap *heap);
	ElemType (*delete_min)(Heap *heap);
	void (*insert)(Heap *heap, ElemType e);
}heap_operation;
 
int left_child(int index)  //得到一个元素的左孩子下标
{
	return 2*index+1;
}
 
int right_child(int index) //得到一个元素的右孩子下标
{
	return 2*index+2;
}
 
int parent(int index)   //得到一个元素的父结点下标
{
	return (index-1)/2;
}
 
// 将元素下沉，这是堆操作的核心。
void filter_down(Heap *heap, int index)
{
	ElemType ele = heap->data[index];
	int i = index;
	int child=0;
	for(i=index; i*2+1 <= heap->size-1; i=child)
	{
		child = 2*i + 1;
		if(child < heap->size-1 && heap->data[child] > heap->data[child+1])
			child++;
		if(heap->data[child] < ele)
			heap->data[i] = heap->data[child];
		else
			break;
	}
	heap->data[i] = ele;
}
 
//初始化堆
void init_heap(Heap *heap, ElemType *_data, int capacity, int size)
{
	heap->capacity = capacity;
	heap->size = size;
	heap->data = _data;
}
 
 
// 建堆
void build_heap(Heap *heap)
{
	int i = parent(heap->size - 1);
	while(i>=0)
	{
		filter_down(heap, i);
		i --;
	}
}
 
ElemType get_min(Heap *heap)
{
	return heap->data[0];
}
 
void resizeheap(Heap *heap)
{
	ElemType * p;
	p = (ElemType *)malloc((heap->capacity+INCCAPACITY)*sizeof(ElemType));
	if(p==NULL)
        {
		printf("ERROR at line %d\n", __LINE__);
		exit(0);
	}
	memcpy(p, heap->data, sizeof(ElemType)*heap->capacity);
	heap->capacity += INCCAPACITY;
	free(heap->data);
	heap->data = p;
}
 
// 插入一个元素
void insert(Heap *heap, ElemType e)
{
	int i = 0;
	if(heap->size == heap->capacity) 
		resizeheap(heap);
	heap->data[heap->size] = e;
	heap->size++;
	i  = heap->size - 1;
	while(parent(i)>=0)
	{
		if(heap->data[parent(i)]>e)
		{
			heap->data[i] = heap->data[parent(i)];
			i = parent(i);
		}
		else
			break;
	}
	heap->data[i] = e;
}
 
ElemType delete_min(Heap *heap)
{
	ElemType i = heap->data[0];
        heap->data[0] = heap->data[ heap->size-1 ];
	heap->size --;
 
	filter_down(heap, 0);
	return i;
}
 
void print_array(ElemType array[], int n)
{
	int i = 0;
	while(i<n)
	{
		printf("%d ", array[i++]);
	}
	printf("\n");
}
 
void print_heap(Heap *heap)
{
	print_array(heap->data, heap->size);
}
 
int main()
{
	ElemType e;
        ElemType a[] = {30, 6, 7, 4, 5, 1, 6, 1};
	Heap aheap;
 
	heap_operation heap_op;
	heap_op.init_heap = init_heap; 
        heap_op.build_heap = build_heap;
	heap_op.get_min = get_min;
	heap_op.delete_min = delete_min;
        heap_op.insert = insert;
 
	aheap.heap_op = &heap_op;
 
	aheap.heap_op->init_heap(&aheap, a, sizeof(a)/sizeof(a[0]), sizeof(a)/sizeof(a[0]));
	aheap.heap_op->build_heap(&aheap);
 
	print_heap(&aheap);
 
	printf("min of the array %d\n", aheap.heap_op->get_min(&aheap));
        e = aheap.heap_op->delete_min(&aheap);	
	print_heap(&aheap);
 
	aheap.heap_op->insert(&aheap, e);
	print_heap(&aheap);
 
 
	return 0;
}

Posted in C/C++3 条评论

大整数加法

2010/08/24

在CSDN上看到的题，说是华为的上机题。第一次写的时候忘了最高位的进位。被一哥们指出。然后又加了两行。大整数加法应该是大数运算里最简单的，减法稍难，乘法还要难一些，除法最难。学计算机组成原理的时候，除法也是最烦的，运行速度最慢的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
//按小学学的方法做。
void add_big(const char *num1, const char * num2, char *result, int len)
{
    char *p1 = num1 + strlen(num1) - 1;
    char *p2 = num2 + strlen(num2) - 1;
    char *r = result + len;
    int carry = 0;
    result[len+1] = '\0';
    while (p1>=num1 && p2>=num2)
    {
        int tmp = (*p1-'0')+(*p2-'0')+carry;
        if (tmp>=10)
        {
            carry = 1;
            tmp = tmp - 10;
            *r = tmp + '0';
        }
        else
        {
            carry = 0;
            *r = tmp + '0';
        }
        r--;
        p1--;
        p2--;
    }
    while (p1>=num1)
    {
        int tmp = *p1-'0'+carry;
        if (tmp>=10)
        {
            carry = 1;
            tmp = tmp - 10;
            *r = tmp + '0';
        }
        else
        {
            carry = 0;
            *r = tmp + '0';
        }
        r--;
        p1--;
 
    }
 
    while (p2>=num2)
    {
        int tmp = *p2-'0'+carry;
        if (tmp>=10)
        {
            carry = 1;
            tmp = tmp - 10;
            *r = tmp + '0';
        }
        else
        {
            carry = 0;
            *r = tmp + '0';
        }
        r--;
        p2--;
    }
 
    if(carry==1) *r = '1'; //这儿是新加的。
    else *r = '0';
}
 
 
int main()
{
    char *result;
    char *num1 = "99999999999999";
    char *num2 = "99999999999999";
    int len = 0;
    int num1_len = strlen(num1);
    int num2_len = strlen(num2);
 
    if (num1_len > num2_len)
        len = num1_len;
    else
        len = num2_len;
 
    result = (char *)malloc(len+2);
    memset(result, '0', len+2);
    if (result!=NULL)
    {
        char *p = result-1;
        add_big( num1, num2, result, len);
        while (*(++p)=='0');
        printf("%s\n", p);
 
    }
    return 0;
}

Posted in C/C++6 条评论

选择排序

2010/08/23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int find_smallest(int *array, int left, int right)  
{
	int smallest = left;
	while(left<=right)
	{
		if(array[left] < array[smallest])
			smallest = left;
		left++;
	}
	return smallest;
}
 
void select_sort(int *array, int left, int right)
{
	int i = left;
	for(; i<right; i++)
	{
		int index = find_smallest(array, i, right); //找出最小的元素的下标
		myswap(array+i, array+index); //交换
	}
}

Posted in C/C++我抢沙发

插入排序

2010/08/23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void insert_sort(int *array, int left, int right)
{
	int j = left+1;       //从第二个元素开始
	for(; j<=right; j++)   //直到最后一个元素
	{
		int i = j;                           
		int data = array[i];
		for(; i>left; --i)      //查找data的正确位置
		{
			if(data<array[i-1])
				array[i] = array[i-1];
			else
				break;
		}
		array[i] = data; //放置data
	}
}

Posted in C/C++我抢沙发

qsort

2010/08/23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

void myswap(int *a, int *b)
{
	int i = *a;
	*a = *b;
	*b = i;
}
 
int get_pivot(int *array, int l, int r)
{
	int i = rand()%(r-l+1)+l;//生成 [l, r]之间的随机数
	myswap(array+l, array+i);//把随机得到的基准放在array[l]
	return array[l];
}
 
void myqsort(int array[], int left, int right)
{
	if(left<right)
	{
		get_pivot(array, left, right); //随机化
		int x = array[left]; //以此为基准
		int l = left;         //待分的其实是[left+1, right], 但l和r分别设成了left, right+1. 因为
		int r = right+1; //下面的循环中先++l，--r再访问。
		while(1)
		{
			while(array[++l] < x && l<right);
			while(array[--r] > x && r>left);
			if(l<r) myswap(array+l, array+r);
			else break;
		}//当循环退出时，array[r]小于等于x, array[l]大于等于x
		myswap(array+left, array+r);// 所以，把较小的array[r]同array[left]交换
		myqsort(array, left, r-1);
		myqsort(array, r+1, right);
	}
}

Posted in C/C++我抢沙发

下一页