這張圖中能數出多少個三角形？

01-07

只能一個個數嗎？有沒有方便的計算方法？

提供一種高級做法，計算鄰接矩陣。思路來自下面 @咲神 (雖然他的回答是錯的。。。)

先看簡單的情況：

一。構成：對稱矩陣，i與j兩點相連，對應矩陣[i, j]，[j, i] 位置的值為1，否則為零。

二。鄰接矩陣相乘：對於鄰接矩陣^2，a^2[1, 1] = a[1, 1]*a[1, 1] + a[1, 2]*a[2, 1] + a[1, 3]*a[3, 1] + a[1, 4]*a[4, 1] = 2，a[i, j] 可以理解為從i走到j，那等式就表示從1走兩步回到1共有兩種方法：1 - 2 - 1、1 - 3 - 1；同理a^2[1, 2] = 1，表示從1走兩步到2隻有一種方法1 - 3 - 2。推廣考慮A = 鄰接矩陣^n，則A[i, j] 表示的是從i出發走n步到點j，有多少種走法。 照這麼考慮求鄰接矩陣^3 的跡就是這題答案嘍。

但是注意幾個問題：

1）三角形三個頂點，每個頂點都算了一遍，所以跡要除3.

2）鄰接矩陣^3 會帶來方向問題。上圖設C = 鄰接矩陣^3，C[1, 1] = 2, 表示的是從1出發走3步回到點1有兩種路徑，看圖有 1 - 2 - 3 - 1、1 - 3 - 2 - 1，兩種路徑只是方向差異。易得每個三角形都包含兩個方向，跡再除2.

3）上圖C[1, 3] = 4, 表示從1出發走3步到點3有4條路徑，1 - 3 - 2 - 3、1 - 2 - 1 - 3、1 - 3 - 1 - 3、1 - 3 - 4 - 3，發現有些路徑再瞎胡走。此題構成三角形恰好要求最終回到原點，避免了這個問題。

4）在一條直線上的點不能構成三角形，共K條直線，每條各ki個點，則最後減掉C (ki，3) 對K求和。

5）鄰接矩陣的寫法問題。在一條直線上所有點都是相互連通的。若一條直線為1 - 2 - 3，則1 - 2，1 - 3，2 - 3。有趣的是如果我們只考慮最緊鄰鄰接1 - 2，2 - 3, 這樣構成的連接矩陣。那鄰接矩陣^3 求跡後除6得到的是什麼呢？答：得到的是三角形網眼數。最後不減掉什麼是因為一條直線上走三小步回不到原點。自己理解一下吧。

三。綜上：

三角形總個數 = 跡[鄰接矩陣^3]/6 - C (直線上點的個數，3) 對直線求和

三角形網眼數 = 跡[考慮直線上最近鄰兩點構成的鄰接矩陣^3]/6

舉個例子：

驗證一下： dat={{1,4,5,6,7,8,9,10,11,12,13,2},{1,27,28,29,30,31,34,35,44,45,23},{1,14,15,16,17,18,19,20,21,3},{2,22,23,24,25,26,3},{4,27,14},{5,28,15},{6,29,16},{6,30,33,18},{16,30,32,8},{7,30,17},{7,32,31},{17,33,31},{8,31,18},{31,9},{31,58,39,46,19},{18,58,34,36,37,11},{18,39,40,35,41,38,42,43,2},{18,46,47,48,49,50,23},{9,34,40,47,51,20},{19,51,52,53,54,24},{10,36,35,48,52,55,57,3},{10,37,41,44,49,53,56,26},{20,55,56,25},{11,38,45,50,54,25},{21,57,26},{12,42,23},{13,43,22}}; mat=Transpose@#+#@Normal[SparseArray[#-&>1/@Catenate[Subsets[#,{2}]/@dat],58]]; Tr[mat.mat.mat]/6-Total[Binomial[Length@#,3]/@dat](*鄰接矩陣*) Length@FindCycle[Graph[#1&<-&>#2 @@@Catenate[Subsets[#,{2}]/@dat]],{3},All]-Total[Binomial[Length@#,3]/@dat](*圖論法*)

