3

それは私が推測する数学の問題であり、プログラミングは何もありません。

があり、のstackを見つけたいとしpermutationsます1,2,3,...n。私はできpushますpop。たとえば、n=2 の場合: push,pop,push,pop1,2 およびpush,push,pop,pop2,1

n=4の場合、 ..を使用して順列14からのみ取得できます。生成できるスタックの数(1 つだけ) を生成できる人はいますか? 例 f(1)=124stackfunction F(n)permutations

f(2)=2

f(4)=14

4

2 に答える 2

3

そのような関数はカタロニア語です。数式については、http://en.wikipedia.org/wiki/Catalan_numberを参照してください。

于 2011-01-16T20:06:17.967 に答える
0

そのための非常に簡単な公式があると思います。1 つの単純なルールに従って、Nプッシュ操作 (「X」) とポップ (「Y」) 操作の順列を探しています。N

  • 空のスタックではポップしない (fe Y.... と XXYYY... は無効)

おそらく、いくつかの再帰的な定義が役立ちます:

function F(n_push, n_pop) {
  int total_count = 0;

  if (n_push > 0) total_count += F(n_push - 1, n_pop);
  if (n_pop > n_push) total_count += F(n_push, n_pop - 1);

  return total_count;
}
于 2011-01-16T19:58:18.353 に答える