2015年2月18日 星期三

訓練數學感 52 ─ 最短路徑有幾種?

http://4rdp.blogspot.com/2015/02/52.html

上下有兩個 4 x 3 方格相交於 B 點,現在由 A 點出發,沿著格線行進,經過 B 點,到達終點 C,請問總共有幾種最短路徑走法?



這題是小朋友考我的,在餐廳用餐 30 秒鐘解出,大家解看看。

11 則留言:

  1. 一共 (7C3) * (7C3) 這麼多種!

    回覆刪除
    回覆
    1. 新春快樂,答案有誤,再想想看。

      刪除
    2. 那,由A點到B點的最短路徑,是不是7C3 ,也就是35個?

      刪除
    3. 你好,

      終於從南部塞車回台北,仔細計算,確實你提供的答案是正確的,當時在餐廳並未仔細確認自己的邏輯有誤,把問題簡化為每節點向右及向下兩種選擇,那A到B就變成 2^6 = 64,你之前的貼文正確,怎麼不見了?我就重貼文如下。

      刪除
  2. 我是這樣想的
    首先,由起點到終點,包含了兩個部分,A點到B點,和B點到C點。
    而這兩個部分,就像選外衣的組合,如下例。

    例1:
    小美家裡只有3件上衣(分別以A,B及C表示),及只有5件下衣(分別以1,2,3,4及5表示)。
    她的選擇是A1, A2, A3, A4, A5, B1, B2, B3, B4, B5, C1, C2, C3, C4 及 C5 共15個組合,也就是 3 * 5。
    這裡總數目是要乘出來的。

    然後,言歸正傳。
    根據題目要求,我們是必須經過B點的,所以我們先討論由A點到B點的情況。
    由於最終要求,要的是路徑最短,所以若我們只向右行走,或只向下行走,那便行了。
    而由A點到B點,必須行4次右,3次下,先後次序沒所謂,因為走7次,已經是最短的路徑了。
    基於要排次序,總組合數目便就是7C3。
    而7C3甚樣算的呢?

    我們可以先想像,這裡有7個空格( _ ) 我們需要選其中三個空格來放置一個X,
    X X X _ _ _ _ 、X X _ X _ _ _ 、X X _ _ _ _ X 等等,都是可能的選法
    因為是從7個不同的空格,選出其中三個出來放東東,所以選法共有7C3這麼多種。

    而相似地,排 向右、及向下 的排法時,只須從7個次序中,抓三個用來 放向下的指令,而其餘四個便不用選擇,就可放置向右的指令。所以排法也是有7C3這多種。

    如: 下 下 下 右 右 右 右 、 右 下 下 右 下 右 右 、 右 下 下 右 右 下 右 ,等等。若用例舉發,也只會有35個組合。

    由於A往B,與B往C是相似的,所以B往C的最短路徑的數目也就是7C3。

    由於總路徑是最短時,由A往B,及B往C的路徑,也必須同時是最短。而且走完A往B時,也必須再走完B往C。
    所以兩者相乘後的結果,才是最短總路徑的可能數目。(7C3 * 7C3)



    另外,這題也有另一個想法,便就是若要路徑最短,那也是必須只向右走和只向下走。
    所以到達某一點(C)的路線數目,就是該點以上的點(U)的路線數目,再加上該點左方的點(L)的路線數目。

    所以路線路面如下,
    01 01 01 01 01
    01 02 03 04 05
    01 03 06 10 15
    01 04 10 20 35
    所以數目也是35 ,然後往後的也就是和上面差不多。

    我的想法就是這樣了。

    回覆刪除
  3. 夫子,你好
    我也不知道為何貼文會消失掉,我也因心血不見了傷心了一會。
    不過網絡就是會這樣,總會有些稀稀奇奇的問題。

    如图是由12个小正方形组成的43矩形网格,一质点沿网格线从点A到点B的不同路径之中,最短路 径有

    条 解: 总揽全局:把质点沿网格线从点A到点B的最短路径分为七步,其中四步向右,三步向上,不同走法的区别在于哪三步向上, 因此,本题的结论是:353 7C.
    http://wenku.baidu.com/view/ba2ea2d384254b35eefd3426.html?re=view
    夫子,你可以到這中國大陸的百度看看。
    很有趣的,

    回覆刪除
  4. 我也覺得奇怪,貼了好幾次都不見了,可能與匿名貼文有關。

    謝謝你提供連結參考,看過後,讓我想到一個加分題:
    把這平面路徑拓展成立體格狀,如果有 4 x 4 x 4 的立體網格,請問從立體方塊的一角,沿著網格線行進,請問到達對角位置最短路徑,有幾種走法?

    回覆刪除
  5. 我估計可能是那個機人驗證上,出了問題。

    這題答案有點難,沒太大信心。
    是不是12C4 * 8C4 ?

    回覆刪除
    回覆
    1. 嗯,正解,把往三軸方向分別以 XYZ 符號代表,那有四個 X,四個 Y,四個 Z,依你的算式 12C4 就是先排完 X,再排 Y = 8C4,剩餘的就是 Z。

      對了,方便留下讀者資料嗎?想認識你這位數學愛好者,http://4rdp.blogspot.tw/2014/01/2014-reader-survey.html

      好再來進階題,以上圖 A 到 B,平面路徑不重複有幾種走法?

      刪除
    2. 這題進階題,主要分別在於"最短"與否,
      而其中一個可能走法是
      下下上下下右右右右,共9步。
      而行9步的不重複走法,是有限的。
      而由A行11步到B的不重複走法,也是有限的。
      ,如此類推行13步,行15步,17、19、等等等,也是有限的。
      而由於行走步數沒設限,平面路徑不重複的走法總數目,必然是無限。
      (無限多個1加在一起,必然是無限。)

      刪除
    3. 您好,

      可能並未對進階題題義作清楚解釋,造成「路徑不重複」的看法差異,簡單的說,路徑最多只能走一次。

      以你提供範例 下下(上下)下右右右右,在第三及第四這兩步驟是重複的路徑,也就是該次行進時,走過的路徑是不能再走一次,包含逆向行進,也就是範例的第三步驟。
      關於節點相交是允許的,例如 下下右下右上左上右右右下下,在第七步驟與第三步有同交於一節點,是允許的。這進階題不以最短路徑為限制。

      題目修正如下,
      進階題一,由 A 點出發,沿著格線行進,走過的路徑是不能再走一次,包含逆向行進,行進時節點相交是允許的,請問到 B 點,總共有幾種走法?
      進階題二,由 A 點出發,沿著格線行進,走過的路徑是不能再走一次,包含逆向行進,行進時節點相交是不允許的,請問到 B 點,總共有幾種走法?
      進階題三,由 A 點出發,沿著格線行進,走過的路徑方向是不能再走一次,也就是可以逆向行進一次,行進時節點相交是允許的,請問到 B 點,總共有幾種走法?
      進階題四,由 A 點出發,沿著格線行進,走過的路徑方向是不能再走一次,也就是可以逆向行進一次,行進時節點相交是不允許的,請問到 B 點,總共有幾種走法?

      這幾題進階題難度很高,把它加入待解難題中。

      刪除