hdu 递推 Tri Tiling 汉诺塔II 三角形下沙的沙子有几粒？献给杭电五十周年校庆的礼物

131 阅读 0 评论 87 点赞

我是靠谱客的博主清新路人，这篇文章主要介绍hdu 递推 Tri Tiling 汉诺塔II 三角形下沙的沙子有几粒？献给杭电五十周年校庆的礼物，现在分享给大家，希望可以做个参考。

hdu 1143

http://acm.hdu.edu.cn/showproblem.php?pid=1143

Tri Tiling

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2335 Accepted Submission(s): 1333

Problem Description

In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.

Input

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.

Output

For each test case, output one integer number giving the number of possible tilings.

Sample Input

复制代码

Sample Output

复制代码

当n为奇数的时候是不能用2*1的方块摆满的，所以f[i] = 0;

当n为偶数的时可以这样划分，2和f[n-2]，则有2*f[n-2]种，4和f[n-4]但是4的部分不能分解为2,2否则的话就跟2和f[n-2]这种情况重复了，在这种情况下只有两种摆法；接着是6和f[n-6]，8和f[n-8].................f[0],这些情况都只有2种摆法。

递推方程f[n] = f[n-2]*f[2]+2*(f[n-4]+f[n-6]+f[n-8]............+f[0]);

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include<string>
#include<string.h>
using namespace std;

int main()
{
    int f[32] ;
    f[0] = 1 ;
    f[2] = 3 ;
    f[1] = 0 ;
    for(int i = 3  ; i<= 31 ; i++){
        if(i &1)
            f[i] = 0 ;
        else{
             f[i] = f[i -2] * f[2] ;
             int j = i - 4 ;
             while(j >= 0){
                f[i] += f[j]*2 ;
                j -= 2 ;
             }
        }

    }
     int n ;
     while(cin>>n )  {
        if(n == -1)
        break ;
        cout<< f[n]<<endl;
     }
    return 0;
}

hdu 1207

http://acm.hdu.edu.cn/showproblem.php?pid=1207

汉诺塔II

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5652 Accepted Submission(s): 2741

Problem Description

经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩，当然这个传说并不可信，如今汉诺塔更多的是作为一个玩具存在。Gardon就收到了一个汉诺塔玩具作为生日礼物。
　　Gardon是个怕麻烦的人（恩，就是爱偷懒的人），很显然将64个圆盘逐一搬动直到所有的盘子都到达第三个柱子上很困难，所以Gardon决定作个小弊，他又找来了一根一模一样的柱子，通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是：当Gardon在一次游戏中使用了N个盘子时，他需要多少次移动才能把他们都移到第三个柱子上？很显然，在没有第四个柱子时，问题的解是2^N-1，但现在有了这个柱子的帮助，又该是多少呢？

Input

包含多组数据，每个数据一行，是盘子的数目N(1<=N<=64)。

Output

对于每组数据，输出一个数，到达目标需要的最少的移动数。

Sample Input

复制代码

Sample Output

复制代码

解题思路：

对于i个盘子，从1到i进行枚举（变量设为j），将j个盘子移动到第四个柱子上，对于剩下的盘子，则可看成是三个柱子下的情况，枚举过程中找到一个最小值即为此时i个盘子的最小移动次数。注：三个柱子情况下，n个盘子需要移动2^n-1次

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include<string>
#include<string.h>
using namespace std;

int main()
{
    double a3[65] ;
    double f4[65] ;
    int i  , j ;
    a3[1] = 2 ;
    f4[1] = 1 ;
    for(i = 2 ; i < 65 ; i++)
        a3[i] = 2 * a3[i - 1] ;
    for(i =  1 ; i < 65 ; i++)
        a3[i] -= 1 ;
    for(i = 1 ;  i < 65  ; i++){
        double mmin= a3[i] ;
        double temp ;
        for(j = 1 ;  j < i ; j ++){
            temp = a3[i - j] + 2 * f4[j] ;
            if(temp < mmin)
                mmin = temp ;
        }
        f4[i] = mmin ;
    }

     int n ;
     while(cin>>n )  {

        cout<< f4[n]<<endl;
     }
    return 0;
}

