对于long long类型也存放不下的超长整数，可以使用字符串模拟的办法来对其进行运算的模拟。此处仅做加法的示范，其他运算思想类似。 每四位视为一个整数，进位等情况对下一次的计算考虑影响。 ~~~ #include<iostream> using namespace std; #define MAX_LEN 50 int nNumA[MAX_LEN]; int nLenA = 0; int nNumB[MAX_LEN]; int nLenB = 0; int nResult[2*MAX_LEN]; int nLenR = 0; void CharToInt(char *szSource, int *nDes, int *Len) { int j = 0; int nDesLoc = 0; int nTotalNum = 0; int thisNum = 0; //当前char的值 int nHead = strlen(szSource) % 4; if (nHead != 0) { for (int k = 0; k< nHead; k++) { thisNum = (int)(szSource[k] - '0') + 0; nTotalNum = nTotalNum*10 + thisNum; j++; } nDes[nDesLoc] = nTotalNum; //数组开头不足四位 nTotalNum = 0; j = 0; nDesLoc++; } for (int i= nHead; i<strlen(szSource); i++) { if (j == 4) { nDes[nDesLoc] = nTotalNum; //每一个int数组为上存储四个数字 nTotalNum = 0; j = 0; nDesLoc++; } thisNum = (int)(szSource[i] - '0') + 0; nTotalNum = nTotalNum*10 + thisNum; j++; } if (nTotalNum != 0) { nDes[nDesLoc] = nTotalNum; nTotalNum = 0; j = 0; nDesLoc++; } *Len = nDesLoc; cout<<"长度为"<<nDesLoc<<endl; for (int j = 0; j< nDesLoc; j++) { cout<<nDes[j]<<" "; } cout<<endl; } void LenAdd() { int ALen = nLenA; int BLen = nLenB; int CStart = 0; int nFlag = 0; while (ALen != 0 && BLen != 0) { nResult[CStart] = (nNumA[ALen-1] + nNumB[BLen-1] + nFlag) % 9999; nFlag = (nNumA[ALen-1] + nNumB[BLen-1] + nFlag) / 9999; CStart++; ALen--; BLen--; } while (ALen > 0) { nResult[CStart] = (nNumA[ALen-1] + nFlag) % 9999; nFlag = (nNumA[ALen-1] + nFlag) / 9999; CStart++; ALen--; } while (BLen > 0) { nResult[CStart] = (nNumB[BLen-1] + nFlag) % 9999; nFlag = (nNumB[BLen-1] + nFlag) / 9999; CStart++; BLen--; } nLenR = CStart; cout<<"相加结果为："<<endl; for (int i = CStart-1; i >-1 ; i--) { cout<<nResult[i]<<" "; } cout<<endl; } int main() { char szInput[100]; cout<<"输入第一个操作数"<<endl; cin>>szInput; CharToInt(szInput, nNumA, &nLenA); cout<<"输入第二个操作数"<<endl; cin>>szInput; CharToInt(szInput,nNumB, &nLenB); LenAdd(); system("pause"); } ~~~ 

蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。与它对应的是确定性算法。为象征性地表明这一方法的概率统计特征，故借用赌城蒙特卡罗命名。 对于求圆周率PI的问题，可以模拟在一个长宽均为1的正方形里面均匀的随机落入点，然后根据落在半径为1的圆中的点的个数来求得Pi的大小，点的数目越多，结果越准确。 ~~~ #include <iostream> #include <time.h> using namespace std; #define MAX_NUM 5000000 int g_nInCircle = 0; int main() { double nX; double nY; double dDis = 0; double Pi = 0; srand(time(NULL)); for (long int i=0; i< MAX_NUM; i++) { nX = (double)rand()/RAND_MAX; //可能生成都最大随机数 nY = (double)rand()/RAND_MAX; dDis = pow(nX, 2) + pow(nY, 2); if (dDis < 1.0) { g_nInCircle++; } } Pi =(double) g_nInCircle / MAX_NUM * 4; cout<<"Pi = "<<Pi<<endl; system("pause"); } ~~~ 

