另类单堆拈游戏及其源代码 减治法实现

算法导论 算法作业 算法参考 减治法实现

/*
题 	  目：另类的单堆拈游戏
算法思想：减治法
思    路：	  电脑每次都让自己处于安全的状态，即电脑取完后剩下的棋子lessNumAfter，和原来
		  剩下的棋子lessNumBefore，还有最大可取的数目mostNum应满足如下关系：
				lessNumAfter = lessNumBefore % （mostNum + 1） -1。
		      当然，如果
				lessNumBefore % （mostNum + 1） = 0。
		  就让电脑取最大的可取数。
		  这样电脑就会处于安全的状态。
算法分析：易得电脑每次取数和玩家的取数的和是mostNum+1，对双方都是最优策略。
		  当然，在游戏开始初期，如果两方都是按照最优策略走的话，那么胜败已定。
		  因此可得算法的时间复杂度为O（n/（m+1））。
*/
#include
#include“fun_head.h“
using namespace std;

int main（）
{	
	bool isContinue=1;
	cout<<“游戏：另类的单堆拈游戏“<		<<“游戏规则如下：“<		<<“玩家输入总共的棋子数目，和一次最多可取走的数目（最少一个）。“<		<<“谁要是取走最后一个棋子，谁就输了！“<	while（isContinue）{
		fight（）;			//开始游戏
		cout<<“是否继续游戏（1/0）？“;
		cin>>isContinue;
		cout<	}
	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1017  2010-08-17 11:26  拈游戏.cpp

     文件       3746  2009-12-11 16:56  fun_head.h

     文件     548953  2010-01-19 19:59  拈游戏.exe

----------- ---------  ---------- -----  ----

               553716                    3