/*---------------------------------------------------------------------------
File name: recursionTree.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/16/2007 06:51:13
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------
利用递归树来找到递归式
T(n)=T(n-a)+T(a)+cn (0)
的渐近紧确解，其中a>=1且c>0是常数。 不甚感激！！！

Modify the recurrence formula (0) to a resonable assumption
T(n) = b, if 1<=n<=a
= T(n-a)+T(a)+cn, if n>a. (0')
where b is a constant.

Analysis:
---------------------------------------------------------------------------
We need to make some assumptions, since we don't know the values of T(1)
to T(a). One of such assumptions is
T(1) = T(2) = ... = T(a) = b, (1)
where b is a constant. b can be well taken as 1. After this assumption,
one does the math to arrive at
T(n-a+1) + T(n-a+2) + ... + T(n) = n*b + c/2*n*(n+1) - c_1, (2)
where c_1 is a constant dependent on a only.
Then we assume that (approximately)
T(n-a+1) = T(n-a+2) = ... = T(n). (3)
Equation (3) gives us that
a*T(n) = n*b + c/2*n*(n+1) - c_1,
or
T(n) = b/a*n + c/2*a * n* (n+1) - c_1/a.
Thus, the asymptotic soln for T(n) is
T(n) = c/(2*a) * n^2. (4)

Sample output:
---------------------------------------------------------------------------
0.5
-0.25
0.166667
0
0.1
0.0277778
0.0714286
0.03125
0.0555556
0.03
0.0454545
0.0277778
0.0384615
0.0255102
0.0333333
0.0234375
0.0294118
0.0216049
0.0263158
0.02
0.0238095
0.018595
0.0217391
0.0173611
0.02
0.0162722
0.0185185
0.0153061
0.0172414
0.0144444
0.016129
0.0136719
0.0151515
0.0129758
0.0142857
0.0123457
0.0135135
0.0117729
0.0128205
0.01125
0.0121951
0.010771
0.0116279
0.0103306
0.0111111
0.00992439
0.0106383
0.00954861
0.0102041
0.0092
0.00980392
0.00887574
0.00943396
0.00857339
0.00909091
0.00829082
0.00877193
0.00802616
0.00847458
0.00777778
0.00819672
0.00754422
0.00793651
0.00732422
0.00769231
0.00711662
0.00746269
0.00692042
0.00724638
0.00673469
0.00704225
0.00655864
0.00684932
0.00639153
0.00666667
0.00623269
0.00649351
0.00608153
0.00632911
0.0059375
0.00617284
0.00580012
0.0060241
0.00566893
0.00588235
0.00554354
0.00574713
0.00542355
0.00561798
0.00530864
0.00549451
0.00519849
0.00537634
0.0050928
0.00526316
0.00499132
0.00515464
0.00489379
0.00505051
0.0048
Press any key to continue . . .

Reference:
---------------------------------------------------------------------------

1. http://bbs.bc-cn.net/viewthread.php?tid=155557

*/

#include <iostream>
using namespace std;

// try MAX = 10000 or larger
#define MAX 100
int T[MAX];

/**
Initiate T[1..a] to be b and then implement the
recurrence formula (0').
*/
void recur(int a, int b, int c);

int main()
{
int a = 2;
int b = 1;
int c = 2;
int i;

recur(a, b, c);

/**
Check if T(n)/n^2 is close to c/(2*a).
*/
for(i=0; i<MAX; ++i)
{
cout<< double(T[i]) / double( (i+1)*(i+1) )
- double(c)/double(2*a) <<endl;
}

return 0;
}

void recur(int a, int b, int c)
{
int i;
for(i=0; i<a; ++i)
{
T[i] = b;
}

for(i=a; i<MAX; ++i)
{
T[i] = T[i-a] + T[a-1] + c*i;
}
}

[此贴子已经被作者于2007-7-16 22:22:32编辑过]