Re: [閒聊] 程設作業

[game0416 (鳳狼)]

資結第一項程設作業...

講起來可能也是不知道還有什麼好講作法的，某個角度上王老大都講完了


試著用不同方式
去解析題目該怎麼作...吧(?)


然後我要先聲明，講是講要問誰想裝死
不過我沒提過我自己不交這件事Q
寫不出來的人數多的話，向後延不是很意外的發展hmmm


--


雖然只要有人問起我就不太確定要作多大的

不過10*10跟20*20大概只差陣列宣告大小的差別，不要太擔心(?)
所以..因為我想多少都有個概念了，至少知道題目要幹嘛

這樣的話，請先忘記三小堆疊的事情，這種話出現在題目裡面只是混淆視聽而已
記得作程設應該比較像是「找出方法」而不是「套用方法」
﹕ 講這種話讓我自己都想吐嘈自己數學也該這樣學（死在地上）

而在多數情況之下，暴力法在人腦思考下都是最直觀的作法
以走迷宮來說，暴力法就會是"走過每一種路線、經過每一個點"

這個才是現在我們作走迷宮的想法，跟那什麼堆疊都還扯不上關係
然後為了作到這個方法，我們就去規劃"怎麼作"

也就是再來王老大在上課的說明內容.....
下頁我試著用不同的方去講這件事


--

首先，要想"如何能確保會走每一種路線"

這件事可以從排列組合來看...
如果沒有公式，排 1 2 3 4有幾種排法，我們就會照順序逐個排
首先是照順序
1 2 3 4
再來調整最後一項發現不能改，所以退而求其次，調倒數第二項
1 2 4 3
然後倒數第二項再來也不能動，就改倒數第三項...
1 3....2 4
發現排完倒數第三項，再來 2 4 會有兩種，就照順序 1 3 2 4先
1 3 4 2 後
1 4 2 3
1 4 3 2
...略
...略
4 3 2 1
用同樣的邏輯來看地圖上的點....嗯，這樣說明不太容易理解
取前兩天的測資作說明

--

先拿上次寫出來當測資的圖作代表
最上面一列、最左邊一行作為索引
就當地圖座標就好

  0 1 2 3 4 5 6 7 8 9
0 0 1 1 1 1 1 1 1 1 1           這是張稍微小小複雜了點的地圖
1 1 0 1 1 1 1 1 1 1 1           當然，我們的起/終點是0,0 9,9
2 1 1 0 1 0 0 0 0 0 0
3 1 0 1 1 1 1 1 1 1 0           方法是上課提的順時針法檢測...
4 0 1 1 0 0 1 1 1 0 1
5 0 1 0 1 1 1 1 1 1 0
6 0 0 1 1 1 1 1 1 1 0
7 1 0 1 0 0 0 0 1 1 0           另外一張一本道(?)地圖在寫現在講解
8 1 0 0 1 1 1 1 0 0 1           這段之前，用作測試程式會不會正確移動的
9 1 1 1 1 1 1 1 1 1 0

單憑簡單的肉眼走，我想是能直觀寫出路線
不過電腦很笨，照著我們的判斷法會走很多路
再來我直接寫出來電腦走的路徑，這樣應該會比講一堆ㄆ話來得快

--
 →為x
 ↓為y，取絕對值...或說是座標轉換也好_A_
反正參考圖旁邊索引就是了

(0,0) -> (1,1) -> (2,2) -> (1,3) -> (0,4) -> (0,5) -> (1,6) ->
(2,5) -> (3,5) -> (2,5) -> (1,6) -> (1,7) -> (2,8) -> (3,7) ->
(4,7) -> (5,7) -> (6,7) -> (7,8) -> (8,8) -> (9,7) -> (9,6) ->
(9,5) -> (8,4) -> (9,3) -> (9,2) -> (8,2) -> (7,2) -> (6,2) ->
(5,2) -> (4,3) -> (4,2) -> (4,3) -> (5,2) -> (6,2) -> (7,2) ->
(8,2) -> (9,2) -> (9,3) -> (8,4) -> (9,5) -> (9,6) -> (9,7) ->
(8,8) -> (9,9)

