[理工] 100台大電機丙 第一題(已解決)

看板Grad-ProbAsk作者 (你逆)時間9年前 (2017/01/13 11:02), 9年前編輯推噓4(4推 0噓 24→)
留言28則, 4人參與, 最新討論串1/1
大家好想要請教一下，爬文答案是E http://i.imgur.com/g42qaAZ.png
http://i.imgur.com/gA4c9Eo.png
http://i.imgur.com/hU4Oo7D.png
'********************* '剛剛發現漏貼一張sorry '********************* http://i.imgur.com/CJCEOHC.png
http://i.imgur.com/svnagSd.png
不知道為啥我跑完一次之後變成n!，想問大家我是不是哪裡漏了沒考慮到? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.236.38.21 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484276538.A.E9E.html
推
01/13 11:53, , 1F
你每個K後面寫的是那個loop的還是加總的呢？
01/13 11:53, 1F
回cshcsh6847 K後面那個是第一次進去for的i
推
01/13 11:55, , 2F
我認為你漏掉swap的time complexity了？
01/13 11:55, 2F
→
01/13 11:56, , 3F
我算了兩個版本，一個是有包含swap的，一個沒有
01/13 11:56, 3F
→
01/13 11:57, , 4F
我發現不包含swap的那個跟你一樣
01/13 11:57, 4F
→
01/13 11:58, , 5F
包含swap：T(n)=(n-1)[T(n-1)+1], T(n)=O(n*n!)
01/13 11:58, 5F
→
01/13 11:59, , 6F
不包含swap:T(n)=(n-1)T(n-1)，T(n)=n!
01/13 11:59, 6F
→
01/13 11:59, , 7F
以上兩個的T(1)=n
01/13 11:59, 7F
→
01/13 12:00, , 8F
但我其實也沒很肯定到底要不要包含swap，不過這兩種版
01/13 12:00, 8F
→
01/13 12:00, , 9F
本硬要在選項選的話，似乎(E)選項都是最近的？
01/13 12:00, 9F
→
01/13 12:04, , 10F
我看你的推導過程感覺不出什麼問題就是了
01/13 12:04, 10F
→
01/13 12:05, , 11F
補充說明一下，我這邊的n其實不是題目給的n，應該是
01/13 12:05, 11F
→
01/13 12:06, , 12F
n-k才對，就是他們兩個的差值，我重寫好了
01/13 12:06, 12F
→
01/13 12:06, , 13F
令x=n-k
01/13 12:06, 13F
→
01/13 12:07, , 14F
包含swap:T(x)=(x-1)[T(x-1)+1], T(1)=n, T(n)=n*n!
01/13 12:07, 14F
→
01/13 12:08, , 15F
不包含swap:T(x)=(x-1)T(x-1), T(1)=n, T(n)=n!
01/13 12:08, 15F
→
01/13 12:08, , 16F
阿阿上面應該都要用big-Oh包起來才對
01/13 12:08, 16F
推
01/13 14:21, , 17F
印出所有的排列組合,有n!種,每一種都要印出來花n,所以O
01/13 14:21, 17F
→
01/13 14:21, , 18F
(n!*n)
01/13 14:21, 18F
推
01/13 14:33, , 19F
我沒仔細看,可能沒考慮到印一次花O(n)吧
01/13 14:33, 19F
→
01/13 15:16, , 20F
感謝大家回覆我先看一下@@
01/13 15:16, 20F
※ 編輯: angel861047 (36.236.38.21), 01/13/2017 15:31:58
→
01/13 16:23, , 21F
我找到原因了，其實這個程式根本是錯的，他沒辦法輸出
01/13 16:23, 21F
→
01/13 16:24, , 22F
所有的permutation
01/13 16:24, 22F
→
01/13 16:25, , 23F
else的那個for迴圈要用for (i=k;i<n;i++)才會正確輸出
01/13 16:25, 23F
→
01/13 16:25, , 24F
所有permutation，他這樣寫只會輸出(n-1)!個字串
01/13 16:25, 24F
→
01/13 16:26, , 25F
所以每個char算O(1)的話，的確是原po那樣導的沒錯
01/13 16:26, 25F
→
01/13 16:27, , 26F
但是直覺來說我覺得k大的解釋最好，因為考試根本無法
01/13 16:27, 26F
→
01/13 16:27, , 27F
驗證到這麼細，就是在考k大說的觀念而已
01/13 16:27, 27F
→
01/13 17:56, , 28F
http://imgur.com/a/a709Y 注意上下兩個版本的for迴圈
01/13 17:56, 28F
的確是直接用K大那樣解最快XD，謝謝! ※ 編輯: angel861047 (36.236.38.21), 01/13/2017 18:30:56
‣ 更多 angel861047 的文章
文章代碼(AID): #1OU4CwwU (Grad-ProbAsk)