由于最近看到论坛上的朋友的问题有很多是重复，所以开个接龙帖子，大家把经常用的算法以接龙的方式跟帖下去，以便后来者查询，请大家踊跃跟贴，请勿灌水，有问题请另外开贴提问！

要求：写清楚题目，算法思想和注释。

我会把帖子以索引的形式整理在1楼，标有“算法思想”的代表只给出最简单算法主干。

1、索引 2、裴波那契数列 3、josephus问题(算法思想) 4、遍历国际象棋棋盘 5、八皇后问题(算法思想) 6、汉诺塔问题 7、矩阵算法 8、符号转换表 9、四则混合运算 10、灌水

11、灌水 12、Selection Algorithm 13、有穷范围内(n)的偶数都可分解成两个素数之和(歌德巴赫猜想有穷实例前提证明) 14、复数运算(利用重载实现) 15、Selection Algorithm实现

感谢以下朋友提供算法(括号中的数字代表提供的数量)：

corrupt (2) kappa314 (2) 三少爷 (1)

[此贴子已经被作者于2004-11-22 11:29:27编辑过]

//裴波那契数列(1,1,2,3,5,8……) //规律:f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2)...(n>2)

//循环算法(求前n个fibonacci数) #include<iostream.h> #include<iomanip.h> void main() { int fab1=1,fab2=1,fabn,n,i; cout<<"input the quantity number:"; cin>>n; cout<<setiosflags(ios::right)<<setw(3)<<fab1; cout<<setiosflags(ios::right)<<setw(3)<<fab2; for(i=3;i<=n;i++) { fabn=fab1+fab2; fab1=fab2; fab2=fabn; cout<<setiosflags(ios::right)<<setw(3)<<fabn; } cout<<endl; }

/*递归算法(求第n个fibonacci数) #include<iostream.h> #include<iomanip.h> int fibonacci(int); void main() { int n; cout<<"input the serial number:"; cin>>n; cout<<"the fibonacci you want is:" <<fibonacci(n)<<endl; } int fibonacci(int n) { if(n==1||n==2) return 1; else return fibonacci(n-1)+fibonacci(n-2); }*/

//N个小孩围成一圈报数，凡是报到指定数字的小孩离开圈子 //打印最后剩下的小孩的号码

#include<iostream.h>

void main() { const int N=10; //假定有10个小孩 int kid[N],*p; int interval; //报到此数的小孩离开 int count=0,leave=0; //报数计数器和离开的小孩数

for(int i=0;i<N;i++) kid[i]=i+1; //给每个小孩一个号码

cout<<"please input the Count off number: "; cin>>interval;

while(leave!=N-1) //当离开人数不等于总人数 { for(p=kid;p<kid+N;p++) //从号码是1的小孩开始数

if(*p!=0) //已离开的小孩不用报数 { count++;

if(count==interval) //报到此数时 { count=0; //由1开始重新报数 cout<<*p<<" "; *p=0; //离开的小孩号码置零 leave++; } } }

p=kid;

while(*p==0) //最后只剩下一个号码不是0的小孩 p++;

cout<<endl<<"the last one is: "<<*p<<endl; }

求从棋盘的左下角到右上角的无循环路径的总数 #include"stdio.h" #define N 8 //因为算出来的数据太大，所以要算很久，可以改变N的值进行测试。 #include"iostream.h" //此算法采用回溯法

enum bin{fal,tr}; int top=0; long int num=0; int row[]={-1,-2,-2,-1,1,2,2,1}; int col[]={-2,-1,1,2,2,1,-1,-2}; bin mark[N][N];

struct stack { int x,y; int dir;}board[N*N];

void push(stack it) { board[top].x=it.x; board[top].y=it.y; board[top].dir=it.dir; mark[board[top].x][board[top].y]=tr; top++; }

stack pop() { --top; mark[board[top].x][board[top].y]=fal; board[top].dir++; return board[top]; }

bin empty() { if(top==0) return tr; else return fal; }

