作者LiquidTLO (俊伟)
看板Math
标题[其他] 离散一题
时间Tue Oct 27 17:55:45 2020
题目:
https://imgur.com/a/oCMXgxw
不知道想法对不对
(a)
Since if n has k digits, then the shortest-length formula must be <= k.
-> shortest-length formula must be finite
It's possible to enumerate the set of possible arithmetic formulas for n,
with condition len(each formula) <= k
-> the set is finite
-> We can find the shortest-length formula in that set for a given n.
-> It's possible to write a program to find the shortest formula for any n.
(b)
先说hint部分
我不太知道要如何判断
a program halts on given input -> halting problem -> unsolvable
多了within t steps
我应该可以用个counter去数有没有超过t
所以应该做得出来
还有如果a program does not halt within t steps
execution time就找不到minimum吧
那整个program cannot be done
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.224.180.237 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1603792548.A.D7B.html
1F：→ hwanger : (a)(b)差不多就是你的想法 10/27 22:07
2F：→ hwanger : (a) 列出所有长度小於等於k的字串 筛出well-formed 10/27 22:08
3F：→ hwanger : formula 找会算出n的最短字串 10/27 22:08
4F：→ hwanger : (b) 先写一个副程式Count(t,P) 判断P 1.是否为一个 10/27 22:09
5F：→ hwanger : 合法程式码 2.如果是合法程式码 则是否能在t步内执 10/27 22:09
6F：→ hwanger : 行完毕 10/27 22:09
7F：→ hwanger : 接着考虑一段直接印出n的程式码 [例如在c中 10/27 22:10
8F：→ hwanger : #include<stdio.h>(换行符号)int main(int argc, 10/27 22:10
9F：→ hwanger : char** argv){printf("%d",n);return 0;}] 10/27 22:10
10F：→ hwanger : 计算他的执行步数+符号个数 T 然後考虑所有符号个数 10/27 22:11
11F：→ hwanger : 在T内的字串P 再用Count(T,P)筛选 找会印出n的最短 10/27 22:11
12F：→ hwanger : 程式码 >>>所以是可以找出"最短"的程式码的 10/27 22:12
13F：→ hwanger : 上面是大致的想法 你可能还是依你们上课的严谨程度 10/27 22:15
14F：→ hwanger : 来完成细节 冏 10/27 22:15
15F：→ LiquidTLO : 了解，所以\sum_{i=0}^{\infty} Count(i,P)就能筛完 10/27 23:01
16F：→ LiquidTLO : 且保证minimum time/length 10/27 23:02
17F：→ hwanger : 不是很清楚你想表达什麽 不过跟(a)的k一样 我们会有 10/27 23:04
18F：→ hwanger : 一个T的bound 10/27 23:04
19F：→ hwanger : 另外 在(b)中 还有一种case就是允许程式一开始就接 10/27 23:06
20F：→ LiquidTLO : 也对，因为length就是(a)的 10/27 23:06
21F：→ hwanger : 受一个外部参数 或中途输入(scanf之类的) 但每接受 10/27 23:07
22F：→ hwanger : 一个字符就会耗去一次执行次数 所以可以input的字串 10/27 23:08
23F：→ hwanger : 长度也是有一个和T有关的上限N存在 所以也可以把所 10/27 23:10
24F：→ hwanger : 有长度N的字串放在Count的参数中考虑 Count(T,P,W) 10/27 23:12
25F：→ hwanger : 例如W="321\r44\r" 当程式要两次读入数字时 他就会 10/27 23:13
26F：→ hwanger : 先读321 下次再读44 而Count可以计算在某个W下 P的 10/27 23:15
27F：→ hwanger : 执行次数 10/27 23:15
28F：→ hwanger : 这边表达的有点混乱 抱歉 不过因为你原本就有差不多 10/27 23:27
29F：→ hwanger : 的想法 我想传达应该还是有传达到 如果不清楚再问 10/27 23:28