程序员的算法趣题：Q19 朋友的朋友也是朋友吗（Java版）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了程序员的算法趣题：Q19 朋友的朋友也是朋友吗（Java版），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5376字，纯文字阅读大概需要8分钟。

内容图文

题目描述

“六度空间理论”非常有名。大概的意思是1个人只需要通过6个中间人就可以和世界上任何1 个人产生间接联系。
本题将试着找出数字的好友（这里并不考虑亲密指数）。
假设拥有同样约数（不包括 1）的数字互为“好友”，
也就是说，如果两个数字的最大公约数不是 1，那么称这两个数互为好友。

从1~N 中任意选取一个“合数”，求从它开始，要经历几层好友，才能和其他所有的数产生联系
（所谓的“合数”是指“有除 1 以及自身以外的约数的自然数”）。
举个例子，N ＝ 10 时，1~10 的合数有4、6、8、9、10这 5 个。
如果选取的是10，那么10的好友数字就是公约数为2的4、6、8这3个。
而9是6的好友数字（公约数为3），所以10只需要经过2层就可以和 9 产生联系。
如果选取的是6，则只需经过1层就可以联系到4、8、9、10这些数字。
因此N＝10时，无论最初选取的合数是什么，最多经过2层就可以与其它所有数产生联系。

从1~N中选取7个合数，
每个数字都可以与其它的6个数字建立联系，
7个数字中关系最远的两个数字必须达到6层间接关系
求满足上述条件的最小N。

思路

1.已知：合数 = a * b; 即合数一定可以表示成两个数字相乘的形式，且a和b都不为1
2.如果 n1 = a * b; n2 = b * c; 则n1和n2是好友（有公约数b，且b不为1）
3.若要达到6层间接关系，则这7个数字一定满足如下形式：
    a*b, b*c, c*d, d*e, e*f, f*g, g*h 且a~h必须互质，否则不满足“达到6层间接关系”
  此时：
  1) 每个数字都能与其它数字建立联系
  2) 7个数字中关系最远的两个数字（a*b、g*h）达到了6层间接关系
4.因为要找最小N，所以：
  1) 第一个数字最好是平方数： a*a  ==> a*a, a*b, b*c, c*d, d*e, e*f, f*g
  2) 最后一个数字最好也是平方数： f*f  ==> a*a, a*b, b*c, c*d, d*e, e*f, f*f
  3) 从最小的质数开始，只需要a~f这6个即可
5.通过递归对这6个质数进行排列，尝试出所有结果，求出最小的N

代码

public static int N ; // 最小值（合数集合中的最大值）

public static void main(String[] args) {
    // 1.从小到大生成6个质数，并存入质数集合primeList
    List<Integer> primeList = new ArrayList<>();
    for (int i = 2; primeList.size() < 6; i++) {
        if (isPrime(i)) { // 如果是质数，则存入primeList
            primeList.add(i);
        }
    }
    System.out.println(primeList); // [2, 3, 5, 7, 11, 13]
    // 将N的初始值设置为6个质数中最大质数的平方（最小N不可能超过这个值）
    N = primeList.get(primeList.size() - 1) * primeList.get(primeList.size() - 1);

    // 2.依次从每个数字开始，罗列出所有的排列方式
    List<Integer> compList = new LinkedList<>(); // 用于保存7个合数
    for (int i = 0; i < primeList.size(); i++) {
        Integer firstNum = primeList.get(i);    
        primeList.remove(firstNum);             // 从质数集合中删除选中的数字
        compList.add(firstNum * firstNum);      // 计算平方数，并存入合数集合compList
        mul(firstNum, primeList, compList);     // 进一步递归，选择第二个、第三个...数字
        primeList.add(i, firstNum);             // 恢复原始状态，以便进行下一轮尝试
        compList.clear();                       // 恢复原始状态，以便进行下一轮尝试
    }
}

