取数游戏 Description
题目描述
我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是间隔一个的不能同时被取走，如果1表示取走，0表示不取走，则不能出现101的连续串。
如果你能算出一共有多少种取法，那么你会被天神小泰泰奖励。
输入
输入仅包含一个数n（1≤ n ≤ 25）。
输出
输出仅包含一个数你的答案。
样例
输入 复制
4
输出 复制
12
提示
递归穷举即可。答案在2147483647以内。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <iomanip>
using namespace std;
int result = 0;
int a[30];
void output(int n)
{
int i;
for(i=0;i<=n-1;i++)
{
if (i < n - 2)
{
if (a[i] == 1 && a[i + 1] == 0 && a[i + 2] == 1)
{
return;
}
}
if (i == n - 1)
{
result++;
}
}
}
void search(int m,int n)
{
int i;
if(m==n)
{
output(n);
}
else
{
for(i=0;i<=1;i++)
{
a[m]=i;
search(m+1,n);
}
}
}
int main()
{
int array[30]={0,2,4,7,12,21,37,65,114,200,351,616,1081,1897,3329,5842,10252,17991,31572,55405,97229,170625,299426,525456,922111,1618192};
int n;
cin>>n;
search(0,n);
if(array[n] != result)cout<<"error"<<endl;
cout<<result<<endl;
result = 0;
return 0;
}
源码给你你继续研究吧
能不能翻译一下测试样例为什么是12
int main()
{
int N;
cin >> N;
int x, y, z;
int count=0;
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < 29; j++) {
x = i & (7 << j);
y = 5 << j;
z = x ^ y;
if (!z) {
count++;
break;
}
}
}
cout << (1<<N)-count;
}
找到规律了
#include<bits/stdc++.h>
using namespace std;
long long dp[100005][2];
int main(){
int n;
while(scanf("%d",&n)!=EOF)
//for(n = 1; n <= 25; n++)
{
memset(dp, 0, sizeof(dp));
dp[1][0] = dp[1][1] = 1;
for(int i = 2; i <= n; i++)
{
dp[i][1] = dp[i-1][0] + dp[i-1][1];
dp[i][0] = dp[i][1] - dp[i-2][0];
}
//printf("%lld + %lld = %d\n",dp[n][0], dp[n][1], dp[n][0]+dp[n][1]);
printf("%lld\n", dp[n][0]+dp[n][1]);
}
return 0;
}
