再帰小結

2色ハノイタワー問題DescriptionはA、B、Cの3つのタワーを設置しています.最初は、タワーAにn個の円盤が重ねられ、これらの円盤は下から上へ、大きくから小さく重ねられている.各円盤は小から大まで1,2,......,n,奇数号円盤は青,偶数号円盤は赤である.次に、タワーA上のこれらの円盤の重ね合わせをタワーB上に移動し、同様の順序で重ね合わせることが要求される.ディスクを移動するときは、ルール(1):毎回1つのディスクしか移動できません.ルール(2):大きな円盤を小さな円盤の上に押し付けることは、いつでも許されない.ルール(3):いつでも同色の円盤を重ねることは許されない.ルール(4):移動ルール(1)-(3)を満たす前提で、円盤をA,B,Cのいずれかのタワーに移動できます.タワーA上のn個の円盤を最小の移動回数でタワーB上に移動し,同じ順序で重畳するアルゴリズムを設計してみた.与えられた正の整数nについて、プログラミングは最適な移動スキームを計算する.Inputは複数のテストデータを含み、各テストデータは正の整数nを含む.Output各テストデータのセットには複数行が含まれています.各行は、一定のシナリオを記述します.
各行は正の整数kと2文字c 1とc 2からなり、k番目の円盤をタワーc 1からタワーc 2に移動することを示す.
各データ間はスペースで区切られています.Sample Input 3
Sample Output 1 A B 2 A C 1 B C 3 A B 1 C A 2 C B 1 A B
考え方:一般的には、i番目の皿をB柱に置くには、i-1番目の皿を過度の柱に置き、i番目の皿を目標柱に置き、最後に元の柱を遷移柱とし、そのi-1番目の皿を遷移柱から目標柱に移す必要があるので、再帰的に使用されますが、二色と単色は区別されません.

