中文XML论坛--常用算法(C++描述)--网友提供

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> 本版讨论高级C/C++编程、代码重构(Refactoring)、极限编程(XP)、泛型编程等话题

[返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机技术与应用 → 『 C/C++编程思想』 → 常用算法(C++描述)--网友提供

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 21960 个阅读者　　

*	贴子主题：常用算法(C++描述)--网友提供	举报打印推荐 IE收藏夹
	本主题类别:

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	楼主

常用算法(C++描述)--网友提供

网友提供，借花献佛了~
由于最近看到论坛上的朋友的问题有很多是重复，所以开个接龙帖子，大家把经常用的算法以接龙的方式跟帖下去，以便后来者查询，请大家踊跃跟贴，请勿灌水，有问题请另外开贴提问！
要求：写清楚题目，算法思想和注释。
索引的形式整理在1楼，标有“算法思想”的代表只给出最简单算法主干。
1楼、索引
2、裴波那契数列
3、josephus问题(算法思想)
4、遍历国际象棋棋盘
5、八皇后问题(算法思想)
6、汉诺塔问题
7、矩阵算法
8、符号转换表
9、四则混合运算
10、Selection Algorithm
11、有穷范围内(n)的偶数都可分解成两个素数之和(歌德巴赫猜想有穷实例前提证明)
12、复数运算(利用重载实现)
13、Selection Algorithm实现

收藏分享
顶(0)

----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:54:00

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第2楼

裴波那契数列

//裴波那契数列(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);
}*/
----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:54:00

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第3楼

josephus问题(算法思想)

//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;
}
----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:54:00

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第4楼

遍历国际象棋棋盘

求从棋盘的左下角到右上角的无循环路径的总数
#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
----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:54:00

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第5楼

八皇后问题(算法思想)

八皇后问题由高斯提出,但是当时他自己没有完全解决掉,共有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");
}
----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:55:00

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第6楼

汉诺塔问题

汉诺塔是一个经典的算法题，以下是其递归算法：
#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个盘子的搬运过程
}
----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:55:00

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第7楼

矩阵算法

输入一个数(这里以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;
----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:55:00

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第8楼

符号转换表

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就有了（狂晕~~~）
----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:56:00

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第9楼

计算器的，（但是太急了，只是后缀输入，不要介意啊，以后扑上）
#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
----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:56:00

DMman

  威望：1
  头衔：数据挖掘青年
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：803
  积分：5806
  门派：W3CHINA.ORG
  注册：2007/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第10楼

Selection Algorithm,
该算法的功能是：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);
}
----------------------------------------------
数据挖掘青年 http://blogger.org.cn/blog/blog.asp?name=DMman
纪录片之家（很多纪录片下载）http://www.jlpzj.com/?fromuid=137653

2007/9/27 12:57:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2024/5/2 17:22:39

本主题贴数14，分页： [1] [2]

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	140.625ms