The mook jong
Accepts: 506
Submissions: 1281
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
ZJiaQ want to become a strong man, so he decided to play the mook jong。ZJiaQ want to put some mook jongs in his backyard. His backyard consist of n bricks that is 1*1,so it is 1*n。ZJiaQ want to put a mook jong in a brick. because of the hands of the mook jong， the distance of two mook jongs should be equal or more than 2 bricks. Now ZJiaQ want to know how many ways can ZJiaQ put mook jongs legally(at least one mook jong).
Input
There ar multiply cases. For each case, there is a single integer n( 1 < = n < = 60)
Output
Print the ways in a single line for each case.
Sample Input
123456
Sample Output
1235812
问题描述
ZJiaQ为了强身健体，决定通过木人桩练习武术。ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。由于ZJiaQ是个强迫症，所以他要把一个木人桩正好摆在一个地砖上，由于木人桩手比较长，所以两个木人桩之间地砖必须大于等于两个，现在ZJiaQ想知道在至少摆放一个木人桩的情况下，有多少种摆法。
输入描述
输入有多组数据，每组数据第一行为一个整数n(1 < = n < = 60)
输出描述
对于每组数据输出一行表示摆放方案数
输入样例
123456
输出样例
1235812
解题思路：
1、排列组合：
代码如下：
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorithm>#include <string>#include <vector>#include <deque>#include <list>#include <set>#include <map>#include <stack>#include <queue>#include <numeric>#include <iomanip>#include <bitset>#include <sstream>#include <fstream>#include <limits.h>#define debug "output for debug\n"#define pi (acos(-1.0))#define eps (1e-6)#define inf (1<<28)#define sqr(x) (x) * (x)#define mod 1000000007using namespace std;typedef long long ll;typedef unsigned long long ULL;ll c[65][65];//排列组合void cinit(){int i,j;for(i=0;i<=60;i++){c[i][0]=c[i][i]=1;for(j=1;j<i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];}}int main(){int i,n;ll sum;cinit();while(~scanf("%d",&n)){//i的范围for(i=1,sum=0;3*(i-1)+1<=n;i++){int m=n-2*(i-1);sum+=c[m][i];}printf("%I64d\n",sum);}return 0;}
2、找规律
n=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
ans=1,2,3,5,8,12,18,27,40,59,87,128,188,276,405,594,871,1277,1872,2744
根据上面的结果ans以及n，可以发现，ans[i]=ans[i-1]+ans[i-3]+1；
代码如下：
#include <cstdio>#include <iostream>using namespace std;typedef long long ll;int main(){int i,n;ll a[65];a[1]=1;a[2]=2;a[3]=3;for(i=4;i<=60;i++)a[i]=a[i-1]+a[i-3]+1;while(~scanf("%d",&n)){printf("%I64d\n",a[n]);}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
让情谊在笑声中升腾，当朋友遇到了难题的时候，
