又一个有意思的算法题，来，头脑风暴下吧,该如何处理
又一个有意思的算法题，来，头脑风暴下吧
又一个有意思的题
以后再碰到这种描述简单 又比较有趣味的题 就和大家一起分享下
这次的是：
一个N位数列 由0和1组成 但是不能出现连1 问给定N 有多少种符合条件的数列？
我想了一个递归算法 结果TLE（超时）了 因为递归的过程中要分支 所以运算次数呈指数增加
大家动脑 想想有没有效率更高的办法
我把我的递归代码贴到楼下吧
COME ON BOYS!
------解决方案--------------------
#include "stdio.h"
#define N 4
void cal(int a,int count,int* result)
{
if (count == N)
{
(*result)++;
return;
}
else
{
count++;
}
if (a == 0)
{
cal(0,count,result);
cal(1,count,result);
}
else if (a == 1)
{
cal(0,count,result);
}
}
main()
{
int res = 0;
cal(1,1,&res);
printf("%d",res);
}
------解决方案--------------------
根本不需要递归，递推就行了，用f(n,x) 表示n位满足条件的，且末位为x的个数，则有：
f(n+1, 0) = f(n, 0) + f(n, 1) 因为在尾部加零，只要原来没有连1，就肯定不会有连1
f(n+1, 1) = f(n, 0) 因为尾部为1的，如果在尾部加1就连1了，尾部为0的，加上没关系
f(1, 0) = 1
f(1, 1) = 1
int calc(int n)
{
int f0=1, f1=1;
for (int i=1; i<n; i++)
{
int temp = f0;
f0 += f1;
f1 = temp;
}
return f0 + f1;
}
------解决方案--------------------
用递推可以，count[i,0] = count[i-1,1] + count[i-1,0] （所有末位为1的加上一个0和所有末位为0的加上0）
count[i,1] = count[i-1,0];（所有末位为0的加上1）
countSum[i] = count[i,0] + count[i,1] （个数是所有末位为0的加上末位为1的）
=>
count[i,0] = countSum[i-1]
count[i,1] = ount[i-1,0] = countSum[i-2]
=>
countSum[i] = count[i,0] + count[i,1] = countSum[i-1] + countSum[i-2]
原来还是斐波那契数列，那么求解用递推，或直接用母函数计算都可以(不考虑大数运算的话这个效率能达到log(n))
------解决方案--------------------
楼主是前两天问DP的那个吧。。
这个题目也可以理解为DP。
设dp[i][0]为长度为i，以0结尾的数的个数
dp[i][1]为长度为i，以1结尾的数的个数
那么
dp[i][0]=dp[i-1][0]+dp[i-1][1]
dp[i][1]=dp[i-1][0]
最后输出dp[len][0]+dp[len][1]就好了
当然时间复杂度可以优化到O(1)。楼上的代码已经写出来了
又一个有意思的题
以后再碰到这种描述简单 又比较有趣味的题 就和大家一起分享下
这次的是：
一个N位数列 由0和1组成 但是不能出现连1 问给定N 有多少种符合条件的数列？
我想了一个递归算法 结果TLE（超时）了 因为递归的过程中要分支 所以运算次数呈指数增加
大家动脑 想想有没有效率更高的办法
我把我的递归代码贴到楼下吧
COME ON BOYS!
------解决方案--------------------
#include "stdio.h"
#define N 4
void cal(int a,int count,int* result)
{
if (count == N)
{
(*result)++;
return;
}
else
{
count++;
}
if (a == 0)
{
cal(0,count,result);
cal(1,count,result);
}
else if (a == 1)
{
cal(0,count,result);
}
}
main()
{
int res = 0;
cal(1,1,&res);
printf("%d",res);
}
------解决方案--------------------
根本不需要递归，递推就行了，用f(n,x) 表示n位满足条件的，且末位为x的个数，则有：
f(n+1, 0) = f(n, 0) + f(n, 1) 因为在尾部加零，只要原来没有连1，就肯定不会有连1
f(n+1, 1) = f(n, 0) 因为尾部为1的，如果在尾部加1就连1了，尾部为0的，加上没关系
f(1, 0) = 1
f(1, 1) = 1
int calc(int n)
{
int f0=1, f1=1;
for (int i=1; i<n; i++)
{
int temp = f0;
f0 += f1;
f1 = temp;
}
return f0 + f1;
}
------解决方案--------------------
用递推可以，count[i,0] = count[i-1,1] + count[i-1,0] （所有末位为1的加上一个0和所有末位为0的加上0）
count[i,1] = count[i-1,0];（所有末位为0的加上1）
countSum[i] = count[i,0] + count[i,1] （个数是所有末位为0的加上末位为1的）
=>
count[i,0] = countSum[i-1]
count[i,1] = ount[i-1,0] = countSum[i-2]
=>
countSum[i] = count[i,0] + count[i,1] = countSum[i-1] + countSum[i-2]
原来还是斐波那契数列，那么求解用递推，或直接用母函数计算都可以(不考虑大数运算的话这个效率能达到log(n))
------解决方案--------------------
楼主是前两天问DP的那个吧。。
这个题目也可以理解为DP。
设dp[i][0]为长度为i，以0结尾的数的个数
dp[i][1]为长度为i，以1结尾的数的个数
那么
dp[i][0]=dp[i-1][0]+dp[i-1][1]
dp[i][1]=dp[i-1][0]
最后输出dp[len][0]+dp[len][1]就好了
当然时间复杂度可以优化到O(1)。楼上的代码已经写出来了