经典算法实现一 （hanio， fibonacci数列， pascaltriangle，三色旗）
1 hanio
从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
解法：运用递归的思想，分两步走：
1 若想将n号盘放到z轴上，那么必须先将（1，...，n-1）号盘移动到y轴上，此时z轴作为辅助轴。
2 然后将y轴上的（1，...，n-1）号盘移动到z轴上，此时x轴作为辅助轴
代码实现：
int count = 1;
void move(int n, char a, char b)
{
cout<<"move "<<count<<"th "<<a<<"->"<<b<<endl;
count++;
}
void hanoi(int n, char a, char b, char c)
{
if(n == 1){
move(1, a, c);
return;
}
hanoi(n-1, a, c, b);
move(n, a, c);
hanoi(n-1, b, a, c);
}
int main()
{
char a='A', b='B', c='C';
int n=20;
hanoi(n, a, b, c);
return 0;
}
2 fibonacci数列
如以下： 1、1 、2、3、5、8、13、21、34、55、89......
解法：每个数等于前面两个数相加
代码实现：
void gossip(int gos[], int n)
{
gos[1] = gos[0] = 1;
for(int i=2; i<n; i++){
gos[i]= gos[i-1] + gos[i-2];
}
}
int main()
{
int gos[19];
gossip(gos, sizeof(gos)/sizeof(gos[0]));
for(int i=0; i<sizeof(gos)/sizeof(gos[0]); i++){
cout<<gos[i]<<" ";
}
cout<<endl;
return 0;
}
3 pascaltriangle
解法一：两边元素为1，中间元素等于两肩元素之和
代码实现：
#define N 11
指针版：
void combi(int **comb, int n)
{
for(int i = 0; i<n; i++){
*((int*)comb + i*n) = 1;
*((int*)comb + i*n + i) = 1;
for(int j = 1; j<i; j++){
*((int*)comb + i*n + j) = *((int*)comb + (i-1)*n + j-1) + *((int*)comb + (i-1)*n + j);
}
}
}
数组版
void combi_1(int comb[][N])
{
for(int i=0; i<N; i++){
comb[i][0] = 1;
comb[i][i] = 1;
for(int j=1; j<i; j++)
comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
}
}
解法二：杨辉三角的第n行就是二项式展开式的系数列
long combi_3(int n, int r)
{
int i, j;
long p = 1, q =1;
for(i=1; i<=r; i++){
p = p*(n-i+1);
q = i*q;
}
p = p/q;
return p;
}
void paint() {
int n, r, t;
for(n = 0; n <= N; n++) {
for(r = 0; r <= n; r++) {
int i;
if(r == 0) {
for(i = 0; i <= (N-n); i++)
printf(" ");
}else {
printf(" ");
}
printf("%3ld", combi_3(n, r));
}
printf("\n");
}
}
4 三色旗
假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您
希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上
进行这个动作，而且一次只能调换两个旗子
解法：在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问
题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到
白色留在中间，遇到红色往后移，如下所示：
只是要让移动次数最少的话，就要有些技巧：
1 如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。
2 如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。
3 如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。
注意B、W、R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动结束呢？一开始
时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗
子就都是红色了，此时就可以结束移动。
代码实现：
void tricolor(char *array, int n, char *expect)
{
char *p1 = &array[0], *p2 = &array[0], *p3 = &array[n-1];
while(p2 <= p3){
if(*p2 == expect[0]){
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
p1++;
p2++;
}else if(*p2 == expect[1]){
p2++;
}else if(*p2 == expect[2]){
char tmp = *p3;
*p3 = *p2;
*p2 = tmp;
p3--;
}
}
}
int main()
{
char expect[3] = {'B', 'W', 'R'};
char array[10] = {'R', 'W', 'R', 'W', 'B', 'B', 'R', 'W', 'B', 'B'};
tricolor(array, 10, expect);
for(int i=0; i<10; i++){
cout<<array[i]<<" ";
}
cout<<endl;
return 0;
}