第1个回答 2014-03-17
裴波那契数列
//裴波那契数列(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 n);
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);
}
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;
}
遍历国际象棋棋盘
求从棋盘的左下角到右上角的无循环路径的总数
#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;
}
}
}
}
cout<<"the total number is:"<<num;
getchar();
}
八皇后问题(算法思想)
八皇后问题由高斯提出,但是当时他自己没有完全解决掉,共有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;本回答被提问者采纳
//裴波那契数列(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 n);
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);
}
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;
}
遍历国际象棋棋盘
求从棋盘的左下角到右上角的无循环路径的总数
#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;
}
}
}
}
cout<<"the total number is:"<<num;
getchar();
}
八皇后问题(算法思想)
八皇后问题由高斯提出,但是当时他自己没有完全解决掉,共有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;本回答被提问者采纳
相似回答
