在上一篇裡我們用蠻力搜尋法解決了水平直線的同一側兩點的最短路徑問題。蠻力搜尋法的計算量龐大,可不是人用手算可以輕易完成的工作。那麼有沒有更簡捷的方法求得同樣的最短路徑呢?看完接下來分享的聰明解法,或許會讓你發出 「啊,原來如此」的驚嘆。
數學關鍵字: 直線方程式、斜率。
Scratch程式:https://scratch.mit.edu/projects/158120049/
https://scratch.mit.edu/projects/158227195/ (第二版)
用不同方法解出最短路徑問題
蠻力法搜尋軸線上所有可能產生最小路徑的點進行計算,在動手做2–1的例子中一共計算了290個點,如果有turbo模式(按住shift鍵+小綠旗)大約一、兩秒也就算出來了。但是如果用尺量再用手算290個點的距離,那可就有點吃不消了。
應用數學的技巧,另外有一種簡單的方法可以計算出一模一樣的答案。
我們如果將點A對水平軸線做鏡射,可以得到點A’。點A到水平軸線的距離等於點A’到水平軸線的距離。
這時候我們將點B和點A’連接起來,和水平軸線交會在點C。
由於兩點間最短的距離就是連接兩點的直線,線段A’B是點A’到點B的最短路徑。
由於點A’是點A的鏡射,可以看到線段AC等於線段A’C。
因此歸納起來,點C就會是我們要找的最小路徑解答。
運用這樣的數學技巧,不須要大量的計算,用手算就可以輕鬆地求得最小路徑距離。
直線的斜率
斜率是一個用來表示直線方向和傾斜程度的數字,在數學裡通常用字母m表示直線的斜率。
直線的斜率定義是直線的縱軸變化量除以橫軸變化量。在卡氏直角座標裡可以找到直線上任兩點(x1, y1)和(x2, y2),斜率m可以表示成下面的式子。
在式子裡的△x唸做delta x,代表x方向的變化量。同理,△y唸做delta y,代表y方向的變化量。
一條直線的方向有上升、下降、水平、垂直四種。觀察這四種方向的直線斜率會發現,
1. 直線從左到右呈上升狀,斜率為正值。直線越陡峻,斜率越大。
2. 直線從左到右呈下降狀,斜率為負值。直線越陡峻,斜率的絕對值越大。
3. 水平線斜率為0。
4. 垂直線斜率為無窮大(∞)。
下面四個圖例顯示四種不同的斜率值。
直線方程式
笛卡兒將幾何與代數連結在一起後,漸漸發展出了解析幾何這門學問。在解析幾何裡,二維平面的一條直線可以轉換成二元一次方程式,而看到直線的方程式也可以畫出相對應二維平面裡的直線。
我們以下圖當做範例,來看看直線的方程式要怎麼轉換。
圖例裡的直線有幾個我們知道的特徵,
1. 直線通過點(1, 2)。
2. 直線通過點(4, 8)。
3. 直線的斜率:
二維平面的直線會轉換為二元一次方程式。二元的意思就是有兩個變數,在卡式座標裡指的就是x和y。一次的意思就是變數x和y都只有一次方。
在直線上任一點的座標記為(x, y),我們可以利用同一條直線斜率一樣的特性列出方程式。
想法1:點(x, y)到點(1, 2)的斜率和點(4, 8)到點(1, 2)的斜率相等,
開始化簡方程式到一個更簡潔的形式,
想法1的方法叫直線的兩點式,只要知道直線上兩個已知點(x0, yo)(x1, y1),就可以寫出直線方程式:
想法2:點(x, y)到點(1, 2)的斜率是2,利用斜率的定義可以寫下,
開始化簡方程式到一個更簡潔的形式,
想法2的方法叫直線的點斜式,只要知道直線的斜率m和一個已知點(x0, yo),就可以寫出點斜式:
想法3:由想法2的點斜式做進一步的化簡,
想法3的方法叫直線的點截式,m是直線的斜率,b是x=0時直線和y軸的交點。
動手做2–2 用鏡射法找出最短路徑
[程式設計需求規格]
運用鏡射法找出A’,將點A’連結到點B通過水平線點C,和動手做2–1比較結果。最後再求解通過點A’和點B的直線方程式。
[程式設計角色和舞台]
角色和舞台背景與動手作2–1完全相同。
[程式設計解決方案]
在這個範例中,紅點座標為(-140, 50),藍點座標為(150, 90)。角色藍點、紅點、軸線的程式和動手做2–1完全一樣。但是角色黑點會多加兩個客製積木「鏡射連接」和「直線方程式」。
[程式檢視]
程式[黑點2–2.4]將黑點移到紅點鏡射位置,也就是和紅點有相同的x座標,由於軸線位於y=0,鏡射後座標就是紅點y座標乘上-1。
程式[黑點2–2.4]最後會呼叫客製方塊「藍點軌跡」畫出藍點到黑點的軌跡。當我們按下空白鍵後,可以看到鏡射求出的解和之前蠻力法求出的解在軸線上完全重合。說明了這兩種方法都可以求得軸線上正確的點。
程式[黑點2–2.5]客製方塊「直線方程式」用想法3的斜截式來計算直線方程式。先依照兩點間的斜率定義求得斜率值,再依想法3的計算求b,設成變數「係數」的值。
我們將變數「斜率」和「係數」乘以10000做四捨五入,再除以10000。等效於將變數值取到小數點後四位,小數點後第五位做四捨五入。
程式[黑點2–2.6]我們要在舞台上畫出這個直線方程式。掃描所有x軸的點,套進方程式中可以求得每一個對應的y值。
程式執行到按下d鍵就開始方程式計算,然後在舞台畫出對應的直線,並且顯示直線方程式。
第二版:掃描 x 軸上點同時畫直方圖,顯示最小路徑 x 座標。
延伸閱讀:
Scratch & Math: 天花板上的蜘蛛(一) Scratch & Math: 天花板上的蜘蛛(二)