《算法竞赛入门经典》 第四章：函数与程序结构

发表于 | 分类于

基础知识

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
// 计算两点之间的欧几里德的距离
double dist(double x1, double x2, double y1, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double dist_1(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return hypot(dx, dy);
}

struct Point {
    double x, y;
};

double dist_2(struct Point a, struct Point b) {
    return hypot(a.x - b.x, a.y - b.y);
}

typedef struct {
    double x, y;
}Point_;

double dist_3(Point_ a, Point_ b) {
    return hypot(a.x - b.x, a.y - b.y);
}
1
2
3
4
5
6
7
8
9
10
11
12
// 4.1 组合数（有BUG，中间变量可能会溢出）
long long factorial(int n) {
    long long m = 1;
    for (int i = 1; i <= n; i++) {
        m *= i;
    }
    return m;
}

long long C(int n, int m) {
    return factorial(n) / (factorial(m) * factorial(n - m));
}
1
2
3
4
5
6
7
8
// 4.1 组合数
long long C(int n, int m) {
    if (m < n - m) m = n - m;
    long long ans = 1;
    for (int i = m + 1; i <= n; i++) ans *= i;
    for (int i = 1; i <= n - m; i++) ans /= i;
    return ans;
}
1
2
3
4
5
6
7
// 4.2 素数判定 （有问题）
int is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

1会被误判为素数，当n太大的时候，当n为接近int最大值的素数时候，i*i有可能会发生溢出。

1
2
3
4
5
6
7
8
9
// 4.2 素数判定
int is_prime_1(int n) {
    if (n <= 1) return 0;
    int m = floor(sqrt(n) + 0.5);
    for (int i = 2; i <= m, i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

避免了重复计算sqrt(n)，同时+0.5避免了xxx.99999出现后取整的误差。

1
2
3
4
5
6
7
8
9
// 4.3 用函数交换变量（错误）
void swap(int a, int b) {
    int t = a; a = b; b = t;
}

    int a, b;
    a = 3; b = 4;
    swap(3, 4);
    printf("a: %d b: %d\n", a, b);

同理，试了下，java也是不行的。

1
2
3
4
5
6
7
8
9
10
11
public static void swap(int a, int b) {
    int t = a;
    a = b;
    b = t;
}

public static void main(String[] args) {
    int a = 3, b = 4;
    swap(a, b);
    System.out.printf("a = %d, b = %d.", a, b);
}

1
2
3
4
5
6
7
8
9
10
// 4.3 用函数交换变量
void swap(int* a, int* b) {
    int t = *a; *a = *b; *b = t;
}

    int a =3, b = 4;
    swap(&a, &b);
    printf("a = %d, b = %d\n", a, b);

a = 4, b = 3

Q：递归和迭代到底是什么关系？

1
2
3
4
5
6
7
8
9
10
11
12
13
// 计算数组的元素和（错误，PS：C++中是可行的，亲测）
int sum(int a[]) {
    int ans = 0;
    for (int i = 0; i < sizeof(a); i++) {
        ans += a[i];
    }
    return ans;
}

    int a[] = {1,2,3};
    printf("%d\n", sum(a));
    
6(C++测得)

新建了个c项目测试了下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>

int sum(int a[]) {
    int ans = 0;
    for (int i = 0; i < sizeof(a); i++) {
        ans += a[i];
    }
    return ans;
}

int main() {
    int a[] = {1,2,3};
    printf("%d\n", sum(a));
    return 0;
}

D:\Markdown\Coding\C\Exercises\main.c: In function 'sum':
D:\Markdown\Coding\C\Exercises\main.c:5:31: warning: 'sizeof' on array function parameter 'a' will return size of 'int *' [-Wsizeof-array-argument]
     for (int i = 0; i < sizeof(a); i++) {
                               ^
D:\Markdown\Coding\C\Exercises\main.c:3:13: note: declared here
 int sum(int a[]) {

修改后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

int sum(int* a, int n) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i];
    }
    return ans;
}

int main() {
    int a[] = {1,2,3};
    printf("%d\n", sum(a + 1, 2));
    return 0;
}

5

回到c++的环境中来：c可以的c++一定可以嘛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 计算数组的元素和（正确）
int sum(int* a, int n) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i];
    }
    return ans;
}

    int a[] = {1,2,3};
    printf("%d\n", sum(a + 1, 2));
    return 0;

5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 计算左闭右开区间的元素和（两种写法）
// 方法一
int sum(int* begin, int* end) {
    int n = end - begin;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += begin[i];
    }
    return ans;
}

// 方法二
int sum(int* begin, int* end) {
    int *p = begin;
    int ans = 0;
    for (int *p = begin; p != end; p++) {
        ans += *p;
    }
    return ans;
}

