黑马程序员技术交流社区

标题: 判断亲密数 [打印本页]
作者: 李 玉林    时间: 2012-9-11 11:58
标题: 判断亲密数
如果整数A的所有因子(包括1,不包括整数本身)之和等于整数B,并且整数B的所有因子(包括1,不包括整数本身)之和等于A,则将整数A和整数B称为亲密数.求3000以内的所有亲密数.
作者: 许庭洲    时间: 2012-9-11 13:43
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace 判断亲密数
{
      calss Program
      {
            static void Main(string[] args)
            {
                   Console.WriteLine("请输入整数A:");
                   string a1 = Console.ReadLine();
                   int A = Convert.ToInt32(a1);
                  
                   Console.WriteLine("请输入整数B:");
                   string b1 = Console.ReadLine();
                   int B = Convert.ToInt32(b1);

                    int i= 1;
                    int sum1= 0;
                    int sum2= 0;

                    while( i < =3000 )
                    {
                           if((A%i)==0)  
                           {  
                                    sum1 = sum1 +i ;//每次循环一次sum1的值在递增
                                    i++;
                           }
                           if((B%i)==0)  
                           {  
                                    sum2 = sum2 +i ;//每次循环一次sum2的值在递增
                                    i++;
                           }
                           else continue;
                    }
                    
                    if(sum1==sum2)
                    {
                            Console.WriteLine("整数A和整数B是亲密数");
                    }                  
                    esle
                    {
                            Console.WriteLine("整数A和整数B不是亲密数");
                    }                              
             }
       }
}
作者: 杨进    时间: 2012-9-20 19:07
本帖最后由 杨进 于 2012-9-21 10:27 编辑
  1. int sumI;
  2.             int sumJ;
  3.             int[] numArray = new int[3000];
  4.             for (int i = 0; i < 3000; i++)
  5.             {
  6.                 numArray[i] = i + 1;
  7.             }

  9.             for (int i = 0; i < 3000; i++)
  10.             {
  11.                 sumI = 0;
  12.                 sumJ = 0;
  13.                 if (numArray[i] == 0)
  14.                 {
  15.                     continue;
  16.                 }
  17.                 for (int h = 1; h < numArray[i]; h++)
  18.                 {
  19.                     if (numArray[i] % h == 0)
  20.                     {
  21.                         sumI += h;
  22.                     }
  23.                 }
  24.                 if (sumI <= 3000)
  25.                 {
  26.                     for (int k = 1; k < sumI; k++)
  27.                     {
  28.                         if (sumI % k == 0)
  29.                         {
  30.                             sumJ += k;
  31.                         }
  32.                     }
  33.                     if (sumJ == numArray[i] && numArray[i] != sumI)
  34.                     {
  35.                         Console.WriteLine("{0}与{1}是一对亲密数", numArray[i], sumI);
  36.                         numArray[sumI-1] = 0;
  37.                     }
  38.                 }
  39.             }
  40.             Console.ReadKey();
复制代码
作者: 李阳Leo    时间: 2012-9-22 15:05
刚好写了一个，楼上的，如果有十万个数，你就定义一个长度十万的数组？一百万呢？
  1. int num1 = 0;
  2.             int num2 = 0;
  3.             int a = 0;
  4.             int b = 0;
  5.             string tmp = "";
  6.             int count = 0;


  9.             string[] result = null;
  10.             for (int i = 1; i <= 3000; i++) {
  11.                 a = i;
  12.                 for (int j = 1; j < i; j++) {
  13.                     if (i % j == 0) {
  14.                         //i的因子和
  15.                         num1 += j;
  16.                     }
  17.                     b = num1;
  18.                 }
  19.                 //Console.WriteLine(num1.ToString());
  20.                 for (int k = 1; k < num1; k++) {
  21.                     if (b % k == 0) {
  22.                         //b的因子和
  23.                         num2 += k;
  24.                     }
  25.                 }
  26.                 //a的因子和等于b，b的因子和等于a，且a不等于b
  27.                 if (num1 == b && num2 == a && a!=b)
  28.                 {
  29.                   
  30.                   
  31.                     tmp += a + "," + b+",";
  32.                 }
  33.                 num1 = 0;
  34.                 num2 = 0;
  35.             }
  36.             //算出有几对亲密数
  37.             for (int i = 0; i < tmp.Length; i++) {
  38.                 if(tmp.Substring(i,1)==","){
  39.                     count++;
  40.                 }
  41.             }
  42.             //new一个数组存放结果
  43.             result = new string[count];
  44.             count = 0;
  45.             for (int i = 0; i < tmp.Length; i++) {
  46.                 //读取字符串，如果是逗号，标记自加
  47.                 if(tmp.Substring(i,1)==","){
  48.                     count++;
  49.                 }
  50.                 //否则将当前字符加入数组当前位置
  51.                 else {
  52.                     result[count] += tmp.Substring(i, 1);
  53.                     
  54.                 }
  55.             }
  56.             //输出1和3,5和7，以此类推
  57.             for (int i = 0; i < result.Length-2; i++) {
  58.                 if (i % 2 != 0) {
  59.                     Console.WriteLine("{0}和{1}是亲密数",result[i],result[i+2]);
  60.                     i = i + 2;
  61.                 }
  62.                
  63.             }
  64.             Console.ReadKey();
  65.            
