[問題] 走捷徑

[MKing (爾玉之倫)]

由 C走捷徑至 B，其法有幾？    不要用累加法，答案是90

                  B
            ┌┬┐
          ┌┼┼┤
        ┌┼┼┼┤
      ┌┼┼┼┼┤
      └┴┴┴┴┘
     C



此題是由下面由 A至 B加上某條件變化而來。

                     B
       ┌┬┬┬┬┬┐
       ├┼┼┼┼┼┤
       ├┼┼┼┼┼┤
       ├┼┼┼┼┼┤
       └┴┴┴┴┴┘
      A



--

最後一顆子彈留給我

--- 一個18歲不到，先休了大學去當三年特戰小兵的記事

--- 除了中國統戰和對中國的偏愛（這算是不可免的制約）以外，還值得一看

原載 http://www.sonicbbs.com/war/boarddisplay.asp?BoardID=9

授權 http://210.5.4.91/gate/big5/www.cmfu.com/readbook.asp?bl_id=1735

※ 編輯: MKing           來自: 140.112.8.141        (06/24 12:17)
→ bbbing:先說第二題是C10取6
→ doa2:第一題C(9,5)-C(9,7)
> -------------------------------------------------------------------------- <

作者: potoser (喝) 看板: tutor
標題: Re: [問題] 走捷徑
時間: Tue Jun 24 14:19:10 2003


※ 引述《MKing (爾玉之倫)》之銘言：
: 由 C走捷徑至 B，其法有幾？    不要用累加法，答案是90
:                   B
:             ┌┬┐
:           ┌┼┼┤
:         ┌┼┼┼┤
:       ┌┼┼┼┼┤
:       └┴┴┴┴┘
:      C
: 此題是由下面由 A至 B加上某條件變化而來。
:                      B
:        ┌┬┬┬┬┬┐
:        ├┼┼┼┼┼┤
:        ├┼┼┼┼┼┤
:        ├┼┼┼┼┼┤
:        └┴┴┴┴┴┘
:       A

  座標化A(0,0)  是不通(0,1) (1,2)  (2,3)  (3,4) 吧

  不過要限定不能用XXX法 好像有一點自愉

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw) 
◆ From: 140.112.213.163

> -------------------------------------------------------------------------- <

作者: SwakAqua (阿翔) 看板: tutor
標題: Re: [問題] 走捷徑
時間: Tue Jun 24 16:58:44 2003

※ 引述《MKing (爾玉之倫)》之銘言：
: 由 C走捷徑至 B，其法有幾？    不要用累加法，答案是90
:                   B
:             ┌┬┐
:           ┌┼┼┤
:         ┌┼┼┼┤
:       ┌┼┼┼┼┤
:       └┴┴┴┴┘
:      C
: 此題是由下面由 A至 B加上某條件變化而來。
:                      B
:        ┌┬┬┬┬┬┐
:        ├┼┼┼┼┼┤
:        ├┼┼┼┼┼┤
:        ├┼┼┼┼┼┤
:        └┴┴┴┴┴┘
:       A

我是先畫成     E  D         然後算到D點的路線減去到E點的路線數就是到B點的路徑數
               ┌┐
             ┌┼┤B
           ┌┼┼┤
         ┌┼┼┼┤
       ┌┼┼┼┼┤
      C└┴┴┴┴┘

到D點的 由完整圖看

   ┌┬┬┬┬┐D(5,5)   一定是 U(UP) 5次 R(RIGHT) 5 次
   ├┼┼┼┼┤         但是不可RISE ABOVE S-D那條線 否則就不符合規定
   ├┼┼┼┼┤         假設不考慮RISE ABOVE 總路徑數是 C(10,5)
   ├┼┼┼┼┤         而有RISE ABOVE的情況中 把超越後的軌跡反轉可以發現一個
 S ├┼┼┼┼┤         現象 EX:RRUUUU│RURR 在線後的是超越後的軌跡(不含第一個
 C └┴┴┴┴┘         超越的U) 把線後的軌跡反轉 得 RRUUUUURUU 結束會落在(3,7)
                        這一點(不在圖上)，也就是說，所有不合規定但最終走到D的路
                        徑在經過上述處理後都會產生一條到(3,7)的路徑

                        接著計算到(3,7)的路共有C(10,3)條

                        所以到D且在S-D連線下的路徑共有C(10,5)-C(10,3)=132條

到E點的路也一樣

    ┌┬┬┬┐E(4,5)    先找一個不合路徑的映射點(就是經過反轉後會走到的那點)
    ├┼┼┼┤          找出是(3,6)，所以到(3,6)的路徑數會等同於到E點但卻
    ├┼┼┼┤          RISE ABOVE S-E連線的路徑數
    ├┼┼┼┤          到E點路徑總數=C(9,4)
  S ├┼┼┼┤          到(3,6)路徑總數=C(9,3)
  C └┴┴┴┘          所以到E點的合規定路徑數=C(9,4)-C(9,3)=42

                        而到D點的只能從B或E來
                        故到B點的路徑數=132-42=90

因為我不知道怎麼直接算到B的路徑數所以才要這樣用減的
也許有人有更方便的方法吧

這方法是在離散數學裡學到的



--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw) 
◆ From: 61.216.27.238

> -------------------------------------------------------------------------- <

作者: TwoOneboy (soga 言之有理!!) 看板: tutor
標題: Re: [問題] 走捷徑
時間: Tue Jun 24 18:08:14 2003

※ 引述《MKing (爾玉之倫)》之銘言：
: 由 C走捷徑至 B，其法有幾？    不要用累加法，答案是90
:                   B
:             ┌┬┐
:           ┌┼┼┤
:         ┌┼┼┼┤
:       ┌┼┼┼┼┤
:       └┴┴┴┴┘
:      C
      ┌┬┐
      ├┼┤
      ├┼┤
      ├┼ㄨ┬┬┐
      ├ㄨ┼┼┼┤
      ㄨ┼┼┼┼┤
      ├┼┼┼┼┤
      └┴┴┴┴┘

就降啦，C(9,4) - C(9,2) = 90

其實也沒有比累加法還快

--
家教好難找....XD

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw) 
◆ From: 140.112.212.119
→ Triheart:好在我已經不用找了 :p 學弟加油
→ doa2:如果大一點就比累加快了阿
> -------------------------------------------------------------------------- <

作者: ChiRen (~@@~) 看板: tutor
標題: Re: [問題] 走捷徑
時間: Tue Jun 24 18:06:21 2003

※ 引述《MKing (爾玉之倫)》之銘言：
: 由 C走捷徑至 B，其法有幾？    不要用累加法，答案是90
:                   B
:             ┌┬┐
:           ┌┼┼┤
:         ┌┼┼┼┤
:       ┌┼┼┼┼┤
:       └┴┴┴┴┘
:      C
: 此題是由下面由 A至 B加上某條件變化而來。
:                      B
:        ┌┬┬┬┬┬┐
:        ├┼┼┼┼┼┤
:        ├┼┼┼┼┼┤
:        ├┼┼┼┼┼┤
:        └┴┴┴┴┴┘
:       A

        把A點當做是(0,0)，
        C9取5減去過(0,2)或(1,3)或(2,4)的情況
        即C9取5-C7取2-C4取1*C5取1-C6取2+2*5+4*2+6-4=90

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw) 
◆ From: 218.167.174.138