不小心遇到一题4次求和，推公式推了好久。。想想实在是没有必要，每次遇到还得推一边实在是累。。所以，回来就写了一个差分的版本，单次计算的效率不比直接公式差，不容易出错，而且，再也不用蛋去推多项式公式了
至于什么是差分序列，这个我就不解释了，wiki上应该可以找到。我的写法是借鉴了牛顿插值的，使用了一个递推的写法（一般求多项式都会用这个， 比如4n^3 + n^2 + 2 * n + 3，一般写成 ((4n + 1) * n + 2) * n + 3）
初始化细节说明：order是生成的多项式的阶，请确保它大于或等于实际的多项式阶。order阶的多项式需要用order+1项进行init，请把这前order+1项存入数组cof中。最后调用init函数，就可以用calc来计算任意项了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| /******************************************************************************
* Differential Sequence
* init: O(order^2)
* you should init the cof[i] with the value of i-th value of sequence
* the sequene start from startfrom, default is 0, so a[0] is the first one
* of sequence a
* calc: O(order)
****************************************************************************/
const int ORDERLIM = 100;
double cof[ORDERLIM + 1];
int order;
const int startfrom = 0;
void init()
{
int i, j;
for(i = 1; i <= order; i++) {
for(j = order; j >= i; j--) {
cof[j] -= cof[j - 1];
}
}
}
double calc(double n)
{
int i;
double res = 0;
for(i = order; i > 0; i--) {
res += cof[i];
res *= (n - i + 1 - startfrom) / i;
}
res += cof[i];
return res;
}
/******************************************************************************
* MOD version of Differential Sequence
* cof should not overflow MOD
* MOD should should not less than order
* MOD should be prime
* need inverse in mod MOD system
****************************************************************************/
typec MOD = 1000000007;
typec cof[ORDERLIM + 1];
typec inv[ORDERLIM + 1];
int order;
const int startfrom = 0;
void init()
{
int i, j;
for(i = 1; i <= order; i++) {
inv[i] = inverse(i, MOD);
for(j = order; j >= i; j--) {
cof[j] -= cof[j - 1];
}
}
}
typec calc(typec n)
{
int i;
typec res = 0;
for(i = order; i > 0; i--) {
res += cof[i], res %= MOD;
res *= (n - i + 1 - startfrom) % MOD * inv[i] % MOD;
res %= MOD;
}
res += cof[i], res %= MOD;
while(res < 0) res += MOD;
return res;
} |
如果你对指针有着更深的理解，你就会意识到，指针不仅仅是一个地址，它同时还具有一个偏移属性。
指针的基本偏移就是地址自加之后和原地址的差。在一般情况下，这个差是由指针类型决定的，char的基本偏移是1个字节，int型是4个字节（32bit机中），比如对于int *p，p+1和p的物理地址差是4个字节，对于数组int a[3]，情况就少复杂，在使用中a是作为指针调用的，a的基本偏移是4个字节，但是你还可以对a进行如下操作&a，这个结果也是一个指针，所指向的地址跟a一样（数组首地址），但是基本偏移是不同的，这个偏移等于sizeof(int)*3,即3×4=12(其实就是sizeof(a))字节，加一后，它直接指向数组后面（已经在数组外了）。考虑二维数组的话，你会发现更好的结果，比如int a[3][7]，行宽是7，a的基本偏移就是4×7字节，*a是4字节，**a已经不是地址，它指向数组的元素，再看&a，跟一维的情况一样它指向数组后，偏移是4×7×3(即sizeof(a))。
值得注意的是：以上对于数组的情况不适用于一般的指针，指针似乎只有单层次的偏移，而数组的作为指针引用的时候，偏移却是多层的。编译器似乎给了数组而外的属性，sizeof对数组的作用和对指针的作用是完全不同的。在使用指针对数组引用的时候（仅用数组名），会有很多额外的属性，而指针试图像数组般引用确实很困难的。
我目前依然没有办法仅用指针构建多维数组（可以给出一个不连续的地址块，不能像二维数组般是一个连续的地址快,或者可以用一维模拟多维，但是它的引用比数组麻烦的多）。
之所以说它诡异，不是没有道理的。就一个初学者的角度（比如我的角度），const这个东西似乎是很不必要的，而引用也只是替代了指针的传地址而已(我几个月前学了C，或许就是因为这点吧，导致了这么多悲剧)。
当我通读了《C++简明教程》之后，我打算编写一个大数类（以前用C编过一个简陋的），好吧，我选择了一个足够庞大的工程！如果你看到了那个工程的最初版本，并且很了解C++的话，就会发现我有多悲剧了。闲话不说，切入正题——const和引用
先来谈谈我的经验和教训：(对于类T而言)
- const和引用最好同时出现，没有把握的情况下，不要只用引用
- 如果类的成员函数不会对当前的this对象造成值的改变（访问函数），那么尽量把函数定义为const类型（T function() const;）
- 临时对象如果被一个const引用绑定，其生命周期会延长到const引用生命的结束
- 构造函数的功能不仅仅只是对象的初始化，有些构造函数（单参数构造函数）定义了一个隐式类型转换，比如T add(T a);这个函数，如果有构造函数T(int a);那么你将看到add(3)能正常工作！如果你对效率要求没高到什么的 程度的话，你会发现这是多么好的功能啊
- 对于上一点，这种转换也可以给予引用，但是必须是const引用（在上一个例子中，T add(const T& a);函数也可以支持add(3)操作，但是别指望T add(T& a);也能支持！）！这也是我强调第一点的原因
- 别指望把函数内部创建的对象（不是你手动分配的内存）以const引用返回后，它也如同上面第三点一样延长生命周期（这个时候编译器一般会有警告）
- 如果你的类需要支持复合运算（比如我的大数类），以上的每一点你都应该支持
先来看第二点，有一类函数是很有代表性的——比较函数，这里给一个==操作符实例
bool operator==(const largenum &right) const;
//注意最后的那个const，没有了就会导致下面的悲剧
这是我大数类的一个函数,注意到比较函数原本就不应该改变this对象,所以用const不会错。当然一开始我可不知道const的好处，于是悲剧不可避免的发生了，当我试图在一个函数中比较一个传入的const引用和另一个对象的时候，出现了error。原因在于我试图把把一个const对象作为==的this对象，而我之前没有把他声明为访问函数（函数不是const类型）
int function(const largenum &x)
{
return (x==10)?0:1; //x是一个const引用，这里就悲剧了
}顺便通过上面的代码接入隐式类型转换，注意到x==10这个东西没？这东西我可是没定义啊，我定义的只是两个largenum类型的比较。那么这怎么能工作呢？
原因在于下面的构造函数提供的隐式类型转换能力
largenum(int a);//该构造函数把int型转为我定义的largenum类型
这使得x==10照常的工作了？还差一点，构造函数产生的隐式类型转换只会生成一个临时对象。如果你试图把它传递==的参数声明是单纯的引用，那么它将不能正常工作！注意到我说的第5点，const引用，它是有效的。还有如果函数的参数根本没有引用，那么将调用拷贝构造函数，他也能正常工作。好像这两个函数已经包含了我所要说的一切吧，确实是。
为什么临时对象不能和单纯的引用绑定呢？因为临时对象是const类型的（好吧，我还不能证实这一点，我只是搜索的时候注意到的）
最后再强调一点，也就是第一点，单纯的引用少用，除非你想要很多bug，或者你想额外编一些不必要的代码（当工程比较大的时候）
给出一个tranp函数，该函数把10进制转化为p进制的输出
void tranp(int n,int p)
{
if(n>p-1)
tranp(n/p,p);
printf("%d",n%p);
}在给出p进制到十进制的函数
int tranpt(int n,int p) //假设p小于10
{
return n? tranpt(n/10,p)*p+n%10:0;
}类似的有十进制到p进制的函数
int trantp(int n,int p)
{
return n? trantp(n/p,p)*10+n%p:0;
}如果要进行p进制数的运算，可以先在十进制运算，再转为p进制。
附加的给出个求n！的函数
int fact(int n)
{
return n? n*fact(n-1):1;
}