スタック順序の問題
5496 ワード
番号が1からnのn個の要素で、順番に1つのスタックに入ると、可能なスタックのシーケンスは何種類ありますか?
スタックとCatalan数について考える
*
* *
* * *
* * * *
* * * * *
このような形をした直角三角形のメッシュは、左上から右へと下へしか歩けません.全部で何種類の歩き方がありますか.
問題の由来:番号が1からnのn個の要素で、順番に1つのスタックに入ると、可能なスタックのシーケンスは何種類ありますか?
問題の転化と思考:n個の要素のスタックとスタックを出て、全部でn回のスタックとn回のスタックを経験します.これは,この2 nステップの動作を配列することに相当する.
1つのモデル:n*nの正方形メッシュで、左上の頂点から右下の頂点まで、右へと下へしか歩けません.全部で何種類の歩き方があるかを聞く.上記問題に対応するスタックを右に進み、上記問題に対応するスタックを下に進むと、このモデルは上記問題の具体的な説明と見なすことができる.この問題を解決するには,左上角から右下角までの合計2 nステップにおいて,右方向へのステップ数,すなわちC(n 2 n)共有中のステップを選択すればよい.
しかし,走行法が対角線を越えた場合,上記の問題に対応して入スタック数より出スタック数が多いという問題があり,これは現実的ではない.
以上のモデルを処理し,対角線は以上の正方形メッシュを2つの部分に分割し,対角線を含む下半分のみを残しておくと,対角線を越える問題は生じない.この問題が最初に提起された問題だ.
-------------------------------------------------------
問題は:n個の1とn個の0が1 2 nビットを構成する2進数に等価で、左から右へスキャンすることを要求して、1の積算数は0の積算数より小さくなくて、この条件を満たす数を試みていくらありますか?
P 2 nは、このようにして得られる数の個数とする.2 nビットにn個の1を埋め込むスキーム数はC(n 2 n)である.
1を記入しない残りのnビットは自動的に0を記入します.C(n 2 n)から要求に合致しないシナリオ数を減算することが求められる.
要求されない数とは、左から右にスキャンし、0の累積数が1を超える累積数が現れる数を指す.
要求されない数の特徴は,左から右へスキャンすると,必ずある奇数2 m+1ビットにm+1個の積算数と,m個1の積算数が最初に現れることである.
その後の2(n−m)−1位にはn−m個1,n−m−1個0がある.後の部分2(n−m)−1位を1と交換してn−m個0,n−m−1個1とすると、n＋1個0とn−1個1からなる2 nビット数、すなわち、n−1個0とn＋1個1からなる1個の配列が得られる.
逆に、いずれかのn+1個の0,n−1個の1からなる2 nビット数は、0の個数が2個多く、2 nが偶数であるため、ある奇数ビットに0の積算数が1を超える積算数が必ず現れる.同様に後の部分では,0と1を交換し,n個の0とn個の1からなる2 nビット数とする.すなわち、n+1個の0とn−1個の1からなる2 nビット数は、必ず要求されない数に対応する.
上記の方法でn＋1個の0とn−1個の1からなる2 nビット数を確立し,n個の0とn個の1からなる2 nビット数のうち左から右へスキャンすると0の積算数が1を超える積算数の1つに対応した.
例えば10100101
は、4つの0と4つの1からなる8ビット2進数です.しかし、左から右へスキャンすると5番目(赤で表示される)に0の積算数3が1を超える積算数2が現れ、3つの1、5つの0からなる10100010に対応する.
逆に10100010
10100101に対応
従って、要求に合わない2 nビット数は、n+1個0,n−1個1組成の配列に1つずつ対応するので、
P2n ＝ C(n 2n)— C(n＋1 2n)
この結果は「カタラン数」Catalanであり,組合せ数学で紹介されており,関連資料を参照できる.
-----------------------------------------------------
もっと思考習慣に合った方法でこの問題を解決することができますか?
この問題を二元グループとして記述することができ、(n,0)はn個の要素がスタックに入るのを待っていることを示し、0個の要素がスタックに入っていることを示し、これは問題の最初の状況に相当する.次に問題を(n-1,1)に変換する.(n,0)=(n-1,1)と言える.(n-1,1)については(n-1,0)+(n-2,2)に相当する.
(n-1,0)はスタック内の1つの要素がスタックから出ることを示し、(n-2,2)はもう1つの要素がスタックに入ることを示す.
問題を一般的には(n,m)の配列問題を(n,m-1)+(n-1,m+1)に変換することができる.m=0の場合(n,0)の問題は(n-1,1)にしか変換できない.問題が(0,m)の場合、再帰境界が得られ、この問題の解は1つの配列しかない.
手順は次のとおりです.
実行結果:
The total count of stackout permutation is 132.
-----------------------------------------------------
上記の方法は可能ですが、実際のプログラミングでは再帰を使用しないほうがいいです.これにより、再帰回数が多ければスタックオーバーフローが発生しやすくなります.大きなパラメータで関数を呼び出してみるとruntime errorになります.
また、純粋な再帰は大量の繰り返し計算をもたらします.例えば、getPermuStack(5,5)を計算するときにgetPermuStack(5,4)を計算し、getPermuStack(5,3)を計算するときにもう一度計算します.もちろんダイナミックプランニングの考え方で2次元配列を設定して計算結果を記録することはできますが、スペースがかかりすぎます.
直感的な方法で効率的に問題を解決できれば、数学から解く人はそんなに多くありません.
再帰の致命的な欠点は、複雑な計算を機械に残すことであり、再帰は往々にして迅速で簡潔な思考で問題の解を求めることができ、得られるアルゴリズムは低効率であるかもしれない.だから再帰は怠け者のアルゴリズムであるべきだ.「数学的に解く」とは、問題を前向きに考える解であり、再帰的には逆方向に解くことである.
長さnの重複しないシーケンスがスタックに入るすべてのスタック方式
——by hahabrother
これは興味深い問題であり、例えば1、2、3の3つの数字であり、スタックに入ってスタックを出るには321、312、231、213、123の5つの方法がある.では、長さnの重複しないシーケンスのすべてのスタック方式についてどのようなものがあるのでしょうか.
計算アルゴリズムを設計するために、入力をキュー(queue)でシミュレートすることができ、キューの出力は元のシーケンスの順序でシミュレートすることができます.スタック(stack)を使用して入スタックと出スタックをシミュレートし、結果は別のキュー(queue)に保存されます.
今の問題は、どのようにしてすべてのスタック入スタック操作を実現することができますか.まず、出桟と入桟とはどういうことかを見てみましょう.123というシーケンスでは、1が先に入桟した後に2つの選択があり、1が出桟と2が入桟した後、2が出桟する前に1が先に出桟できないので、1は2が入桟する前に出桟した場合を考慮するだけで、1が桟内に2が入桟した場合、1と2は全体としか見えません.
これにより再帰的に解くことができ、偽コードは以下の通りである.
dostack(入力キュー、中間スタック、出力キュー)
if(入力キューが空)
if(中間スタックが空)
出力キューの結果を出力
else
中間スタックはスタックを出て、出力キューに入れます
dostack(入力キュー、中間スタック、出力キュー)
else
if(中間スタックが空でない)
新規入力キュー2、中間スタック2、出力キュー2
中間スタック2はスタックを出て出力キュー2に入れる
dostack(入力キュー2、中間スタック2、出力キュー2)
キューのデキュー数を入力し、中間スタックに押し込みます.
dostack(入力キュー、中間スタック、出力キュー)
その基本思想は,中間スタックの各時刻について撮影し,その後のすべての可能性を再帰することであり,再帰が戻る際には再帰前の情報が必要であるため,再帰のたびに新規データ構造が作成され,現在の時刻の状態が保存される.入力キューが空の場合、中間スタックは1つのスタック方式しかなく、中間スタックも空の場合に再帰的に終了します.
詳細コードは次のとおりです.
入力はシーケンスの長さnであり、初期化シーケンスは1,2,3...nであり、出力は可能なすべてのスタック数列である.
スタックとCatalan数について考える
*
* *
* * *
* * * *
* * * * *
このような形をした直角三角形のメッシュは、左上から右へと下へしか歩けません.全部で何種類の歩き方がありますか.
問題の由来:番号が1からnのn個の要素で、順番に1つのスタックに入ると、可能なスタックのシーケンスは何種類ありますか?
問題の転化と思考:n個の要素のスタックとスタックを出て、全部でn回のスタックとn回のスタックを経験します.これは,この2 nステップの動作を配列することに相当する.
1つのモデル:n*nの正方形メッシュで、左上の頂点から右下の頂点まで、右へと下へしか歩けません.全部で何種類の歩き方があるかを聞く.上記問題に対応するスタックを右に進み、上記問題に対応するスタックを下に進むと、このモデルは上記問題の具体的な説明と見なすことができる.この問題を解決するには,左上角から右下角までの合計2 nステップにおいて,右方向へのステップ数,すなわちC(n 2 n)共有中のステップを選択すればよい.
しかし,走行法が対角線を越えた場合,上記の問題に対応して入スタック数より出スタック数が多いという問題があり,これは現実的ではない.
以上のモデルを処理し,対角線は以上の正方形メッシュを2つの部分に分割し,対角線を含む下半分のみを残しておくと,対角線を越える問題は生じない.この問題が最初に提起された問題だ.
-------------------------------------------------------
問題は:n個の1とn個の0が1 2 nビットを構成する2進数に等価で、左から右へスキャンすることを要求して、1の積算数は0の積算数より小さくなくて、この条件を満たす数を試みていくらありますか?
P 2 nは、このようにして得られる数の個数とする.2 nビットにn個の1を埋め込むスキーム数はC(n 2 n)である.
1を記入しない残りのnビットは自動的に0を記入します.C(n 2 n)から要求に合致しないシナリオ数を減算することが求められる.
要求されない数とは、左から右にスキャンし、0の累積数が1を超える累積数が現れる数を指す.
要求されない数の特徴は,左から右へスキャンすると,必ずある奇数2 m+1ビットにm+1個の積算数と,m個1の積算数が最初に現れることである.
その後の2(n−m)−1位にはn−m個1,n−m−1個0がある.後の部分2(n−m)−1位を1と交換してn−m個0,n−m−1個1とすると、n＋1個0とn−1個1からなる2 nビット数、すなわち、n−1個0とn＋1個1からなる1個の配列が得られる.
逆に、いずれかのn+1個の0,n−1個の1からなる2 nビット数は、0の個数が2個多く、2 nが偶数であるため、ある奇数ビットに0の積算数が1を超える積算数が必ず現れる.同様に後の部分では,0と1を交換し,n個の0とn個の1からなる2 nビット数とする.すなわち、n+1個の0とn−1個の1からなる2 nビット数は、必ず要求されない数に対応する.
上記の方法でn＋1個の0とn−1個の1からなる2 nビット数を確立し,n個の0とn個の1からなる2 nビット数のうち左から右へスキャンすると0の積算数が1を超える積算数の1つに対応した.
例えば10100101
は、4つの0と4つの1からなる8ビット2進数です.しかし、左から右へスキャンすると5番目(赤で表示される)に0の積算数3が1を超える積算数2が現れ、3つの1、5つの0からなる10100010に対応する.
逆に10100010
10100101に対応
従って、要求に合わない2 nビット数は、n+1個0,n−1個1組成の配列に1つずつ対応するので、
P2n ＝ C(n 2n)— C(n＋1 2n)
この結果は「カタラン数」Catalanであり,組合せ数学で紹介されており,関連資料を参照できる.
-----------------------------------------------------
もっと思考習慣に合った方法でこの問題を解決することができますか?
この問題を二元グループとして記述することができ、(n,0)はn個の要素がスタックに入るのを待っていることを示し、0個の要素がスタックに入っていることを示し、これは問題の最初の状況に相当する.次に問題を(n-1,1)に変換する.(n,0)=(n-1,1)と言える.(n-1,1)については(n-1,0)+(n-2,2)に相当する.
(n-1,0)はスタック内の1つの要素がスタックから出ることを示し、(n-2,2)はもう1つの要素がスタックに入ることを示す.
問題を一般的には(n,m)の配列問題を(n,m-1)+(n-1,m+1)に変換することができる.m=0の場合(n,0)の問題は(n-1,1)にしか変換できない.問題が(0,m)の場合、再帰境界が得られ、この問題の解は1つの配列しかない.
手順は次のとおりです.
#include <stdio.h>
#define ELEMNUM 6;
int getPermuStack(int n, int m)
{
if(n == 0)//
return 1;
if(m == 0)//(n,0)
return getPermuStack(n-1, 1);
return getPermuStack(n, m-1) + getPermuStack(n-1, m+1);
}
int main()
{
printf("The total count of stackout permutation is %d.", getPermuStack(6, 0));
return 0;
}実行結果:
The total count of stackout permutation is 132.
-----------------------------------------------------
上記の方法は可能ですが、実際のプログラミングでは再帰を使用しないほうがいいです.これにより、再帰回数が多ければスタックオーバーフローが発生しやすくなります.大きなパラメータで関数を呼び出してみるとruntime errorになります.
また、純粋な再帰は大量の繰り返し計算をもたらします.例えば、getPermuStack(5,5)を計算するときにgetPermuStack(5,4)を計算し、getPermuStack(5,3)を計算するときにもう一度計算します.もちろんダイナミックプランニングの考え方で2次元配列を設定して計算結果を記録することはできますが、スペースがかかりすぎます.
直感的な方法で効率的に問題を解決できれば、数学から解く人はそんなに多くありません.
再帰の致命的な欠点は、複雑な計算を機械に残すことであり、再帰は往々にして迅速で簡潔な思考で問題の解を求めることができ、得られるアルゴリズムは低効率であるかもしれない.だから再帰は怠け者のアルゴリズムであるべきだ.「数学的に解く」とは、問題を前向きに考える解であり、再帰的には逆方向に解くことである.
長さnの重複しないシーケンスがスタックに入るすべてのスタック方式
——by hahabrother
これは興味深い問題であり、例えば1、2、3の3つの数字であり、スタックに入ってスタックを出るには321、312、231、213、123の5つの方法がある.では、長さnの重複しないシーケンスのすべてのスタック方式についてどのようなものがあるのでしょうか.
計算アルゴリズムを設計するために、入力をキュー(queue)でシミュレートすることができ、キューの出力は元のシーケンスの順序でシミュレートすることができます.スタック(stack)を使用して入スタックと出スタックをシミュレートし、結果は別のキュー(queue)に保存されます.
今の問題は、どのようにしてすべてのスタック入スタック操作を実現することができますか.まず、出桟と入桟とはどういうことかを見てみましょう.123というシーケンスでは、1が先に入桟した後に2つの選択があり、1が出桟と2が入桟した後、2が出桟する前に1が先に出桟できないので、1は2が入桟する前に出桟した場合を考慮するだけで、1が桟内に2が入桟した場合、1と2は全体としか見えません.
これにより再帰的に解くことができ、偽コードは以下の通りである.
dostack(入力キュー、中間スタック、出力キュー)
if(入力キューが空)
if(中間スタックが空)
出力キューの結果を出力
else
中間スタックはスタックを出て、出力キューに入れます
dostack(入力キュー、中間スタック、出力キュー)
else
if(中間スタックが空でない)
新規入力キュー2、中間スタック2、出力キュー2
中間スタック2はスタックを出て出力キュー2に入れる
dostack(入力キュー2、中間スタック2、出力キュー2)
キューのデキュー数を入力し、中間スタックに押し込みます.
dostack(入力キュー、中間スタック、出力キュー)
その基本思想は,中間スタックの各時刻について撮影し,その後のすべての可能性を再帰することであり,再帰が戻る際には再帰前の情報が必要であるため,再帰のたびに新規データ構造が作成され,現在の時刻の状態が保存される.入力キューが空の場合、中間スタックは1つのスタック方式しかなく、中間スタックも空の場合に再帰的に終了します.
詳細コードは次のとおりです.
入力はシーケンスの長さnであり、初期化シーケンスは1,2,3...nであり、出力は可能なすべてのスタック数列である.
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int n,i,j;
int res;
stack <int> s;
queue <int> in,out;
void clear(stack <int> &s)
{
while(!s.empty())
s.pop();
}
void clear(queue <int> &s)
{
while(!s.empty())
s.pop();
}
void print(queue <int> i)
{
while(!i.empty())
{
cout<<i.front();
i.pop();
}
cout<<endl;
}
void dostack(queue <int> in,stack <int> s,queue <int> out)
{
if(in.empty())
{
if(s.empty())
{
res++;
print(out);
}
else
{
out.push(s.top());
s.pop();
dostack(in,s,out);
}
}
else
{
if(!s.empty())
{
stack <int> ts;
queue <int> tin,tout;
tin=in;
ts=s;
tout=out;
tout.push(ts.top());
ts.pop();
dostack(tin,ts,tout);
}
s.push(in.front());
in.pop();
dostack(in,s,out);
}
}
int main()
{
while(cin>>n)
{
res=0;
clear(in);
clear(out);
clear(s);
for(i=n;i>=1;i--)
in.push(i);
dostack(in,s,out);
cout<<res<<endl;
}
return 0;
}