新手求问一道简单算法题！

两个足够聪明的人玩轮流取石头的游戏，谁取到最后一个谁就赢了，他们一次只能取1个、3个、7个或8个石头，写程序判断n个石头时先取的人是输还是赢（按如下输出）。 用c++写

15 个解决方案

#1

#2

搜“倒推法”？

#3

引用 2 楼 zhao4zhong1 的回复:

搜“倒推法”？

能写个程序让我参考一下吗？

#4

https://www.baidu.com/s?wd=取石子游戏%20倒推法

#5

#include <string>
#include <iostream>

class Game {
public:
    void setAmounts();
	int getAmounts();
	static std::string runGame(Game &);
private:
	int amounts;
};

void Game::setAmounts() {
	std::cout << "Please set the amounts of stones:" << std::endl;
	int amount;
	std::cin >> amount;
	this->amounts = amount;
}

void Game::setAmounts() {
	std::cout << "Please set the amounts of stones:" << std::endl;
	int amount;
	std::cin >> amount;
	this->amounts = amount;
}

int Game::getAmounts() {
	return amounts;
}

std::string Game::runGame(Game &game){
	game.setAmounts();
	int amounts = game.getAmounts();
	if (amounts >= 14) {
		float temp = float((amounts - 13) % 15) / 2;
		if (temp == 1 || temp == 2 || temp == 3 || temp == 4) {
			return "Defeat";
		}
		else
			return "Win";
	}
	else {
		float temp = float(amounts) / 2;
		if (temp == 1 || temp == 2 || temp == 3) {
			return "Defeat";
		}
		else
			return "Win";
	}

}

int main() {
	Game game;
	std::string results = Game::runGame(game);
	std::cout << results << std::endl;
	return 0;
}

#6

没想到什么好的算法  楼主将就着看吧

#7

引用 6楼freshman_cy 的回复:

没想到什么好的算法  楼主将就着看吧

万分感谢！不过能麻烦您稍微给我讲下嘛？
我在算法这方面是真新手呀……

#8

好像mod 15循环啊，mod15=0,2,4,6必败态吧

#9

引用 7 楼 Bayernherz 的回复:

Quote: 引用 6楼freshman_cy 的回复:

没想到什么好的算法  楼主将就着看吧

万分感谢！不过能麻烦您稍微给我讲下嘛？
我在算法这方面是真新手呀……

石头总数超过13之后,是一个mod 15的循环,余数为2,4,6,8必败,其他都必赢,至于少于13个的情况,余数为2,4,6必败;应该有
通用算法,楼主可以继续研究下

#10

引用 8楼FancyMouse 的回复:

好像mod 15循环啊，mod15=0,2,4,6必败态吧

谢谢朋友！

#11

引用 9楼freshman_cy 的回复:

Quote: 引用 7 楼 Bayernherz 的回复:

Quote: 引用 6楼freshman_cy 的回复:

没想到什么好的算法  楼主将就着看吧

万分感谢！不过能麻烦您稍微给我讲下嘛？
我在算法这方面是真新手呀……

石头总数超过13之后,是一个mod 15的循环,余数为2,4,6,8必败,其他都必赢,至于少于13个的情况,余数为2,4,6必败;应该有
通用算法,楼主可以继续研究下

嗯嗯 明白了 我再好好研究下 万分感谢

#12

我只是在想，穷举法怎么弄。。。

#13

引用 2 楼 zhao4zhong1 的回复:

搜“倒推法”？

你看懂了没？？什么叫只能一次取1个 7个和8个？？

#14

参考4楼，4楼正解！

#15

引用 12楼欧阳春晖 的回复:

我只是在想，穷举法怎么弄。。。

石头总数太大了 穷举法适用吗