双色汉诺塔问题：圆盘最初是混合颜色的从小到大排好的，现在要求根据其颜色分开到两个柱子上分别从小到大排好。三色汉诺塔问题可与此类似，分别是排到三个柱子上。 与汉诺塔问题类似，稍作一点改动，假设柱子的编号为ABC，共有n个圆盘(n为偶数) 1.将最上面的n-1个圆盘从A移动到B上面 2.将底部那个圆盘从A移动到C 3.将B柱上的n-2个圆盘移动到A上，从而形成了第二个图那样的情景 因此，可以根据一个递归的解法来解决此问题  ~~~ //双色汉诺塔问题 #include<iostream> using namespace std; int removeTimes = 0; void hanoiorignal(int nmovnum, char czsource, char cztemp, char czdes) { if (nmovnum == 0) { return; } else if (nmovnum == 1) { cout<<"move the "<<nmovnum<<" disk from "<<czsource <<" to "<<czdes<<endl; removeTimes++; } else { hanoiorignal(nmovnum -1, czsource, czdes, cztemp); cout<<"move the "<<nmovnum<<" disk from "<<czsource <<" to "<<czdes<<endl; removeTimes++; hanoiorignal(nmovnum -2, cztemp, czdes, czsource); } } void hanoitwocolor(int ndisk) { char szsource = 'a'; char sztemp = 'b'; char szdes = 'c'; for (int i = ndisk ; i > 0; i-= 2) { hanoiorignal(ndisk, szsource, sztemp, szdes); } cout<<"总共移动次数为："<<removeTimes<<endl; removeTimes = 0; } void main() { int ndisknum = 0; cout<<"输入塔上的盘碟数目，必须是2的倍数，输入0结束"<<endl; cin>>ndisknum; while (ndisknum) { hanoitwocolor(ndisknum); cout<<"输入塔上的盘碟数目，必须是2的倍数，输入0结束"<<endl; cin>>ndisknum; } system("pause"); } ~~~ 输入共有6个圆盘，输出结果如下： 

生命游戏（game of life）为1970年由英国数学家J. H. Conway所提出，某一细胞的邻居包括上、下、左、右、左上、左下、右上与右下相邻之细胞，游戏规则如下： 孤单死亡：如果细胞的邻居小于一个，则该细胞在下一次状态将死亡。 拥挤死亡：如果细胞的邻居在四个以上，则该细胞在下一次状态将死亡。 稳定：如果细胞的邻居为二个或三个，则下一次状态为稳定存活。 复活：如果某位置原无细胞存活，而该位置的邻居为三个，则该位置将复活一细胞。 ~~~ #include <iostream> #include <time.h> using namespace std; #define ROW 10 #define COLUMN 10 #define ALIVE 1 #define DEAD 0 int nCellSta[ROW][COLUMN]; int nTempSta[ROW][COLUMN]; int CellCount(int nRow, int nColumn) { int nSum = 0; for (int i = nRow-1; i< nRow +2; i++) { for (int j = nColumn -1; j< nColumn +2 ; j++) { if (i < 0 || i >ROW-1 || j<0 || j>COLUMN -1) { continue; } if (nCellSta[i][j] == ALIVE) { nSum++; } } } switch(nSum) { case 0: case 1: case 4: case 5: case 6: case 7: case 8: return DEAD; case 2: return nCellSta[ROW][COLUMN]; case 3: return ALIVE; } } int PrintValue() { int nSum = 0; for (int i = 0; i< COLUMN; i++) { for (int j = 0; j< ROW; j++) { cout<<nCellSta[i][j]<<" "; nSum += nCellSta[i][j]; } cout<<endl<<endl; } return nSum; } int main() { int nFlag = 0; memset(nCellSta, 0, sizeof(nCellSta)); memset(nTempSta, 0, sizeof(nTempSta)); srand(time(NULL)); for (int i = 0; i< COLUMN; i++) { for (int j = 0; j< ROW; j++) { nCellSta[i][j] = rand() % 2; } } PrintValue(); while (1) { cout<<"新一轮游戏进化开始"<<endl; for (int i = 0; i< COLUMN; i++) { for (int j = 0; j< ROW; j++) { nTempSta[i][j] = CellCount(i, j); } } memcpy(nCellSta,nTempSta,sizeof(nCellSta)); if(!PrintValue()) { cout<<"全部死亡，进化结束"<<endl; break; } cout<<"是否开启下一轮进化，1继续，0退出"<<endl; cin>>nFlag; if (nFlag) { continue; } else break; } system("pause"); } ~~~ 

