アップ/ダウンシーケンスを交互にカウントする

Question

問題の説明： いくつかの入力nから上に行くすべてのシーケンスの数を計算します。 したがって、ユーザーは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を得る。あなたは（n、k）はkはあなたのシーケンスの最後の数であると長さnのアップダウンシーケンスの数のタブを呼び出す場合

#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

、あなたは再帰的な式を書くことができますし、そのようにそれを実装：

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）を計算する場合、最高のvalが位置kにあり、インデックスがゼロであるとします。これは、kの偶数に対してはゼロです。 kが奇数のために我々が得る：

F（N、k）を=（N-1、K）* F（K）* F（N - K - 1）を選択します

（n）はFを取得するには、奇数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