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

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

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

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

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

//裴波那契数列(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

八皇后问题由高斯提出,但是当时他自己没有完全解决掉,共有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就有了（狂晕~~~）

#include<iostream.h>
#include<math.h>
class NODE
{ friend class STACK;
NODE * NEXT;
float DATA;
};
class STACK
{ private:
NODE *HEAD;
public:
STACK()
{   HEAD=0;
} void push(float Data)
{   NODE *P=new NODE;
  P->DATA=Data;
  if(HEAD==0)
  {
   P->NEXT=0;
   HEAD=P;
  }
  else
  {
   P->NEXT=HEAD;
   HEAD=P;
  }
} float pop()
{   float Data;
  NODE *q,*n;
  Data=HEAD->DATA;
  n=q=HEAD;
  HEAD=q->NEXT;
        delete q;
  return Data;
} };
class Calulator
{ private:
STACK s;
public:
void compute(char op);
void run();
};
void Calulator::compute(char op)
{ float opend1=s.pop();
float opend2=s.pop();
switch(op)
{ case '+':
  s.push(opend1+opend2);
  break;
case '-':
        s.push(opend1-opend2);
  break;
case '*':
        s.push(opend1*opend2);
  break;
case '/':
        s.push(opend1/opend2);
  break;
case '^':
        s.push(pow(opend1,opend2));
  break;
} }
void Calulator::run()
{ char c;
float newoperate;
cout<<"press enter calulator:";
while(cin>>c,c!='=')
{   switch(c)
  {
  case '+':
  case '-':
  case '*':
  case '/':
  case '^':
   compute(c);
   break;
default:
         cin.putback(c);
   cin>>newoperate;
   s.push(newoperate);
   break;   
  }
} cout<<"the result is:"<<s.pop()<<endl;
}
int main()
{ Calulator calc;
calc.run();
return 0;
}

输入：    4 3 * 2 +  ＝      回车

输出     14

该算法的功能是：1。Sorting the list in decreasing order, and then the Kth largest value will be in position K.

                            2。A related technique to this would be to find the largest value and then move it to the last  location

                                 in the list. If we again look for the largest value in the list, ignoring the value we already found,

                                 we get the second largest value, which can be moved to the second last location in the list.

                                 If we con tinue this process, we will find the Kth largest value on the Kth pass.

This gives the algorithm:

#include"iostream"

using namespace std;

void Find_Kth_Largest(int list[],int n,int k){

//list:the value to look through

//n:the size of the list

//k:the element to select

       int i,largest,largest_location,j;

       for(i=1;i<=k;i++){//for_1

              largest=list[1];

        largest_location=1;

              for(j=2;j<=n-(i-1);j++){//for_2

                     if(list[j]>largest){

                            largest=list[j];

                            largest_location=j;

                     }//if

              }//for_2

              swap(list[n-(i-1)],list[largest_location]);//exchanging, making the largest elements

                                                                      //in the last elements of the list

       }//for_1

       cout<<"The number is:"<<largest<<"\n";

}//Find_Kth_Largest

void swap(int &a,int &b){//exchange

       int temp;

       temp=a;

       a=b;

       b=temp;

}//swap

void main(){

       int List[16],K,i;

    cout<<"Please input the K:";

       cin>>K;

       cout<<"\n";

       List[0]=0;

       for(i=1;i<=15;i++){

              List[i]=2*i-1;

              List[0]++;//List[0] is stored the length of the List

       }//for

    cout<<"\n"<<List[0]<<"\n";//output the length

    Find_Kth_Largest(List,List[0],K);

}

/*【Background】

Personally it's considered as meaningful in exercise

【Problem Description】

求n之内的所有偶数表示为两个素数之和。
注：歌德巴赫猜想是要证明对任何大于6的自然数n命题成立。

【Input Example】

10

【Output】

6=3+3

8=3+5

10=3+7     */

file://IDE:VC++6.0file://long型最大值范围内求解素数(之所以只是用long，因为范围再大也是一样永远是有限个数无法完全 file://证明此命题，只是一个示例验证罢了) file://素数就用的那经典判定法：2到此数square root不能被此数整除
#include <iostream.h>
#include <math.h>
#include <conio.h>

