《算法基础》打开算法之门(Algorithms Unlocked) 读书笔记

递归

阶乘函数

  1. n == 0 ? n! = 1
  2. n > 0 ? n! = n * (n - 1) * (n - 2) … 2 * 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define __STDC_WANT_LIB_EXT1__ 1
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

long factory(int);

int main(int argc, char *argv[])
{
int n = 0;
printf("input a number: ");
scanf("%d", &n);
long res = factory(n);
printf("factory: %ld\n", res);
return 0;
}

long factory(int n) {
if (n == 0) {
return 1;
}
return n * factory(n - 1);
}

递归查找

  1. 数组长度计算: sizeof nums / sizeof(int);
  2. 索引变化值保存到 int idx = 0; 将 idx 指针传进去
  3. *pi 先取值在 ++
  4. 找到的条件 nums[i] == x
  5. 未找到的提交 i >= len
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
#include <stdio.h>
#include <stdlib.h>

int recursive_find(int [], int, int, int *);

int main(int argc, char *argv[]) {

int nums[] = {1, 2, 3, 4, 5};
int len = sizeof nums / sizeof(int);

for (int i = 0; i < len; i++) {
printf("%d: %d\n", i, nums[i]);
}

int idx = 0;
int val = 0;
printf("input a num to find: ");
scanf("%d", &val);
int res = recursive_find(nums, len, val, &idx);

printf("found x at %d\n", res);

return 0;
}

int recursive_find(int nums[], int len, int x, int *pi) {

int i = *pi;
if (nums[i] == x) {
return i;
}

// not found
if (i >= len) {
return -1;
}

printf("recursive_find x: %d, i: %d, el: %d\n", x, i, nums[i]);
(*pi)++;

return recursive_find(nums, len, x, pi);
}

查找

二分查找法

初级版

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
#include <stdio.h>
#include <unistd.h>

int binary_search(int [], int, int);

int main(int argc, char *argv[]) {

int nums[5] = {0};

for (int i = 0; i < 5; i++) {
nums[i] = 2 * i + 1;
}

int len = sizeof(nums) / sizeof(int);
int n = 0;

while(1) {
printf("input value to find: ");
scanf("%d", &n);
binary_search(nums, n, len);
}

return 0;
}

int binary_search(int nums[], int target, int len) {
int start = 0;
int end = len - 1;
int mid = len / 2;
int res = 0;
int i = 0;

printf("%d,%d,%d\n", target, nums[start], nums[end]);
if (target < nums[start] || target > nums[end]) {
printf("beyond, not found.\n");
return -1;
}

while (end != start && target != nums[mid]) {
printf("[%d] len: %d, start: %d, mid: %d, res: %d, end: %d\n", i++, len, start, mid, nums[mid], end);
if (target < nums[mid]) {
end = mid;
mid = (mid - start) / 2 + start;
} else if (target > nums[mid]) {
start = mid;
mid = (end - mid) / 2 + mid;
}

// 剩下最后两个值了
if (mid == start || mid == end) {
if (target == start) {
mid = start;
} else if (target == end) {
mid = end;
}
start = end;
}

sleep(1);
}

if (nums[mid] == target) {
printf("found %d at %d\n", nums[mid], mid);
} else {
printf("not found %d\n", target);
}
printf("----------------------------------\n");

return nums[mid];
}
  1. 非法值判断,超出数组值得范围了不用进入循环查找了
  2. 结束条件:找到值了 targetnums[mid] 相等 , 循环结束了 start == end
  3. 剩下最后两个值得临界点: mid, start 相等或 midend 相等。

优化版

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

int binary_search(int nums[], int target, int len) {
int start = 0;
int end = len - 1;
int mid = len / 2;
int res = 0;
int i = 0;

if (target < nums[start] || target > nums[end]) {
return -1;
}

while (start <= end) {
i++;
mid = (start + end) / 2;

int val = nums[mid];
if (val == target) {
printf("found step: %d\n", i);
return mid;
}

if (target < val) {
end = mid - 1;
} else if (target > val) {
start = mid + 1;
}
}
printf("not found step: %d\n", i);

return -1;
}

优化版原理是排除了中间 nums[mid] 元素,因为这个元素本身已经被比较过了,所以在中间索引发生变化的时候只需要

mid 向前后移动一位即可得到正确的未比较的范围。

这样就省去了 初级版 中的 mid, start, end 之间的互相比较,因为 mid +- 1 之后必然会有一个会碰到 startend 的值。

然后就是在循环体内部如果找到了目标值,直接返回下标即可。

递归版

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

int binary_search(int nums[], int start, int end, int target) {

printf("start[%d] - end[%d]\n", start, end);

// 取中值比较,找到了退出
int mid = (start + end) / 2;
int val = nums[mid];
if (val == target) {
return mid;
}

// 没找到,判断是否循环结束,结束了退出
if (start >= end) {
printf("over not found.\n");
return -1;
}

// 两者都不是,则还可以继续找
if (target < val) {
end = mid - 1;
} else if (target > val) {
start = mid + 1;
}
// 下一次查找
return binary_search(nums, start, end, target);
}

递归版,需要改进下传递进入的参数。

这个时候需要将 start, end 两个变动的索引值保存起来,便下次传入 binary_search 使用,

这里面有三个关键地方:

  1. 找到的条件, nums[mid]target 值相等,表示找到了
  2. 没找到,但是没有更多的元素需要遍历的,这属于最差的情况
  3. 进入下一次递归的准备工作,即改变 start-end 的值,进入下一次循环查找

排序

选择排序

选择排序原理:总以从 i = 0 未排序的元素作为参考,查找后面比它小的元素,找到了就替换,直到数组最后一个元素为止,

如果没找到就将 i + 1 往前推进,查找后面比 i + 1 位置的元素小的,找到替换,如此往复,知道 i + 1 到达

数组末尾,排序结束。

递归示例

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

int select_sort_recursive(int nums[], int count, int *step, int *total) {
int tmp = 0;

if (*step > count - 1) {
return -1;
}

for (int i = *step + 1; i < count; i++) {
int curr = nums[*step];
// 交换
if (nums[i] < curr) {
tmp = curr;
nums[*step] = nums[i];
nums[i] = tmp;
}
(*total)++;
}

(*step)++;

select_sort_recursive(nums, count, step, total);

return 0;
}

上面的程序,需要执行的步骤计算方式:

step: 1 需要循环 count - 1 次,

step: 2 需要循环 count - 2 次,

step: count - 1 需要循环 1 次。

最后得出结论: (n - 1) + (n - 2) + ... + 1 -> (n - 1) * n / 2

例子中数组长度为: 7,即需要执行 6 * 7 / 2 = 21

时间复杂度即为: O(n2)

双重循环示例

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

int select_sort_for(int nums[], int count) {

int tmp = 0, times = 0;

for (int i = 0; i < count; i++) {
for (int j = i + 1; j < count; j++) {

times++;
if (nums[j] < nums[i]) {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}

printf("times: %d\n", times);

return 0;
}

本文标题:《算法基础》打开算法之门(Algorithms Unlocked) 读书笔记

文章作者:ZhiCheng Lee

发布时间:2019年05月09日 - 22:59:12

最后更新:2019年05月15日 - 23:20:38

原始链接:http://blog.gcl666.com/2019/05/09/c_algorithm_unlocked/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%