// 判断num是否为质数
private static boolean isPrime(int num) {
    // 除了1和它本身，是否还能被其它数字整除
    for (int i = 2; i < num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

/**
 * 从质数集合中取出一个数字与上一次选择的数字相乘，将乘积存入合数集合
 * @param pre       上一次选择的数字
 * @param primeList 质数集合（最初共6个数字）
 * @param compList  合数集合（最终共7个数字）
 */
private static void mul(int pre, List<Integer> primeList, List<Integer> compList) {
    // 不合法情况
    if (primeList == null || compList == null) return;

    // 递归出口：6个质数都已取完，计算出第7个合数，统计合数集合的最大值
    if (primeList.size() == 0) {                 // 此时primeList的6个质数都已经用完了，pre就是最后一次取的那个质数的值
        compList.add(pre * pre);                 // compList的最后一个数字就是pre的平方值
        int max = Collections.max(compList);     // 计算compList集合中的最大值
        if (N >= max) {                          // 当前compList集合中的最大值是目前的最小N
            N = max;                             // 更新最小N
            System.out.println("max = " + max + " ==> " + compList); // 打印该候选结果
        }
        compList.remove(new Integer(pre * pre)); // 恢复compList集合添加最后一个数字之前的状态，以便本层递归返回后，继续进行其它尝试（注意：不可直接删除pre * pre，会把pre * pre当成下标）
        return;
    }

    // 依次尝试每一种可能：依次取出质数集合中的每一个数字与pre相乘
    for (int i = 0; i < primeList.size(); i++) {
        Integer num = primeList.get(i);                 // 这一次尝试取出num
        compList.add(pre * num);                        // 相乘后添加到合数集合
        primeList.remove(num);                          // 从质数集合中删去num
        mul(num, primeList, compList);                  // 进一步递归，选择下一个数字
        primeList.add(i, num);                          // 恢复本次尝试num之前的状态
        compList.remove(new Integer(pre * num));        // 删除本次尝试的记录（注意：不可直接删除pre * num，会把pre * num当成下标）
    }
}

结果

[2, 3, 5, 7, 11, 13]
max = 169 ==> [4, 6, 15, 35, 77, 143, 169]
max = 143 ==> [4, 6, 15, 35, 91, 143, 121]
max = 143 ==> [4, 6, 15, 55, 143, 91, 49]
max = 121 ==> [4, 6, 15, 65, 91, 77, 121]
max = 121 ==> [4, 6, 21, 91, 65, 55, 121]
max = 91 ==> [4, 6, 33, 55, 65, 91, 49]
max = 91 ==> [4, 6, 33, 77, 91, 65, 25]
max = 77 ==> [4, 6, 39, 65, 55, 77, 49]
max = 77 ==> [4, 10, 65, 39, 33, 77, 49]
max = 77 ==> [4, 14, 77, 33, 39, 65, 25]
max = 77 ==> [4, 14, 77, 55, 65, 39, 9]
max = 65 ==> [4, 22, 33, 39, 65, 35, 49]
max = 65 ==> [4, 22, 55, 65, 39, 21, 49]
max = 55 ==> [4, 26, 39, 33, 55, 35, 49]
max = 55 ==> [9, 39, 26, 22, 55, 35, 49]
max = 55 ==> [25, 55, 22, 26, 39, 21, 49]
max = 55 ==> [25, 55, 33, 39, 26, 14, 49]
max = 55 ==> [49, 14, 26, 39, 33, 55, 25]
max = 55 ==> [49, 21, 39, 26, 22, 55, 25]
max = 55 ==> [49, 35, 55, 22, 26, 39, 9]
max = 55 ==> [49, 35, 55, 33, 39, 26, 4]
最小N = 55

内容总结

以上是互联网集市为您收集整理的程序员的算法趣题：Q19 朋友的朋友也是朋友吗（Java版）全部内容，希望文章能够帮你解决程序员的算法趣题：Q19 朋友的朋友也是朋友吗（Java版）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---