趣味:“四角同色矩形”不存在的行数
Autukill 发表于 2014-06-09 08:20:13 2077

本帖最后由 Autukill 于 2014-7-7 18:44 编辑

一同学问的课程设计:
[attach]574[/attach]
题目:在一个nx4的方格纸上(N为不小于2的某一个正整数),每一个方格用黑色或者白色进行涂色游戏。涂了若干行后,要求总找不到“四角同色矩形”,请问最多能涂多少行?如图蓝色部分的矩形四个角都是白色,所以不符合要求。当N= 6 时,可以得到都不会出现“四角同色矩形”的涂法;而当N >=7时,“四角同色矩形”总是存在。

这类题呢,显然都存在于《C语言趣味编程100例》等书籍中,大学老师就喜欢这些?问题稍有变动。

寻找思路:
1. 既然四角不同色,那就采取“保持间隔”原则,行与行,列与列间都保持间隔,间隔不一,但有规律。
操笔即画,寻找间隔规律,折腾了半个小时,发现行不通。

2.就在那半个小时时,我的第六感悄悄的告诉我:6(题中所说的最多6行),这不就是高中学的排列组合吗?
6 = A(2\4) 除以 A(2\2).

一大段题目变成了:有4个格子,取出2个涂黑,共多少种涂法?
[attach]575[/attach]

也就是说,每行涂黑2个是最优的,N=6的时候,也就是最大行数。再往下(7及其以上),将重复叠加单行涂法(仅6种)。
最新回复 (4)
  • 啊擦喵 发表于 2014-06-22 02:06:51
    0 1
    = =那直接打表把几个状态存下来就行了嘛..
  • Autukill 发表于 2014-06-22 05:50:15
    0 2
    Quote啊擦喵 发表于 2014-6-22 02:06
    = =那直接打表把几个状态存下来就行了嘛..


    天天夜猫子呀
  • Autukill 发表于 2014-06-22 05:49:29
    0 3
    嗯,很直接的输出。

    在一行中,涂黑两个,对没涂黑的2个是平衡的。

    而只要出现1次涂黑1个或者涂黑3个的情况,这行就不平衡,或者说黑白不均,结果不优