给出了八个硬币，只知道其中七个都是真的，另外一个是假的，假的那个比真的总或者比真的轻，请找出哪个是假的。 此处用决策树来解决，决策树算法一般用在一些数据分类问题方面，该问题其实并不是非常适合，仅作为使用演示。决策树是一种依托于策略选择而建立的树，可以是二叉树也可以是多叉树。决策树有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。 为所有的硬币赋相同的值，随机选择一个来赋予不同的值，是为假硬币。通过决策树来选择那个假的硬币，详见代码： ~~~ //八枚银币比较问题，决策树，根据每次比较结果的不同而采用不同的决策 #include <iostream> #include <time.h> using namespace std; void CoinCmp(int *coins, int smallOne, int bigOne, int RightOne) { if (coins[smallOne] < coins[RightOne]) { cout<<"银币"<<smallOne+1<<"为假银币，重量较轻"<<endl; } else cout<<"银币"<<bigOne+1<<"为假银币，重量较重"<<endl; } void EightCoid(int *CoinWeight) { if (CoinWeight[0] + CoinWeight[1] + CoinWeight[2] == CoinWeight[3] + CoinWeight[4] + CoinWeight[5] ) { if (CoinWeight[6] > CoinWeight[7]) { CoinCmp(CoinWeight, 7, 6, 0); } else CoinCmp(CoinWeight, 6, 7, 0); } else if (CoinWeight[0] + CoinWeight[1] + CoinWeight[2] > CoinWeight[3] + CoinWeight[4] + CoinWeight[5]) { if ( CoinWeight[0] + CoinWeight[3] > CoinWeight[1] + CoinWeight[4]) { CoinCmp(CoinWeight, 4, 0, 2); } else if (CoinWeight[0] + CoinWeight[3] < CoinWeight[1] + CoinWeight[4]) { CoinCmp(CoinWeight, 3, 1, 2); } else CoinCmp(CoinWeight, 5, 2, 0); } else if (CoinWeight[0] + CoinWeight[1] + CoinWeight[2] < CoinWeight[3] + CoinWeight[4] + CoinWeight[5]) { if ( CoinWeight[0] + CoinWeight[3] < CoinWeight[1] + CoinWeight[4]) { CoinCmp(CoinWeight, 0, 4, 2); } else if (CoinWeight[0] + CoinWeight[3] > CoinWeight[1] + CoinWeight[4]) { CoinCmp(CoinWeight, 1,3, 2); } else CoinCmp(CoinWeight, 2, 5, 0); } } int main() { int nCoinWeight[8]; for (int i = 0; i< 8; i++) { nCoinWeight[i] = 20; } srand(time(NULL)); nCoinWeight[rand()%8] = rand()%40; for (int i = 0; i< 8; i++) { cout<<i+1<<": "<<nCoinWeight[i]<<endl; } EightCoid(nCoinWeight); system("pause"); return 1; } ~~~ 运行结果如下： 

