《关于求约数的算法》

来源：百度知道 编辑：UC知道 时间：2024/05/09 01:28:25
如果一个数x的约数和（不包括它本身，下同）比它本身小，那么x可以变成它的约数和；如果对于某个y>x且y的约数和为x，那么x也可以变成y。例如，4可以变为3，1可以变为7。限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没有重复数字出现的最多变换步数。

样例说明
4→3→1→7。
-----------------------------------------------------------

麻烦各位写出算法，或者给出C语言源程序。多谢了 。

4->3 (1+2)
3->1 (1)
1->7 (7>1且约数只有1所以)

化成一个图的问题.

从1到n的数字是这个图的顶点集.
根据题意,当x可以变成y时,y也可以变成x,所以每一组这样的x,y,可以用一条无向边连接这两个顶点.
最后,当整个图构造完成以后,找出图中的最长路径就可以了.
这些算法在数据结构教材都可以找到,就不多说了.

下面是算法的大概步骤:(用邻接表存储)
首先建立顶点集,值为1,2,...,n.
然后从1到n循环,对每个数x求出其因子总和y,建立从x到y的边及y到x的边.
最后(用深度优先遍历?)求出最长路径的长度.

OVER.
至于代码...就略了吧....

你没说清1是怎么变成7的，或者7是怎么来的

说清楚就能做了