www.gusucode.com > C++四柱汉诺塔源代码-源码程序 > C++四柱汉诺塔源代码-源码程序/code/Hanoi.cpp
//Download by http://www.NewXing.com // Hanoi.cpp: implementation of the Hanoi class. // ////////////////////////////////////////////////////////////////////// #include "Hanoi.h" #include <iostream> ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// Hanoi::Hanoi() { ThreePegs = NULL; FourPegs = NULL; nMaxDishNum = -1; } Hanoi::~Hanoi() { delete []ThreePegs; delete []FourPegs; } bool Hanoi::Init(int num) { if (num <= nMaxDishNum) { return true; } else { Number *pegs_3 = new Number[num+1]; Number *pegs_4 = new Number[num+1]; for(int i=0; i<nMaxDishNum; i++) { pegs_3[i] = ThreePegs[i]; } for(int j=0; j<nMaxDishNum; j++) { pegs_4[j] = FourPegs[j]; } delete []ThreePegs; delete []FourPegs; ThreePegs = pegs_3; FourPegs = pegs_4; nMaxDishNum = num; return true; } return false; } /************************************************************************/ /* 三柱汉诺塔问题 */ /************************************************************************/ Number & Hanoi::ThreePegsHanoi(int num) { if (!Init(num)) { exit(1); } Number times; if (num <= 0) { ThreePegs[num] = Number(0); return ThreePegs[num]; } else if (num == 1) { ThreePegs[num] = Number(1); return ThreePegs[num]; } else { if (ThreePegs[num-1].Compare(Number(0)) != 0) { ThreePegs[num] = ThreePegs[num-1]+ThreePegs[num-1]+Number(1); return ThreePegs[num]; } else { times = ThreePegsHanoi(num-1); ThreePegs[num] = times+times+Number(1); return ThreePegs[num]; } } } /************************************************************************/ /* 四柱汉诺塔问题 */ /************************************************************************/ Number & Hanoi::FourPegsHanoi(int num) { if (!Init(num)) { exit(1); } Number minTimes; Number times; Number fourPegsTimes; if (num <= 0) { FourPegs[num] = Number(0); return FourPegs[num]; } else if (num == 1) { FourPegs[num] = Number(1); return FourPegs[num]; } else if (FourPegs[num].Compare(Number(0)) != 0) { return FourPegs[num]; } else { fourPegsTimes = FourPegsHanoi(0); times = fourPegsTimes+ThreePegsHanoi(num)+fourPegsTimes; minTimes = times; for (int i=1; i<num; i++) { fourPegsTimes = FourPegsHanoi(i); times = fourPegsTimes+ThreePegsHanoi(num-i)+fourPegsTimes; minTimes = Number::MinNum(minTimes, times); } FourPegs[num] = minTimes; return FourPegs[num]; } }