2015年2月18日 星期三

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

http://4rdp.blogspot.com/2015/02/52.html?m=0

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



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

標籤： ,

11 則留言:

  1. 匿名2015年2月20日 凌晨1:22

    一共 (7C3) * (7C3) 這麼多種！

    回覆刪除
    回覆
    1. Bridan2015年2月20日 上午10:33

      新春快樂，答案有誤，再想想看。

      刪除
    2. 匿名2015年2月21日 晚上8:19

      那，由A點到B點的最短路徑，是不是7C3 ，也就是35個？

      刪除
    3. Bridan2015年2月21日 晚上9:23

      你好，

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

      刪除
  2. Bridan2015年2月22日 上午10:40

    我是這樣想的
    首先，由起點到終點，包含了兩個部分，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. Bridan2015年2月22日 上午10:41

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

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

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

    回覆刪除
  4. Bridan2015年2月22日 上午10:55

    我也覺得奇怪，貼了好幾次都不見了，可能與匿名貼文有關。

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

    回覆刪除
  5. 匿名2015年2月23日 凌晨1:14

    我估計可能是那個機人驗證上，出了問題。

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

    回覆刪除
    回覆
    1. Bridan2015年2月23日 上午10:17

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

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

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

      刪除
    2. 匿名2015年2月27日 凌晨12:27

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

      刪除
    3. Bridan2015年2月27日 上午8:03

      您好，

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

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

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

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

      刪除

訂閱： 張貼留言 (Atom)