點對演算法
㈠ 3、離散數學的思想和知識點對計算機演算法設計、程序設計有哪些作用
離散數學課程所傳授的思想和方法，廣泛地體現在計算機科學技術及相關專業的諸領域，從科學計算到信息處理，從理論計算機科學到計算機應用技術，從計算機軟體到計算機硬體，從人工智慧到認知系統，無不與離散數學密切相關。由於數字電子計算機是一個離散結構，它只能處理離散的或離散化了的數量關系， 因此，無論計算機科學本身，還是與計算機科學及其應用密切相關的現代科學研究領域，都面臨著如何對離散結構建立相應的數學模型；又如何將已用連續數量關系建立起來的數學模型離散化，從而可由計算機加以處理。
㈡ n個點距離最短演算法
所需的演算法就是排序取中間點.
因為,
到線段兩端點的距離和最短的點必然在該線段上；將n個點按從小到大排序,則未被選中的點必須均勻分布在被選中的點的兩側,才能保證被選中的點能夠在每一對點（兩點分別在該點左側和右側）組成的線段上；
所以,
必須選擇中間點,【即：當n為奇數時,選擇第 (n+1)/2 個點；當n為偶數時,選擇第 n/2 個點或第 (n+2)/2 個點；】,才能使該點到所有點距離和最短.
x1 x2 x3 x4 x5
2 4 5 6 100
選擇中間點 x3 = 5 ,沒錯啊
㈢ ACM:給定點集S,求S中周長最小的三角形（點集中點數N<=20000),求一個復雜度可接受的演算法（n^2以下）
關於搜尋一定范圍內素數的演算法及其復雜度分析
——曾曉奇
關於素數的演算法是信息學競賽和程序設計競賽中常考的數論知識，在這里我跟大家講一下尋找一定范圍內素數的幾個演算法。看了以後相信
對大家一定有幫助。
正如大家都知道的那樣，一個數 n 如果是合數，那麼它的所有的因子不超過sqrt(n)--n的開方,那麼我們可以用這個性質用最直觀的方法
來求出小於等於n的所有的素數。
num = 0;
for(i=2; i<=n; i++)
{ for(j=2; j<=sqrt(i); j++)
if( j%i==0 ) break;
if( j>sqrt(i) ) prime[num++] = i; //這個prime[]是int型，跟下面講的不同。
}
這就是最一般的求解n以內素數的演算法。復雜度是o(n*sqrt(n))，如果n很小的話，這種演算法（其實這是不是演算法我都懷疑，沒有水平。當然沒
接觸過程序競賽之前我也只會這一種求n以內素數的方法。-_-~）不會耗時很多.
但是當n很大的時候，比如n=10000000時，n*sqrt(n)>30000000000,數量級相當大。在一般的機子它不是一秒鍾跑不出結果，它是好幾分鍾都跑不
出結果，這可不是我瞎掰的，想鍛煉耐心的同學不妨試一試~。。。。
在程序設計競賽中就必須要設計出一種更好的演算法要求能在幾秒鍾甚至一秒鍾之內找出n以內的所有素數。於是就有了素數篩法。
（我表達得不清楚的話不要罵我，見到我的時候扁我一頓我不說一句話。。。）
素數篩法是這樣的：
1.開一個大的bool型數組prime[]，大小就是n+1就可以了.先把所有的下標為奇數的標為true,下標為偶數的標為false.
2.然後：
for( i=3; i<=sqrt(n); i+=2 )
{ if(prime[i])
for( j=i+i; j<=n; j+=i ) prime[j]=false;
}
3.最後輸出bool數組中的值為true的單元的下標，就是所求的n以內的素數了。
原理很簡單，就是當i是質(素)數的時候，i的所有的倍數必然是合數。如果i已經被判斷不是質數了，那麼再找到i後面的質數來把這個質
數的倍數篩掉。
一個簡單的篩素數的過程：n=30。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
第 1 步過後2 4 ... 28 30這15個單元被標成false,其餘為true。
第 2 步開始：
i=3; 由於prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]標為false.
i=4; 由於prime[4]=false,不在繼續篩法步驟。
i=5; 由於prime[5]=true, 把prime[10],[15],[20],[25],[30]標為false.
i=6>sqrt(30)演算法結束。
第 3 步把prime[]值為true的下標輸出來：
for(i=2; i<=30; i++)
if(prime[i]) printf("%d ",i);
結果是 2 3 5 7 11 13 17 19 23 29
這就是最簡單的素數篩選法，對於前面提到的10000000內的素數，用這個篩選法可以大大的降低時間復雜度。把一個只見黑屏的演算法
優化到立竿見影，一下就得到結果。關於這個演算法的時間復雜度，我不會描述，沒看到過類似的記載。只知道演算法書上如是說：前幾年比
較好的演算法的復雜度為o(n),空間復雜度為o(n^(1/2)/logn).另外還有時間復雜度為o(n/logn),但空間復雜度為O(n/(lognloglogn))的演算法。
我水平有限啦，自己分析不來。最有說服力的就是自己上機試一試。下面給出這兩個演算法的程序：
//最普通的方法：
#include<stdio.h>
#include<math.h>
#define N 10000001
int prime[N];
int main()
{
int i, j, num = 0;
for(i=2; i<N; i++)
{ for(j=2; j<=sqrt(i); j++)
if( j%i==0 ) break;
if( j>sqrt(i) ) prime[num++] = i;
}
for(i=2; i<100; i++) //由於輸出將佔用太多io時間，所以只輸出2-100內的素數。可以把100改為N
if( prime[i] )printf("%d ",i);
return 0;
}
//用了篩法的方法：
#include<stdio.h>
#include<math.h>
#define N 10000001
bool prime[N];
int main()
{
int i, j;
for(i=2; i<N; i++)
if(i%2) prime[i]=true;
else prime[i]=false;
for(i=3; i<=sqrt(N); i++)
{ if(prime[i])
for(j=i+i; j<N; j+=i) prime[i]=false;
}
for(i=2; i<100; i++)//由於輸出將佔用太多io時間，所以只輸出2-100內的素數。可以把100改為N
if( prime[i] )printf("%d ",i);
return 0;
}
裝了vc的同學上機跑一下這兩個程序試一試。這個差別，絕對是天上地下。前面那個程序絕對是n分鍾黑屏的說。
另外，對於這樣的篩法，還可以進一步優化，就是bool型數組裡面只存奇數不存偶數。如定義prime[N],則0表示
3，1表示5，2表示7，3表示9...。如果prime[0]為true,則表示3時素數。prime[3]為false意味著9是合數。
這樣的優化不是簡單的減少了一半的循環時間，比如按照原始的篩法，數組的下標就對應數。則在計算30以內素
數的時候3個步驟加起來走了15個單位時間。但是用這樣的優化則是這樣：
則由於只存3 5 7 9 11 13 15 17 19 21 23 25 27 29，只需要14個單元
第 1 步 把14個單元賦為true (每個單元代表的數是2*i+3,如第0單元代表3，第1單元代表5...)
第 2 步開始：
i=0; 由於prime[0]=true, 把 [3], [6], [9], [12]標為false.
i=1; 由於prime[1]=true, 把 [6], [11]標為false
i=2 2*i+3>sqrt(30)演算法結束。
這樣優化以後總共只走6個單位時間。
當n相當大以後這樣的優化效果就更加明顯，效率絕對不僅僅是翻倍。
出了這樣的優化以外，另外在每一次用當前已得出的素數篩選後面的數的時候可以一步跳到已經被判定不是素數的
數後面，這樣就減少了大量的重復計算。（比如我們看到的，i=0與i=1時都標了[6],這個就是重復的計算。）
我們可以發現一個規律，那就是3（即i=0）是從下標為[3]的開始篩的，5（即i=1）是從下標為[11]開始篩的（因為[6]
已經被3篩過了）。然後如果n很大的話，繼續篩。7（i=2）本來應該從下標為[9]開始篩，但是由於[9]被篩過了，而
[16]也已經被5（i=1）篩過了。於是7（i=2）從[23]（就是2*23+3=49）開始篩。
於是外圍循環為i時，內存循環的篩法是從 i+(2*i+3)*(i+1)即i*(2*i+6)+3開始篩的。
這個優化也對演算法復雜度的降低起到了很大的作用。
相比於一般的篩法，加入這兩個優化後的篩法要高效很多。高興去的同學可以試著自己編寫程序看一看效率。我這里
有程序，需要的可以向我要。不懂得也可以問我。
上面的素數篩法是所有程序設計競賽隊員都必須掌握的，而後面加了兩個優化的篩法是效率很高的演算法，是湖南大學
huicpc39同學設計的（可能是學來的，也可能是自創的。相當強悍）。在數量級更大的情況下就可以發現一般篩法和
優化後的篩法的明顯區別。
另外，台灣的ACMTino同學也給我介紹了他的演算法：a是素數，則下一個起點是a*a,把後面的所有的a*a+2*i*a篩掉。
這上面的所有的素數篩選的演算法都可以再進一步化為二次篩選法，就是欲求n以內的素數，就先把sqrt(n)內的素數求
出來，用已經求得的素數來篩出後面的合數。
我把一般的篩選法的過程詳細的敘述了一遍，應該都懂了吧？後面的優化過程及不同的方法，能看懂最好。不是很難的。
相關知識：
最大公約數只有1和它本身的數叫做質數（素數）——這個應該知道吧？-_-b
至今為止，沒有任何人發現素數的分布規律，也沒有人能用一個公式計算出所有的素數。關於素數的很多的有趣的性質或者科學家的努力
我不在這里多說，大家有興趣的話可以到網路或google搜一下。我在下面列出了一個網址，上面只有個大概。更多的知識需要大家一點一點
地動手收集。
http://www.scitom.com.cn/discovery/universe/home01.html
1.高斯猜測，n以內的素數個數大約與n/ln(n)相當，或者說，當n很大時，兩者數量級相同。這就是著名的素數定理。
2.十七世紀費馬猜測，2的2^n次方+1，n=0，1，2…時是素數，這樣的數叫費馬素數，可惜當n=5時，2^32+1就不是素數，
至今也沒有找到第六個費馬素數。
3.18世紀發現的最大素數是2^31-1，19世紀發現的最大素數是2^127-1，20世紀末人類已知的最大素數是2^859433-1，用十進製表示，這是一個258715位的數字。
4.孿生素數猜想：差為2的素數有無窮多對。目前知道的最大的孿生素數是1159142985×2^2304－1和1159142985×2^2304＋1。
5.歌德巴赫猜想：大於2的所有偶數均是兩個素數的和，大於5的所有奇數均是三個素數之和。其中第二個猜想是第一個的自然推論，因此歌德巴赫猜想又被稱為1+1問題。我國數學家陳景潤證明了1+2，即所有大於2的偶數都是一個素數和只有兩個素數因數的合數的和。國際上稱為陳氏定理。
㈣ 地理中對跖點的演算法，求詳細經過，舉個例子，一定要詳細經過，我地理學的撇，求詳細，謝謝
地理中對跖點就是這個地點關於地心的對稱點。計算一個地點關於地心的對稱點位置時，把南北緯度互換，把經度換成與該地點相差180°即可。例如計算北緯40°，東經120°關於地心對稱的位置，把北緯換成南緯，即南緯40°，把經度換成相差180°的，就是西經60° 。
㈤ 用C++寫的分治演算法求最近點對的問題，求高手解答！ 出錯提示：訪問沖突
重新檢查你程序中的數組使用，是否越界，還是指針指向的內存空間有問題，因為你給的是程序的片段，所以無法幫你調試運行，只能夠看了之後提出建議，謝謝！
祝你成功~~~
㈥ 24點的演算法技巧
1、利用3×8＝24、4×6＝24求解。
把牌面上的四個數想辦法湊成3和8、4和6，再相乘求解。如3、3、6、10可組成（10—6÷3）×3＝24等。又如2、3、3、7可組成（7＋3—2）×3＝24等。實踐證明，這種方法是利用率最大、命中率最高的一種方法。
2、利用0、11的運算特性求解。
如3、4、4、8可組成3×8＋4—4＝24等。又如4、5、J、K可組成11×（5—4）＋13＝24等。
3、在有解的牌組中，用得最為廣泛的是以下六種解法：（我們用a、b、c、d表示牌面上的四個數）
①(a—b）×（c＋d）
如（10—4）×（2＋2）＝24等。
②（a＋b）÷c×d
如（10＋2）÷2×4＝24等。
③（a－b÷c）×d
如（3—2÷2）×12＝24等。
④（a＋b－c）×d
如（9＋5—2）×2＝24等。
⑤a×b＋c—d
如11×3＋l—10＝24等。
⑥（a－b）×c＋d
如（4—1）×6＋6＝24等。
(6)點對演算法擴展閱讀
乘法是加法的簡便運算，除法是減法的簡便運算。
減法與加法互為逆運算，除法與乘法互為逆運算。
整數的加減法運演算法則：
1、相同數位對齊；
2、從個位算起；
3、加法中滿幾十就向高一位進幾；減法中不夠減時，就從高一位退1當10和本數位相加後再減。
加法運算性質
從加法交換律和結合律可以得到：幾個加數相加，可以任意交換加數的位置；或者先把幾個加數相加再和其他的加數相加，它們的和不變。例如：34+72+66+28=(34+66)+(72+28)=200。
㈦ 二十四點演算法是什麼
例如：4個數A、B、C、D，我們可以用F(A,B,C,D)=24來表示。那麼。我們就可以把函數F拆解成F1(B,C,D)=P1(24,A)。（意思是：B，C，D之間的四則運算可以得到A和24之間的四則運算結果）。那麼F1又可以繼續拆解為C和D之間的四則運算關系得到結果後再和B來一次四則運算結果。這樣，就可以得到很簡單的一個數組6*6*6=216種結果而已。當然，這是A，B，C，D順序固定的組合，那麼把A，B，C，D換個位置，又一種組合。所以，所有的結果有6*6*6*12種。但，我們還是忽略了一種情況：A和B的值與C和D的值再進行四則運算，那麼我們還需要再加一組6*6*6就可以了。
㈧ 如何對點進行k均值聚類演算法 matlab
在聚類分析中,K-均值聚類演算法（k-means algorithm）是無監督分類中的一種基本方法,其也稱為C-均值演算法,其基本思想是：通過迭代的方法,逐次更新各聚類中心的值,直至得到最好的聚類結果.\x0d假設要把樣本集分為c個類別,演算法如下：\x0d（1）適當選擇c個類的初始中心；\x0d（2）在第k次迭代中,對任意一個樣本,求其到c個中心的距離,將該樣本歸到距離最短的中心所在的類,\x0d（3）利用均值等方法更新該類的中心值；\x0d（4）對於所有的c個聚類中心,如果利用（2）（3）的迭代法更新後,值保持不變,則迭代結束,否則繼續迭代.\x0d下面介紹作者編寫的一個分兩類的程序,可以把其作為函數調用.\x0d%% function [samp1,samp2]=kmeans(samp); 作為調用函數時去掉注釋符\x0dsamp=[11.1506 6.7222 2.3139 5.9018 11.0827 5.7459 13.2174 13.8243 4.8005 0.9370 12.3576]; %樣本集\x0d[l0 l]=size(samp);\x0d%%利用均值把樣本分為兩類,再將每類的均值作為聚類中心\x0dth0=mean(samp);n1=0;n2=0;c1=0.0;c1=double(c1);c2=c1;for i=1:lif samp(i)<th0\x0dc1=c1+samp(i);n1=n1+1;elsec2=c2+samp(i);n2=n2+1;endendc1=c1/n1;c2=c2/n2; %初始聚類中心t=0;cl1=c1;cl2=c2;\x0dc11=c1;c22=c2; %聚類中心while t==0samp1=zeros(1,l);\x0dsamp2=samp1;n1=1;n2=1;for i=1:lif abs(samp(i)-c11)<abs(samp(i)-c22)\x0dsamp1(n1)=samp(i);\x0dcl1=cl1+samp(i);n1=n1+1;\x0dc11=cl1/n1;elsesamp2(n2)=samp(i);\x0dcl2=cl2+samp(i);n2=n2+1;\x0dc22=cl2/n2;endendif c11==c1 && c22==c2t=1;endcl1=c11;cl2=c22;\x0dc1=c11;c2=c22;\x0dend %samp1,samp2為聚類的結果.\x0d初始中心值這里採用均值的辦法,也可以根據問題的性質,用經驗的方法來確定,或者將樣本集隨機分成c類,計算每類的均值.\x0dk-均值演算法需要事先知道分類的數量,這是其不足之處.
㈨ Floyd演算法是什麼
Floyd演算法又稱為弗洛伊德演算法，插點法，是一種用於尋找給定的加權圖中頂點間最短路徑的演算法。
通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。
從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……；最後又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個後繼節點矩陣path來記錄兩點間的最短路徑。
採用的是(鬆弛技術)，對在i和j之間的所有其他點進行一次鬆弛。所以時間復雜度為O(n^3); 其狀態轉移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]} map[i,j]表示i到j的最短距離 K是窮舉i,j的斷點 map[n,n]初值應該為0，或者按照題目意思來做。
當然，如果這條路沒有通的話，還必須特殊處理，比如沒有map[i,k]這條路
㈩ C#獲取不規則點列圖各點坐標的方法 演算法 問題
建議：
先基於原數據的點建立平面直角坐標系，確定各個點的位置
以兩列間最小間隔和兩行間最小間隔的公約數為一個區間，製作矩陣，如果不好確定，以「1」為單位製作矩陣
確定每一橫行的和每一縱列，然後進行獲取點坐標，賦值