程序员编程艺术 第六章 求解500万以内的亲和数
分享一下我老师大神的人工智能教程！零基础，通俗易懂！http://blog.csdn.net/jiangjunshow
也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！
第六章、亲和数问题--求解500万以内的亲和数
作者：上善若水、July、yansha。
出处：http://blog.csdn.net/v_JULY_v 。
前奏
本章陆续开始，除了继续保持原有的字符串、数组等面试题之外，会有意识的间断性节选一些有关数字趣味小而巧的面试题目，重在突出思路的“巧”，和“妙”。本章亲和数问题之关键字，“500万”，“线性复杂度”。
第一节、亲和数问题
题目描述：
求500万以内的所有亲和数
如果两个数a和b，a的所有真因数之和等于b,b的所有真因数之和等于a,则称a,b是一对亲和数。
例如220和284，1184和1210，2620和2924。
分析：
首先得明确到底是什么是亲和数?
亲和数问题最早是由毕达哥拉斯学派发现和研究的。他们在研究数字的规律的时候发现有以下性质特点的两个数：
220的真因子是：1、2、4、5、10、11、20、22、44、55、110；
284的真因子是：1、2、4、71、142。
而这两个数恰恰等于对方的真因子各自加起来的和（sum[i]表示数i 的各个真因子的和），即
220=1+2+4+71+142=sum[284],
284=1+2+4+5+10+11+20+22+44+55+110=sum[220]。
得284的真因子之和sum[284]=220，且220的真因子之和sum[220]=284，即有sum[220]=sum[sum[284]]=284。
如此，是否已看出丝毫端倪?
如上所示，考虑到1是每个整数的因子，把出去整数本身之外的所有因子叫做这个数的“真因子”。如果两个整数，其中每一个真因子的和都恰好等于另一个数，那么这两个数，就构成一对“亲和数”（有关亲和数的更多讨论，可参考这：http://t.cn/hesH09）。
求解：
了解了什么是亲和数，接下来咱们一步一步来解决上面提出的问题（以下内容大部引自水的原话，同时水哥有一句原话，“在你真正弄弄懂这个范例之前，你不配说你懂数据结构和算法”）。
第二节、伴随数组线性遍历
依据上文中的第3点思路，编写如下代码：
//求解亲和数问题//第一个for和第二个for循环是logn（调和级数）*N次遍历,第三个for循环扫描O（N）。//所以总的时间复杂度为 O（n*logn）+O（n）=O（N*logN）（其中logN为调和级数）。//关于第一个for和第二个for寻找中，调和级数的说明：//比如给2的倍数加2，那么应该是 n/2次，3的倍数加3 应该是 n/3次，...//那么其实就是n*（1+1/2+1/3+1/4+...1/(n/2)）=n*（调和级数）=n*logn。//copyright@ 上善若水//July、updated，2011.05.24。#include<stdio.h>int sum[5000010]; //为防越界int main() { int i, j; for (i = 0; i <= 5000000; i++) sum[i] = 1; //1是所有数的真因数所以全部置1 for (i = 2; i + i <= 5000000; i++) //预处理，预处理是logN（调和级数）*N。 //@litaoye：调和级数1/2 + 1/3 + 1/4......的和近似为ln(n)， //因此O(n *(1/2 + 1/3 + 1/4......)) = O(n * ln(n)) = O(N*log(N))。 { //5000000以下最大的真因数是不超过它的一半的 j = i + i; //因为真因数，所以不能算本身，所以从它的2倍开始 while (j <= 5000000) { //将所有i的倍数的位置上加i sum[j] += i; j += i; } } for (i = 220; i <= 5000000; i++) //扫描，O（N）。 { // 一次遍历，因为知道最小是220和284因此从220开始 if (sum[i] > i && sum[i] <= 5000000 && sum[sum[i]] == i) { //去重，不越界，满足亲和 printf("%d %d/n",i,sum[i]); } } return 0;}
运行结果：
@上善若水：
1、可能大家理解的还不是很清晰，我们建立一个5 000 000 的数组，从1到2 500 000 开始，在每一个下标是i的倍数的位置上加上i，那么在循环结束之后，我们得到的是什么？是 类似埃斯托拉晒求素数的数组（当然里面有真的亲和数），然后只需要一次遍历就可以轻松找到所有的亲和数了。时间复杂度，线性。
2、我们可以清晰的发现连续数据的映射可以通过数组结构本身的特点替代，用来节约空间，这是数据结构的艺术。在大规模连续数据的回溯处理上，可以通过转化为递推生成的方法，逆向思维操作，这是算法的艺术。
3、把最简单的东西运用的最巧妙的人，要比用复杂方法解决复杂问题的人要头脑清晰。
第三节、程序的构造与解释
我再来具体解释下上述程序的原理，ok，举个例子，假设是求10以内的亲和数，求解步骤如下：
因为所有数的真因数都包含1，所以，先在各个数的下方全部置1
然后取i=2,3,4,5（i<=10/2），j依次对应的位置为j=（4、6、8、10），（6、9）,（8）,（10）各数所对应的位置。依据j所找到的位置，在j所指的各个数的下面加上各个真因子i（i=2、3、4、5）。整个过程，即如下图所示（如sum[6]=1+2+3=6，sum[10]=1+2+5=8.）：
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1
2 2 2 2
3 3
4
5然后一次遍历i从220开始到5000000，i每遍历一个数后，
将i对应的数下面的各个真因子加起来得到一个和sum[i]，如果这个和sum[i]==某个i’，且sum[i‘]=i，
那么这两个数i和i’，即为一对亲和数。i=2；sum[4]+=2，sum[6]+=2，sum[8]+=2，sum[10]+=2，sum[12]+=2...
i=3，sum[6]+=3，sum[9]+=3...
......i=220时，sum[220]=284，i=284时，sum[284]=220；即sum[220]=sum[sum[284]]=284，
得出220与284是一对亲和数。所以，最终输出220、284，...
特别鸣谢
litaoye专门为本亲和数问题开帖子继续阐述，有兴趣的朋友可继续参见：http://topic.csdn.net/u/20110526/21/129c2235-1f44-42e9-a55f-878920c21e19.html。同时，任何人对本亲和数问题有任何问题，也可以回复到上述帖子上。
using System; using System.Collections.Generic; namespace CSharpTest { class Program { public static void Main() { int max = 5000000; DateTime start = DateTime.Now; int[] counter = CreateCounter(max); for (int i = 0; i < counter.Length; i++) { int num = counter[i] - i; } Console.WriteLine((DateTime.Now - start).TotalSeconds); Console.ReadKey(); } static int[] CreateCounter(int n) { List<int> primes = new List<int>(); int[] counter = new int[n + 1]; counter[1] = 1; for (int i = 2; i <= n; i++) { if (counter[i] == 0) { counter[i] = i + 1; primes.Add(i); } for (int j = 0; j < primes.Count; j++) { if (primes[j] * i > n) break; if (i % primes[j] == 0) { int k = i; int l = primes[j] * primes[j]; while (k % primes[j] == 0) { l *= primes[j]; k /= primes[j]; } counter[primes[j] * i] = counter[k] * (l - 1) / (primes[j] - 1); break; } else counter[primes[j] * i] = counter[i] * (primes[j] + 1); } } return counter; } } } //求解亲和数问题//copyright@ litaoye//July、胡滨，updated，2011.05.26。using System;using System.Collections.Generic;namespace CSharpTest{ class Program { public static void Main() { int max = 5000000; DateTime start = DateTime.Now; int[] counter = CreateCounter(max); for (int i = 0; i < counter.Length; i++) { int num = counter[i] - i; //if (num < counter.Length && num > i && counter[num] == counter[i]) // Console.WriteLine("{0} {1}", i, num); } Console.WriteLine((DateTime.Now - start).TotalSeconds); Console.ReadKey(); } static int[] CreateCounter(int n) { List<int> primes = new List<int>(); int[] counter = new int[n + 1]; counter[1] = 1; for (int i = 2; i <= n; i++) { if (counter[i] == 0) { counter[i] = i + 1; primes.Add(i); } for (int j = 0; j < primes.Count; j++) { if (primes[j] * i > n) break; if (i % primes[j] == 0) { int k = i; int l = primes[j] * primes[j]; while (k % primes[j] == 0) { l *= primes[j]; k /= primes[j]; } counter[primes[j] * i] = counter[k] * (l - 1) / (primes[j] - 1); break; } else counter[primes[j] * i] = counter[i] * (primes[j] + 1); } } return counter; } }}/*测试结果：0.484375 0.4843750.46875单位second。*/本章完。
3.3续、求给定区间内的第K小（大）元素 第九章、闲话链表追赶问题 第十章、如何给10^7个数据量的磁盘文件排序
面试题征集令
十三个经典算法研究系列+附、红黑树系列（国内有史以来最为经典的红黑树教程），共计20+6=26篇文章，带目录+标签的PDF文档，耗时近一个星期，足足346页（够一本书的分量了），已在花明月暗的帮助下，正式制作完成。想要的，发一道你自认为较好的面试题（c，c++，数据结构，算法，智力题，数字逻辑或运算题）至我的邮箱：zhoulei0907@yahoo.cn，即可。我收到后，三天之内传送此PDF文件。July、20110.5.24.此声明永久有效。版权所有，本人对本blog内所有任何内容享有版权及著作权。实要转载，请以链接形式注明出处。
给我老师的人工智能教程打call！http://blog.csdn.net/jiangjunshow
你好！ 这是你第一次使用 **Markdown编辑器** 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。
新的改变
我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：
全新的界面设计 ，将会带来全新的写作体验；在创作中心设置你喜爱的代码高亮样式，Markdown 将代码片显示选择的高亮样式 进行展示；增加了 图片拖拽 功能，你可以将本地的图片直接拖拽到编辑区域直接展示；全新的 KaTeX数学公式 语法；增加了支持甘特图的mermaid语法1 功能；增加了 多屏幕编辑 Markdown文章功能；增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能，功能按钮位于编辑区域与预览区域中间；增加了 检查列表 功能。功能快捷键
撤销：Ctrl/Command + Z
重做：Ctrl/Command + Y
加粗：Ctrl/Command + B
斜体：Ctrl/Command + I
标题：Ctrl/Command + Shift + H
无序列表：Ctrl/Command + Shift + U
有序列表：Ctrl/Command + Shift + O
检查列表：Ctrl/Command + Shift + C
插入代码：Ctrl/Command + Shift + K
插入链接：Ctrl/Command + Shift + L
插入图片：Ctrl/Command + Shift + G
合理的创建标题，有助于目录的生成
直接输入1次#，并按下space后，将生成1级标题。
输入2次#，并按下space后，将生成2级标题。
以此类推，我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。
如何改变文本的样式
强调文本 强调文本
加粗文本 加粗文本
标记文本
删除文本
引用文本
H2O is是液体。
210 运算结果是 1024.
插入链接与图片
链接: link.
图片:
带尺寸的图片:
当然，我们为了让用户更加便捷，我们增加了图片拖拽功能。
如何插入一段漂亮的代码片
去博客设置页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.
// An highlighted block var foo = 'bar';
生成一个适合你的列表
项目 项目 项目 项目1项目2项目3 计划任务 完成任务创建一个表格
一个简单的表格是这么创建的：
设定内容居中、居左、居右使用:---------:居中
使用:----------居左
使用----------:居右
SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如：
TYPEASCIIHTMLSingle backticks'Isn't this fun?'‘Isn’t this fun?’Quotes"Isn't this fun?"“Isn’t this fun?”Dashes-- is en-dash, --- is em-dash– is en-dash, — is em-dash创建一个自定义列表
Markdown Text-to- HTML conversion tool Authors John Luke如何创建一个注脚
一个具有注脚的文本。2
注释也是必不可少的
Markdown将文本转换为 HTML。
KaTeX数学公式
您可以使用渲染LaTeX数学表达式 KaTeX:
Gamma公式展示 Γ ( n ) = ( n − 1 ) ! ∀ n ∈ N Gamma(n) = (n-1)!quadforall ninmathbb N Γ(n)=(n−1)!∀n∈N 是通过欧拉积分
Γ ( z ) = ∫ 0 ∞ t z − 1 e − t d t   . Gamma(z) = int_0^infty t^{z-1}e^{-t}dt,. Γ(z)=∫0∞tz−1e−tdt.
你可以找到更多关于的信息 LaTeX 数学表达式here.
新的甘特图功能，丰富你的文章
gantt dateFormat YYYY-MM-DD title Adding GANTT diagram functionality to mermaid section 现有任务 已完成 :done, des1, 2014-01-06,2014-01-08 进行中 :active, des2, 2014-01-09, 3d 计划一 : des3, after des2, 5d 计划二 : des4, after des3, 5d 12345678 关于 甘特图 语法，参考 这儿,
UML 图表
可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图：:
张三 李四 王五
你好！李四, 最近怎么样? 你最近怎么样，王五？ 我很好，谢谢! 我很好，谢谢! 李四想了很长时间, 文字太长了 不适合放在一行. 打量着王五... 很好... 王五, 你怎么样? 张三 李四 王五
这将产生一个流程图。:
关于 Mermaid 语法，参考 这儿,FLowchart流程图
我们依旧会支持flowchart的流程图：
关于 Flowchart流程图 语法，参考 这儿.导出与导入
导出如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ，生成一个.md文件或者.html文件进行本地保存。
导入如果你想加载一篇你写过的.md文件或者.html文件，在上方工具栏可以选择导入功能进行对应扩展名的文件导入，
继续你的创作。
mermaid语法说明 ↩︎
注脚的解释 ↩︎
相关知识
程序员编程艺术 第六章 求解500万以内的亲和数
JAVA编程艺术
元编程艺术，第 1 部分: 元编程简介
程序员修炼之道
女神节，我们用scratch（图形化编程工具）为女神绘制一朵玫瑰花吧
BLOOM鲜花网：七夕爆红的背后，是500万核心用户的支持
JavaScript+DOM编程艺术总结
人人学习网 – 第21页 – 专注于Web开发技术&互联网&PHP编程
MA2灯光秀编程精通课程
用于植物细胞的细胞重编程的系统和方法与流程
网址: 程序员编程艺术 第六章 求解500万以内的亲和数 https://m.huajiangbk.com/newsview104757.html
| 上一篇: 开花流水 |
下一篇: 一30岁青工，原有发作性意识丧失 |
