交替递增/递减序列的计数

Question

问题描述： 计算从某些输入n上升的所有序列的数量。 所以用户输入n;与N，然后我创建一个数字1..1的数组，然后与属性号序列

例子：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; 
} 

Answer 2

如果调用标签（N，K）长度为n与k是在你的序列中的最后一个数字的递增递减序列号，你可以写一个递推公式，并实现它这样的：

int N = 5+1; 
int** tab = new int*[N]; 
for (int n = 0; n < N; n++) { 
    tab[n] = new int[N]; 
    for (int k = 0; k < N; k++) { 
     tab[n][k] = 0; 
    } 
} 
tab[1][1] = 1; 
for (int n = 2; n < N; n++) { 
    for (int k = 1; k <= n; k++) { 
     if (n % 2 == 0) { 
      for (int j = 0; j < k; j++) { 
       tab[n][k] += tab[n-1][j]; 
      } 
     } 
     else { 
      for (int j = k; j < n; j++) { 
       tab[n][k] += tab[n-1][j]; 
      } 
     } 
    } 
} 
int res = 0; 

for (int j = 0; j < N; j++) { 
    res += tab[N - 1][j]; 
} 

Answer 3

就可以解决这个无需经过排列迭代。假设你正在计算f（n）。新的高数字去哪里？它必须处于“向上”的位置，这是一个偶然的位置。您可以在它之前有任何有效的奇数长度的序列，以及它后面的任何有效序列。假设我们正在计算f（n，k），其中最高值位于位置k，零索引。这对k甚至是零。对于奇ķ我们得到：

F（N，K）=选择（N-1，K）* F（K）* F（N - K - 1）

为了得到F（N），在奇数k上的和f（n，k）n。

我们必须手工计算出前几个。

f(0) = 1 
f(1) = 1 
f(2) = 1 
f(3) = f(3,1) = choose(2,1) * f(1) * f(1) = 2 * 1 *1 = 2 
f(4) = f(4,1) + f(4,3) = choose(3,1) * f(1) * f(2) + choose(3,3) * f(3) * f(0) = 3*1*1 + 1*2*1 = 5 
f(5) = f(5,1) + f(5,3) = choose(4,1) * f(1) * f(3) + choose(4,3) * f(3) * f(1) = 4*1*2 + 4*2*1 = 16