看全色黄大色黄大片爽一下,亚洲欧洲日产韩国综合,888影视网

.Net編程自動調(diào)試監(jiān)視工具(Auto Debug For .Net)v1.5 注冊專業(yè)版

類型：編程輔助大小：1.8M語言：英文評分：6.0
標(biāo)簽：

立即下載

一直想寫這篇關(guān)于算法的文章，但是由于看到園子里眾多研究算法的高手讓我一直沒有決心寫下來，但高手歸高手，不是高手也可以寫出來讓高手們拍磚，所以今天就在這里獻(xiàn)丑了。相親數(shù)和完全數(shù)作為數(shù)學(xué)問題的確是頂級難題，可是拿來做娛樂就不同了，從剛接觸編程時(shí)C語言書上的課后習(xí)題到兩年前的Intel多核編程大賽，這個(gè)題目一直伴隨著我們，讓我們來娛樂一下吧。

簡單說一下概念，相親數(shù)是指兩個(gè)正整數(shù)中，彼此的全部約數(shù)之和（本身除外）與另一方相等。舉例來說：

220的全部約數(shù)(除掉本身)相加是：1+2+4+5+10+11+20+22+44+55+110=284

284的全部約數(shù)(除掉本身)相加的和是：1+2+4+71+142=220

所以220和284就是一對相親數(shù)。

那什么是完全數(shù)呢？即它所有的真因子（即除了自身以外的約數(shù)）的和恰好等于它本身。例如：

第一個(gè)完全數(shù)是6，它有約數(shù)1、2、3、6，除去它本身6外，其余3個(gè)數(shù)相加，1+2+3=6

第二個(gè)完全數(shù)是28，它有約數(shù)1、2、4、7、14、28，除去它本身28外，其余5個(gè)數(shù)相加，1+2+4+7+14=28

概念不多說了，直接上算法。

算法一：直接計(jì)算約數(shù)之和

這是最直接的方式了，循環(huán)計(jì)算所有可能成為約數(shù)的數(shù)字然后加和，直接到不用做過多的解釋，只要會寫程序，用任何語言都能實(shí)現(xiàn)！

1: /// <summary>
2: /// 直接計(jì)算約數(shù)之和(串行)
3: /// </summary>
4: public class Algorithm1
5: {
6: private int GetSum(int num)
7: {
8: int sum = 1;
9: int limit = (int)Math.Sqrt(num);
10: for (int i = 2; i <= limit; i++)
11: if (num % i == 0) sum += i + num / i;
12: return sum;
13: }
14:
15: public void Run(int from, int to)
16: {
17: int perfertCount = 0;
18: int amicablePairCount = 0;
19: for (int num = from; num <= to; num++)
20: {
21: int sum1 = this.GetSum(num);
22: if (sum1 == num)
23: {
24: Console.WriteLine("{0}是完全數(shù)", num);
25: perfertCount++;
26: }
27: if (sum1 > num)
28: {
29: int sum2 = this.GetSum(sum1);
30: if (sum2 == num)
31: {
32: Console.WriteLine("{0}和{1}是一對相親數(shù)", sum1, sum2);
33: amicablePairCount++;
34: }
35: }
36: }
37: Console.WriteLine("在{0}到{1}中共有{2}個(gè)完全數(shù)和{3}對相親數(shù)", from, to, perfertCount, amicablePairCount);
38: }
39: } 測試代碼，從2計(jì)算到5000000：

1: static void Main(string[] args)
2: {
3: var stopwatch = Stopwatch.StartNew();
4: Algorithm1 algorithm = new Algorithm1();
5: algorithm.Run(2, 5000000);
6: stopwatch.Stop();
7: Console.WriteLine("計(jì)算完成共花費(fèi){0}秒", stopwatch.Elapsed.TotalSeconds);
8: Console.ReadKey();
9: } 在我的ThinkPad R400上測試運(yùn)行時(shí)間大概在51秒左右，速度能不能再提高呢，讓我們看看.Net4.0為我們帶來的并行計(jì)算的新特性表現(xiàn)如何。

1: /// <summary>
2: /// 直接計(jì)算約數(shù)之和(并行)
3: /// </summary>
4: public class Algorithm2
5: {
6: private int GetSum(int num)
7: {
8: int sum = 1;
9: int limit = (int)Math.Sqrt(num);
10: for (int i = 2; i <= limit; i++)
11: if (num % i == 0) sum += i + num / i;
12: return sum;
13: }
14:
15: public void Run(int from, int to)
16: {
17: int perfertCount = 0;
18: int amicablePairCount = 0;
19: Parallel.For(from, to, num =>
20: {
21: int sum1 = this.GetSum(num);
22: if (sum1 == num)
23: {
24: Console.WriteLine("{0}是完全數(shù)", num);
25: perfertCount++;
26: }
27: if (sum1 > num)
28: {
29: int sum2 = this.GetSum(sum1);
30: if (sum2 == num)
31: {
32: Console.WriteLine("{0}和{1}是一對相親數(shù)", sum1, sum2);
33: amicablePairCount++;
34: }
35: }
36: });
37: Console.WriteLine("在{0}到{1}中共有{2}個(gè)完全數(shù)和{3}對相親數(shù)", from, to, perfertCount, amicablePairCount);
38: }
39: } 注意第19行，我們使用System.Threading.Tasks下的Parallel類取代傳統(tǒng)的for循環(huán)，由于在該算法中每一次計(jì)算都是獨(dú)立的，所以很適合并行，廢話不多說，直接運(yùn)行看結(jié)果，運(yùn)行時(shí)間在26秒左右，由于我的機(jī)器是雙核，所以同樣是從2計(jì)算到5000000，并行的時(shí)間差不多是之前的(51秒)一半，看來Parallel真是不錯的新工具�。‘�(dāng)然，這個(gè)是從技術(shù)上達(dá)到了速度的提升，算法本質(zhì)還沒有變，那能不能從算法本身提高計(jì)算效率呢？答案當(dāng)然是肯定的！