算法（第4版） Chapter 1

Jacendfeng 发布于2019-08-14 17:07 / 2075人阅读

摘要：由的位置决定乘以几，依次为，，，，，。递归算法递归算法就是本次结果用另外的参数调用自己。然而这个函数方法本身并没有用，因为方法中若传递参数为基本型如，在方法中对其值的改变并不会在主函数中产生影响。

Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 谢路云

笔记 二分查找 BinarySearch

    public static int indexOf(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1; // 记住要-1
        int mid;
        while (lo <= hi) { //记住有等号
            mid = (lo + hi) / 2;
            if (key < a[mid])
                hi = mid - 1;
            else if (key > a[mid])
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }

练习题 求对数

Exe 1.1.14
编写一个静态方法 lg()，接受一个整型参数N，返回不大于log2(N)的最大整数。不要使用Math库。

    public static int lg(int N){
            // m = log a N 
            int a=2; //a为底数            
            int m=0; 
            for(;N>1;N/=a){ 
                m++;
            }
            return m;
        }

递归乘法/乘方

Exe 1.1.18
乘法
函数即为乘法的递归形式，返回值为a*b
分析：
引入二进制例子
2|4……0
2|2……0
2|1……1
4的二进制表示为100

eg:3*4
011
* 100
11000

将b看做二进制，当b的二进制位为1时，与a相乘。由1的位置决定a乘以几，依次为1，2，4，8，16，...,2^n。将各个乘积累加起来。
（类似于十进制的乘法运算方式，不同位置的乘法依次会乘以1，10，100，1000，...，10^n，最后累加）
代码思想：
1.循环判断
大循环
判断b的二进制位是否为1{若是，sum+=a;若不是，不需要做任何操作，因为加0不影响}
a=a*2
继续看更高一位，直到看完。
return sum。
（类似于综合法）

    public static int multi(int a, int b) {
        int isys = 4; //n进制
        int sum=0; //这个不能写在for里面，因为for里面声明的为局部变量。
        for (; b != 0; b /= isys) {
            if (b % isys != 0) {
                sum += a * (b % isys);
            }
            a *= isys;
        }
        return sum;
    }

2.递归算法
递归算法就是return 本次结果+用另外的参数调用自己。
（类似于分析法，抽丝剥茧回去）

    public static int multi2(int a, int b)
    {
        if (b == 0) return 0;
        if (b % 2 == 0) return multi(2*a, b/2);
        return multi(2*a, b/2) + a;
    }

乘方的递归形式

    public static int power(int a, int b)
    {
        if (b == 0) return 1;
        if (b % 2 == 0) return power(a*a, b/2);
        return power(a*a, b/2) * a;
    }

交换

用异或的方式交换两个变量，不使用第三个变量，节省一个空间。
然而这个函数方法本身并没有用，因为方法中若传递参数为基本型（如int），在方法中对其值的改变并不会在主函数中产生影响。

    public static void exch(int a, int b){
        a=a^b;
        b=a^b;
        a=a^b;
    }

待补充

局部变量；全局变量；静态变量

GPU云服务器云服务器 python 第4版 hadoop权威指南第4版 linux防火墙第4版第4代编程语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66435.html

算法（第4版） Chapter 5.1 字符串排序

摘要：区别把数字对应成字符。这个是字符串的第位。稍作修改可适应不等长的字符串。因此增加一个组别，记录字符为空的频次。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter 5 Section 1 字符串排序参考资料http://blog.csdn.net/gua...

Amio 2019-08-14 17:15 评论0 收藏0
算法（第4版） Chapter 2.4 优先队列

摘要：堆中位置的结点的父节点的位置为，子节点的位置分别是和一个结论一棵大小为的完全二叉树的高度为用数组堆实现的完全二叉树是很严格的，但它的灵活性足以使我们高效地实现优先队列。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter 2 Section 4 优先队列 ...

Turbo 2019-08-14 17:17 评论0 收藏0
算法（第4版） Chapter 4 练习题答案

摘要：离心率计算题目释义计算点的离心率，图的直径，半径，中心计算图的围长定义点的离心率图中任意一点，的离心率是图中其他点到的所有最短路径中最大值。图的中心图中离心率长度等于半径的点。改动离心率计算，在遍历中增加的赋值即可。离心率计算 4.1.16 The eccentricity of a vertex v is the the length of the shortest path fr...

13651657101 2019-08-14 17:13 评论0 收藏0
算法（第4版） Chapter 4.2 强联通性 Tarjan算法补充

摘要：在实际的测试中，算法的运行效率也比算法高左右。此外，该算法与求无向图的双连通分量割点桥的算法也有着很深的联系。学习该算法，也有助于深入理解求双连通分量的算法，两者可以类比组合理解。固属于同一连通分支。参考资料http://blog.csdn.net/acmmmm/a...https://www.byvoid.com/blog/s...http://blog.csdn.net/noth...

maybe_009 2019-08-14 17:13 评论0 收藏0
算法（第4版） Chapter 4.3 最小生成树

摘要：算法图示代码复杂度时间初始化优先队列，最坏情况次比较每次操作成本次比较，最多还会多次和次操作，但这些成本相比的增长数量级可忽略不计详见空间 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter 4 Section 3 最小生成树定义树是特殊的图图的生...

asoren 2019-08-14 17:16 评论0 收藏0