[其他] 離散一題

看板Math作者 (俊偉)時間3年前 (2020/10/27 17:55), 編輯推噓0(0推 0噓 29→)
留言29則, 2人參與, 3年前最新討論串11/15 (看更多)
題目: 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://www.ptt.cc/bbs/Math/M.1603792548.A.D7B.html
→
10/27 22:07, 3年前 , 1F
(a)(b)差不多就是你的想法
10/27 22:07, 1F
→
10/27 22:08, 3年前 , 2F
(a) 列出所有長度小於等於k的字串 篩出well-formed
10/27 22:08, 2F
→
10/27 22:08, 3年前 , 3F
formula 找會算出n的最短字串
10/27 22:08, 3F
→
10/27 22:09, 3年前 , 4F
(b) 先寫一個副程式Count(t,P) 判斷P 1.是否為一個
10/27 22:09, 4F
→
10/27 22:09, 3年前 , 5F
合法程式碼 2.如果是合法程式碼 則是否能在t步內執
10/27 22:09, 5F
→
10/27 22:09, 3年前 , 6F
行完畢
10/27 22:09, 6F
→
10/27 22:10, 3年前 , 7F
接著考慮一段直接印出n的程式碼 [例如在c中
10/27 22:10, 7F
→
10/27 22:10, 3年前 , 8F
#include<stdio.h>(換行符號)int main(int argc,
10/27 22:10, 8F
→
10/27 22:10, 3年前 , 9F
char** argv){printf("%d",n);return 0;}]
10/27 22:10, 9F
→
10/27 22:11, 3年前 , 10F
計算他的執行步數+符號個數 T 然後考慮所有符號個數
10/27 22:11, 10F
→
10/27 22:11, 3年前 , 11F
在T內的字串P 再用Count(T,P)篩選 找會印出n的最短
10/27 22:11, 11F
→
10/27 22:12, 3年前 , 12F
程式碼 >>>所以是可以找出"最短"的程式碼的
10/27 22:12, 12F
→
10/27 22:15, 3年前 , 13F
上面是大致的想法 你可能還是依你們上課的嚴謹程度
10/27 22:15, 13F
→
10/27 22:15, 3年前 , 14F
來完成細節 冏
10/27 22:15, 14F
→
10/27 23:01, 3年前 , 15F
了解，所以\sum_{i=0}^{\infty} Count(i,P)就能篩完
10/27 23:01, 15F
→
10/27 23:02, 3年前 , 16F
且保證minimum time/length
10/27 23:02, 16F
→
10/27 23:04, 3年前 , 17F
不是很清楚你想表達什麼 不過跟(a)的k一樣 我們會有
10/27 23:04, 17F
→
10/27 23:04, 3年前 , 18F
一個T的bound
10/27 23:04, 18F
→
10/27 23:06, 3年前 , 19F
另外 在(b)中 還有一種case就是允許程式一開始就接
10/27 23:06, 19F
→
10/27 23:06, 3年前 , 20F
也對，因為length就是(a)的
10/27 23:06, 20F
→
10/27 23:07, 3年前 , 21F
受一個外部參數 或中途輸入(scanf之類的) 但每接受
10/27 23:07, 21F
→
10/27 23:08, 3年前 , 22F
一個字符就會耗去一次執行次數 所以可以input的字串
10/27 23:08, 22F
→
10/27 23:10, 3年前 , 23F
長度也是有一個和T有關的上限N存在 所以也可以把所
10/27 23:10, 23F
→
10/27 23:12, 3年前 , 24F
有長度N的字串放在Count的參數中考慮 Count(T,P,W)
10/27 23:12, 24F
→
10/27 23:13, 3年前 , 25F
例如W="321\r44\r" 當程式要兩次讀入數字時 他就會
10/27 23:13, 25F
→
10/27 23:15, 3年前 , 26F
先讀321 下次再讀44 而Count可以計算在某個W下 P的
10/27 23:15, 26F
→
10/27 23:15, 3年前 , 27F
執行次數
10/27 23:15, 27F
→
10/27 23:27, 3年前 , 28F
這邊表達的有點混亂 抱歉 不過因為你原本就有差不多
10/27 23:27, 28F
→
10/27 23:28, 3年前 , 29F
的想法 我想傳達應該還是有傳達到 如果不清楚再問
10/27 23:28, 29F
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1Vb-warx (Math)
討論串 (同標題文章)
完整討論串 (本文為第 11 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1Vb-warx (Math)