1.2 递归算法

  • 「折半查找」(递归实现)
#define COMPARE(x, y) (((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1)

int binsearch(int list[], int searchnum, int left, int right)
{
    int middle;
    if (left <= right) {
        middle = (left + right) / 2;
        switch (COMPARE(list[middle], searchnum)) {
        case -1: 
            return binsearch(list, searchnum, middle + 1, right)
        case 0: return middle;
        case 1: 
            return binsearch(list, searchnum, left, middle - 1)
        }
    }
    return -1;
}
  • 「全排列」 给定由 n(n1)n(n \geq 1) 个元素组成的集合,输出该集合所有可能的排列。 要解决 nn 个元素集合的排列问题,就要解决 n1n - 1 个元素集合的排列问题。程序中的 i 即正在解决 i 个元素集合的排列问题,从 i = 0i = n,初始函数调用的是 perm(list, 0, n-1)
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void perm(char *list, int i, int n)
{
    int j, temp;
    if (i == n) {
        for (j = 0; j <= n; j++)
            printf("%c", list[j]);
        printf("    ");
    }
    else {
        for (j = i; j <= n; j++) {
            SWAP(list[i], list[j], temp);
            perm(list, i+1, n);
            SWAP(list[i], list[j], temp);
        }
    }
}

results matching ""

    No results matching ""