有问题先搜索一下：
楼主： 发表于
06:34 [回复100次/有效97个，浏览1204次]
计算f(2m)=f(0)+f(1)+...+f(m)
来源：http://topic.gimoo.net/u//38e-452c-a194-1ed8f6b49c99.html
现有递推公式：f(2m + 1) = f(2m)
　　　　　　　f(2m) = f(2m - 2) + f(m)
初始条件：　　f(0) = f(1) = 1
易知：f(2m) = f(0) + f(1) + ... + f(m)
要求：写一个C#或C++程序，对任意输入的n（0≤n＜100亿），计算f(n)。
对于较大的n，f(n)会超出UInt64所能表示的范围，结果可以存储为BigInteger。
参考：/skyivben/archive//1251697.html
可以利用递推公式写一个递归的程序，对于很大的n，程序有可能无法完成计算(来源贴13楼)。
可以计算 f(0) + f(1) + ... + f(m)，对于很大的n，存储空间可能不够(来源贴30楼)。
核心提示：该问题已在129楼由litaoye完美解决。125楼mathe也给出了很好的思路。
2楼 发表于
学习~~~····
3楼 发表于
不急，慢慢来，有空时想想就行。
不在乎时间，一周、两周、一两个月，都没关系，呵呵。
只是看到这个题有点意思，贴出来让大家动动脑筋。:)
4楼 发表于
目前一般用的是.net 2.0。
也有*** Visual Studio 2008，可以使用.net 3.5，
但没有*** Visual Studio 2010，所以没有.net 4.0环境。
5楼 发表于
优化了一下算组合的部分，多等待一下，就可以算到2^100（已经远远大于100亿了）
C# code
using S
using Skyiv.N
namespace ConsoleApplication6
{
class Program
{
public static BigInteger[,] Matrix = new BigInteger[256, 256];
public static BigInteger[,] BinomialMatrix = new BigInteger[256, 256];
public static void Main(String[] args)
{
for (int i = 1; i & 101; i++)
Console.WriteLine(&{0} {1}& , i, Count(1, i));
Console.ReadKey();
}
public static BigInteger Count(int column, int row)
{
if (column & 0)
return 0;
if (column == 0 || row == 0)
return 1;
if (Matrix[column, row] == null)
{
if (column &= row)
{
Matrix[column, row] = 0;
for (int i = 1; i
6楼 发表于
学习~~~~~~~~~~
7楼 发表于
高手好多啊
，还是不发言了
8楼 发表于
靠 有变颜色了
9楼 发表于
%%…………
10楼 发表于
11楼 发表于
计算机运算的很慢啊
有没有想过还有什么更好的方法吗 ？
12楼 发表于
13楼 发表于
看看。。。。学习下。。。。
14楼 发表于
xuexile学习了
15楼 发表于
不好意思，外面玩了一天，晚上才回这个帖子。说一些思路，就当抛砖引玉了。
首先我推算的结果同空军算出的结果差别很大，我是按照
f(2n) 约等于 f(n) * n / log(n) * k来递推的，其中k的取值可能有些问题，大概我算的项还不够多吧，
但似乎不应当有如此之大的差异，多半是我这里算错了，回头再查一查。
这个问题如果想算到100亿，我认为靠现有的这个递推，应该是不够的，需要利用乘法或更高级别的运算（目前是加法），比如：将f(2n)直接降成k(f(n))来处理，才可以，并且这个k不能是个复杂度很高的函数，我的思路主要集中在生成函数上面，但根据生成函数来找通项公式的可能性并不大，目前希望的是找到一个更好的递推，这个还是有可能的。不过以我目前的知识，恐怕还需学习不少东西才行，不知道周末是否有足够的时间，但愿吧。
16楼 发表于
学习.....
..
17楼 发表于
路过，学习学习
18楼 发表于
因为 f(2m + 1) = f(2m)，所以 f(2m - 1) = f(2m - 2)，因此我们有：
f(2m) = f(2m - 1) + f(m) = f(2m - 2) + f(m)。
19楼 发表于
没看懂，顶！！
20楼 发表于
感觉如果还想提升速度,应该从f(2m) 的积分函数方向考虑
(如果存在的话)
热门脚本语言：