计算交替的上/下序列

Question

问题描述:计算从某个输入n向上的所有序列的数量.所以用户输入n; 然后我创建一个数字1..n数组,然后用该属性编号序列

例: n = 4

1 3 2 4
1 4 2 3
2 3 1 4
2 4 1 3
3 4 1 2

回答: 5

我的程序有效,但出于某种原因,我有时会得到0而不是答案.

#include <stdio.h>
#include <stdlib.h>

void *safeMalloc(int n) {
    void *p = malloc(n);
    if (p == NULL) {
        printf("Error: malloc(%d) failed. Out of memory?\n", n);
        exit(EXIT_FAILURE);
    }
    return p;
}

void swap(int *fir, int *sec) {
    int temp = *fir;
    *fir = *sec;
    *sec = temp;
}

void permute(int *array, int i, int length, int *count) {
    if (length == 2) {
        *count = 1;
        return;
    }
    if (length == i) {
        int v = 0, flag = 1;
        while (v < length) {
            if (v % 2 == 0) {
                if (array[v] < array[v + 1]) {
                    v++;
                } else {
                    flag = 0;
                    return;
                }
            }

            if (v % 2 != 0) {
                if (array[v] > array[v + 1]) {
                    v++;
                } else {
                    flag = 0;
                    return;
                }
            }
        }
        if (flag == 1) {
            /*
            int a;
            for (a = 0; a < length; a++)
                printf("%d", array[a]);
            printf("\n");
            */
            *count = *count + 1;
        }
    }
    int j = i;
    for (j = i; j < length; j++) {
        swap(array + i, array + j);
        permute(array, i + 1, length, count);
        swap(array + i, array + j);
    }
    return;
}

int main(int argc, char **argv) {
    int n;
    scanf("%d", &n);
    int *arr = safeMalloc(n * sizeof(int));
    int i;
    for (i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    int count = 0;
    permute(arr, 0, n, &count);
    printf("%d\n", count);
    return 0;
}

Answer 1

您基本上生成数组元素的所有排列并计算有效的排列。

您的代码有一个小缺陷：

• 循环while (v < length) {走得太远：您访问，tab[v + 1]因此循环应停止于v < length - 1。按照当前的编码，它具有未定义的行为。

您可以进一步简化代码：

• 应该没有必要特殊情况length == 2。
• flag无用，因为当你清除它时你总是会返回。
• if (v % 2 != 0)是多余的：else就足够了。

这是一个固定且简化的版本：

#include <stdio.h>
#include <stdlib.h>

void *safeMalloc(int n) {
    void *p = malloc(n);
    if (p == NULL) {
        printf("Error: malloc(%d) failed. Out of memory?\n", n);
        exit(EXIT_FAILURE);
    }
    return p;
}

void swap(int *fir, int *sec) {
    int temp = *fir;
    *fir = *sec;
    *sec = temp;
}

void permutate(int *array, int i, int length, int *count) {
    if (i == length) {
        for (int v = 0; v < length - 1; v++) {
            if (v % 2 == 0) {
                if (array[v] >= array[v + 1]) {
                    return;
                }
            } else {
                if (array[v] <= array[v + 1]) {
                    return;
                }
            }
        }
        *count = *count + 1;
    } else {
        for (int j = i; j < length; j++) {
            swap(array + i, array + j);
            permutate(array, i + 1, length, count);
            swap(array + i, array + j);
        }
    }
}

int main(int argc, char **argv) {
    int n;
    if (scanf("%d", &n) == 1 && n > 0) {
        int *arr = safeMalloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        int count = 0;
        permutate(arr, 0, n, &count);
        printf("%d\n", count);
    }
    return 0;
}