貼圖、程式等,版主可任意修改或刪除,轉貼文章請多用連結,一天 (00:00-23:59) 請只開一個話題,請大家合作,謝謝。02/20/2019 22:15:29 意見庫存 |
外獨會意見交流 |
||
---|---|---|
這個數學題,我想了兩天. |
圓周上有任意6個點,畫6個弦,每一個點都只有兩個弦通過,有幾個畫法? |
Record ID: 1543812624 | From: 台灣 |
想像有六根線,左邊編號固定,如下
0----------------------- 1----------------------- 2----------------------- 3----------------------- 4----------------------- 5----------------------- 右邊6個編號,由上而下列在R55 |
Record ID: 1543812624R056 | From: 韓國 |
呵呵,還有一個限制未考慮
例如,以上程式碼將 點0接點5,點5接點0 這種接法也算在內了,得除去 |
Record ID: 1543812624R057 | From: 韓國 |
connect函式修改如下
void connect(int index) { int i,j,k; for(i=0;i<6;i++) { if(index==i) continue; for(j=0;j if(lines[j]==i) break; } if(j!=index) continue; lines[index]=i; if(index==5) { char cond=1; for(j=0;j<6;j++) { if(lines[lines[j]]==j) { cond=0; break; } } if(cond) { printf("%d%d%d%d%d%d\n",lines[0],lines[1],lines[2],lines[3],lines[4],lines[5]); match++; } } else connect(index+1); } } |
Record ID: 1543812624R058 | From: 韓國 |
想像有六根線,左邊編號固定,如下
0----------------------- 1----------------------- 2----------------------- 3----------------------- 4----------------------- 5----------------------- 排序右邊編號, 不能與左邊相同,不能重複, 不能左點0接右點5,左點5接右點0 共160種 120453 120534 123450 123504 124053 124530 125034 125403 130452 130524 134052 134250 134502 135024 135204 135420 140253 140532 143052 143502 143520 145023 145203 145230 150234 150423 153024 153402 153420 154032 154203 154230 201453 201534 203451 203514 204153 204531 205134 205413 231450 231504 234051 234501 234510 235014 235401 235410 241053 241530 243051 243150 243501 245031 245103 245130 251034 251403 253014 253104 253410 254013 254103 254130 301452 301524 304152 304251 304512 305124 305214 305421 320451 320514 324150 324501 324510 325104 325401 325410 340152 340251 340521 341250 341502 341520 345120 345201 350124 350214 350412 351204 351402 351420 354102 354210 401253 401532 403152 403512 403521 405123 405213 405231 420153 420531 423051 423150 423510 425013 425031 425130 430251 430512 430521 431052 431250 431520 435021 435210 450123 450132 450213 451023 451032 451230 453012 453120 501234 501423 503124 503412 503421 504132 504213 504231 520134 520413 523014 523104 523401 524013 524031 524103 530214 530412 530421 531024 531204 531402 534012 534201 540123 540132 540231 541023 541032 541203 543021 543102 match=160 |
Record ID: 1543812624R059 | From: 韓國 |
感謝各位先進高明留言,我得到了啟發.
尤其是R035 >一定要分出有連成三角形與沒有三角形的兩個狀況的計算式。 >有連成三角形時,另外三點只有一種畫法,沒有連成三角形時另外三點有六種畫法。 有連成三角形時,另外三點只有一種畫法,總計10種畫法。 C(6 3)/2 = 10 沒有連成三角形時另外三點有六種畫法,總計60種畫法。 C(5 2) x 3 x 2 = 60 兩個加總,70種畫法。 |
Record ID: 1543812624R060 | From: 台灣 |
周上有任意6個點,畫6個弦,每一個點都只有兩個弦通過,且任意兩個弦都不平行.
沒有連成三角形時,有60種畫法,有60條"迷圓周率線"能畫出. 連成三角形時,有10種畫法,不能畫出"迷圓周率線"。 |
Record ID: 1543812624R061 | From: 台灣 |
欄主提出的問題
與diy所陳述的六根線左右編號問題 是等價的 |
Record ID: 1543812624R062 | From: 韓國 |
> 有連成三角形時,另外三點只有一種畫法,總計10種畫法。
> C(6 3)/2 = 10 啊,對,C(6,3) 還要除以 2。 > 沒有連成三角形時另外三點有六種畫法,總計60種畫法。 > C(5 2) x 3 x 2 = 60 不止喲,再想想對 R038 進一步的思考
|
Record ID: 1543812624R063 | From: 台灣 |
> R038 的演算法中,ABC 那組只有 A 連去 BC 的狀況,而沒有包括到 B 連去 AC 和 C 連去 AB 的狀況。
> 後面連去 123 的各種變化,都不會產生 B 連去 AC 或 C 連去 AB 的圖。 嗯,A 連去 B & 1 的時候就可以有 B 連去 A & C 的圖,餘類推。所以 C(5, 2) x 3 x 2 = 60 不用再乘 2 或乘 3 的。 |
Record ID: 1543812624R064 | From: 台灣 |
這個問題看來沒有比窮舉法更省事的
|
Record ID: 1543812624R065 | From: 韓國 |
R054,058是遞迴程式
R059是答案 |
Record ID: 1543812624R066 | From: 韓國 |
欄主的問題和以下陳述是等價的
圓周上有六個點,其編號為0、1、2、3、4、5 從這六點上各引一條弦出來,如下 0----------------------- 1----------------------- 2----------------------- 3----------------------- 4----------------------- 5----------------------- |
Record ID: 1543812624R067 | From: 韓國 |
這六條弦的終點在哪呢?有三個限制
起點終點號碼不同,右邊號碼不能重複,左右端點不能交叉連接 那麼,這六點就是某條弦的起點,另一條的終點 寫成程式,就是很簡單的遞迴程式了 |
Record ID: 1543812624R068 | From: 韓國 |
六個點分成兩個三角形 就(6*5*4)/6 20種
但是選到a b c 與 選到 d e f 畫出來的圖形是一樣的 所以要除以2 於是答案變成 120+10=130種 如果題目變成五個點 就只有5!/5=24種 然後7個點時 可以分成一筆畫 與 四點+三點 兩種情況 8個點時 可以分成一筆畫 與 五點+三點 和 四點+四點 三種情況 9個點是 一樣一筆畫 與 六點+三點 五點+四點 和 三點+三點+三點 四種情況 故事演變成 如果有n個點 會有幾種畫法 感覺上這題目會更精彩 |
Record ID: 1543812624R069 | From: 台灣 |
純銅大大,
Orz. |
Record ID: 1543812624R070 | From: 台灣 |
話說 如果點是 分佈在球面上
一樣要求 每一點只能接到兩條弦 計算幾種畫法 也是相當有趣的 |
Record ID: 1543812624R071 | From: 台灣 |
圓周上有任意N個點,畫N個弦,每一個點都只有兩個弦通過,有幾個畫法?
這是一個很大很大的題目. N=1 -> 0個畫法 N=2 -> 0個畫法 N=3 -> 1個畫法 N=4 -> 3個畫法 N=5 -> 12個畫法 N=6 -> 70個畫法 N=7 -> ?個畫法 N=7, 360個畫法 C(6 2) x 4 x 3 x 2 x 1=360 (一筆畫) 105個畫法 C(7 3) x 3 =105 (*1個三角形,1個四角形) 總共465個畫法 |
Record ID: 1543812624R072 | From: 台灣 |
我一個問題 要突破兩次盲點 才能悟出正確答案 真糟糕
六個點一筆連成畫完 123456 不僅和 234561 345612... 畫出來的圖相同 也和 654321 543216 432165... 相同 所以 n 個點一筆畫完 畫出來東西 只有 n!/(2n) 種 我已經預見下一個盲點了 九個點 分成三個三角形 有幾種方法 因為正是 盲點 所以得認真思考一下 因為涉及到 如果有3n個點 分成n個三角形 有幾種可能? 有沒有公式呢? 這個更一般化的問題 我只用高中社會組數學 真的無法突破盲點 |
Record ID: 1543812624R073 | From: 台灣 |
> 六個點一筆連成畫完 123456 不僅和 234561 345612... 畫出來的圖相同
> 也和 654321 543216 432165... 相同 > 所以 n 個點一筆畫完 畫出來東西 只有 n!/(2n) 種 會不會想的太複雜了? 六個點因為要全畫到並接回起點,所以從哪一點開始總畫法都一樣,所以不必用 6! 起算,用 5! 起算就好了。 再來是因為最後一筆要畫回起點,所以畫過去的和畫回來的兩個會重複計算到,就得到 5!/2 了。 |
Record ID: 1543812624R074 | From: 台灣 |
>九個點 分成三個三角形 有幾種方法
C(9 3) x C(6 3) ÷6 = 280 |
Record ID: 1543812624R075 | From: 台灣 |