- 類型：編程輔助大�。�1.8M語言：英文 評分：6.0
- 標(biāo)簽：
一直想寫這篇關(guān)于算法的文章，但是由于看到園子里眾多研究算法的高手讓我一直沒有決心寫下來，但高手歸高手，不是高手也可以寫出來讓高手們拍磚，所以今天就在這里獻丑了。相親數(shù)和完全數(shù)作為數(shù)學(xué)問題的確是頂級難題，可是拿來做娛樂就不同了，從剛接觸編程時C語言書上的課后習(xí)題到兩年前的Intel多核編程大賽，這個題目一直伴隨著我們，讓我們來娛樂一下吧。
簡單說一下概念，相親數(shù)是指兩個正整數(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ù)）的和恰好等于它本身。例如：
第一個完全數(shù)是6，它有約數(shù)1、2、3、6，除去它本身6外，其余3個數(shù)相加，1+2+3=6
第二個完全數(shù)是28，它有約數(shù)1、2、4、7、14、28，除去它本身28外，其余5個數(shù)相加，1+2+4+7+14=28
概念不多說了，直接上算法。
算法一：直接計算約數(shù)之和
這是最直接的方式了，循環(huán)計算所有可能成為約數(shù)的數(shù)字然后加和，直接到不用做過多的解釋，只要會寫程序，用任何語言都能實現(xiàn)！
1: /// <summary>
2: /// 直接計算約數(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}個完全數(shù)和{3}對相親數(shù)", from, to, perfertCount, amicablePairCount);
38: }
39: } 測試代碼，從2計算到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("計算完成共花費{0}秒", stopwatch.Elapsed.TotalSeconds);
8: Console.ReadKey();
9: } 在我的ThinkPad R400上測試運行時間大概在51秒左右，速度能不能再提高呢，讓我們看看.Net4.0為我們帶來的并行計算的新特性表現(xiàn)如何。
1: /// <summary>
2: /// 直接計算約數(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}個完全數(shù)和{3}對相親數(shù)", from, to, perfertCount, amicablePairCount);
38: }
39: } 注意第19行，我們使用System.Threading.Tasks下的Parallel類取代傳統(tǒng)的for循環(huán)，由于在該算法中每一次計算都是獨立的，所以很適合并行，廢話不多說，直接運行看結(jié)果，運行時間在26秒左右，由于我的機器是雙核，所以同樣是從2計算到5000000，并行的時間差不多是之前的(51秒)一半，看來Parallel真是不錯的新工具��！當(dāng)然，這個是從技術(shù)上達到了速度的提升，算法本質(zhì)還沒有變，那能不能從算法本身提高計算效率呢？答案當(dāng)然是肯定的！
喜歡 
頂
難過
囧
圍觀
無聊