程序放在最後面了，演算法就是記錄每條線段上的頂點，然後58個頂點C(58,3)挨個查是不是三角形。直接套圖論演算法找三角形也可行，但是這裡面因為共線的點比較多，按照無向圖來存的話稍微麻煩一點，而且因為數據量比較小，速度優勢也不會很明顯。嚴正聲明：Mathematica大法好

-----------------------------------------------------------------------------------------

我數到了184個，如果需要額外的數據請聯繫我

111、184放大了是這個樣子的

定義圖中各個頂點的坐標和各條線段上的頂點，是用另一段Mathematica代碼+滑鼠在屏幕上戳戳戳生成的

處理出來

這是用來找三角形的代碼

這是用來輸出上面那個大圖的代碼

6889個肯定是沒有的。

這張圖一共只有27條獨立的大線段，三角形的數量不會超過Comb(27,3)=2925個。

對於數三角形的問題一種程序演算法是:

放到笛卡爾坐標系裡對所有的交點和邊建立無向圖先跑一遍floyd算任意2點的最短路再枚舉所有3個點的組合判斷這3點是否任意2點的最短路都等於他們之間的距離且3點不在同一直線上符合條件則構成一個三角形

複雜度O(n^3) n是交點數

有答主給出了代碼和答案佩服毅力+點贊把圖放到坐標系裡挺麻煩的

開腦洞想了一種演算法

先統計每條線段上有哪些點及每個點直線連接的點的數目

遍歷所有線段對於一條線段中的所有點對這2點可以和與它們直線連接的點構成三角形(除去和該點對共線的點)

最後他們的和除以3似乎就是總三角形數

我初中老師教我的方法：把圖用鉛筆畫一遍，三角形有兩個重要的條件，一個角，一條和兩條射線都相交的線。所以數三角形的方法是，認準一個角，數下面的線段。數完之後，把那個角直接抹掉。數完之後，把那個角直接抹掉。數完之後，把那個角直接抹掉。

移步評論區，這個方法確實有些小bug。但不至於完全拋棄，至少我覺得～

看了那麼多O(n^3)的做法，我來提供一個無向圖中尋找三元環很經典的一個分塊演算法。

這個演算法在稀疏圖時很優秀，在稠密圖中也表現的比暴力枚舉好些，複雜度是O(msqrtm)

這裡n為點數，m為邊數。

對於點分成兩類，1類是度數大於sqrtm的點，1類是度數小於sqrtm的點。

第一類點的個數不會超過sqrtm個，所以我們可以通過三重循環枚舉尋找所有三個點都是第一類點的三元環，這一塊的複雜度是O(msqrtm)。

接著計算至少包含一個第二類點的三元環個數。這裡我們用鄰接表來存儲所有邊的信息。

枚舉第二類點的任意兩條邊，判斷這兩點是否相連，這樣每條邊會被枚舉sqrtm次，因為第二類點度數不超過sqrtm，總體複雜度是O(msqrtm)。

當然，上面那種做法寫起來不太容易做到msqrtm，有可能還需要在鄰接表二分什麼的，我這裡有一種本質一樣但是更好寫的方法，這種方法是由 @真之仲間提供的。

枚舉所有點u，然後記錄一下他所有的鄰接點，枚舉他的所有鄰接點u，且u為第二類點，然後再枚舉鄰接點u的所有點s，check一下這個點s是否和最初枚舉的點u相連，這樣就枚舉出了所有的三元環（當然這裡還有一些簡單的判斷，就略過了），這樣的做法和前一個本質是一樣的。

班門弄斧一下啦，我覺得分塊演算法很神奇，兩個很簡單的暴力演算法往往能通過分塊演算法整合成一個更快的演算法。

數過每個點的三角形數目，加起來總數/3

這不就是無向圖裡求三元環的個數嗎。無需那麼暴力。

很簡單，對於每條邊，取兩個頂點，看看這兩個頂點有沒有共同的可以一跳抵達的第三個頂點，有就有一個三元環唄。