hdu 1249

http://acm.hdu.edu.cn/showproblem.php?pid=1249

三角形

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5253 Accepted Submission(s): 3567

Problem Description

用N个三角形最多可以把平面分成几个区域?

Input

输入数据的第一行是一个正整数T(1<=T<=10000),表示测试数据的数量.然后是T组测试数据,每组测试数据只包含一个正整数N(1<=N<=10000).

Output

对于每组测试数据,请输出题目中要求的结果.

Sample Input

复制代码

Sample Output

复制代码

分析：数学递推题

f [ i ] = f [ i - 1 ] + 6 * ( i - 1 ) ;

f[n] = 3n(n - 1) + 2

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<span style="background-color: rgb(255, 255, 255);">int main()
{
    int f[10004] ;
    f[1] = 2 ;
    for(int i = 2 ;  i < 10001 ; i++)
        f[i] = f[i - 1] + 6 * (i  -1 )  ;
     int  t  , n;
     cin>> t  ;
     while(t-- )  {
        cin >> n ;
        cout<< f[n]<<endl;
     }
    return 0;
}</span>

hdu 1267

http://acm.hdu.edu.cn/showproblem.php?pid=1267

下沙的沙子有几粒？

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2963 Accepted Submission(s): 1554

Problem Description

2005年11月份，我们学校参加了ACM/ICPC 亚洲赛区成都站的比赛，在这里，我们获得了历史性的突破，尽管只是一枚铜牌，但获奖那一刻的激动，也许将永远铭刻在我们几个人的心头。借此机会,特向去年为参加ACM亚洲赛而艰苦集训了近半年的各位老队员表示感谢。
实际上，除了获奖以外，在这次比赛期间还有一件事也让我们记忆深刻。那是比赛当天等待入场的时候，听到某个学校的一个队员在说：“有个学校的英文名很有意思，叫什么Hangzhou Dianzi University”. 哈哈，看来我们学校的英文名起的非常好，非常吸引人呀。
不过，事情的发展谁也没有料到，随着杭电英文校名的这一次曝光，影响越来越大，很多人开始对杭电英文校名进行研究，不久以后甚至还成立了一个专门的研究机构，叫做“HDU 校名研究会”。并不断有报道说-相-当-多的知名科学家改行，专门对该问题进行研究，学术界称之为“杭电现象”。很多人在国际知名期刊上发表了研究论文，这其中，尤以中国超级女科学家宇春小姐写的一篇研究报告最为著名，报告发表在science上，标题是“杭电为什么这样红？” 文中研究发现：Hangzhou Dianzi University这个校名具有深刻的哲学思想和内涵，她同时提出了一个大胆的猜想：“假定一个字符串由m个H和n个D组成，从左到右扫描该串，如果字符H的累计数总是不小于字符D的累计数,那么，满足条件的字符串总数就恰好和下沙的沙粒一样多。”
这就是当今著名的“宇春猜想”！
虽然还没能从数学上证明这个猜想的正确性，但据说美国方面在小布什的亲自干预下，已经用超级计算机验证了在（1<=n<=m<=1000000000000）时都是正确的。my god! 这是一个多么伟大的猜想！虽然我们以前总说，21世纪是属于中国的，可还是没想这一天来的这么早，自豪ing... + 感动ing...
感动和自豪之余，问题也来了，如果已知m和n的值，请计算下沙的沙粒到底有多少。

Ps:
1. 中国有关方面正在积极行动，着手为宇春小姐申报诺贝尔奖。
2、“宇春猜想”中提到的H和D组成的字符串现在被学术界成为“杭电串串”（“杭电串串”前不久被一个卖羊肉串的注册了商标，现在我校正在积极联系买断，据说卖方的底价是1000万欧元，绝不打折，看来希望不大，sigh...）

Input

