作者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/m.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