题意描述：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 可从行出发考虑，对于第一行中的第一个位置都考虑其摆放一个皇后，然后移动到下一行第一个位置，并考虑在该位置摆放皇后是否会造成攻击，若是则考虑该行的下一个位置；如不是则继续考虑下一行，直到八个皇后都被放置。 总的来说就是采用深度搜索加上迭代的方法来解决这个问题。 ~~~ //八皇后问题，采用回溯法 #include<iostream> using namespace std; int g_nQueenLoc[8][8]; int nLeftToRight[15] = {0}; //对角线是否有皇后 int nRightToLeft[15] = {0}; int nRow[8] = {0}; int g_nQueenDown = 0; //已经放置的皇后数目 int g_nTotalNum = 0; //可能的解数目 void printQueen() { cout<<endl<<"第"<<g_nTotalNum<<"种放置方法为:"<<endl; for(int i = 0; i< 8; i++) { for (int j = 0; j < 8; j++) { cout<<" "; if (g_nQueenLoc[i][j]) { cout<<"█"; } else cout<<g_nQueenLoc[i][j]<<" "; } cout<<endl; } cout<<endl; } void PutQueenDown(int xParm, int yParm) { int left2Right = 7 - xParm + yParm; int Right2Left = xParm + yParm; if(nLeftToRight[left2Right] == 0 && nRightToLeft[Right2Left] == 0 && nRow[yParm] == 0) //表明该位置可以放置皇后 { nLeftToRight[left2Right] = 1; //标记该位置已经放置皇后 nRightToLeft[Right2Left] = 1; nRow[yParm] = 1; g_nQueenLoc[xParm][yParm] = 1; g_nQueenDown++; if (g_nQueenDown != 8) { PutQueenDown(xParm+1, 0); } else if (g_nQueenDown == 8) { g_nTotalNum++; printQueen(); } //还原该位置 g_nQueenDown--; nLeftToRight[left2Right] = 0; nRightToLeft[Right2Left] = 0; nRow[yParm] = 0; g_nQueenLoc[xParm][yParm] = 0; } if (yParm == 7) { return; } else PutQueenDown(xParm, yParm+1); } int main() { cout<<"八皇后问题"<<endl; memset(g_nQueenLoc, 0, sizeof(g_nQueenLoc)); PutQueenDown(0, 0); cout<<"共有解法"<<g_nTotalNum<<"种"<<endl; system("pause"); return 0; } ~~~ 运行结果：其中方块表示皇后所在的位置 

