• <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 閱讀(425) 評論(0)  編輯 收藏 引用 所屬分類: 組合數學動態規劃給我啟發題
            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久九九精品99国产精品| 很黄很污的网站久久mimi色| 久久婷婷五月综合97色直播 | 亚洲国产一成人久久精品| 国产亚洲美女精品久久久2020| 亚洲精品无码专区久久久| 久久综合香蕉国产蜜臀AV| 国产一区二区精品久久| 久久亚洲高清综合| 日韩人妻无码一区二区三区久久 | 久久成人小视频| 99久久99久久久精品齐齐 | 2020国产成人久久精品 | 久久久精品无码专区不卡| 久久精品一本到99热免费| 久久综合久久综合久久| 久久亚洲国产最新网站| 蜜桃麻豆www久久| 久久久久亚洲精品无码蜜桃| 热久久国产欧美一区二区精品| 欧洲人妻丰满av无码久久不卡| 久久夜色精品国产| 日韩亚洲欧美久久久www综合网| 人人妻久久人人澡人人爽人人精品 | 久久发布国产伦子伦精品| 久久久久女教师免费一区| 国产成人久久AV免费| 久久精品国产亚洲av麻豆图片| 精品久久久久久无码人妻蜜桃| 久久天天躁夜夜躁狠狠躁2022| 久久精品不卡| 狠狠精品久久久无码中文字幕| 精品国产福利久久久| 99久久免费国产精精品| 欧美黑人激情性久久| 久久久久久久久66精品片| 久久久精品日本一区二区三区| 国产成人精品综合久久久| 久久免费精品一区二区| 国产精品久久一区二区三区| 久久久久99精品成人片直播|