• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 195,  comments - 30,  trackbacks - 0

            One curious child has a set of N little bricks. From these bricks he builds different staircases. Staircase consists of steps of different sizes in a strictly descending order. It is not allowed for staircase to have steps equal sizes. Every staircase consists of at least two steps and each step contains at least one brick. Picture gives examples of staircase for N=11 and N=5:

            Your task is to write a program that reads from input numbers N and writes to output numbers Q - amount of different staircases that can be built from exactly N bricks.


            Input

            Numbers N, one on each line. You can assume N is between 3 and 500, both inclusive. A number 0 indicates the end of input.

             

             


            Output

            Numbers Q, one on each line.

             


            Sample Input

            3
            5
            0
            

            Sample Output

            1
            2
            
            方法1,動態規劃

            #include<iostream>
            #include<cstdlib>
            using namespace std;
              int main()
              {
              freopen("s.txt","r",stdin);
              freopen("key.txt","w",stdout);
              double f[501][501]={0};
              double s;
              int i,j,k,n;
              for(i=3;i<=500;i++)
              for(j=1;j<=(i-1)/2;j++)
                f[i][j]=1;
              for(i=3;i<=500;i++)
                for(j=1;j<=(i-1)/2;j++)
                {
             for(k=j+1;k<=(i-j-1)/2;k++)
               f[i][j]=f[i-j][k]; 
             }
                while(scanf("%d",&n),n) {
                    s=0;
                    for(i=1;i<=(n-1)/2;i++) s+=f[n][i]; //f[n]=f[n][1]+f[n][2]+-----+f[n][floor((i-1)/2)]
                    printf("%.0f\n",s);
                }
              //system("PAUSE");
              return   0;
              }
            更妙的方法:生成函數法
            計算(1+x)(1+x^2)(1+x^3)-----,x^n的系數即為所求
            int i,j;
            double ans[510]={1,1};//已經把ans[1]和ans[0]賦為1了,其余為0
             for(i=2;i<=500;i++) {  
                    for(j=500;j>=0;j--) { 
                        if(i+j<=500) ans[i+j]+=ans[j];
                    } 
                } 

            先計算(1+x)(1+x^2)
            再計算(1+x)(1+x^2)   *(1+x^3)
            posted on 2009-06-27 10:44 luis 閱讀(426) 評論(0)  編輯 收藏 引用 所屬分類: 組合數學動態規劃給我啟發題
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久久国产打桩机| 色欲av伊人久久大香线蕉影院| 欧洲人妻丰满av无码久久不卡| 97精品国产97久久久久久免费| 亚洲精品国产美女久久久| 国内精品伊人久久久久| 久久www免费人成精品香蕉| 久久人人爽人人爽人人片AV不| 日韩久久久久久中文人妻| 久久免费线看线看| 久久精品人妻中文系列| 久久精品视频网| yy6080久久| 91精品国产高清久久久久久国产嫩草| 国产三级观看久久| 色88久久久久高潮综合影院| 久久国产精品免费| 国产午夜福利精品久久2021| 亚洲欧美久久久久9999| 国产99久久久国产精免费| 欧美黑人激情性久久| 一本久道久久综合狠狠躁AV| 国内精品久久国产大陆| 无码专区久久综合久中文字幕 | 久久综合香蕉国产蜜臀AV| 久久国产免费直播| 欧美伊香蕉久久综合类网站| 亚洲va久久久噜噜噜久久| 久久成人小视频| 欧美午夜精品久久久久久浪潮| 久久综合丝袜日本网| 国产精品一区二区久久精品| 少妇久久久久久久久久| 久久久久久久久久久久久久| 久久五月精品中文字幕| 久久久人妻精品无码一区| 久久露脸国产精品| 四虎国产精品成人免费久久| 久久综合色老色| 久久精品一本到99热免费| 无码国内精品久久人妻|