新微赢技术网

标题: 常用算法(C++描述) [打印本页]

作者: _睡覺覺c◆s 时间: 2009-11-3 00:59
标题: 常用算法(C++描述)
由于最近看到论坛上的朋友的问题有很多是重复，所以开个接龙帖子，大家把经常用的算法以接龙的方式跟帖下去，以便后来者查询，请大家踊跃跟贴，请勿灌水，有问题请另外开贴提问！
要求：写清楚题目，算法思想和注释。
我会把帖子以索引的形式整理在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)

作者: ＂Ｍy!ove-、 时间: 2009-11-3 00:59
//裴波那契数列(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); }*/

作者: 牛牛 时间: 2009-11-3 01:00
//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; }

作者: 罗ぷ曼ㄉ帝Ke 时间: 2009-11-3 01:00
求从棋盘的左下角到右上角的无循环路径的总数 #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

作者: [日青](忝) 时间: 2009-11-3 01:00
八皇后问题由高斯提出,但是当时他自己没有完全解决掉,共有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"); }

作者: 冰美人 时间: 2009-11-3 01:00
汉诺塔是一个经典的算法题，以下是其递归算法：
#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个盘子的搬运过程 }

作者: 風雲々無心メ 时间: 2009-11-3 01:00
输入一个数(这里以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;

作者: 停淼心泪 时间: 2009-11-3 01:00
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就有了（狂晕~~~）

作者: 爱(じΩvê) 时间: 2009-11-3 01:00
哈。那我也写一个把，计算器的，（但是太急了，只是后缀输入，不要介意啊，以后扑上）
#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
///////////需要注释

作者: 可爱 时间: 2009-11-3 01:00
想问一下,大数的加, 减, 乘, 除该怎么算呀?

欢迎光临新微赢技术网 (http://bbs.weiying.cn/)