徒手寫，程式放在家裡懶得當場刻出來只為了寫教學
所以可能哪邊有小錯誤...應該是沒有啦(?)
大概注意一下紅字點上的走路方向與走回紅字這兩件事
第一次進入(1,6)，順時鐘方向先看到(2,5)是活路，所以就往那邊過去了
走到(3,5)發現死路，這裡記得此時的(2,5)應該在地圖上已經標記成是死路
就回頭走回(2,5)，也發現已經找不到方向，所以再退回(1,6)
(1,6)再一次的看看哪裡還是活路，找到(1,7)，於是繼續運行...(8,8)同理


--

比較特別的，在做移動的時候，只要是自己走過的地方就當成是死路
因為照我們的組合方法、順時鐘檢查、移動方向
一定會慢慢檢查過現在所在路徑之上/右上方每一個點所能延伸出來的走法
也就是說，我們的檢測路線方法，可以說成



從地圖上方找出一條最能沿著邊緣移動的路線，然後沿著該路徑最末端開始掃描
這樣好像還算動態規劃(DP)…不斷由兩個最接近且沒有走過的點作為單元
開始組成整張地圖的所有路徑
這樣講起來又變複雜了...
直接把第一次/第二次走到(1,6)在電腦"認知"上的地圖畫出來比較快








--




   第一次走到(1,6)
  0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 0 0 0 0 0 0
3 1 1 1 1 1 1 1 1 1 0
4 1 1 1 0 0 1 1 1 0 1
5 1 1 0 1 1 1 1 1 1 0
6 0 1 1 1 1 1 1 1 1 0
7 1 0 1 0 0 0 0 1 1 0
8 1 0 0 1 1 1 1 0 0 1
9 1 1 1 1 1 1 1 1 1 0





--



  走到(3,4)時

  0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 0 0 0 0 0 0
3 1 1 1 1 1 1 1 1 1 0
4 1 1 1 1 0 1 1 1 0 1
5 1 1 1 1 1 1 1 1 1 0
6 0 1 1 1 1 1 1 1 1 0
7 1 0 1 0 0 0 0 1 1 0
8 1 0 0 1 1 1 1 0 0 1
9 1 1 1 1 1 1 1 1 1 0





--



   第二次走到(1,6)

  0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 0 0 0 0 0 0
3 1 1 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 1 0 1
5 1 1 1 1 1 1 1 1 1 0
6 0 1 1 1 1 1 1 1 1 0
7 1 0 1 0 0 0 0 1 1 0
8 1 0 0 1 1 1 1 0 0 1
9 1 1 1 1 1 1 1 1 1 0





--

大概像是這樣...吧

雖然我不知道這樣解釋會不會比王老大來得容易理解一點點

比起從第一格開始往外踏出第一步這件事
在這題目可能更要想清楚在某條路徑最末端開始往回每一步後的下一步
該說每走上一個點都像是起點這樣的想法嗎(?)

--
違背命運是人之常情。

　　人們從在犯了錯之後，才向神明祈禱以求補償。
　
　　　 　　 　　　　　　　　                       狼與辛香料　克拉福‧羅倫斯

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.130.128.171
※ 編輯: game0416        來自: 220.130.128.171      (10/25 15:53)
→ game0416:附上code就會直接抄下去了...行數理論上不會太多
※ 編輯: game0416        來自: 220.130.128.171      (10/25 15:58)
推 j2612280:科科
→ game0416:樓上笑什麼qq
推 gentlefaith:鳳郎用心推!!
推 johlmike:努力中QQ~教學文推
※ 編輯: game0416        來自: 119.14.27.224        (10/31 20:41)
※ 編輯: game0416        來自: 119.14.27.224        (10/31 20:42)