输入数据包含多个测试实例，每个占一行，由两个整数m和n组成，m和 n 分别表示字符串中H和D的个数。由于我们目前所使用的微机和老美的超级计算机没法比，所以题目给定的数据范围是（1<=n<=m<=20）。

Output

对于每个测试实例，请输出下沙的沙粒到底有多少，计算规则请参考“宇春猜想”，每个实例的输出占一行。

Sample Input

复制代码

Sample Output

复制代码

公式为

a[n][m] = a[n-1][m] +a[n][m-1]

此二维中，n是记录的H，m记录的是D

而a[n-1][m]代表的是a[n][m]以D结尾时，则前面就是a[n-1]的数目

同理a[n][m-1]也是一个意思

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
复制代码int main()
{
    int m ,  n ;
    long long a[23][23] ;
    memset(a , 0 , sizeof(a)) ;
    for(int i =1 ; i <= 20 ; i++)
        a[i][1] = i ;
    for(int i = 2 ; i <= 20 ; i++){
        for(int j = 2 ;  j<= i ; j++)
            a[i][j] = a[i][j - 1] + a[i -1][j] ;
    }
     while(cin>>m>>n )  {
        cout<< a[m][n]<<endl;
     }
    return 0;
}int main()
{
    int m ,  n ;
    long long a[23][23] ;
    memset(a , 0 , sizeof(a)) ;
    for(int i =1 ; i <= 20 ; i++)
        a[i][1] = i ;
    for(int i = 2 ; i <= 20 ; i++){
        for(int j = 2 ;  j<= i ; j++)
            a[i][j] = a[i][j - 1] + a[i -1][j] ;
    }
     while(cin>>m>>n )  {
        cout<< a[m][n]<<endl;
     }
    return 0;
}

hdu 1290

http://acm.hdu.edu.cn/showproblem.php?pid=1290

献给杭电五十周年校庆的礼物

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7963 Accepted Submission(s): 4372

Problem Description

或许你曾经牢骚满腹
或许你依然心怀忧伤
或许你近在咫尺
或许你我天各一方

对于每一个学子
母校
永远航行在
生命的海洋

今年是我们杭电建校五十周年，这是一个值得祝福的日子。我们该送给母校一个怎样的礼物呢？对于目前的大家来说，最好的礼物当然是省赛中的好成绩，我不能参赛，就送给学校一个DOOM III球形大蛋糕吧，这可是名牌，估计要花掉我半年的银子呢。

想象着正式校庆那一天，校长亲自操刀，把这个大蛋糕分给各地赶来祝贺的校友们，大家一定很高兴，呵呵，流口水了吧...

等一等，吃蛋糕之前先考大家一个问题：如果校长大人在蛋糕上切了N刀（校长刀法极好，每一刀都是一个绝对的平面），最多可以把这个球形蛋糕切成几块呢？

做不出这个题目，没有蛋糕吃的！
为-了-母-校-，为-了-蛋-糕-（不是为了DGMM，枫之羽最会浮想联翩...），加-油-！

Input

输入数据包含多个测试实例，每个实例占一行，每行包含一个整数n(1<=n<=1000)，表示切的刀数。

Output

对于每组输入数据，请输出对应的蛋糕块数，每个测试实例输出一行。

Sample Input

复制代码

Sample Output

复制代码

分析：

数学递推题：

这类问题一般都有固定的公式，告诉大家一个技巧：二维的一般是an^2+bn+c,三维的一般是an^3+bn^2+cn+d.

用带定系数法求出各个系数就OK了，不用想破脑筋找规律。。。。。。

这种方法对类似问题都可以，变通一下好多问题都可以迎刃而解。。

4 - 15

复制代码

1
f(n) = (n * n + 5 ) *n  / 6 + 1 ;

复制代码

1
2
3
4
5
6
7
8
9
int main()
{
   int n ;
     while(cin>>n )  {
           int  s = (n * n + 5 ) *n  / 6 + 1 ;
        cout<<  s<<endl;
     }
    return 0;
}