→ hwanger : (a)(b)差不多就是你的想法 10/27 22:07
→ hwanger : (a) 列出所有長度小於等於k的字串 篩出well-formed 10/27 22:08
→ hwanger : formula 找會算出n的最短字串 10/27 22:08
→ hwanger : (b) 先寫一個副程式Count(t,P) 判斷P 1.是否為一個 10/27 22:09
→ hwanger : 合法程式碼 2.如果是合法程式碼 則是否能在t步內執 10/27 22:09
→ hwanger : 行完畢 10/27 22:09
→ hwanger : 接著考慮一段直接印出n的程式碼 [例如在c中 10/27 22:10
→ hwanger : #include<stdio.h>(換行符號)int main(int argc, 10/27 22:10
→ hwanger : char** argv){printf("%d",n);return 0;}] 10/27 22:10
→ hwanger : 計算他的執行步數+符號個數 T 然後考慮所有符號個數 10/27 22:11
→ hwanger : 在T內的字串P 再用Count(T,P)篩選 找會印出n的最短 10/27 22:11
→ hwanger : 程式碼 >>>所以是可以找出"最短"的程式碼的 10/27 22:12
→ hwanger : 上面是大致的想法 你可能還是依你們上課的嚴謹程度 10/27 22:15
→ hwanger : 來完成細節 冏 10/27 22:15
→ LiquidTLO : 了解，所以\sum_{i=0}^{\infty} Count(i,P)就能篩完 10/27 23:01
→ LiquidTLO : 且保證minimum time/length 10/27 23:02
→ hwanger : 不是很清楚你想表達什麼 不過跟(a)的k一樣 我們會有 10/27 23:04
→ hwanger : 一個T的bound 10/27 23:04
→ hwanger : 另外 在(b)中 還有一種case就是允許程式一開始就接 10/27 23:06
→ LiquidTLO : 也對，因為length就是(a)的 10/27 23:06
→ hwanger : 受一個外部參數 或中途輸入(scanf之類的) 但每接受 10/27 23:07
→ hwanger : 一個字符就會耗去一次執行次數 所以可以input的字串 10/27 23:08
→ hwanger : 長度也是有一個和T有關的上限N存在 所以也可以把所 10/27 23:10
→ hwanger : 有長度N的字串放在Count的參數中考慮 Count(T,P,W) 10/27 23:12
→ hwanger : 例如W="321\r44\r" 當程式要兩次讀入數字時 他就會 10/27 23:13
→ hwanger : 先讀321 下次再讀44 而Count可以計算在某個W下 P的 10/27 23:15
→ hwanger : 執行次數 10/27 23:15
→ hwanger : 這邊表達的有點混亂 抱歉 不過因為你原本就有差不多 10/27 23:27
→ hwanger : 的想法 我想傳達應該還是有傳達到 如果不清楚再問 10/27 23:28