# 一步步学算法(算法例题)-2

www.MyException.Cn  网友分享于：2013-09-10  浏览：10次

# 1。河内之塔(Hanoi)

```#include <stdio.h>

void Move(int n,char a,char b)
{
printf("%d:%c-->%c\n",n,a,b);
}

void Hanoi(int n,char a,char b,char c)
{
if(n==1)//将A上的1个圆盘直接移到C,递归退出条件
Move(n,a,c);
else
{
Hanoi(n-1,a,c,b);//将A上n-1个圆盘借助C移到B
Move(n,a,c);//将A上剩下的1个圆盘直接移到C
Hanoi(n-1,b,a,c);//将B上n-1个圆盘借助A移到C
}
}

int main()
{
int n;
printf("\ninput   number:");
scanf("%d",&n);
Hanoi(n,'A','B','C');
return 0;
}
/* 打印结果

input   number:3
1:A-->C
2:A-->B
1:C-->B
3:A-->C
1:B-->A
2:B-->C
1:A-->C
*/```

# 2。Algorithm Gossip: 费式数列

f(n) = f(n-1)+f(n-2)---- if n>1

f(n) = n ------if n = 0, 1

..斐波那契数列，应该是每个写代码的都接触过了。虽然简单，不过还是罗列出来，谁叫它经典呢。

```#include <stdio.h>
#define N 10

int main()
{
int Fib[N] = {0};
int i;
Fib[0] = 0;
Fib[1] = 1;
for(i = 2; i < N; i++)
Fib[i] = Fib[i-1] + Fib[i-2];
for(i = 0; i < N; i++)
printf("%d ", Fib[i]);
printf("\n");
return 0;
}/* 打印结果
0 1 1 2 3 5 8 13 21 34
*/```

# 3.三色旗

```#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
using namespace std;
char c[]={'r','b','w','w','b','b','r','w','b'};
void swap(int i,int j)
{
char t=c[i];
c[i]=c[j];
c[j]=t;
}
int main(int argc, char* argv[])
{

int w=0;
int b=0;
string s=c;
int r=s.length()-1;
while(w<=r)
{
if(c[w]=='w')
w++;
else if(c[w]=='b')
{
swap(b,w);
b++;
w++;
}
else
{
while(r>=w&&c[r]=='r')
r--;
swap(w,r);
r--;
}
}
cout<<c;
return 0;
}
```

# 4.Algorithm Gossip: 老鼠走迷官(一)

```#include <stdio.h>
#include <stdlib.h>

int startI = 1, startJ = 1; // 入口
int endI=5,endJ=5; //出口
int success = 0;

int maze[7][7] =
{
{2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 2, 0, 2, 2},
{2, 2, 0, 2, 0, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2}
};

int visit(int i, int j)
{
maze[i][j] = 1;
if(i == endI && j == endJ)
success = 1;
if(success != 1 && maze[i][j+1] == 0)
visit(i, j+1);
if(success != 1 && maze[i+1][j] == 0)
visit(i+1, j);
if(success != 1 && maze[i][j-1] == 0)
visit(i, j-1);
if(success != 1 && maze[i-1][j] == 0)
visit(i-1, j);
if(success != 1)
maze[i][j] = 0;

return success;
}

int main()
{
int i, j;
printf("显示迷宫:\n");
for(i = 0; i < 7; i++)
{
for(j = 0; j < 7; j++)
if(maze[i][j] == 2)
printf("█");
else
printf(" "); printf("\n");
}
if(visit(startI, startJ) == 0)
printf("\n没有找到出口!\n");
else
{
printf("\n显示路径:\n");
for(i = 0; i < 7; i++)
{
for(j = 0; j < 7; j++)
{
if(maze[i][j] == 2)
printf("█");
else if(maze[i][j] == 1)
printf("◇");
else
printf(" ");
}
printf("\n");
}
}
return 0;
}
```

# 5.Algorithm Gossip: 老鼠走迷官(二)

```#include <stdio.h>
#include <stdlib.h>

int startI = 1, startJ = 1; // 入口
int endI=7,endJ=7; //出口

int maze[9][9] =
{
{2, 2, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2, 2, 2}
};

void visit(int i, int j)
{
int m, n;
maze[i][j] = 1;
if(i == endI && j == endJ)
{
printf("\n显示路径:\n");
for(m = 0; m < 9; m++)
{
for(n = 0; n < 9; n++)
if(maze[m][n] == 2)
printf("█");
else if(maze[m][n] == 1)
printf("◇");
else
printf(" ");
printf("\n");
}
}
if(maze[i][j+1] == 0)
visit(i, j+1);
if(maze[i+1][j] == 0)
visit(i+1, j);
if(maze[i][j-1] == 0)
visit(i, j-1);
if(maze[i-1][j] == 0)
visit(i-1, j);
maze[i][j] = 0;
}

int main(void)
{
int i, j;
printf("显示迷宫:\n");
for(i = 0; i < 7; i++)
{
for(j = 0; j < 7; j++)
if(maze[i][j] == 2)
printf("█");
else
printf(" ");
printf("\n");
}
visit(startI, startJ);
return 0;
}
```

# 6**  坐旋转字符串

```#include "string.h"

///////////////////////////////////////////////////////////////////////
// Move the first n chars in a string to its end
///////////////////////////////////////////////////////////////////////
char* LeftRotateString(char* pStr, unsigned int n)
{
if(pStr != NULL)
{
int nLength = static_cast<int>(strlen(pStr));
if(nLength > 0 || n == 0 || n > nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n - 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength - 1;

// reverse the first part of the string
ReverseString(pFirstStart, pFirstEnd);
// reverse the second part of the strint
ReverseString(pSecondStart, pSecondEnd);
// reverse the whole string
ReverseString(pFirstStart, pSecondEnd);
}
}

return pStr;
}

///////////////////////////////////////////////////////////////////////
// Reverse the string between pStart and pEnd
///////////////////////////////////////////////////////////////////////
void ReverseString(char* pStart, char* pEnd)
{
if(pStart == NULL || pEnd == NULL)
{
while(pStart <= pEnd)
{
char temp = *pStart;
*pStart = *pEnd;
*pEnd = temp;

pStart ++;
pEnd --;
}
}
}

PS：(XTYT)T=(YT)T(XT)T=YX
```