任意三角形 and 国际象棋
Challenge: 任意三角形
问题描述:
圆上任选三点组成三角形，这个三角形是锐角三角形的概率是多少？
锐角必定包含圆心, 问题转化为构成的三角形包含圆心的概率
做三条过圆心的直线
A随便选一个，假定选A
then B和A必须分居C所在的直线两侧，所以只能选B`，概率1/2
C必须在AB`确定的优弧上(或者说AC必须分居在B所在直线两侧)，概率1/2
所以构成三角形包含圆心的概率是 1/4
Challenge: 国际象棋
问题描述:
国际象棋棋盘有8行8列，上面的格子是黑白相间的，每个格子里要么没有棋子，要么有1个棋子.
有没有可能在棋盘上摆若干个棋子，使得每一行，每一列都有奇数个棋子，而且棋盘上黑色格子里的棋子总数也是奇数？
try(位运算):
- llu,数过于大
- 生成方法奇偶校验,不如直接打表
- 列判断的一个方法:我觉得可以8个8位异或在一起,得到的结果是255就能说明符合题意
try(伪递归and分治):
- 递归(误):其思想利用奇偶校验码生成第八行以及第八列
其复杂度由8*8降到7*7, 没有本质变化
- 分治:行的影响是横向的, 列的影响是纵向的, 分块讨论情形过于复杂
try(无损变换):
对于任意摆放, 定义满足不改变每行/每列/黑格上棋子奇偶性的变换为无损变换
易知如下三种变换皆为无损变换:
任取两行两列，考察其四个交点: 1. 若四个交点都有棋子，则同时取下四个棋子(总数-4)
2. 若其中三个交点有棋子，则取下此三个棋子，再将原空位上补一个棋子(总数-2)
3. 若其中两个交点有棋子，则取下此两个棋子，再向另两个空位上补上棋子(总数不变)
然后对问题进行进一步拆分, 得到如下四个子命题:
对于任何满足[每行每列都是奇数]的摆放:
- 棋子总数必定为偶数
- 若棋子总数为8, 则其每行每列都必定只有一个棋子
- 若棋子总数为8, 则其可以经由无损变换把棋子都放置到对角线上
- 只要棋子总数大于8, 就可以经由无损变换使总数-2, 反复执行此过程可使总数降到8
如果四个子命题同时成立, 那么但凡满足[每行每列都是奇数]的摆放方式, 都可以经无损变换化归为8个棋子皆在主对角线上的摆放, 易知此种摆放黑格子上的棋子为偶数, 所以任意满足每行每列都是奇数的摆放, 其黑色格子上的棋子数必定为偶数, 题目要求的摆放并不存在
如下是四个子命题的证明:
- 子命题1: 8个奇数相加结果为偶数
- 子命题2: 反证法, 略
- 子命题3: 这里可以写个算法了,往下找吧骚年
- 子命题4: 如果棋盘不止8个棋子，则每次只关注其中10个棋子, 必定至少有一行一列都有不少于3个棋子的, 这时一定会出现十字,八字或T字型的局部, 运用变换2(总数不变)统统变成T字型, 而后可运用变换3使总数-2, 只要总数仍大于8, 则仍然可执行此过程,使得总数最终降为8
此为十字形, 八字形略(鸣谢dalao顺手帮忙制图233333)
附: 命题三的算法
沿着主对角线向右下不断缩小棋盘:
if(子棋盘左上角未归位):
考虑子棋盘的第1行及第1列, 找到这一行一列上的棋子;
运用变换2, 子棋盘的左上角瞬间归位;
然后缩小, 处理下一个子棋盘即可;
前方高能
前方高能
前方高能
- 而你群大佬犹然笑之 -
- 记棋盘的横坐标是abcd…h, 纵坐标是123…8
- 记N(1)为第1行棋子的数量, N(a)为第a列棋子的数量等等
- N(a) + N(c) + N(e) + N(g) + N(2) + N(4) + N(6) + N(8) = 偶数.
- 其中白色格子被计算了两次, 黑色格子只计算了一次.
- 所以黑色格子的棋子数 = 偶数 - 偶数 = 偶数
大佬: 一个能打的都没有.jpg