void main() { stack temp={N-1,N-1,-1}; push(temp); while(!empty()) { int g,h; temp=pop(); int i=temp.x; int j=temp.y; int dir=temp.dir; while(dir<8) { g=i+row[dir]; h=j+col[dir]; if((g<0)||(h<0)||(g>=N)||(h>=N)||mark[g][h]) dir++; else { if(g==0&&h==0) {num++;dir++;} else { temp.x=i; temp.y=j; temp.dir=dir; push(temp); i=g; j=h; dir=0; }//else }//else }//while }//while cout<<"the total number is:"<<num; getchar(); }//main

[此贴子已经被作者于2004-10-17 11:17:05编辑过]

八皇后问题由高斯提出,但是当时他自己没有完全解决掉,共有92个解,完全不同的解共有12种(考虑棋盘翻转)

问题:在国际象棋棋盘上放置八个皇后(很强的:-),使她们互不攻击,问共有多少种方法?

算法:可以用穷举法,穷举法通过循环或者递归来实现;还可以用试探法,同样可以用递归来实现(包含回溯).我想解决问题的核心就是算法,知道算法了,具体用什么语言来实现就不是很难了.

#include<stdio.h>

#define N 8 int layout[N];//布局 int key=0; int judge(int row, int col)//判断能否在（row，col）放下 { int i; for(i=0;i<row;i++) { if(layout[i]==col) return 0;//同一列 if(i-layout[i]==row-col) return 0;//同一条主对角线 if(i+layout[i]==row+col) return 0;//同一条副对角线 } return 1; } void lay(int row)//在row行上放Queen { int i; if (row==N)//放完N个Queen输出布局 { printf("\n%02d ", ++key); for(i=0;i<N;i++) printf("%c%d ",layout[i]+'a',i+1); } else { for(i=0;i<N;i++)//在i列上放Queen { layout[row]=i; if(judge(row,i)) lay(row+1); } } }

void main() { lay(0); printf("\n"); }

汉诺塔是一个经典的算法题，以下是其递归算法：

#include<iostream.h>

void hanio(int n,char,char,char);

void main() { char A='A',B='B',C='C'; int n=3; hanio(n,A,B,C); }

void hanio(int n,char A,char B,char C) { if(n==1) { cout<<"将第"<<n<<"个盘面从"<<A<<"柱搬到"<<C<<"柱上"<<endl; } else { hanio(n-1,A,C,B); cout<<"将第"<<n<<"个盘面从"<<A<<"柱搬到"<<C<<"柱上"<<endl; hanio(n-1,B,A,C); } }

运行结果是： 将第1个盘面从A柱搬到C柱上 将第2个盘面从A柱搬到B柱上 将第1个盘面从C柱搬到B柱上 将第3个盘面从A柱搬到C柱上 将第1个盘面从B柱搬到A柱上 将第2个盘面从B柱搬到C柱上 将第1个盘面从A柱搬到C柱上

这个不是从递归算法出发用栈消解得出的算法，而是直接从当前情况来判断移动的步骤。非递归算法：

#include<iostream.h> #include<vector>

using namespace std;

class Needle { public: Needle() { a.push_back(100); } void push(int n) { a.push_back(n); } int top() { return a.back(); } int pop() { int n = a.back(); a.pop_back(); return n; } int movenum(int n) { int i = 1;while (a[i] > n) i++; return a.size() - i; } int size() { return a.size(); } int operator [] (int n) { return a[n]; } private: vector<int> a; };

void Hanoi(int n) { Needle needle[3], ns; int source = 0, target, target_m = 2, disk, m = n; for (int i = n; i > 0; i--) needle[0].push(i); while(n) { if(!m) { source = ns.pop(); target_m = ns.pop(); m = needle[source].movenum(ns.pop()); } if(m % 2) target = target_m; else target = 3 - source - target_m; if(needle[source].top() < needle[target].top()) { disk = needle[source].top();m--; cout<< disk << " move " << (char)(source + 0x41) << " to "<< (char)(target + 0x41) << endl; needle[target].push(needle[source].pop()); if(disk == n) { source = 1 - source; target_m = 2; m = --n; } } else { ns.push(needle[source][needle[source].size() - m]); ns.push(target_m); ns.push(source); m = needle[target].movenum(needle[source].top()); target_m = 3 - source - target; source = target; } } }

void main() { Hanoi(6);//6个盘子的搬运过程 }

输入一个数(这里以3为例)打印以下距阵(回字矩阵)：

1 1 1 1 1 1 1 2 2 2 2 1 1 2 3 3 2 1 1 2 3 3 2 1 1 2 2 2 2 1 1 1 1 1 1 1

#include<iostream.h> #include<iomanip.h> void main() { int n,a,b,i,j; cout<<"\ninput the number of the laps: "; cin>>n; cout<<endl; for(i=1;i<=2*n;i++) { for(j=1;j<=2*n;j++) { a=i>n?(2*n+1-i):i; b=j>n?(2*n+1-j):j; cout<<setw(3)<<(a=(a<b)?a:b); } cout<<'\n'; } cout<<endl; }

以1 1 1 1为例，分成两部分： 1 1 1 1 1 1 2 2 1 2 1 1 2 2 1 2 2 1 2 2 1 1 2 1 1 1 1 1 1 1 1 1

对应的数组坐标为： (0,3) (0,0)(0,1)(0,2)(0,3) (1,2)(1,3) (1,0)(1,1)(1,2) (2,1)(2,2)(2,3) (2,0)(2,1) (3,0)(3,1)(3,2)(3,3) (3,0)

对应的判断为： if((i+j)>=m) if((i+j)<=m)

a[i][j]=(i>=j)?(m-i):(m-j); a[i][j]=(i<=j)?(i+1):(j+1);

这样就可以确定赋值给上半边还是下半边了！

接下来的问题就是打印输出了！

if(j==(m-1)) cout<<endl;

keywords: 注：keywords VC++没有实现出来，（直到2003也是，考虑到代码兼容问题），如需要使用应该#include<iso646.h>，具体内容： /* iso646.h standard header */ #ifndef _ISO646 #define _ISO646 #define and && #define and_eq &= #define bitand & #define bitor | #define compl ~ #define not ! #define not_eq != #define or || #define or_eq |= #define xor ^ #define xor_eq ^= #endif /* _ISO646 */

Digraphs: <% { %> } <: [ :> ] %: # %:%: ## 注：以上二元符号在VC++6.0下也没实现出来，VC++.net 2003里面可以使用

Trigraphs: ??= # ??( [ ??) ] ??< { ??> } ??/ ??' ^ ??! | ??- ~ ??? ? 注：以上三元符号VC++6.0就有了（狂晕~~~）