问题描述：一个骑士在棋盘中，给予其一个初始位置，求其是否能够走完整个棋盘。 骑士的走法和中国象棋的马走法相同，在前进过程中，骑士在其落足过的地方不能再次落足。 代码如下： ~~~ //骑士走棋盘问题，骑士的走法与象棋中马的走法相同，要求骑士便利棋盘中所有的点，但不能重复走一个点两次 //本题采用优先选择+回溯到方法进行，每次最先选择下一次能走路径最少的点 #include <iostream> using namespace std; #define MAX_SIZE 9 int nAlreayVisit = 0; int nChessBoard[MAX_SIZE][MAX_SIZE]; //模拟棋盘状况，0表示没有被访问过 int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; //可访问的各个点相对当前点位置 int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1}; //int nArray void PrintChessBoard() { cout<<endl<<"已经访问的位置数目为："<<nAlreayVisit<<endl; for (int i = 0; i< MAX_SIZE; i++) { for (int j = 0; j < MAX_SIZE; j++) { cout<<nChessBoard[i][j]<<" "; } cout<<endl; } } //测试该位置有多少个下一步的路径可选 int TestNextWay(int nTestX, int nTestY) { int tempX,tempY; int nRet = 0; for (int i = 0; i< 8; i++) { tempX = nTestX + ktmove1[i]; tempY = nTestY + ktmove2[i]; if (tempX > -1 && tempX < MAX_SIZE && tempY > -1 && tempY < MAX_SIZE && nChessBoard[tempX][tempY] == 0) { nRet++; } } return nRet; } bool KnightTour(int nStartX, int nStartY) { nAlreayVisit++; //当前点被访问了 nChessBoard[nStartX][nStartY] = nAlreayVisit; //表示其被访问的次序 //PrintChessBoard(); if(nAlreayVisit == MAX_SIZE*MAX_SIZE) //棋盘上的所有点都已经被访问过了，返回true { return true; } //选取下一个要访问的点 int nCanVisit[MAX_SIZE][2]; int nCanNum = 0; //下一步可以走到选择方法 int tempX,tempY; int nNextWay = 0; int NextX, NextY; //下一步要走的坐标 int nLeastWay = 9; //选取下下步走法最少的路径 for (int i = 0; i< 8; i++) { tempX = nStartX + ktmove1[i]; tempY = nStartY + ktmove2[i]; if (tempX > -1 && tempX < MAX_SIZE && tempY > -1 && tempY < MAX_SIZE && nChessBoard[tempX][tempY] == 0) { nCanVisit[nCanNum][0] = tempX; nCanVisit[nCanNum][1] = tempY; nCanNum++; nNextWay = TestNextWay(tempX,tempY); if (nNextWay < nLeastWay) { nLeastWay = nNextWay; NextX = tempX; NextY = tempY; } } } bool bFlag = false; if (nCanNum == 0) //无法继续走下去了 { nAlreayVisit--; //当前点访问被撤销 nChessBoard[nStartX][nStartY] = 0; return false; } else { bFlag = KnightTour(NextX,NextY); if (bFlag) { return true; } else { for (int k = 0; k< nCanNum; k++) { bFlag = KnightTour(nCanVisit[k][0], nCanVisit[k][1]); if (bFlag) { return true; } } } } //遍历完所有可走节点都无法完成 nAlreayVisit--; //当前点访问被撤销 nChessBoard[nStartX][nStartY] = 0; return false; } int main() { int x,y; cout<<"请输入起始位置坐标x和y(即数组的下标，为0到7范围)"<<endl; cin>>x>>y; memset(nChessBoard, 0, sizeof(nChessBoard)); if (KnightTour(x,y)) { cout<<"遍历棋盘成功"<<endl; PrintChessBoard(); } else cout<<"遍历1棋盘失败"<<endl; system("pause"); } ~~~ 