复制代码
作者: 杨进    时间: 2012-9-23 10:19
本帖最后由 杨进 于 2012-9-23 10:30 编辑
李阳_TickTock 发表于 2012-9-22 15:05
刚好写了一个，楼上的，如果有十万个数，你就定义一个长度十万的数组？一百万呢？ ...


我倒是认为你最后输出1和3,5和7一点数学依据都没有，不过把得到的数字加上逗号存到一个字符串中这点子真不错。
而且定义一个100万的数组真的是几秒钟的事，耗时间的是后面的循环和判断，你可以试试：
int[] numArray = new int[1000000];
            for (int i = 0; i < 1000000; i++)
            {
                numArray = i + 1;
            }

1.jpg (96.94 KB, 下载次数: 86)

1.jpg
作者: 李阳Leo    时间: 2012-9-23 10:43
本帖最后由 李阳_TickTock 于 2012-9-23 10:53 编辑
杨进 发表于 2012-9-23 10:19
我倒是认为你最后输出1和3,5和7一点数学依据都没有，不过把得到的数字加上逗号存到一个字符串中这点子真 ...

输出1和3,5和7，你观察下数组里面的规律就明白了，它就是这么排列的，不管后面出来多少对亲密数，它的排列顺序都是这样

数组长度不是说时间怎么怎么长，而是空间
一个int32占用4字节的空间
1KB的内存空间就是256个int32
一百万个是3906KB，差不多4M的内存

内存空间是非常宝贵的，而用计算机来进行科学计算是不可能仅仅是百万级的，所以我认为有多少个数就声明一个长度是多少的数组是不可行的
:P



不过我刚刚才看视频发现，string是个很特殊的东西，它的值是不可改变的，每次对它改变，都会重新分配一块新的内存空间，然后指针指向新的内存空间，旧的内存空间中的内容并不会立即消除，所以我这个方法可能比你声明一个长度非常恐怖的数组更占空间{:soso_e149:}

所以结果就是，如果要计算一个1到一个非常庞大的数字中的亲密数
你的程序，一开始运行就死了
我的程序，运行了一段时间后，死了

最后，我们都死了{:soso_e101:}
作者: 杨进    时间: 2012-9-23 11:02
李阳_TickTock 发表于 2012-9-23 10:43
输出1和3,5和7，你观察下数组里面的规律就明白了，它就是这么排列的，不管后面出来多少对亲密数，它的排列 ...

到10万级别的时候，真的不是这么规律的，{:soso_e120:}

2.jpg (91.59 KB, 下载次数: 67)

2.jpg

3.jpg (22.83 KB, 下载次数: 73)

3.jpg
作者: 杨进    时间: 2012-9-23 11:08
{:soso_e103:}非常庞大的数字，你该不会搞个几百亿几千亿吧。。那超出咱的研究范围咯
作者: 李阳Leo    时间: 2012-9-23 11:20
本帖最后由 李阳_TickTock 于 2012-9-23 12:33 编辑
杨进 发表于 2012-9-23 11:02
到10万级别的时候，真的不是这么规律的，

呃，我只验证到1万，不严谨不严谨。。我现在算下一百万试试


算100万算了一个小时

输出1和3，5和7,，，，确实是没有依据的



PS：1-100万，一共有82对亲密数



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2