#include
#include 
#include 
#include 
using namespace std;
void mov(int n,char a,char b)
{
    cout<" "<" "<void digui(int n,char a,char c,char b)
{
if(n==1) mov(n,a,b);
else
{
digui(n-1,a,b,c);
mov(n,a,b);
digui(n-1,c,a,b);
}
}
int main()
{
int n;
while(cin>>n)
{
digui(n,'A','C','B');
}
return 0;
}

2のべき乗次数
Descriptionのいずれの正の整数も2のべき乗次数で表すことができます.例えば、137=27+23+20同時約定方次は括弧で表され、すなわちabはa(b)で表される.このことから、137は、2(7)+2(3)+2(3)+2(0)さらに、7=22+2+20(21は2で表す)3=2+20であるので、最後の137は、2(2(2)+2+2(0))+2(2+2(2+2(0)+2(0)であり、1315=210+28+25+2+15+1であるので、1315は、最後に、2(2(2(2(2+2(0))+2)+2(2(2(2(2+2(0)))))+2(2(2(2(2)+2(2(2)+2(2(2)+2(0))))+2(2(2(0)))+2テストデータ、各試験データは正の整数n(n≦20000)を含む
Outputは、約定されたnの0,2に該当する(表示にスペースがない)Sample Input 137,1315を表す
Sample Output 2(2(2)+2+2(0))+2(2+2(0))+2(0) 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
考え方:再帰するたびに目標値Nに最も近い最大の等しい値より小さい値を見つけて、それから彼が2の何次方であるかを記録して、両者が等しいならプラス記号を追加する必要はありません.そうでなければプラス記号を追加する必要がありますが、もしこの桁数が1であれば、「2+」を直接出力し、カッコを必要とせず、そうでなければ次のレイヤに再帰すると、余分な2(0)が現れ、また2つのレイヤに分けて再帰し、指数cntを再帰し、残りの値(n-tmp)を再帰する.

#include 
using namespace std;
void digui(int n)
{
    if(n==1)
    {
        cout<<"2(0)";
        return;
    }
    if(n==2)
    {
        cout<<"2";
        return;
    }
    int tmp=1,cnt=0;
    while(tmp<=n)
    {
        tmp=tmp<<1;
        cnt++;
    }
    tmp=tmp>>1;
    cnt--;
    if(n==tmp)
    {
        cout<<"2(";
        digui(cnt);
        cout<<")";
    }
    else
    {
        if(cnt==1)
        {
            cout<<"2+";
            digui(n-tmp);//     cnt,            1
        }
        else
        {
            cout<<"2(";
            digui(cnt);
            cout<<")+";
            digui(n-tmp);
        }
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        digui(n);
        cout<return 0;
}

数のカウントDescription我々は以下の性質数(入力を含む自然数n)を探し出すことを要求する:まず1つの自然数n(n≦1000)を入力して、それからこの自然数に対して以下の方法で処理する:1.いかなる処理をしない;2.その左側に自然数を加えるが、その自然数は原数(入力n)の半分を超えてはならない.3.数を加算した後、自然数が加算されないまで、この規則に従って処理を続けます.例えば、n=6の場合、条件を満たす数は6,16,26126,36136の6個のInputが複数の試験データを含み、各試験データは正の整数nを含む
Outputは、条件を満たす数の個数を出力します.
Sample Input 6
Sample Output 6
構想:dp[j][i]はiの左側にjを追加する場合の数を表し、繰返し式for(int k=0;k<=j/2;k++)dp[j][i]+=dp[k][j]を得ることができる.

#include 
#include 
using namespace std;
long long ans=0;
int dp[509][1009];
int main()
{
    int n;
    while(cin>>n)
    {
        memset(dp,0,sizeof dp);
        ans=0;
        for(int i=1; i<=n; i++)
            dp[0][i]=1;
        for(int i=0; i<=n; i++)
            for(int j=1; j<=i/2; j++)
                for(int k=0; k<=j/2; k++)
                    dp[j][i]+=dp[k][j];
         for(int i=0;i<=n/2;i++)
            ans+=dp[i][n];
         cout<return 0;
}

集合区分問題Descriptionは、Sがn個の要素を有する集合であり、S＝｛a 1,a 2,…,an｝とする.ここで、Sは、以下の条件を満たすk個のサブ集合S 1,S 2,…,Skに分割され、(1)すべてのサブセットが空(2)の任意の2つのサブセットと等しくない.(3)すべてのサブセットの並列集合が集合sに等しいことをS 1,S 2,…,Skと呼び,集合Sの1つの区分である.n個の要素を含む集合sをk個のサブセットに分割する分割数S(n,k)はいくらですか?例えば、n=4の場合、集合S={1,2,3,4}は、{{{1},{2},{3},{1,2},{4},{{{1,2},{3},{4},{{{1,3},{4},{{1,3},{2},{4},{1,4},{2},{2},{3,{2,{2,3},{1},{1,{4},{2,{4},{2,{2,4},{1},{3,{3,{3,{3,{4},{1},{1,{1,{2,{2,{1},{1,{2,{1,{1,{2,{1,{,2},{3,4},{{1,3},{2,4}}, { {1,4},{2,3} }, { {1,2,3},{4} }, { {1,2,4},{3} }, { {1,3,4},{2} }, { {2,3,4},{1} }, { {1,2,3,4} }. 明らかに、S(4,1)=1がある.S(4,2)=7; S(4,3)=6; S(4,4)=1. Inputは複数のテストデータを含み、各テストデータは2つの正の整数nとkを含む.
Output出力S(n,k).
Sample Input 4 1 4 2 4 3 4 4
Sample Output 1 7 6 1
考え方:1つの集合を指定した数のサブセットに分割するには、1つの個別の数について、既存のサブセットに入れるか、新しいサブセットに入れるかを考慮する必要があります.これにより、再帰式digui(n−1,m−1)+digui(n−1,m)*mを得ることができる.前者はそれを新しい集合に入れる場合であり、後者はそれを既存の集合に入れる場合であり、既存の集合個数はmであるため、mを乗じなければならない.

#include 
#include 
using namespace std;
long long ans=0;
int n,k;
long long digui(int n,int m)
{
   if(m==1||n==m) return 1;
   return digui(n-1,m-1)+digui(n-1,m)*m;
}
int main()
{

    while(cin>>n>>k)
    {
      cout<return 0;
}

封筒をまちがえる
Descriptionのある人はn通の手紙とn個の封筒を書いて、もしすべての手紙が封筒を間違えたら.すべての手紙が封筒を間違えて何種類の異なる状況があるかを求めます.
Inputは複数の試験データを含み、各試験データは正の整数n(すなわち、手紙または封筒の数、15を超えない)を含む.
Outputは、装着ミスの種類数を出力します.
Sample Input 1 2 3 4
Sample Output 0 1 2 9考え方:誤配式

#include 
#include 
using namespace std;
long long ans=0;
int n,k;

int digui(int n)
{
   if(n==1) return 0;
   if(n==2) return 1;
   return (n-1)*(digui(n-1)+digui(n-2));
}
int main()
{

    while(cin>>n)
    {
      cout<return 0;
}