一只老鼠走进了一个迷宫，如何从其中走出去，在此处我们用2表示墙壁或障碍，0表示可以通过的路径通过深度搜索+回溯的方式可以解得答案老鼠每次选择一个方向前进，如果可以则继续深度搜索，否则换一个方向继续尝试。 如果各个方向都无法找到迷宫出口，则退回到老鼠到该点之前所在的点继续尝试其他方向实现代码如下： ~~~ //回溯法，也可以看作是一种深度搜索 #include <iostream> using namespace std; int g_nEndY = 5; int g_nEndX = 6; int g_nMapArr[7][7] = { {2, 0, 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, 0, 2}}; int MouseMove(int x, int y) { int nFlag = 0; //标志迷宫是否完成 g_nMapArr[x][y] = 1; //老鼠走过 if(x ==g_nEndX && y == g_nEndY) //已知迷宫出口和未知迷宫出口两种判断方式，如果未知，则判断边界条件 nFlag = 1; if (nFlag == 0 && g_nMapArr[x][y+1] == 0 ) { nFlag = MouseMove(x,y+1); } if (nFlag == 0 && g_nMapArr[x+1][y] == 0) { nFlag = MouseMove(x+1, y); } if (nFlag == 0 && g_nMapArr[x-1][y] == 0) { nFlag = MouseMove(x-1,y); } if(nFlag == 0 && g_nMapArr[x][y-1] == 0) { nFlag = MouseMove(x, y-1); } if (nFlag == 1) { return 1; } else g_nMapArr[x][y] = 0; //撤销 return nFlag; } void main() { int nStartY = 0; int nStartX = 1; int nXLen = 7; int nYLen = 7; for (int i = 0; i< nYLen; i++) { for (int j = 0; j< nXLen; j++) { if (g_nMapArr[i][j] == 2) { cout<<"█"; } else if (g_nMapArr[i][j] == 1) { cout<<"◇"; } else cout<<" "; } cout<<endl; } int nflag = MouseMove(nStartY, nStartX); cout<<endl<<endl; if (nflag == 0) { cout<<"Mouse can't get out"<<endl; } else { cout<<"迷宫路径"<<endl; for (int i = 0; i< nYLen; i++) { for (int j = 0; j< nXLen; j++) { if (g_nMapArr[i][j] == 2) { cout<<"█"; } else if (g_nMapArr[i][j] == 1) { cout<<"◇"; } else cout<<" "; } cout<<endl; } } system("pause"); } ~~~ 运行结果如下：  对于不止一条路径的情况该程序稍作修改就可以找出所有路径并统计其数目 ~~~ //回溯法，也可以看作是一种深度搜索 //带有统计性质，其关键为每次达到预定条件后统计计数加一，然后撤销 #include <iostream> using namespace std; int nTotalWays = 0; int g_nEndY = 7; int g_nEndX = 8; int nXLen = 9; int nYLen = 9; int g_nMapArr[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, 0, 2}}; void PrintWay() { cout<<endl; cout<<"第"<<nTotalWays<<"种迷宫路径"<<endl; for (int i = 0; i< nYLen; i++) { for (int j = 0; j< nXLen; j++) { if (g_nMapArr[i][j] == 2) { cout<<"█"; } else if (g_nMapArr[i][j] == 1) { cout<<"◇"; } else cout<<" "; } cout<<endl; } } int MouseMove(int x, int y) { int nFlag = 0; //标志迷宫是否完成 g_nMapArr[x][y] = 1; //老鼠走过 if(x ==g_nEndX && y == g_nEndY) //已知迷宫出口和未知迷宫出口两种判断方式，如果未知，则判断边界条件 { nFlag = 1; } if (nFlag == 0 && g_nMapArr[x][y+1] == 0 ) { MouseMove(x,y+1); } if (nFlag == 0 && g_nMapArr[x+1][y] == 0) { MouseMove(x+1, y); } if (nFlag == 0 && g_nMapArr[x-1][y] == 0) { MouseMove(x-1,y); } if(nFlag == 0 && g_nMapArr[x][y-1] == 0) { MouseMove(x, y-1); } if (nFlag == 1) { nTotalWays++; PrintWay(); } g_nMapArr[x][y] = 0; //撤销 return nFlag; } void main() { int nStartY = 1; int nStartX = 1; for (int i = 0; i< nYLen; i++) { for (int j = 0; j< nXLen; j++) { if (g_nMapArr[i][j] == 2) { cout<<"█"; } else if (g_nMapArr[i][j] == 1) { cout<<"◇"; } else cout<<" "; } cout<<endl; } MouseMove(nStartY, nStartX); cout<<endl<<endl; if (nTotalWays == 0) { cout<<"Mouse can't get out"<<endl; } else cout<<"共有"<<nTotalWays<<"种走法"<<endl; system("pause"); } ~~~ 运行结果为： 

