第一百零八章 怎么解
“n皇后问题，其实还是比较简单的。”张栋梁慢慢说道。
听到这话，在座的部分高中生受到了暴击。
“先说说约束条件。”
众人心道果然。
“第一：大家没有键盘，也没有编译器，需要用纸和笔，30分钟之内写好代码给我，超时弃权。编程语言要求为c/c++/java，这需要考察各位对编程语言基本的理解。”
“第二：这里没有最短运行时间，也不限你们的内存使用量，你们可以用任意方法。但是，方法最优，资源使用最少者胜，这个我来判定。”
“第三：胜者需要你们队伍中选出最多两人来讲解你们的方法和思路，讲不出视为失败。那我就省下一本书了。”
“第四：你们只有一次提交机会，大家熟悉的coi赛制，可以有微小错误，但是不能有逻辑错误，关键逻辑写注释，字迹必须清晰。”
“第四：你们第一堂课需要请假了。”说到这里，张栋梁笑了起来。
“那么，开始！”
话音刚落，他手机上的计时器再次从零开始，飞快转动起来。
而底下的学生们愣了几秒钟之后开始讨论，一时间教室里很是热闹。
“一定是故意的，出这种难度的题……”
“我郁闷啊，我做过八皇后，但是用的是递归，而且30分钟太少了。”一位高一的学生郁闷地说道。
“我用键盘写出来都得十分钟多，别说手写了，我还没怎么用手写过代码呢。”
“这个题谁会去深钻啊，做出来没问题，但是30分钟现想的话有难度了，而且要作出最优的解法更有难度了。”一位高二的学生抓耳挠腮地说道。
“关键是，写出来后，并不知道其他人的解法，所以一定会反复优化自己的解法，这样没有一个目标，很难，非常难。”高三的四大天王相对冷静得多。
“只能先用最快的方法解出，然后再快速优化，排除递归。”一位数竞国一且noip省一的高三学长沉思起来。
众人的好胜心被激发了出来，这种比赛并没有分值，只有胜者。所以，每个人不知道其他人方法的情况下，只能尽力把自己的方法写的更好，更巧妙，降低各项复杂度。这样，获胜的概率才更高。
压力笼罩在每一个人的头顶，毕竟，如果时间足够，只是写出这个算法，在场除开某小白团的成员外几乎所有人都能熬出来。
但是，如果时间缩短到30分钟，估计最多能有一半队伍能写出来就不错了，这是在可以多次修改和编译的情况下。如果是用纸和笔进行白板编程……这个数字就变得很不明朗了。
孟响呆呆的听着张老师宣布完规则，然后看着其他人讨论起来，他转头看向妹妹。
“什么是n皇后？”
孟梦：“……”
看着孟梦呆滞的表情，孟响心里有些平衡了，笑着说道：“原来萌萌你也不知道呀。”
“哼！”孟梦听到哥哥的话非常生气，傲然道：“我当然知道，我刚刚只是被哥哥你的笨给惊到了而已。”
孟响对妹妹投向怀疑的眼神，不屑地说道：“你这丫头，才学计算机几天，连代码都不会写，知道个屁，别吹牛，哥哥又不会笑你。”
刚刚说完，他就感觉腰子一疼。
“嘶……”
“我知道不知道！”孟梦眯起眼睛，手微微用力，威胁道。
孟响冷吸一口气连忙讨饶：“知道知道，梦神千秋万代，一统长星。”
孟梦听到后，非常满意的松了手，又心疼地帮哥哥轻轻揉了揉腰间的软肉。
“那你说说这个玩意儿是啥。”孟响一边享受痛苦后的快乐，，一边把纸和笔摆在了妹妹面前。
孟梦收回了手，拿起哥哥递来的中性笔，一边画图一边说道：“其实，这并不仅仅是一个计算机问题，这是一个数学问题。”
孟响点了点头，收起了开玩笑的表情，示意妹妹继续。
“我很早之前就有看过这类问题，那会儿特地好好琢磨了一下这些问题。”说完，孟梦在纸上花了几个格子，然后问道：“哥哥你知道八皇后嘛？”
孟响用力点了点头，他当然听过。
“那你知道这个题的规则吗？”孟梦再次问道。
“.…..”孟响同学用力摇了摇头，他没玩过国际象棋，而且只是听过这个名词而已。
见哥哥摇头，孟梦露出了胜利般的笑容，孟响甚至能看到妹妹牙齿上的小窟窿。
“我先给哥哥解释一下八皇后吧，八皇后就是在一个8*8的棋盘上，你摆上8个棋子，让他们任意两个棋子不能处在同一行，同一列，或者同一斜线上，就是一种成功的摆法，我们说的八皇后问题，就是要求出，一共有多少种这样的摆法。”
孟响脑中开始开始遍历……
十秒钟之后。
“妈卖批，我核心不够！我要加核。”孟响遍历了不到十种之后，就放弃了这种愚蠢的方法。他对妹妹点了点头问道：“那一共有多少种？”
孟梦稍稍思考了一两秒钟说道：“我记得八皇后问题的解是92种。”
孟响：“.…..”
这要是个求答案的题目该多好呀。
“那，没法用笔算出来嘛？”孟响小心翼翼地问道。
果然，妹妹投来了鄙视的眼神，又好气又好笑地把笔往孟响手里一塞：“给你笔，你算！”
孟响：“.…..”
“当年高斯也就算出76种，而且不知道花了多少时间，这个30分钟我们算什么？而且，这是n皇后问题，要是9皇后呢，10皇后呢，更多的皇后呢？”
孟响听后内牛满面，这次，他活生生被鄙视的体无完肤！
“那我们要怎么办……你会写代码吗？那只能靠你了，萌萌千秋万代，一统长星。”孟响俨然成了一个跟班小人物。
“还没来得及学呢。”孟梦听后翻了个白眼，她这段时间就看了看算法和数据结构的书，数学底子很强的她看起来丝毫不费力，至于代码……她只会伪代码。
“那，你先给我说说这个题要怎么做吧，免得待会儿听都听不懂。”孟响想了想说道，然后又把笔塞给了妹妹。他们反正是来观光的，做不做出来也无所谓了。
孟梦接过笔，微微嘟了一下嘴之后才细细地说道：“这个问题，可以使用多种方法来解，我了解的有递归，枚举法，还有就是回溯法。”
“我觉得，这个的最优解法应该是怎么利用好回溯法。”
你是小天才，你数学好，当然什么都听你的咯。
孟响腹诽道。
听到这话，在座的部分高中生受到了暴击。
“先说说约束条件。”
众人心道果然。
“第一：大家没有键盘，也没有编译器，需要用纸和笔，30分钟之内写好代码给我，超时弃权。编程语言要求为c/c++/java，这需要考察各位对编程语言基本的理解。”
“第二：这里没有最短运行时间，也不限你们的内存使用量，你们可以用任意方法。但是，方法最优，资源使用最少者胜，这个我来判定。”
“第三：胜者需要你们队伍中选出最多两人来讲解你们的方法和思路，讲不出视为失败。那我就省下一本书了。”
“第四：你们只有一次提交机会，大家熟悉的coi赛制，可以有微小错误，但是不能有逻辑错误，关键逻辑写注释，字迹必须清晰。”
“第四：你们第一堂课需要请假了。”说到这里，张栋梁笑了起来。
“那么，开始！”
话音刚落，他手机上的计时器再次从零开始，飞快转动起来。
而底下的学生们愣了几秒钟之后开始讨论，一时间教室里很是热闹。
“一定是故意的，出这种难度的题……”
“我郁闷啊，我做过八皇后，但是用的是递归，而且30分钟太少了。”一位高一的学生郁闷地说道。
“我用键盘写出来都得十分钟多，别说手写了，我还没怎么用手写过代码呢。”
“这个题谁会去深钻啊，做出来没问题，但是30分钟现想的话有难度了，而且要作出最优的解法更有难度了。”一位高二的学生抓耳挠腮地说道。
“关键是，写出来后，并不知道其他人的解法，所以一定会反复优化自己的解法，这样没有一个目标，很难，非常难。”高三的四大天王相对冷静得多。
“只能先用最快的方法解出，然后再快速优化，排除递归。”一位数竞国一且noip省一的高三学长沉思起来。
众人的好胜心被激发了出来，这种比赛并没有分值，只有胜者。所以，每个人不知道其他人方法的情况下，只能尽力把自己的方法写的更好，更巧妙，降低各项复杂度。这样，获胜的概率才更高。
压力笼罩在每一个人的头顶，毕竟，如果时间足够，只是写出这个算法，在场除开某小白团的成员外几乎所有人都能熬出来。
但是，如果时间缩短到30分钟，估计最多能有一半队伍能写出来就不错了，这是在可以多次修改和编译的情况下。如果是用纸和笔进行白板编程……这个数字就变得很不明朗了。
孟响呆呆的听着张老师宣布完规则，然后看着其他人讨论起来，他转头看向妹妹。
“什么是n皇后？”
孟梦：“……”
看着孟梦呆滞的表情，孟响心里有些平衡了，笑着说道：“原来萌萌你也不知道呀。”
“哼！”孟梦听到哥哥的话非常生气，傲然道：“我当然知道，我刚刚只是被哥哥你的笨给惊到了而已。”
孟响对妹妹投向怀疑的眼神，不屑地说道：“你这丫头，才学计算机几天，连代码都不会写，知道个屁，别吹牛，哥哥又不会笑你。”
刚刚说完，他就感觉腰子一疼。
“嘶……”
“我知道不知道！”孟梦眯起眼睛，手微微用力，威胁道。
孟响冷吸一口气连忙讨饶：“知道知道，梦神千秋万代，一统长星。”
孟梦听到后，非常满意的松了手，又心疼地帮哥哥轻轻揉了揉腰间的软肉。
“那你说说这个玩意儿是啥。”孟响一边享受痛苦后的快乐，，一边把纸和笔摆在了妹妹面前。
孟梦收回了手，拿起哥哥递来的中性笔，一边画图一边说道：“其实，这并不仅仅是一个计算机问题，这是一个数学问题。”
孟响点了点头，收起了开玩笑的表情，示意妹妹继续。
“我很早之前就有看过这类问题，那会儿特地好好琢磨了一下这些问题。”说完，孟梦在纸上花了几个格子，然后问道：“哥哥你知道八皇后嘛？”
孟响用力点了点头，他当然听过。
“那你知道这个题的规则吗？”孟梦再次问道。
“.…..”孟响同学用力摇了摇头，他没玩过国际象棋，而且只是听过这个名词而已。
见哥哥摇头，孟梦露出了胜利般的笑容，孟响甚至能看到妹妹牙齿上的小窟窿。
“我先给哥哥解释一下八皇后吧，八皇后就是在一个8*8的棋盘上，你摆上8个棋子，让他们任意两个棋子不能处在同一行，同一列，或者同一斜线上，就是一种成功的摆法，我们说的八皇后问题，就是要求出，一共有多少种这样的摆法。”
孟响脑中开始开始遍历……
十秒钟之后。
“妈卖批，我核心不够！我要加核。”孟响遍历了不到十种之后，就放弃了这种愚蠢的方法。他对妹妹点了点头问道：“那一共有多少种？”
孟梦稍稍思考了一两秒钟说道：“我记得八皇后问题的解是92种。”
孟响：“.…..”
这要是个求答案的题目该多好呀。
“那，没法用笔算出来嘛？”孟响小心翼翼地问道。
果然，妹妹投来了鄙视的眼神，又好气又好笑地把笔往孟响手里一塞：“给你笔，你算！”
孟响：“.…..”
“当年高斯也就算出76种，而且不知道花了多少时间，这个30分钟我们算什么？而且，这是n皇后问题，要是9皇后呢，10皇后呢，更多的皇后呢？”
孟响听后内牛满面，这次，他活生生被鄙视的体无完肤！
“那我们要怎么办……你会写代码吗？那只能靠你了，萌萌千秋万代，一统长星。”孟响俨然成了一个跟班小人物。
“还没来得及学呢。”孟梦听后翻了个白眼，她这段时间就看了看算法和数据结构的书，数学底子很强的她看起来丝毫不费力，至于代码……她只会伪代码。
“那，你先给我说说这个题要怎么做吧，免得待会儿听都听不懂。”孟响想了想说道，然后又把笔塞给了妹妹。他们反正是来观光的，做不做出来也无所谓了。
孟梦接过笔，微微嘟了一下嘴之后才细细地说道：“这个问题，可以使用多种方法来解，我了解的有递归，枚举法，还有就是回溯法。”
“我觉得，这个的最优解法应该是怎么利用好回溯法。”
你是小天才，你数学好，当然什么都听你的咯。
孟响腹诽道。