1、现有一个8*8的方格,要从左下角完成不重不漏的遍历,要求每一步只能向右、上或者左下这三种走法.问是否能够完成此遍历?
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/10/06 13:02:55
1、现有一个8*8的方格,要从左下角完成不重不漏的遍历,要求每一步只能向右、上或者左下这三种走法.问是否能够完成此遍历?
2、现有一个8*8的方格,要求把1到64这些数字一一填入其中,使得其中每一个T字样的四格里的数字之和是5的倍数.问是否能够完成此遍历?
以上两问题,均请给出染色方案和分析过程,
2、现有一个8*8的方格,要求把1到64这些数字一一填入其中,使得其中每一个T字样的四格里的数字之和是5的倍数.问是否能够完成此遍历?
以上两问题,均请给出染色方案和分析过程,
楼上的答案值得商榷.至少我没有看懂他在说什么.
这应该算是五年级的奥数里较难的题了.记得当初小学时,染色问题一直比较弱.现在依然如此,以至于这两题花了我较长的时间.
1、首先,说思路.既然题目已经告诉你要染色了,那其实就限制了思考范围,从而降低了难度.题目中最关键的是你要看见“往右”或“往上”本质是一样的,非常对称.但是“往左下”就不一样了.为什么这么说?因为考虑一下最普通的黑白相隔的染色方案,“往右”或“往上”都能保证每走一步会经过不同颜色的方格,但是“往左下”则保证每走这样一步都会经过相同颜色的方格.所以,他们是不同的.所以,从直觉上判断这里应该是本题的关键所在.
那么,怎么利用这一性质呢?其实问题没有那么复杂,所以不需要考虑太多的方法(我一开始就因为在几种不同的方案上徘徊导致了浪费时间)而只要直接考虑最普通的方案,即找一染色方案保证每走一步(不论是往右或往上或往左下)都会经过不同颜色的方格.
这样,目标其实很清楚了.我们需要三色去染这8*8的方格.如图.至于如何得到此图的染色过程其实不难,只要考虑对角线必须保证不同的颜色,然后又需要三色,这样依次“蓝黑白”地去染每条对角线,然后对于不同的对角线只需要保证相邻的对角线的染色正好错开了一格即可.
染色完成后,数一下.蓝色共22格,黑白各21格,出发点在黑格上.由于蓝色的比黑白两色的多出了1格,这就使我们联想到如果从左上角出发是否能完成遍历?稍作努力便容易知道,这的确可能.如图.这样就更明确了我们的方向,即玄机肯定在这蓝色比黑白两色多出1格的这特点上.
然后,就有这样的思考.出发点不算我们要经过63格,既然每步都会经过不同颜色的方格,而且从左上角的蓝色格出发正好经过了蓝黑白三色各21格(出发点的蓝色不算)正好能够走完,但是从左下角的黑色格出发会经过蓝22格,黑20格,白21格,而且是走不完的.那么这时自然地我们就会考虑如果能够保证“每三步”(任意的)正好经过了蓝黑白三色,那么的确从左下角出发是到达不了的,因为如果能保证“每三步”都经过了蓝黑白三色,那总共的63步就会保证经过蓝黑白三色各21次,但是显然从右下角出发经过的蓝黑数不同.矛盾.另一方面,从左上角的确保证了经过蓝黑白各21次,而且也的确能遍历.
所以,我们就想到是否能够保证“每三步”(任意的)正好经过了蓝黑白三色(顺序不一定)呢?答案是肯定的.原因从图上观察便知.要到达每一黑色格子唯一的方法是通过一白色的格子,而要到达任何的白色的格子只有通过蓝色的格子,而要到达蓝色的格子只有通过黑色的格子,这样循环.所以任何的三步都经过正好三色.从而63步经过三色各21次.与要经过蓝22格,黑20格,白21格矛盾,所以无法遍历.
这应该算是五年级的奥数里较难的题了.记得当初小学时,染色问题一直比较弱.现在依然如此,以至于这两题花了我较长的时间.
1、首先,说思路.既然题目已经告诉你要染色了,那其实就限制了思考范围,从而降低了难度.题目中最关键的是你要看见“往右”或“往上”本质是一样的,非常对称.但是“往左下”就不一样了.为什么这么说?因为考虑一下最普通的黑白相隔的染色方案,“往右”或“往上”都能保证每走一步会经过不同颜色的方格,但是“往左下”则保证每走这样一步都会经过相同颜色的方格.所以,他们是不同的.所以,从直觉上判断这里应该是本题的关键所在.
那么,怎么利用这一性质呢?其实问题没有那么复杂,所以不需要考虑太多的方法(我一开始就因为在几种不同的方案上徘徊导致了浪费时间)而只要直接考虑最普通的方案,即找一染色方案保证每走一步(不论是往右或往上或往左下)都会经过不同颜色的方格.
这样,目标其实很清楚了.我们需要三色去染这8*8的方格.如图.至于如何得到此图的染色过程其实不难,只要考虑对角线必须保证不同的颜色,然后又需要三色,这样依次“蓝黑白”地去染每条对角线,然后对于不同的对角线只需要保证相邻的对角线的染色正好错开了一格即可.
染色完成后,数一下.蓝色共22格,黑白各21格,出发点在黑格上.由于蓝色的比黑白两色的多出了1格,这就使我们联想到如果从左上角出发是否能完成遍历?稍作努力便容易知道,这的确可能.如图.这样就更明确了我们的方向,即玄机肯定在这蓝色比黑白两色多出1格的这特点上.
然后,就有这样的思考.出发点不算我们要经过63格,既然每步都会经过不同颜色的方格,而且从左上角的蓝色格出发正好经过了蓝黑白三色各21格(出发点的蓝色不算)正好能够走完,但是从左下角的黑色格出发会经过蓝22格,黑20格,白21格,而且是走不完的.那么这时自然地我们就会考虑如果能够保证“每三步”(任意的)正好经过了蓝黑白三色,那么的确从左下角出发是到达不了的,因为如果能保证“每三步”都经过了蓝黑白三色,那总共的63步就会保证经过蓝黑白三色各21次,但是显然从右下角出发经过的蓝黑数不同.矛盾.另一方面,从左上角的确保证了经过蓝黑白各21次,而且也的确能遍历.
所以,我们就想到是否能够保证“每三步”(任意的)正好经过了蓝黑白三色(顺序不一定)呢?答案是肯定的.原因从图上观察便知.要到达每一黑色格子唯一的方法是通过一白色的格子,而要到达任何的白色的格子只有通过蓝色的格子,而要到达蓝色的格子只有通过黑色的格子,这样循环.所以任何的三步都经过正好三色.从而63步经过三色各21次.与要经过蓝22格,黑20格,白21格矛盾,所以无法遍历.
用c++编程:马步遍历问题:已知国际象棋棋盘有8×8共64个格子.设计一个程序,使棋子从某位置开始跳马,能够把棋盘上的格
A点有一个卒,需要走到目标B点.行走规则:可以向下(共4步)或者向右(共8步).要求计算从A能够到达B的路径的条数,并输
已知二叉树的先根遍历和中序遍历,求后序遍历的算法?
已知一个有向图如图,请分别写出从顶点a出发进行深度优先遍历和广度优先遍历所得到的顶点序列及生成树.
把8×8的均匀方格剪去左下角和右上角的两个方格,留下62个方格,现从这62个方格剪取1×2方格的长方形,问最多能得到多少
已知二叉树的后序遍历序列和中序遍历序列,怎样求其前序遍历序列!
已知二叉树后序遍历序列是DABEC 中序遍历列是 DEBAC ,它的前序遍历序列是:
已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是什么?
pascal编程,有关图的遍历
已知二叉树的前序和后序遍历,怎么求中序遍历啊?
tsp是什么啊?用TSP算法来遍历图的时候,遍历形成了一个环,没有遍历到所有节点,如何改进,还是这种算法本身就有缺陷啊,
32.对给定的数列R={7,16,4,8,20,9,6,18,5},构造一棵二叉排序树,并且 (1)给出按中序遍历得到