假设有一根绳子，上面有一些红、白、蓝色的旗子。起初旗子的顺序是任意的，现在要求用最少的次数移动这些旗子，使得它们按照蓝、白、红的顺序排列。注意只能在绳子上操作，并且一次只能调换两个旗子。 分析：其实要移动旗子得到要求的结果很简单，但是需要注意的是需要移动最少的次数这个限制条件。 网上的一种解法： 从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移，如下所示： 只是要让移动次数最少的话，就要有些技巧： 如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。 如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。 如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。 注意B、W、R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动结束呢？一开始时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗子就都是红色了，此时就可以结束移动，如下所示： 该程序选自：经典算法大全 老奔整理 Email: [ben0133@163.com](#) ~~~ #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #define BLUE 'b' #define WHITE 'w' #define RED 'r' using namespace std; int times = 0; char color[] = {'r', 'w', 'b', 'w', 'w', 'b', 'r', 'b', 'w', 'r', '\0'}; //#define SWAP(x, y) { char temp; \ // temp = color[x]; \ // color[x] = color[y]; \ // color[y] = temp; } void printArr() { cout<<"第"<<times<<"次的排序结果为："; for (int i =0; i<strlen(color);i++) { cout<<color[i]; } cout<<endl; } void SWAP(int x, int y) { char temp; temp = color[x]; color[x] = color[y]; color[y] = temp; times++; printArr(); }; int main() { int wFlag = 0; int bFlag = 0; int rFlag = strlen(color) - 1; int i; cout<<"移动前："; for(i = 0; i < strlen(color); i++) printf("%c", color[i]); printf("\n"); while(wFlag <= rFlag) { if(color[wFlag] == WHITE) wFlag++; else if(color[wFlag] == BLUE) { SWAP(bFlag, wFlag); bFlag++; wFlag++; } else { while(wFlag < rFlag && color[rFlag] == RED) rFlag--; SWAP(rFlag, wFlag); rFlag--; } } cout<<"移动后："<<endl; for(i = 0; i < strlen(color); i++) printf("%c", color[i]); printf("\n"); cout<<"cost time is :"<<times<<endl; system("pause"); return 0; } ~~~ 程序执行结果为：  注意观察打印出来的结果，可以发现有一些冗余的移动，导致移动次数比较大改进的解法如下：进行两趟遍历，首先对于成对的顺序相反的红色和蓝色旗子，交互其位置其次对前后的蓝色和红色旗帜进行整理，使其聚集到一起 ~~~ //三色旗问题改进 //可大体分为三步，首先交换b和r的位置，直到所有b都在r之前； //然后整理前半部分的b，使其都靠前 //最后整理后半部分的r，使其都靠后 #include <iostream> using namespace std; int g_nExchangeNum = 0; char szFlagInput[1024] = {'r','w','b','w', 'w', 'b', 'r', 'b', 'w', 'r', '\0'}; //char szFlagInput[1024] = {"rwwwwrbbbrrwrrbbrrrbbbbwwwbrr"}; void ExchangeColor(char *pSour, char *pDes) { char szTemp; g_nExchangeNum++; szTemp = *pSour; *pSour = *pDes; *pDes = szTemp; cout<<"第"<<g_nExchangeNum<<"次移动，结果为： "<<szFlagInput<<endl; } //r和b互换 void ScanFrist() { char *pBlue = szFlagInput; char *pRed = szFlagInput + strlen(szFlagInput) - 1; while (pRed > pBlue) { while (pBlue < szFlagInput + strlen(szFlagInput) - 1 && *pBlue != 'r' ) { pBlue++; } while(pRed > szFlagInput && *pRed!= 'b') pRed--; if(pRed > pBlue) ExchangeColor(pBlue, pRed); } } //蓝色旗帜调整完毕后，调整红色旗帜 void ScanSecond() { char *pWhite = NULL; char *pBlue = NULL; char *pRed = NULL; //调整蓝色旗帜 pRed = szFlagInput ; while (pRed < szFlagInput+ strlen(szFlagInput)) { if (*pRed != 'r') { pRed++; } else break; } if (pRed != szFlagInput) //有蓝色的旗帜 { if(pRed == szFlagInput + strlen(szFlagInput) ) pBlue = szFlagInput + strlen(szFlagInput) -1; else pBlue = pRed - 1; pWhite = szFlagInput; while(pWhite < pBlue) { while(pWhite< szFlagInput + strlen(szFlagInput) - 1 && *pWhite != 'w') pWhite++; while(pBlue > szFlagInput && *pBlue!= 'b') pBlue--; if (pWhite < pBlue) { ExchangeColor(pWhite,pBlue); } } } //调整红色旗帜 if(pRed == szFlagInput + strlen(szFlagInput)) return; pWhite = szFlagInput + strlen(szFlagInput) -1; while (pWhite > pRed) { while(pRed< szFlagInput + strlen(szFlagInput) - 1 && *pRed != 'r') pRed++; while( pWhite> szFlagInput && *pWhite!= 'w') pWhite--; if (pWhite > pRed) { ExchangeColor(pWhite,pRed); } } } int main() { cout<<"未移动前结果为： "<<szFlagInput<<endl; ScanFrist(); ScanSecond(); cout<<"the color list of the result is :"<<endl; cout<<" "<<szFlagInput<<endl; cout<<"总共的交换次数为："<<g_nExchangeNum<<endl; system("pause"); return 1; } ~~~ 程序执行结果为3，无冗余移动步骤： 

杨辉三角，又叫帕斯卡三角形，是一个三角形矩阵，其顶端是 1,视为(row0).第1列(row1)(1&1)两个1,这两个1是由他们上头左右两数之和 (不在三角形内的数视为0).依此类推产生第2列(row2):0+1=1;1+1=2;1+0=1.第3列(row3):0+1=1;1+2=3; 2+1=3;1+0=1. 循此法可以产生以下诸列。  (a+b)^n的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。 由此可通过排列组合式来求得其对应的每一项系数，即杨辉三角的对应位置的值。 组合公式为：c(n,m)=p(n,m)/m!=n!/((n-m)!*m!) ~~~ #include <iostream> using namespace std; #define SIZE_TRIANGLE 12 int ResultGet(int row, int column) {//row为行数，column为列数，该函数返回该位置的数字 float fResult = 1; int nBack = 0; for (int i=1; i<= column; i++) { fResult *= (float)(row - i + 1)/i; } nBack = fResult; return nBack; } int main() { for (int i = 0; i<= SIZE_TRIANGLE; i++) { for (int k =0; k<(SIZE_TRIANGLE - i); k++) { cout<<" "; //输出每行前面的括号 } for (int j = 0; j<= i; j++) { printf("%3d", ResultGet(i,j)); cout<<" "; } cout<<endl; } system("pause"); return 1; } ~~~

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 下图分析了黄金圆盘数目分别为1、2、3时的情况，可通过其观察移动的一般规律。  图片来源：http://www.chiuchang.com.tw/toy/hanoi/hanoi.html 通过分析可知，题目要求是将所有圆盘最终从A号柱移动到C号柱，对于问题规模为n的情况，可将问题分解为三步： **1.将顶上的n-1个黄金圆盘从A号柱通过C号柱移动到B号柱上。** **2.将A号柱子上的最后一个圆盘移动到C号柱上。** **3.将B号柱上的n-1个圆盘通过A移动到C号柱上。** 有此可知该问题可以用一递归的思想来解决，实现代码如下： ~~~ //汉诺塔问题，递归 //时间复杂度，设有n个盘 f(n) = 2f(n-1)+1 = 4f(n-2) + 2 + 1 = pow(2, n-1) + pow(2, n-2) + `````+ 4 + 2 + 1 //等积数列 可知最后 f(n) = pow(2, n)-1; #include <iostream> using namespace std; int g_nTimesUsed = 0; void Hanoi(int nDisk, char A, char B, char C) { if (nDisk == 1) { cout<<"moved the "<<nDisk<< " Disk from "<<A <<" to "<<C<<endl; g_nTimesUsed++; return; } else { Hanoi(nDisk-1, A, C, B); cout<<"moved the "<<nDisk<< " Disk from "<<A <<" to "<<C<<endl; g_nTimesUsed++; Hanoi(nDisk-1, B,A, C); } } int main() { int nBow = 0; cout<<"输入塔A上的盘数目"<<endl; cin>>nBow; Hanoi(nBow, 'A','B','C'); cout<<endl<<"used "<<g_nTimesUsed<<" times"<<endl; system("pause"); } ~~~ 本系列(趣味算法系列)内的部分问题题目来自：经典算法大全 老奔整理  Email: [ben0133@163.com](#)

> 原文出处：[趣味算法设计](http://blog.csdn.net/column/details/interestedcodefeng.html) 作者：[firechungelaile](http://blog.csdn.net/firechungelaile) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 趣味算法设计 > 对常出现的一些趣味算法问题进行分析和实现