bool isPrime(long n)
{     for(int i=2;i<=sqrt(n);i++)
       if(n%i==0)
   return false;
    return true;
}

int main()
{     long n;
    cin>>n;
    for(long i=6;i<=n;i+=2)
       for(long j=3;j<=i;j+=2)
          if(isPrime(j)&&isPrime(i-j))
          {
              cout<<i<<"="<<j<<"+"<<i-j<<endl;
       break;
   }
    getch();
    return 0;
}

#include<iostream.h>
class Fushu
{ public:
Fushu(){};
Fushu(float r,float i);
friend Fushu operator +(Fushu &c1,Fushu &c2);
friend Fushu operator -(Fushu &c1,Fushu &c2);
friend Fushu operator *(Fushu &c1,Fushu &c2);
friend Fushu operator /(Fushu &c1,Fushu &c2);
void display();
private:
float real;
float imag;
};
Fushu::Fushu(float r,float i)
{ real=r;
imag=i;
} void Fushu::display()
{
if(real!=0)
{
  if(imag>0)
  {
   if(imag=1)
    cout<<real<<"+i"<<endl;
   else
  cout<<real<<"+"<<imag<<"i"<<endl;
  }
if(imag<0)
  cout<<real<<imag<<"i"<<endl;
else
  cout<<real<<endl;
}
else
{
   if(imag>0)
  {
   if(imag=1)
    cout<<"i"<<endl;
   else
  cout<<"+"<<imag<<"i"<<endl;
  }
if(imag<0)
  cout<<imag<<"i"<<endl;
if(imag=0)
  cout<<"0"<<endl;
}
} Fushu operator +(Fushu &c1,Fushu &c2)
{ Fushu temp;
temp.real=c1.real+c2.real;
temp.imag=c1.imag+c2.imag;
return temp;
} Fushu operator -(Fushu &c1,Fushu &c2)
{ Fushu temp;
temp.real=c1.real-c2.real;
temp.imag=c1.imag-c2.imag;
return temp;
} Fushu operator *(Fushu &c1,Fushu &c2)
{     Fushu temp;
temp.real=c1.real*c2.real-c1.imag*c2.imag;
temp.imag=c1.real*c2.imag+c2.real*c1.imag;
return temp;
} Fushu operator /(Fushu &c1,Fushu &c2)
{ Fushu temp;
float tt;
tt=c2.real*c2.real+c2.imag*c2.imag;
temp.real=(c1.real*c2.real+c1.imag*c2.imag)/tt;
temp.imag=(-c1.real*c2.imag+c2.real*c1.imag)/tt;
return temp;
} int main()
{ Fushu x(1,1),y(1,-1),z;
z=x+y;
z.display();
z=x-y;
z.display();
z=x*y;
z.display();
z=x/y;
z.display();
return 0;
}

#include"iostream"

using namespace std;

void Find_Kth_Largest(int list[],int n,int k){

//list:the value to look through

//n:the size of the list

//k:the element to select

       int i,largest,largest_location,j;

       for(i=1;i<=k;i++){//for_1

              largest=list[1];

        largest_location=1;

              for(j=2;j<=n-(i-1);j++){//for_2

                     if(list[j]>largest){

                            largest=list[j];

                            largest_location=j;

                     }//if

              }//for_2

              swap(list[n-(i-1)],list[largest_location]);//exchanging, making the largest elements

                                              //in the last elements of the list

       }//for_1

       cout<<"The number is:"<<largest<<"\n";

}//Find_Kth_Largest

void swap(int &a,int &b){//exchange

       int temp;

       temp=a;

       a=b;

       b=temp;

}//swap

void main(){

       int List[16],K,i;

    cout<<"Please input the K:";

       cin>>K;

       cout<<"\n";

       List[0]=0;

       for(i=1;i<=15;i++){

              List[i]=2*i-1;

              List[0]++;//List[0] is stored the length of the List

       }//for

    cout<<"\n"<<List[0]<<"\n";//output the length

       Find_Kth_Largest(List,List[0],K);

}