美文网首页算法第四版习题讲解
算法练习(12):数组练习(1.1.30)

算法练习(12):数组练习(1.1.30)

作者: kyson老师 | 来源:发表于2017-09-03 11:50 被阅读267次

    本系列博客习题来自《算法(第四版)》,算是本人的读书笔记,如果有人在读这本书的,欢迎大家多多交流。为了方便讨论,本人新建了一个微信群(算法交流),想要加入的,请添加我的微信号:zhujinhui207407 谢谢。另外,本人的个人博客 http://www.kyson.cn 也在不停的更新中,欢迎一起讨论

    算法(第4版)

    知识点

    • 最大公约数
    • 两数互质的条件

    1.1.30 数组练习。编写一段程序,创建一个 N×N 的布尔数组 a[][]。其中当 i 和 j 互质时(没有相同 因子),a[i][j] 为 true,否则为 false。


    1.1.30 Array exercise. Write a code fragment that creates an N-by-N boolean array a[][] such that a[i][j] is true if i and j are relatively prime (have no common factors), and false otherwise.

    分析

    见小专栏:点击这里

    答案

    见小专栏:点击这里

    
    ###测试用例
    

    public static void main(String[] args) {
    boolean[][] resultArray = boolArray(9);
    for (int i = 0; i < resultArray.length; i++) {
    System.out.println(Arrays.toString(resultArray[i]));
    }
    }

    
    ####视频分析
    [算法练习(12):数组练习(1.1.30)](http://www.miaopai.com/show/dO5HNHlRFYyBu990R9osi4OV7cX~hpcB5k32Nw__.htm)
    
    ###代码索引
    [ArrayExecise.java](https://github.com/kysonzhu/AlgorithmDemo4Demo/blob/master/src/com/kyson/chapter1/section1/ArrayExecise.java)
    
    ### 广告
    我的首款个人开发的APP[壁纸宝贝](https://itunes.apple.com/cn/app/id1334013423)上线了,欢迎大家下载。

    相关文章

      网友评论

      • 5137369014dc:这个题目 可以优化下,最起码一半不用算的,因为a[i][j] 和a[j][i] 互质性是一样的。其他的优化比如第0行和第1行不用算
        5137369014dc:@算法之路 不用存储啊 因为是沿着对角线 对称的
        public static boolean[][] boolm(int N) {
        boolean[][] a = new boolean[N][N];
        if (N == 1)
        return a;
        else if (N == 2)
        a[0][1] = true;
        else if (N == 3) {
        a[0][1] = true;
        a[1][2] = true;
        } else if (N > 3) {
        a[0][1] = true;
        for (int i = 1; i < N; i++) {
        a[1][i] = true;
        }
        for (int i = 2; i < N; i++) {
        if (i + 1 < N)
        a[i][i + 1] = true;
        for (int j = i + 2; j < N; j++) {
        a[i][j] = (Euclid(i, j) == 1) ? true : false;
        }

        }
        }

        for (int i = 1; i < N; i++)
        for (int j = 0; j < i; j++)
        a[i][j] = a[j][i];

        return a;
        }

        哦 还有的小优化就没写了 比如两个双数肯定不会互质之类的
        kyson老师:做了一点点优化,继续优化的话可能要存储之前的值了,或者你有更好的方法嘛
        kyson老师:@NullTS 好,我看看有没有优化空间

      本文标题:算法练习(12):数组练习(1.1.30)

      本文链接:https://www.haomeiwen.com/subject/fnndjxtx.html