自己做视频网站只能用地址连接,电脑网页视频怎么下载,SEO案例网站建设,wordpress外链go零、前言
发现自己数数题做的很烂#xff0c;重新学一遍组合数学吧。
参考卢开澄 卢华明 编著的《组合数学(第4版)》#xff0c;只打算学前四章。 通过几个经典问题来了解组合数学所研究的内容。
一、幻方问题 据说大禹治水之前#xff0c;河里冒出来一只乌龟#xff0c…零、前言
发现自己数数题做的很烂重新学一遍组合数学吧。
参考卢开澄 卢华明 编著的《组合数学(第4版)》只打算学前四章。 通过几个经典问题来了解组合数学所研究的内容。
一、幻方问题 据说大禹治水之前河里冒出来一只乌龟龟背上是一个3*3的矩阵每个格子里面有若干点行和列和对角线和都相等且为15。然后大禹就以15为周期来治水了。 对于一个nxn的矩阵满足行和列和主副对角线和都相等那么这个矩阵就是一个n阶幻方。
最早研究幻方的是南宋的杨辉杨辉三角那个他罗列了3x3、4x4、5x5甚至10x10的幻方。
定义行/列整数和为该幻方的幻和。
n 阶幻方的幻和为 (n^2 1) * n / 2
并非任意阶幻方都有解法
2阶幻方就不存在 会推出某两个元素相等但是a b c d 互不相同。
大约30年前德国数学家L · Bieberbach证明
对于任意大于等于 3 的数 n都存在一个 n 阶的幻方阵。
杨辉提出了一种三阶幻方的构造方法
123、456、789 斜着摆三列得到一个菱形交换菱形对角元素挤压成一个正方形就是一个三阶幻方
但是对于更高阶该如何构造呢
法国一位数学家研究了奇数阶幻方的一般化构造方法
记第 i 行 第 j 列 方格坐标为 (i, j)0 索引初始将 1 放在第 0 行的中间 (0, n / 2)对于 当前要放置的棋子上一枚棋子的坐标为 (x, y)我们尝试放在 ((x - 1) % n, (y 1 % n)) 如果已经被占用则放在 ((x 1) % n, y) 证明略
事实上我们可以将幻方分成三类
奇数阶幻方4m 阶幻方4m 2 阶幻方
每一类都有对应的构造算法。
然而我们发现杨辉构造的三阶幻方和奇数阶构造算法得到的幻方不同但是把幻方上下翻转就相同了。 这让我们思考对于n阶幻方有多少种构造方法
三阶幻方如果认为翻转旋转一样的话只有一种。
四阶幻方如果认为翻转旋转一样的话有880种否则有7040.
五阶已经有 2亿七千多万个了。
六阶数学家大概确定了其数量落在某个范围七阶已经无从得知了……
可见计数问题是组合数学中的一大难题。
算竞中经常遇到这样一类构造题行列乘积、gcd、异或等限制来构造矩阵这其实都是幻方的变形。
二、羊皮纸卷
阿基米德在羊皮纸上的论文流落到寺庙僧人清洗后重新抄写经文。
2003年科学家通过X光照射发现羊皮纸经文下面的阿基米德关于十四巧板的论文。 一位数学家以此为题设置100美元奖项谁先解出来给谁。
然后计算机学家借助计算机设计算法解出来是17152种后来数学家利用排列组合的方式也得到了正解。阿基米德无意间开创了西方世界的组合数学的篇章。
1666年莱布尼茨研究概率学时生造了**组合数学Combinatorics**这个单词。
三、手机密码安全吗
平时在学校基本都是翘课有一次遇到学习通4位密码签到我一看乐了整个程序暴力枚举几乎一瞬间就签上到了。
为什么这么快呢
4位密码每位10种可能也就10000种计算机基本几毫秒就能枚举完所有可能。
很多人手机都有3 * 3 的手势密码其实手势密码可以看作是从一个格子出发得到的一条路径我们怎么计数呢
正难则反总情况 - 不合法路径。
不合法的定义如果选择的两个点连成的线段穿越了第三个点如果这第三个点之前没有被连过则不合法反之则合法
通过计算机程序得到一共有 389112 种方案。
可见如果手机没有输入次数限制的话一部手机很快就能被破解。
计数问题是一类很常见的问题但是并不简单如何做到不重不漏是一个难点。
四、世界杯引出的问题
n 支球队参加比赛一共需要多少场复赛
比较笨的方法局面抽象成节点代表当前剩下的队伍集合挑出两个队伍比赛扔掉一个败者得到新的节点最后节点的数目就是总比赛场数。
但事实上每进行一场比赛都会产生一个败者一个胜者我们最后只有一个冠军所以要进行n - 1场比赛。
可见同样是计数问题不同方法的效率是天差地别的。
五、哥尼斯堡七桥问题
即欧拉路径问题欧拉图欧拉通路欧拉回路Hierholzer算法详解-CSDN博客
沿着桥走每个桥恰好走一次有多少种走法
我们能直接取排列数作为答案吗
显然不能太多非法解了。
不过我们可以借助定理 计算机枚举来求解。
通过定理我们保证枚举方案的合法性可见有技巧的枚举可以更加精巧简洁。