所以用一個bitset存每個頂點可以到達的頂點，然後取每條邊的兩個頂點，取出對應的bitset，做，然後數一的個數就是有多少個三角形。最後的答案要除以3因為每個頂點都計算了一次。數1的個數可以優化到常數時間。所以只需遍歷所有的邊即可。所以只需o(m)就可以了。

特別的對於本題，還需要減掉所有共線的頂點在變成拓撲圖的時候加進來的退化三角形。因為在拓撲圖裡也會表示為一個三元環。

如圖，考慮0 到 1的這條邊：

對於頂點0，可達的點是2,3,1 所以對於頂點0的bitset是 01110 每一位代表這個頂點是否可達。所以對於是可達的的是第1位，第2位，第3位（從0開始哦）

對於頂點1，可達的是點是0,2,3,4 所以對於頂點1的bitset是 11101

頂點0和頂點1有幾個三角形呢？

01110 11101 = 01100 共同頂點是第2和第3位（從0開始哦）所以有兩個三元環。

然後對每一條邊這樣處理就可以了。

0，1 2個三元環

0，2 1個三元環

0，3 1個三元環

1，2 1個三元環

1，3 1個三元環

1，4 0 個

(2+1+1+1+1+0)/3 = 2 個

所以一共有兩個三角形。

如果01 02 03 12 13 共線,那麼再減掉2個三元環。

這圖本來就是原po隨意畫然後隨意編個國家然後隨意騙一些粉絲轉發點贊的

點才58個，邊也不是很多，直線也不是很多。直接給每個直線上的點兩兩連邊，建無向無權圖，沒必要放到笛卡爾坐標系裡。因為點比較少直接用鄰接矩陣存，後邊也好判斷兩點有沒有連邊。O(n^3)複雜度枚舉每三個點，判斷是不是三個點之間都有連邊，再排除一下三點共線的情況。最後統計一下數量就好了。答案跟那個高票回答一樣，184。

python大法好，我的代碼（借用了某人的圖參照著連邊）：

def add(a, b): graph[a][b] = 1 graph[b][a] = 1


def addLine(line):

    global ans

    ans = ans - (len(line) * (len(line) - 1) * (len(line) - 2) / 6)

    for i in line:

        for j in line:

            add(i, j)
def addLines():

    addLine([1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 2])

    addLine([1, 27, 28, 29, 30, 31, 34, 35, 44, 45, 23])

    addLine([1, 14, 15, 16, 17, 18, 19, 20, 21, 3])

    addLine([2, 22, 23, 24, 25, 26, 3])

    addLine([4, 27, 14])

    addLine([5, 28, 15])

    addLine([6, 29, 16])

    addLine([6, 30, 33, 18])

    addLine([16, 30, 32, 8])

    addLine([7, 30, 17])

    addLine([7, 32, 31])

    addLine([17, 33, 31])

    addLine([8, 31, 18])

    addLine([31, 9])

    addLine([31, 58, 39, 46, 19])

    addLine([18, 58, 34, 36, 37, 11])

    addLine([18, 39, 40, 35, 41, 38, 42, 43, 2])

    addLine([18, 46, 47, 48, 49, 50, 23])

    addLine([9, 34, 40, 47, 51, 20])

    addLine([19, 51, 52, 53, 54, 24])

    addLine([10, 36, 35, 48, 52, 55, 57, 3])

    addLine([10, 37, 41, 44, 49, 53, 56, 26])

    addLine([20, 55, 56, 25])

    addLine([11, 38, 45, 50, 54, 25])

    addLine([21, 57, 26])

    addLine([12, 42, 23])

    addLine([13, 43, 22])
def main():

    global ans

    addLines()

    for a in range(1, 59):

        for b in range(a + 1, 59):

            for c in range(b + 1, 59):

                if (graph[a][b] and graph[a][c] and graph[b][c]):

                    ans = ans + 1

    print ans
graph = [[0 for col in range(60)] for row in range(60)]

ans = 0

if (__name__ == "__main__"): main()

可以嘗試一下小學奧數標準方法：擦邊法

保守估計，就算10秒查一個，三個小時最多了

