[理工] 100清大 計算機科學 第一題

看板Grad-ProbAsk作者 (yett)時間9年前 (2017/01/04 17:09), 編輯推噓2(2推 0噓 24→)
留言26則, 3人參與, 最新討論串1/1
http://i.imgur.com/U7PGYgQ.jpg
大家好，想請問這題要怎麼寫 我卡住的地方有兩個 1. 他亂序給 perm(str, str+strlen(str)-1) 跟 perm(0,3)是一樣的意思嗎(排序陣列st r[0]~str[3]) 2. 他的輸出是 231,321,312,132,213,123要如何照個形式輸出呢？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.30.196.218 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483520958.A.99A.html
推
01/04 18:04, , 1F
先給答案我慢慢打想法
01/04 18:04, 1F
→
01/04 18:06, , 2F
swap的部份，須注意x為記憶體位址，*x才是該位址所指向
01/04 18:06, 2F
→
01/04 18:06, , 3F
的內容，我們這邊是要在陣列上面交換元素，所以應該要
01/04 18:06, 3F
→
01/04 18:07, , 4F
用*x, *y才對
01/04 18:07, 4F
→
01/04 18:08, , 5F
由題目可以看出兩兩最後一個元素是相同的
01/04 18:08, 5F
→
01/04 18:09, , 6F
(231,321),(312,132),(213,123)，顯然他的交換是每次
01/04 18:09, 6F
→
01/04 18:10, , 7F
先固定最後一個元素，然後遞迴下去算前面n-1個元素的
01/04 18:10, 7F
→
01/04 18:10, , 8F
permutation
01/04 18:10, 8F
→
01/04 18:13, , 9F
所以permutation(start, end-1);
01/04 18:13, 9F
→
01/04 18:13, , 10F
那麼每次固定最後一個元素要怎麼挑是哪個元素呢？
01/04 18:13, 10F
→
01/04 18:14, , 11F
就是for迴圈在做的事情，想法是依序從第一個挑到
01/04 18:14, 11F
→
01/04 18:15, , 12F
倒數第二個拿來跟最後一個交換，接著permutation
01/04 18:15, 12F
→
01/04 18:15, , 13F
但是permutation結束之後不要忘了把他們交換回來，如此
01/04 18:15, 13F
→
01/04 18:16, , 14F
一來才可以接著下一輪的交換，不然會亂掉
01/04 18:16, 14F
→
01/04 18:17, , 15F
遞迴的中止條件就是當第一個元素等於最後一個元素，也
01/04 18:17, 15F
→
01/04 18:18, , 16F
就是start=end時，就該把他print出來了
01/04 18:18, 16F
→
01/04 18:18, , 17F
這樣想好了，每次遞迴都把end減1，減到end=start時就可
01/04 18:18, 17F
→
01/04 18:19, , 18F
以不用再減了
01/04 18:19, 18F
→
01/04 18:21, , 19F
這題配分只有10分又挖那麼多空格，除非剛好有看過
01/04 18:21, 19F
→
01/04 18:21, , 20F
permutation的演算法，不然最後再來想這題就好
01/04 18:21, 20F
→
01/04 18:25, , 21F
另外提醒一點'\0'是terminate的符號，strlen在計算的
01/04 18:25, 21F
→
01/04 18:25, , 22F
時候不會把他算進去，以這個case來說strlen(str)會回傳
01/04 18:25, 22F
→
01/04 18:26, , 23F
3，所以應該是perm(0,2)才對
01/04 18:26, 23F
→
01/04 19:44, , 24F
嗚嗚我終於看懂了
01/04 19:44, 24F
→
01/04 19:44, , 25F
謝謝你這麼詳細的解答！
01/04 19:44, 25F
推
01/04 22:07, , 26F
這題沒有事先看過真的很難現場想出來@@
01/04 22:07, 26F
‣ 更多 sam7708909 的文章
文章代碼(AID): #1ORBk-cQ (Grad-ProbAsk)