暂时掠过：函数做参数。道理明白，题先放着。

1
2
3
4
// 用递归计算阶乘
int f(int n){
    return n == 0 ? 1 : f(n - 1) * n;
};

记住，调用自己和调用其他函数没有什么本质不同。

4-1 UVa1339 Ancient Cipher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
  char s1[200], s2[200];
  while(scanf("%s%s", s1, s2) == 2) {
    int n = strlen(s1);
    int cnt1[26] = {0}, cnt2[26] = {0};
    for(int i = 0; i < n; i++) cnt1[s1[i] - 'A']++;
    for(int i = 0; i < n; i++) cnt2[s2[i] - 'A']++;
    sort(cnt1, cnt1 + 26);
    sort(cnt2, cnt2 + 26);
    int ok = 1;
    for(int i = 0; i < 26; i++)
      if(cnt1[i] != cnt2[i]) ok = 0;
    if(ok) printf("YES\n"); else printf("NO\n");
  }
  return 0;
}


JWPUDJSTVP
VICTORIOUS

YES

4-2 UVa489 Hangman Judge

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
#include <bits/stdc++.h>
using namespace std;

#define maxn 105
int Left, Chance; // 还要猜left个位置，错chance次后就会输
char s[maxn], s1[maxn];
int win, lose;

void guess(char ch) {
    int bad = 1;
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == ch) { Left--; s[i] = ' '; bad = 0; }
    }
    if (bad) Chance--;
    if (!Chance) lose = 1;
    if (!Left) win = 1;
}

int main() {
    int rnd;
    while (scanf("%d%s%s", &rnd, s, s1) == 3 && rnd != -1) {
        printf("Round %d\n", rnd);
        win = lose = 0;
        Left = strlen(s);
        Chance = 7;
        for (int i = 0; i < strlen(s1); i++) {
            guess(s1[i]);
            if (win || lose) break;
        }
        if (win) printf("You win.\n");
        else if (lose) printf("You lose.\n");
        else printf("You chickened out.\n");
    }

    return 0;
}

4-3 UVa133 The Dole Queue

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
#include <bits/stdc++.h>
using namespace std;

#define maxn 25
int n, m, k, cell[maxn];

int go(int p, int d, int t) {
    while (t--) {
        do {
            p = (p + d + n - 1) % n + 1;
        } while (cell[p] == 0);
    }
    return p;
}

int main() {
    while (scanf("%d%d%d", &n, &k, &m) == 3 && n) {
        for (int i = 1; i <= n; i++) cell[i] = i;
        int left = n;
        int p1 = n, p2 = 1;
        while (left) {
            p1 = go(p1, 1, k);
            p2 = go(p2, -1, m);
            printf("%3d", p1); left--;
            if (p2 != p1) { printf("%3d", p2); left--; }
            cell[p1] = cell[p2] = 0;
            if (left) printf(",");
        }
        printf("\n");
    }

    return 0;
}

4-4 UVa213 Message Decoding

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
// UVa213 Message Decoding
// Rujia Liu
// 此版本保留书中展示的调试语句
#include<stdio.h>
#include<string.h>

int readchar() {
  for(;;) {
    int ch = getchar();
    if(ch != '\n' && ch != '\r') return ch;
  }
}

int readint(int c) {
  int v = 0;
  while(c--) v = v * 2 + readchar() - '0';
  return v;
}

int code[8][1<<8];

int readcodes() {
  memset(code, 0, sizeof(code));
  code[1][0] = readchar();
  for(int len = 2; len <= 7; len++) {
    for(int i = 0; i < (1<<len)-1; i++) {
      int ch = getchar();
      if(ch == EOF) return 0;
      if(ch == '\n' || ch == '\r') return 1;
      code[len][i] = ch;
    }
  }
  return 1;
}

// 用于调试
void printcodes() {
  for(int len = 1; len <= 3; len++)
    for(int i = 0; i < (1<<len)-1; i++) {
      if(code[len][i] == 0) return;
      printf("code[%d][%d] = %c\n", len, i, code[len][i]);
    }
}

int main() {
  while(readcodes()) {
//printcodes();
    for(;;) {
      int len = readint(3);
      if(len == 0) break;
//printf("len=%d\n", len);
      for(;;) {
        int v = readint(len);
//printf("v=%d\n", v);
        if(v == (1 << len)-1) break;
        putchar(code[len][v]);
      }
    }
    putchar('\n');
  }
  return 0;
}

4-5 UVa512 Spreadsheet Tracking

1
2


4-6 UVa12412 A Typical Homework

1
2