但準確度...

呵呵

2018.8.29更新

@Cc jiaowo 的答案應該是沒問題的，我下面的答案只是憑著印象寫出來的，沒有科學根據。只是看到這個題目時想起了一些小時候的印象。

確實最後是算和矩陣的跡有關的東西，「秩」是筆誤。

另外是小學還是初中真的不記得了，總覺得是很久以前的事情了。

————以下是錯誤的原答案，請忽略————

先寫出連接矩陣，連接的是1，沒連接的點是0。

平方，再求秩，就是三角形個數。

這點點，對計算機來說算個矩陣的平方還是小case的。

PO主說30秒內找到100個就是天才，我覺得天才的門檻好低，因為圖裡三角形太多了，別說30秒鐘，就是10秒鐘都能看出來這圖的三角形多於100個好吧！

那麼究竟有多少個，其實提問的博主並不關心，賺足評論轉發量就可以了。可惜的是數學論壇、數學答疑群等平台。真的要求出它有多少三角形，能不能辦到呢。答案顯然是能，三角形是有限個的，無疑可以數出究竟有多少三角形。但是沒有方便的計演算法，小區域可以算一下，但是區域之間以及不同區域的都要考慮進去，工作量就大了，和逐一計數差不多。

圖裡每一個頂點都有一條線段和底邊相交，然而交點卻什麼也不是（也不垂直，也不是中點），這三個交點之間只連結了一對。並且很容易看出，貓尾巴附近的線段還多畫了幾個交叉線段。

簡單來說，沒有技巧。只能一個個的數，當然你可以交給計算機去數。

出題對技術要求是很高的，題目必須是可解的，不能隨手畫就當題（娛樂博主除外）

比如：

下圖中請你數一下當中有多少正方形

（不希望以後這個題將來被當成五年級奧數題出現在娛樂博主上）

===================

怎麼辦？

這個題簡單，數不太大

2017年9月2日：

我覺得光用看找到一千個以上的都是傻子。

不知道這圖哪神奇了，只要你想你可以更神奇。

編程的話我的大概思路是盡量藉助人工記錄一些東西。首先每個點編號，有人數了是58個點。然後列一個58*58矩陣，點和點之間有直線記為1，沒有記為0（大工程，才疏學淺不知道計算機有沒有能直接判斷點和點之間是否連線的方法），得到29*57個數據（對稱，不管對角線），然後排列組合窮舉判斷三個點三條線段值是否均為1，即c（58，3）次判斷，這個活計算機來干就很簡單了。

人工數也應該是有技巧的數。首先要確定一個總的方向，從左到右，從上到下。然後一個圖塊成一個三角的有幾個，兩個圖塊合成的有幾個，有足夠耐心也能數出來。（但是不可避免的還是會漏，不如按上面的思路來無腦數穩當）

總而言之就是費時費力的題目。讓我自己去數的

我是拒絕的。

任意不共線的三點均能構成三角形。先找出一共多少個點，然後找出有多少條線段（含三個點以上），分別排列組合減一下應該就可以了

從本題可以粗略估算我乎程序員比例。。。

要點清楚到底有多少個三角形，手工應該需要很多時間。如果你能寫個程序，讓電腦應該很快就能解決。

把每一點想交的點按順序命名（1.2.3....）然後標明每個點和附近點的關係相連與否。

然後同時滿足 abc 三點互相有關係就可以定義為一個三角形。（但是還需要確認三點不能是直線）

用c寫這個程序應該會花費很多時間，用c++ 可能會容易很多，但是還沒學過。

首先，圖中58個孤立點，27條大線段（根據某些回答中得知的，錯了勿怪）。用n_Li表示第i個大線段Li上有n個點。那麼三角形的個數為：

C（58，3）-C（n_L1，3）-C（n_L2，3）-……C（n_L27，3）

你是不是這樣想的？ ?( ?? ? ?? )?這種方法是錯的，它還需要減去不在同一條直線上而且沒有連上的3點的組數。中槍的舉個手來，沒舉手說明你很聰明，感謝 @Mjx121418 的糾正。