作者LiquidTLO (俊伟)
看板Math
标题[其他] 离散两题
时间Thu Oct 8 16:54:59 2020
题目1:
https://imgur.com/a/bwIe3cc
不需要知道(a)(b)(c)部分
跟(d)(e)无关
(d)部分我有证出後半段
想问要如何证明前半段
Hamming distance between any two codewords
in RS[5,3] is at least 3
(e)部分没什麽想法
题目的max Hamming distance = m-n+1是typo
应该是min Hamming distance = m-n+1
题目2:
https://imgur.com/a/pJud5MX
题目里的Maru还没开始比
他赢第一场就拿1分
之後赢第i场就拿i分
(a)部分没甚麽问题
(b)部分
我的想法是把分数i∈{1,2,...,10}
看作x_1+2x_2+3x_3+...+10x_10 > 27
0 <= x_i <= 1
但是不知道怎麽解含系数!= 1的不等式
我只解过x_1+x_2+...x_n = k这种的
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.224.187.128 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1602147303.A.1B1.html
1F：→ hwanger : 让F是指定的finite field 给定u1,u2在F^3中 并令P1, 10/08 22:13
2F：→ hwanger : P2为其相对应的polynomials 则Hamming distance为 10/08 22:15
3F：→ hwanger : ((P1-P2)(a0),(P1-P2)(a1),...,(P1-P2)(a5))的非零 10/08 22:17
4F：→ hwanger : 个数 注意到(P1-P2)是一个degree小於等於2的多项式 10/08 22:18
5F：→ hwanger : 所以最多两个零根 故至少三个非零 10/08 22:20
6F：→ hwanger : 至於(e) 你的Decode(*)的定义或者所采用的演算法是 10/08 22:22
7F：→ hwanger : 啥? 因为一般的error correction code的decoding 10/08 22:24
8F：→ hwanger : function就是要满足图中的式子 并以此来找decode的 10/08 22:25
9F：→ hwanger : 算法 (一般来说 如果我们接收到错误的代码C' 我们纠 10/08 22:28
10F：→ hwanger : 正错误的方法 就是去找Hamming distance最近的 10/08 22:28
11F：→ hwanger : codeword 再以此decording) 10/08 22:29
12F：→ hwanger : 至於题目2 我目前也没有有效率的算法 不过可以用下 10/08 22:35
13F：→ hwanger : 列递回函数的方式解 令F(n,m)为"从1到n中至少取一个 10/08 22:40
14F：→ hwanger : 且其总和小於等於m"的方法数 则我们有 10/08 22:41
15F：→ hwanger : F(1,k)=1 for all k in N 10/08 22:43
16F：→ hwanger : when m>n, F(n,m)=F(n-1,m)+F(n-1,m-n)+1 10/08 22:45
17F：→ hwanger : when m=n, F(n,m)=F(n-1,m)+1 10/08 22:47
18F：→ hwanger : when m<n, F(n,m)=F(n-1,m) 10/08 22:49
19F：→ hwanger : 则所求为 1023-F(10,27) 至少可以跑程式 冏 10/08 22:50
20F：→ hwanger : 题目2的(b)根本不用上面这麽麻烦 XD 当我们从{1,2, 10/09 15:27
21F：→ hwanger : 3,...,10}中取一些数出来总和大於27时 剩下来的数总 10/09 15:28
22F：→ hwanger : 和就会小於等於27 反之亦然 也就是说我们可以在1024 10/09 15:29
23F：→ hwanger : 个子集合中两两凑对 所以总共有1024/2=512种方法数 10/09 15:30
24F：→ hwanger : 这里凑对的方式就是子集合和他的补集 10/09 15:34
25F：→ hwanger : 所以27这个数字是特别挑过的 (28是1到55的中间) 10/09 15:34
26F：→ LiquidTLO : 对，我後来看到程式结果也想到这样XD 10/09 19:33
27F：推 hwanger : XD 我也是 10/09 20:35
28F：推 hwanger : 这是个很好的警惕 先跑程式看看答案再说 XD 10/09 20:41