其实我们都知道组合有一个公式：
可以用于递归计算，但是，事实告诉我，这不是一个好算法，效率不行，因此需要一个更高效的算法。
显然注意到公式
它的效率显然太高了，悲剧的是如果用上面的乘积除以下面的乘积，很快就溢出了！这样做显然不行。
怎样才能避免溢出呢？对策：让除法优先。
那么怎么保证作用除法的时候一定能整除呢？注意到以下事实，连续的2个整数乘积，必然能被2!整除，连续的3个整数乘积，必然能被3!整除……连续k个整数乘积，必然能被k!整除。其实假设设连续的那k个整数最大的为n，那么整除结果必然是C(n,k)，它显然是一个整数.而且，只要最终结果不溢出，它就不会溢出！
于是给出 代码：
int combinationNumber(int n,int m)
{
int solution=1,g;
m=(n-m<m)?n-m:m; //一个优化，基于C(n,m)=C(n,n-m)
for(int i=0;i<m;i++)
{
if(solution%(i+1)==0)
{
solution/=i+1;
solution*=n-i;
}
else if((n-i)%(i+1)==0)
{
solution*=(n-i)/(i+1);
}
else //之前没考虑到的情况，修复了这个bug
{
g=gcd(solution,i+1);
solution/=g;
solution*=(n-i)/((i+1)/g);
}
}
return solution;
}
为了编写一个更为有效的大数类，我设计了这个开放数组，就是不存在上限的数组（只要机器不崩溃）。
我简单说下思路：
其实数组使用链表模拟的，每个链表单元存储unitsize个元素（给一个unsigned指针分配的连续内存），然后重载operator[]，像数组一样对它索引。unitsize不能太小，因为链表的索引效率不高，同样是1000000个单位，unitsize是1000的话，链表长度就是1000，unitsize是10000的话链表长度就是100；但是unitsize也不能太大，否则当运算位数较低时（比如几百位），初始化效率比较低，也就违背了我的初衷（初始化1000个元素的数组和初始化1000000个元素的数组效率是不同的，尤其是经常有临时对象被创建的时候）。
下面贴一下源代码
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| //############openarray.h#################
#ifndef OPENARRAY_H_INCLUDED
#define OPENARRAY_H_INCLUDED
const unsigned unitsize=1000;
typedef unsigned numunit;
class openarray
{
private:
class arrayunit
{
public:
numunit *num;
arrayunit *next;
public:
arrayunit();
arrayunit(const arrayunit*);
~arrayunit();
};
arrayunit *root; //链表的根节点
public:
openarray(){root=new arrayunit;}
openarray(const openarray &in){root=new arrayunit(in.root);}
~openarray(){delete root;}
//####################################
numunit& operator[](unsigned offset);
void resize(unsigned length);
};
#endif // OPENARRAY_H_INCLUDED
//##############################################
//***************************************************
//#################openarray.cpp###################
#include “openarray.h”
#include <stdio.h>
//#########Class arrayunit##########################
openarray::arrayunit::arrayunit()
{
num=new numunit[unitsize];
for(unsigned i=0;i<unitsize;i++)
{
num[i]=0;
}
next=NULL;
}
openarray::arrayunit::arrayunit(const arrayunit *in)
{ //拷贝该节点以及后面的所有节点
num=new numunit[unitsize];
for(unsigned i=0;i<unitsize;i++)
{
num[i]=in->num[i];
}
if(in->next!=NULL)
{
next=new arrayunit(in->next);
}
else
{
next=NULL;
}
}
openarray::arrayunit::~arrayunit() //析构该节点以及后面所有节点
{
delete [] num;
if(next!=NULL)
{
delete next; //递归析构
}
}
//#########Class openarray##########################
numunit& openarray::operator[](unsigned offset)
{
arrayunit *p=root; //p记录链表中的位置
unsigned adr=offset/unitsize; //adr是p和所寻找节点的偏移
offset%=unitsize; //所寻找元素在节点中的位置
while(adr!=0)
{
if(p->next!=NULL)
{
p=p->next;
}
else
{
p->next=new arrayunit; //如果访问位置溢出，空间将自动增长
p=p->next;
}
adr--;
}
return p->num[offset]; //找到后返回引用
}
void openarray::resize(unsigned length)//允许在外部维护一个length，
{ //释放掉length位置后的内存
arrayunit *p=root;
unsigned adr=length/unitsize;
while(adr!=0)
{
if(p->next!=NULL)
{
p=p->next;
}
else
{
p->next=new arrayunit;
p=p->next;
}
adr--;
}
if(p->next!=NULL)
{
delete p->next;
p->next=NULL;
}
} |
如果你对指针有着更深的理解，你就会意识到，指针不仅仅是一个地址，它同时还具有一个偏移属性。
指针的基本偏移就是地址自加之后和原地址的差。在一般情况下，这个差是由指针类型决定的，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，或者你想额外编一些不必要的代码（当工程比较大的时候）
当我掷出一枚硬币，我有可能在硬币落地之前知道它落地的状态甚至位置吗？（假设我有一台计算力无穷的机器，并且我已经输入了这个世界的每一个部分，虽然这是不可能的）
这其实就是哲学上是一个决定论和非决定论：决定论，这个世界从他出现的一刻开始，他的未来就已经完全确定了，如果我完全知道一个时刻，世界的每一个部分的状态位置，我就“可以”计算出它的任何时刻。如果我有办法在一瞬间使所有事物的速度翻转，那么一切将会反演。非决定论，这个世界存在底层的随机性，存在一个完全不可预知的过程，它导致这个世界是不可预测的，即使速度的翻转也不会反演。
刚开始的我，当然我相信每一个思考这个问题的人，都会转入这样的境地：意识，似乎是不可预测的，它如此神奇，我们很快就会转向非决定论，因为意识似乎就是我们的证据，我们莫名的崇拜它，那个时候我相信二元论，我相信意识的完全独立性……但是，很快的，我感觉到我的意识总是以某种方式工作（后来看了心理学，印证了我的感觉），差不多用了4年多吧，我才真正对意识有足够的理解。这期间我独立的发现了混沌（好吧，我一直怀疑是不是那个混沌，因为这和数学中的混沌确实不同，这是统计学上的概率倾向），在高一的时候，我接触到了描述混沌的著作（相比之下，我原来的思想，只是一些雏形），显然达尔文的进化论只是它的一个特例，而意识的复杂，完全可以通过自组织，自进化的过程构建。要知道这个过程已经构建了生命！从完全无机的环境开始（你相信生命来自于外太空？我可以告诉你，这从来不是必须的，或者说，这个概率虽然存在，但我已经完全可以无视它。而且你还得开始思考另一个问题：外太空的生命又是怎么来的？）。
于是，问题很快就由意识，回到了底层——组成我们宇宙的基元。它拥有底层的随机性吗？在我注意到概率这个东西的时候，你知道我是多么乐于接受量子力学吗？没错，就是量子力学，因为它的理论中出现了不确定性。但是，这个所谓的随机，是真的吗？它是因为其中的复杂，导致的“不可预测”（就如同，我们总是无法预测硬币的正反一样——我说这句话的时候翻了一个巨大的逻辑错误，不过我相信你明白我的意思）？还是它原本特有的随机？