已知递推数列：a(1)=1, a(2i)=a(i),（i为正整数）a(2i+1) = a(i) + a(i+1)（i为正整数）试求该数列的第n项。（设n<30000)

#include<iostream>
using namespace std;
int fun(int n) //函数体
{
while(n>0&&n<30000)
{
if(n==1)return 1;
if(n>1) //递归调用
{
int m=n%2;
if(m==0)
return fun(n/2);
if(m==1)
return fun(n/2)+fun(n/2+1);
}
}
}

int main() //用1~10测试函数，答案正确！
{
for(int i=1;i<10;i++)
cout<<fun(i)<<" ";
return 0;
}

int GetIt(int now) { if(now==1) { return 1; } if(now % 2 == 0) { return GetIt(now/2); } else { now = (now-1) / 2; return GetIt(now) + GetIt(now+1); } }

int _tmain(int argc, _TCHAR* argv[]) { int n = 30000; int result = GetIt(n); printf("result:%d\n",result); return 1; }

斐波那契数列问题

int fib(int n)

{

if(n==1)

return 1;

else if(n==2)

return 1;

else

return(fib(n)+fib(n+1));

}