精华内容
下载资源
问答
  • 递归算法介绍(C++)

    2021-04-05 14:50:50
    递归算法常见案例介绍(C++) 1.反转字符串 编写一个函数,其作用是将输入字符串反转过来。输入字符串以字符数组 char[] 形式给出。不要给另外数组分配额外空间,你必须原地修改输入数组、使用 O(1) 额外...

    递归算法常见案例介绍(C++)

    1.反转字符串

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

    class Solution {
    public:
       void reverse(vector<char>&s,int i)
       {
           int l=s.size();
           if(i>=l/2) return; //设置返回条件
           char temp=s[i];
           s[i]=s[l-1-i];
           s[l-1-i]=temp;//原地交换前后两元素,下标和为l-1
           reverse(s,i+1);//进入下一个递归函数
       }
        void reverseString(vector<char>& s) {
           reverse(s,0);
        }
    };
    

    2.两两交换链表中的节点
    给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
    例:1->2->3->4 变为2->1->4->3

    class Solution {
    public:
        
        ListNode* swapPairs(ListNode* head) {
           if(head==NULL||head->next==NULL) return head;
           ListNode* p=head->next;
           head->next=swapPairs(p->next);
           p->next=head;
           return p;
        }
    };
    

    3.杨辉三角形
    给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。在杨辉三角中,每个数是它左上方和右上方的数的和。
    例:
    输入: 5
    输出:
    [
    [1],
    [1,1],
    [1,2,1],
    [1,3,3,1],
    [1,4,6,4,1]
    ]

    class Solution {
    public:
        vector<vector<int>> generate(int numRows) {
            vector<vector<int>>res;
            res.push_back({{1}});
            for(int i=1;i<numRows;i++)
            {
                vector<int>tmp(i+1,1);
                for(int j=1;j<i;j++)
                {
                    int ans=res[i-1][j-1]+res[i-1][j];
                    tmp[j]=ans;
                }
                res.push_back(tmp);
            }
            return res;
        }
    };
    

    给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。(K从0开始)

    //1.全部计算
    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
        vector<vector<int>>C(rowIndex+1);
        for(int i=0;i<=rowIndex;i++)
        {
            C[i].resize(i+1);
            C[i][0]=1;
            C[i][i]=1;
            for(int j=1;j<i;j++)
            {
                C[i][j]=C[i-1][j-1]+C[i-1][j];
            }
        }
        return C[rowIndex];
        }
    };
    //2.滚动数组优化
    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
        vector<int>pre,cur;
        for(int i=0;i<=rowIndex;i++)
        {
            cur.resize(i+1);
            cur[0]=1,cur[i]=1;
            for(int j=1;j<i;j++)
            {
                cur[j]=pre[j-1]+pre[j];
            }
            pre=cur;
        }
        return cur;
    }
    };
    //3.一维数组
    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int>Row(rowIndex+1);
            Row[0]=1;
            for(int i=1;i<=rowIndex;i++)
            {
                for(int j=i;j>0;j--)
                {
                    Row[j]+=Row[j-1];
                }
            }
            return Row;
        }
    };
    

    4.反转链表
    反转一个单链表。
    例:
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

    //迭代法
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            if(head==NULL) return NULL;
            ListNode* pre=NULL;
            ListNode* cur=head;
            ListNode* nextcur=cur->next;
            while(cur->next)
            {
                nextcur=cur->next;
                cur->next=pre;
                pre=cur;
                cur=nextcur; 
            }
            cur->next=pre;
            return cur;
        }
    };
    //迭代法简洁写法
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            ListNode* cur=NULL;
            ListNode* pre=head;
            while(pre)
            {
                ListNode* t=pre->next;
                pre->next=cur;
                cur=pre;
                pre=t;
            }
            return cur;
        }
    };
    //递归法求解
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
           if(head==NULL||head->next==NULL) return head;
           ListNode* ret=reverseList(head->next);
           head->next->next=head;
           head->next=NULL;
           return ret;
        }
    };
    

    5.斐波那契数列
    斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
    F(0) = 0,F(1) = 1
    F(n) = F(n - 1) + F(n - 2),其中 n > 1

    //自上而下简单递归,引入大量重复计算
    class Solution {
    public:
        int fib(int n) {
            if(n<=1) return n;
            int res;
            res=fib(n-1)+fib(n-2);
            return res;
        }
    };
    //自下而上迭代
    class Solution {
    public:
        int fib(int n) {
            if(n<=1) return n;
            int f0=0,f1=1;
            int f;
            for(int i=2;i<=n;i++)
            {
                f=f0+f1;
                f0=f1;
                f1=f;
            }
            return f;
        }
    };
    //建立unordered_map,略去重复计算
    class Solution {
    public:
        unordered_map<int,int>map;
        int fib(int n) {
            if(n<=1) return n;
            if(map.count(n)) return map[n];
            int a=fib(n-1);
            map[n-1]=a;
            int b=fib(n-2);
            map[n-2]=b;
            int res=fib(n-1)+fib(n-2);
            map[n]=res;
            return res;
        }
    };
    

    6.爬楼梯
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。

    //简单递归
    class Solution {
    public:
        int climbStairs(int n) {
            if(n<=0) return 0;
            if(n<=3) return n;
            int res;
            res=climbStairs(n-1)+climbStairs(n-2);
            return res;
        }
    };
    //简单迭代,也可称作是动态规划,自底向上
    class Solution {
    public:
        int climbStairs(int n) {
            if(n<=0) return 0;
            if(n<=3) return n;
            int a=2,b=3;
            int c;
            int res;
            for(int i=4;i<=n;i++)
            {
                res=a+b;
                a=b;
                b=res;
            }
            return res;
        }
    };
    //和斐波那契数列基本一样
    

    7.求二叉树的最大深度
    给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

    //简单的层序遍历求解
    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            //层序遍历
            if(root==NULL) return 0;
            queue<TreeNode*>q;
            q.push(root);
            int depth=0;
            int count=0;
            while(!q.empty())
            {
                int l=q.size();
                count++;
                for(int i=0;i<l;i++)
                {
                    TreeNode* node=q.front();
                    q.pop();
                    if(node->left) q.push(node->left);
                    if(node->right) q.push(node->right);
                }
            }
            return count;
        }
    };
    //递归法求解,非常简单
    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            //递归求解
            if(root==NULL) return 0;
            return max(maxDepth(root->left),maxDepth(root->right))+1;
        }
    };
    

    实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,x^n)。

    //递归快速幂算法,时间复杂度O(log(n))次
    class Solution {
    public:
        double fastPow(double x,long long int n)//这里的n为正数
        {
            double res,half;
            if(n==0) return 1.0;
            half=fastPow(x,n/2);
            if(n%2==0)
            {
                return half*half;
            }
            else
            {
                return half*half*x;
            }
        }
        double myPow(double x, long long int n) {
            if(x==0&&n==0) return 0;
            if(n==0) return 1;
            if(n==1) return x;
            if(n<0)
            {
                x=1/x;
                n=-n;
            }
            return fastPow(x,n);
        }
            
    };
    

    8.合并两个升序链表
    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    例:输入:l1 = [1,2,4], l2 = [1,3,4]
    输出:[1,1,2,3,4,4]

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if(l1==NULL||l2==NULL) return l1==NULL?l2:l1;
            while(l1&&l2)
            {
                if(l1->val<l2->val) 
                {
                    if(l1->next==NULL) l1->next=l2;
                    else
                    {
                        l1->next=mergeTwoLists(l1->next,l2);
                    }
                    return l1;
                }
                else
                {
                    if(l2->next==NULL) l2->next=l1;
                    else
                    {
                        l2->next=mergeTwoLists(l1,l2->next);
                    }
                    return l2;
                }
            }
            return NULL;
        }
    };
    

    9.第K个语法符号
    在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为01,1替换为10。给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始)
    第一行: 0
    第二行: 01
    第三行: 0110
    第四行: 01101001

    class Solution {
    public:
        int kthGrammar(int N, int K) {
        //貌似前一部分与上一行一样,后面部分为前面部分取反,故只要知道上一行即可
        int res;
        if(K==1) return 0;
        if(K==2) return 1;
        if(K<=pow(2,N-2))
        {
            res=kthGrammar(N-1, K);
        }
        else
        {
            if(kthGrammar(N-1, K-pow(2,N-2))==0) res=1;
            else res=0;
        }
        return res;
        }
    };
    

    10.不同的二叉搜索树
    输入:3
    输出:
    [
    [1,null,3,2],
    [3,2,null,1],
    [3,1,null,null,2],
    [2,1,3],
    [1,null,2,null,3]
    ]

    class Solution {
    public:
        vector<TreeNode*>helper(int start,int end)
        {
            vector<TreeNode*>ret;
            if(start>end) ret.push_back(NULL);
            for(int i=start;i<=end;i++)
            {
                vector<TreeNode*> left=helper(start,i-1);
                vector<TreeNode*> right=helper(i+1,end);
                for(auto l:left)
                {
                    for(auto r:right)
                    {
                       TreeNode* root=new TreeNode(i);//每次root要重新生成
                       root->left=l;
                        root->right=r;
                        ret.push_back(root);
                    }
                }
            }
            return ret;
        }
        vector<TreeNode*> generateTrees(int n) {
            vector<TreeNode*>res;
            if(n<=0) return {};
            res=helper(1,n);
            return res;
        }
    };
    
    展开全文
  • 深入解析递归算法

    2015-05-19 21:05:05
    递归是计算机科学的一个重要概念,递归的方法... 以下我简单介绍一个简单的程序来给大家讲一下递归的基本用法,这个程序的作用是计算前N个整数的和。 int recursive(int n) //递归计算前n个整数的和 { if (n == 1) re

           递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写递归能使程序变得简洁和清晰.据我所知有很多大神都是“无递归不编程”可见递归的重要性和方便性。

           以下我简单介绍一个简单的程序来给大家讲一下递归的基本用法。

    void recursive(int n, int base)
    {

    i++;
    static string DIGIT_TABLE = "0123456789abcdef";
    if (n >= base)
    recursive(n / base, base);
    cout << DIGIT_TABLE[ n % base ];
    }
            

    (recursive的意思就是递归的意思)这个程序很简单就是先调用recursive(n)这个函数接着调用recursive(n、base)这个函数一直到recursive(1)终止递归。

             注意,尽管recursive似乎在调用自身,但实际上它在调用自身的一个副本。该副本只是具有不同参数的另一个函数。任何时候只有一个副本是活动的;其余的都将被挂起。处理所有的簿记工作是计算机的事情,不是你的工作。如果对计算机来说簿记工作都太多了,你们就要考虑一下这个问题是否合适用递归来解决这个问题了。这个我们在下边还会提到,读者先不要急着专研这个问题。

           递归的4条基本规则

    1.基本情形:至少有一种无须递归即可获得解决的情形

    这个很容易理解,因为如果没有一种无须递归即可获得解决的情形,那么我们的递归岂不是成一个死循环了,在上例中recursive(1)就是一种无须递归即可获得解决的情形。

    2.进展:任意递归调用必须向基本情形迈进。

    这个其实跟上边的原则类似,我们只有一步步接近上边说的“一种无须递归即可获得解决的情形”才有可能结束我们的递归,例如上述程序中的recursive(n - 1) ,每次都减去1,使参数越来越接近1.

    3.正确性假说:总是假设递归调用是有效的。

      乍看,这一假设似乎有点奇怪,但是回想一下,我们总是假设函数调用有效,因此假设递归调用有效实际上没有什么不同。和任意函数一样,递归历程需要从其他函数调用组合解决方案以获得一个解决方案。但是其他函数可以包含原始函数更简单的实例。

    4.复利规则:绝对不要通过在单独递归调用中解决同一问题实例的方式来重复工作。

         你应该知道并不是在哪里使用递归都合适。我在这儿给大家 举下面一个例子。这个程序的作用是计算前N个整数的和。

    int printInt(int n)//递归计算前n个整数的和
    {
    if (n == 1)
    return 1;
    else
    {
    return printInt(n - 1) + n;
    }
    }

    这个问题完全没有必要用递归解决,一个for循环就可以轻易解决这个问题。因为我们知道递归其实就是反复调用函数本身,而调用函数是要消耗时间和空间的,每次调用都要进行内部堆栈的压入之后再一个个弹出,所以函数调用开销一般比较大,当然这是使用内联指令可节省的。所以我们这儿有个基本的原则,能用循环解决的问题就不要用递归。

      通过递归调用斐波那契数可说明了一个更加严重的问题。因为斐波那契数是递归定义的,编写递归历程来确定斐波那契数似乎很自然。但是在实际解决这个问题的时候,递归调用总次数比我们试图计算的斐波那契数列要更大,原因是递归调用重复了太多。所以我们要记住绝不要通过在单独递归调用中解决同一问题实例的方式来重复工作。

       到此我对递归的理解先告一段落,欢迎讨论


    展开全文
  • 每次用递归都感觉有点难,这个趁着恶补基础知识的时候,专门看了一遍递归算法4的。...下面这种实现中的注释就言简意赅地说明了代码的作用。 int bin_search(int key, int *a, int left, int right) { //递归第一条

    每次用递归都感觉有点难,这个趁着恶补基础知识的时候,专门看了一遍递归,算法4的。

    1.1 递归介绍

    方法可以调用自己,例如:下面给出了bin_search的二分查找的一种实现。(算法4中使用的是Java,但是我是c++系的,就用c++实现,语言不重要)。我们就会经常使用递归,因为递归代码比相应的非递归代码更加简洁优雅、易懂。下面这种实现中的注释就言简意赅地说明了代码的作用。

    int bin_search(int key, int *a, int left, int right)
    {
        //递归第一条,总是包含一个return的语句
        if(left > right) return -1;
    
        int middle = left + (right - left)/2;
        if(key < a[middle])  bin_search(key, a, left, middle-1);\
        else if(key > a[middle]) bin_search(key, a, middle+1, right);
        else return middle;
    }
    

    编写递归代码时最重要的有以下三点。

    1. 递归总有一个最简单的情况——方法的第一条语句总是一个包含return的条件语句。
    2. 递归调用总是去尝试解决一个规模更小的子问题,这样递归才能收敛到最简单的情况。在上面代码中,第四个参数和第三个参数的差值一直在缩小。
    3. 递归调用的父问题和尝试解决的子问题不应该有交集。在上面代码中,两个子问题各自操作的数组部分是不同的。

    违背其中任意一条都可能得到错误的结果或低效的代码,而坚持这些原则能写出清晰,正确且容易评估性能的程序。使用递归的另一个原因是我们可以使用数学模型来估计程序的性能。这个要在后面讲。

    1.2 练习

    看了递归的总结了之后,要做做练习题,控固一些递归的知识点,所以就做算法4,第一节的练习题。

    1.1.16 给出exR1(6)的返回值

    string exR1(int n)
    {
        if(n < 0) return "";
        return exR1(n - 3) + n + exR1(n - 2) + n;
    }
    
    int main()
    {
        cout << "递归代码学习" << endl;
    
        string str = exR1(6);
        cout << str << endl;
        return 0;
    }
    

    c++好像不知道string加法,不过就这样吧,我们不执行了,直接推结果。
    在这里插入图片描述
    这里已经把递归的流程分析,递归分析不用慌,一层一层分析,知道返回的时候,就有结果了,这道题的答案是:311361142246。

    1.1.17 找出一下递归函数的问题

    string exR2(int n)
    {
        string s = exR2(n -3)+ n + exR2(n -2)+ n;
        if(n < 0) return "";
        return s;
    }
    

    这一个是违反了递归的第一条性质,也就是第一条不包含return语句,这样导致递归函数一直递归,知道把栈搞溢出。

    1.1.18 请看一下递归函数

    int mustery(int a, int b)
    {
        if(b == 0) return 0;
        if(b % 2 == 0) return mustery(a+a, b/2);
        return mustery(a+a, b/2) + a;
    }
    

    mustery(2, 25)和mustery(3, 11)的返回值是多少
    在这里插入图片描述
    这个递归比较简单,只要一个方向递归,像第一题两个方向递归才难。

    1.1.19 在计算机上运行一下程序

    long F(int N)
    {
        if(N==0) return 0;
        if(N==1) return 1;
        return F(N-1)+F(N-2);
    }
    

    计算这段程序在一个小时之内能够得到的F(N)结果的最大N值是多少?这个有谁知道,可以讲解一波,我也不清楚。
    开发F(N)的一个更好的实现,用数组保存已经计算过的值。

    long F2(int N, long *value)
    {
        //static long *value = new long[N];
    
        if(N == 0)
        {
            value[0] = 0;
            value[1] = 1;
            return 0;
        }
        if(N == 1)
        {
            value[0] = 0;
            value[1] = 1;
            return 1;
        }
        //printf("N %ld %ld %ld\n", N, value[N-1]+value[N-2]);
        value[N-1] = F2(N-1, value);
        return value[N-1]+value[N-2];
    }
    

    递归函数还是一贯都是开始是return,因为我们要从0,1开始,所以0,1需要做特殊处理,然后从2开始的话,我们就递归算出每个数组的值,然后利用已经保存好的数组的值,然后在相加,就得到了想要的结果。

    1.1.20 编写一个递归的静态方法计算ln(N!)的值

    unsigned long jieceng(int N)
    {
        if(N == 1 || N == 0) {
            return 1;
        }
    
        return jieceng(N-1)*N;
    }
    

    这是阶乘的答案

    展开全文
  • 图解算法:五大常用算法

    千次阅读 多人点赞 2021-03-10 20:52:40
    目录第一章 递归算法介绍第二章 递归算法应用2.1、求阶乘第三章 回溯算法介绍第四章 回溯算法应用4.1、走迷宫第五章 分治算法介绍第六章 分治算法应用6.1、汉诺塔 项目地址:...


    项目地址:https://gitee.com/caochenlei/algorithms

    第一章 递归算法介绍

    递归算法(recursion algorithm)又称递归法,简单的来说,就是函数自己调用自己。绝大多数编程语言中都支持函数的自调用,在这些语言中函数是可以通过调用自身来进行递归的。计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言中习惯用递归来实现循环。

    那么“递归”和“循环”如何形象的描述呢?

    • 递归: 你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开他,你推开门,发现里面还有一扇门,你继续打开他。若干次之后,你打开面前的门后,发现只有一间屋子,没有门了。然后,你开始原路返回,最终还是可以返回到原点。一般来说,递归需要有边界条件(这里指最后那间屋子)、递归前进段(这里指去的过程)和递归返回段(这里指返回的过程)。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
    • 循环: 在你打开门之前,手里就已经拿了若干把钥匙,每一把钥匙可以打开一道门,当你一扇一扇门打开过去,最终手里的钥匙就会全部用掉,最终成功的从房间里出去,也就是一去不复返,这里不考虑死循环。

    第二章 递归算法应用

    2.1、求阶乘

    计算阶乘的程序在数学上定义为:

    而使用代码来实现却也是很简单:

    public class Factorial {
        public static void main(String[] args) {
            System.out.println("5的阶乘:" + fact(5));
        }
    
        //求阶乘
        public static int fact(int n) {
            if (n == 0) {
                return 1;
            }
            return n * fact(n - 1);
        }
    }
    
    5的阶乘:120
    

    2.2、求年龄

    有5个人坐在一起,问第5个人多少岁,他说比第4个人大2岁。问第4个人多少岁,他说比第3个人大2岁。问第3个人多少岁,他说比第2个人大2岁。问第2个人多少岁,他说比第1个人大2岁。最后问第1个人,他说是10岁。请问第5个人多大?

    计算年龄的程序在数学上定义为:

    而使用代码来实现却也是很简单:

    public class Age {
        public static void main(String[] args) {
            System.out.println(age(5));
        }
    
        //求年龄
        public static int age(int n) {
            if (n == 1) {
                return 10;
            }
            return age(n - 1) + 2;
        }
    }
    
    18
    

    第三章 回溯算法介绍

    回溯算法(backtracking algorithm)又称试探法,实际上是一个类似枚举搜索尝试的过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

    我们实际上可以这么想,如果现在有一个迷宫,有一个入口,有一个出口,也只有一条路可以走出去,如果这个迷宫并没有规律,而是随机生成的,这个时候,一般来说,我们就会每一条路不停的尝试,发现这条路走不通,就会回退到某一点,然后继续尝试,直到最终走出去,其实这就是回溯的一种应用。

    第四章 回溯算法应用

    4.1、走迷宫

    首先我们需要创建一张地图,这里使用二维数组来代替地图中的数据,没有走过的路为0,红色墙的挡板为1,可以走的通路为2,走不通的路为3。上图的绿色方块和黄色方块并没有特殊意义,只是为了告诉大家迷宫入口和出口在哪里。当然了,地图可以设计的很复杂,里边的挡板也可以设计的很复杂,但是为了很好的让大家接受大家暂且和我保持一致,我们就使用上边那张地图。生成地图的代码如下:

    public class Maze {
        public static void main(String[] args) {
            //1.创建地图
            int[][] map = createMap(10, 10);
    
            //2.打印地图
            System.out.println("初始化地图:");
            displayMap(map);
    
            //3.走迷宫
    
            //4.打印地图
    
        }
    
        //创建地图
        public static int[][] createMap(int rows, int cols) {
            //...
        }
    
        //打印地图
    
        //走迷宫
    }
    
    //创建地图
    public static int[][] createMap(int rows, int cols) {
        //创建地图
        int[][] map = new int[rows][cols];
        //建立围墙
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                //绘制第一行和最后一行的墙
                if (i == 0 || i == rows - 1) {
                    map[i][j] = 1;
                }
                //绘制第一列和最后一列的墙
                if (j == 0 || j == cols - 1) {
                    map[i][j] = 1;
                }
            }
        }
        //添加挡板
        map[4][0] = 1;
        map[4][1] = 1;
        map[4][2] = 1;
        map[4][3] = 1;
        map[5][6] = 1;
        map[5][7] = 1;
        map[5][8] = 1;
        map[5][9] = 1;
        //返回地图
        return map;
    }
    

    生成完地图后,我们需要打印一下地图的数据来查看一下地图是否生成正确。打印地图的代码如下:

    //打印地图
    public static void displayMap(int[][] map) {
        //地图行数
        int rows = map.length;
        //地图列数
        int cols = map[0].length;
        //打印地图
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    1 1 1 1 1 1 1 1 1 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 1 1 1 0 0 0 0 0 1 
    1 0 0 0 0 0 1 1 1 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 1 1 1 1 1 1 1 1 1 
    

    看着上边的地图,从绿色的入口出发,我们只能进行上下左右四个方向的走,因此,我们并不能确定先走哪一个方向比较好,并且上下左右有很多组合:

    上 下 左 右 
    上 下 右 左 
    上 左 下 右 
    上 左 右 下 
    上 右 下 左 
    上 右 左 下 
    下 上 左 右 
    下 上 右 左 
    下 左 上 右 
    下 左 右 上 
    下 右 上 左 
    下 右 左 上 
    左 上 下 右 
    左 上 右 下 
    左 下 上 右 
    左 下 右 上 
    左 右 上 下 
    左 右 下 上 
    右 上 下 左 
    右 上 左 下 
    右 下 上 左 
    右 下 左 上 
    右 左 上 下 
    右 左 下 上 
    

    我们可以先观察地图,发现往右走和往下走比较好,所以,我们先指定一个走迷宫的策略:下->右->上->左,先往下走,往下走不通,往右走,往右走不通,往上走,往上走不通,往左走,我们就把这个点标记为3,直到我们走到迷宫的终点也就是黄色的方块处就可以了。

    public class Maze {
        public static void main(String[] args) {
            //1.创建地图
            int[][] map = createMap(10, 10);
    
            //2.打印地图
            System.out.println("初始化地图:");
            displayMap(map);
    
            //3.走迷宫
            walkMap(map, 1, 1);
    
            //4.打印地图
            System.out.println("走迷宫打印:");
            displayMap(map);
        }
    
        //创建地图
        //代码省略
    
        //打印地图
        //代码省略
    
        /**
         * 走迷宫
         *
         * @param map 要走的地图
         * @param x   起始位置x坐标
         * @param y   起始位置y坐标
         * @return
         */
        public static boolean walkMap(int[][] map, int x, int y) {
            //如果走出迷宫,则返回true
            if (map[8][8] == 2) {
                return true;
            }
            //如果没有走出,则继续走迷宫
            if (map[x][y] == 0) {
                //假定该点可以走
                map[x][y] = 2;
                //按照策略继续走
                if (walkMap(map, x + 1, y)) {           //往下走
                    return true;
                } else if (walkMap(map, x, y + 1)) {    //往右走
                    return true;
                } else if (walkMap(map, x - 1, y)) {    //往上走
                    return true;
                } else if (walkMap(map, x, y - 1)) {    //往左走
                    return true;
                } else {                                //走不通
                    map[x][y] = 3;
                    return false;
                }
            }
            //如果这个方块不能再走(如:1遇墙、2已走过、3走不通)
            else {
                return false;
            }
        }
    }
    
    初始化地图:
    1 1 1 1 1 1 1 1 1 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 1 1 1 0 0 0 0 0 1 
    1 0 0 0 0 0 1 1 1 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 1 1 1 1 1 1 1 1 1 
    走迷宫打印:
    1 1 1 1 1 1 1 1 1 1 
    1 2 0 0 0 0 0 0 0 1 
    1 2 0 0 0 0 0 0 0 1 
    1 2 2 2 2 0 0 0 0 1 
    1 1 1 1 2 0 0 0 0 1 
    1 0 0 0 2 0 1 1 1 1 
    1 0 0 0 2 0 0 0 0 1 
    1 0 0 0 2 0 0 0 0 1 
    1 0 0 0 2 2 2 2 2 1 
    1 1 1 1 1 1 1 1 1 1 
    

    我们发现程序已经找到了出去迷宫的路了,那一条全是2的路就是赶往出口的路,当然了,你选择的行走策略不一样这个结果也有可能会不一样,我们目前选择的是下->右->上->左,而如果你想要找到路径最小的一条,那就需要把上边所有的行走策略全部走一遍,才能找到最小的一条,这里就不演示了。

    4.2、八皇后

    八皇后问题(Eight queens),是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。

    问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转,和对角线对称变换的摆法看成一类,共有42类。计算机发明后,有多种计算机语言可以编程解决此问题。

    解决八皇后的具体思路:

    1. 第一个皇后先放第一行第一列。
    2. 第二个皇后放在第二行第一列、然后判断是否 OK, 如果不 OK,继续放在第二列、第三列、依次把所有列都放完,找到一个合适。
    3. 继续第三个皇后,还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置,算是找到了一个正确解,然后输出当前8个皇后的位置。
    4. 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解, 全部得到。
    5. 然后回头继续第一个皇后放第二列,后面继续循环执行 1,2,3,4 的步骤,直到找到所有的解。

    在这个过程中,如何判断是否在同一行、同一列比较容易判断,但是如何判断在同一斜线是一个麻烦的问题,假设一个点A的坐标是[ a , b ],那么和该点在同一斜线上的点A有四种分别是:

    前两种点横纵坐标相减和A点横纵坐标相减后一样,后两种点横纵坐标相加和A点横纵坐标相加一样。

    因此,根据这个我们就可以很方便的判断两个点是否在同一斜线上,只要两个点横纵坐标相加结果相等或者相减结果相等,就可以判断两个点在同一斜线上。

    public class EightQueens {
        private static int max = 8;                 //代表8个皇后的数量
        private static int[] arr = new int[8];      //代表8个皇后的下标
    
        public static void main(String[] args) {
            check(0);
        }
    
        //开始摆放八个皇后
        public static void check(int n) {
            //如果n=8则表明8个皇后已经放好,放好了就直接输出数组信息
            if (n == max) {
                print();
                return;
            }
            //从当前行的第一列(0)开始逐一放八皇后并判断该皇后是否合法
            for (int i = 0; i < max; i++) {
                //把当前列下标放到对应皇后的下标
                arr[n] = i;
                //下标是放好了但是合不合法需判断
                if (judge(n)) {
                    check(n + 1);
                }
            }
        }
    
        //判断位置是否合法
        public static boolean judge(int n) {
            //i代表皇后下标
            for (int i = 0; i < n; i++) {
                //array[n] == array[i]代表:第n个皇后和第i个皇后是否在同一列
                //这里不用判断是不是在同一行,因为完全没有必要,8个皇后分别在8行上
                //Math.abs(n - i) == Math.abs(array[n] - array[i])代表:第n个皇后和第i个皇后是否在同一斜线
                if (arr[n] == arr[i] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
                    return false;
                }
            }
            return true;
        }
    
        //输出8个皇后的位置
        public static void print() {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }
    
    0 4 7 5 2 6 1 3 
    0 5 7 2 6 3 1 4 
    0 6 3 5 7 1 4 2 
    0 6 4 7 1 3 5 2 
    1 3 5 7 2 0 6 4 
    1 4 6 0 2 7 5 3 
    1 4 6 3 0 7 5 2 
    1 5 0 6 3 7 2 4 
    1 5 7 2 0 3 6 4 
    1 6 2 5 7 4 0 3 
    1 6 4 7 0 3 5 2 
    1 7 5 0 2 4 6 3 
    2 0 6 4 7 1 3 5 
    2 4 1 7 0 6 3 5 
    2 4 1 7 5 3 6 0 
    2 4 6 0 3 1 7 5 
    2 4 7 3 0 6 1 5 
    2 5 1 4 7 0 6 3 
    2 5 1 6 0 3 7 4 
    2 5 1 6 4 0 7 3 
    2 5 3 0 7 4 6 1 
    2 5 3 1 7 4 6 0 
    2 5 7 0 3 6 4 1 
    2 5 7 0 4 6 1 3 
    2 5 7 1 3 0 6 4 
    2 6 1 7 4 0 3 5 
    2 6 1 7 5 3 0 4 
    2 7 3 6 0 5 1 4 
    3 0 4 7 1 6 2 5 
    3 0 4 7 5 2 6 1 
    3 1 4 7 5 0 2 6 
    3 1 6 2 5 7 0 4 
    3 1 6 2 5 7 4 0 
    3 1 6 4 0 7 5 2 
    3 1 7 4 6 0 2 5 
    3 1 7 5 0 2 4 6 
    3 5 0 4 1 7 2 6 
    3 5 7 1 6 0 2 4 
    3 5 7 2 0 6 4 1 
    3 6 0 7 4 1 5 2 
    3 6 2 7 1 4 0 5 
    3 6 4 1 5 0 2 7 
    3 6 4 2 0 5 7 1 
    3 7 0 2 5 1 6 4 
    3 7 0 4 6 1 5 2 
    3 7 4 2 0 6 1 5 
    4 0 3 5 7 1 6 2 
    4 0 7 3 1 6 2 5 
    4 0 7 5 2 6 1 3 
    4 1 3 5 7 2 0 6 
    4 1 3 6 2 7 5 0 
    4 1 5 0 6 3 7 2 
    4 1 7 0 3 6 2 5 
    4 2 0 5 7 1 3 6 
    4 2 0 6 1 7 5 3 
    4 2 7 3 6 0 5 1 
    4 6 0 2 7 5 3 1 
    4 6 0 3 1 7 5 2 
    4 6 1 3 7 0 2 5 
    4 6 1 5 2 0 3 7 
    4 6 1 5 2 0 7 3 
    4 6 3 0 2 7 5 1 
    4 7 3 0 2 5 1 6 
    4 7 3 0 6 1 5 2 
    5 0 4 1 7 2 6 3 
    5 1 6 0 2 4 7 3 
    5 1 6 0 3 7 4 2 
    5 2 0 6 4 7 1 3 
    5 2 0 7 3 1 6 4 
    5 2 0 7 4 1 3 6 
    5 2 4 6 0 3 1 7 
    5 2 4 7 0 3 1 6 
    5 2 6 1 3 7 0 4 
    5 2 6 1 7 4 0 3 
    5 2 6 3 0 7 1 4 
    5 3 0 4 7 1 6 2 
    5 3 1 7 4 6 0 2 
    5 3 6 0 2 4 1 7 
    5 3 6 0 7 1 4 2 
    5 7 1 3 0 6 4 2 
    6 0 2 7 5 3 1 4 
    6 1 3 0 7 4 2 5 
    6 1 5 2 0 3 7 4 
    6 2 0 5 7 4 1 3 
    6 2 7 1 4 0 5 3 
    6 3 1 4 7 0 2 5 
    6 3 1 7 5 0 2 4 
    6 4 2 0 5 7 1 3 
    7 1 3 0 6 4 2 5 
    7 1 4 2 0 6 3 5 
    7 2 0 5 1 4 6 3 
    7 3 0 2 5 1 6 4 
    

    第五章 分治算法介绍

    分治算法(divide and conquer algorithm)又称分治法,他的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分解目标完成程序算法,简单问题可用二分法完成。利用分治策略求解时,所需时间取决于分解后子问题的个数、子问题的规模大小等因素,而二分法,由于其划分的简单和均匀的特点,是经常采用的一种有效的方法,例如二分法检索。

    当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把他分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把他们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把他们分成几个更小的子问题,以此类推,直至可以直接求出解为止,这就是分治策略的基本思想。

    第六章 分治算法应用

    6.1、汉诺塔

    法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔(Tower of Hanoi),又称河内塔。

    不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

    不管这个传说的可信度有多大,如果考虑一下把64片金片,由一根针上移到另一根针上,并且始终保持上小下大的顺序,这需要多少次移动呢?假设有n片,移动次数是f(n),显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时,需要移动18446744073709551615次。假如每秒钟一次,那就是18446744073709551615秒。这表明移完这些金片需要5845.42亿年以上,而地球存在至今不过45亿年,太阳系的预期寿命据说也就是数百亿年。真的过了5845.42亿年,不说太阳系和银河系,至少地球上的一切生命,连同梵塔、庙宇等,都早已经灰飞烟灭。

    当n=1时,我们直接把这个金片由A柱移动到C柱即可。

    当n=2时,我们首先把最小的金片由A柱移动到B柱,然后把A柱的金片移动到C柱,最后把B柱最小的金片移动到C柱。

    当n=3时,这时候步骤比较多,我就直接贴出移动步骤图了。

    当n=k时,这时候我们会发现移动盘子的步骤越来越复杂,我们可以把这一个问题进行拆分,当n=1和当n=2时,几步就搞定了,要是把这么复杂的问题抽成n=1时,直接把金片由A柱移动到C柱即可,当n=2时,一共三步的事情,那我们有没有一种可能,当n大于或者等于2的时候,我们把一堆金片分成两部分,最顶上的最小的那一片是一部分,其余剩下的是另外一部分。把第二部分看成一个整体来进行移动,具体细节不用管,因为我们会递归调用,计算机会帮我们逐渐将问题进行分解,最后分解成两部分的情况,然后我们就按照n=2这种情况来进行处理。

    上边讲解了很多,但是真正实现的代码却并不多,比较容易实现,代码如下:

    public class Hanoi {
        public static void main(String[] args) {
            int n = 3;//我们这里金片假设为3片
            hanoi(n, 'A', 'B', 'C');
        }
    
        public static void move(char from, char to) {
            System.out.printf("%c to %c\n", from, to);
        }
    
        public static void hanoi(int n, char a, char b, char c) {
            //当只剩下一个金片的时候直接从A柱移动到C柱
            if (n == 1) {
                move(a, c);
            }
            //当n>=2时就拆成两部分(n-1)代表第二部分
            else {
                //将第二部分由A柱移动到B柱
                hanoi(n - 1, a, c, b);
                //将第一部分由A柱移动到C柱
                move(a, c);
                //将第二部分由B柱移动到C柱
                hanoi(n - 1, b, a, c);
            }
        }
    }
    
    A to C
    A to B
    C to B
    A to C
    B to A
    B to C
    A to C
    

    6.2、棋盘覆盖

    在一个2k×2k (k≥0)个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为特殊方格。显然,特殊方格在棋盘中可能出现的位置有4k种,因而有4k种不同的棋盘,以下是几种情况的图示。棋盘覆盖问题要求用4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。

    首先我们通过观察这些棋盘会发现这是一个四四方方的正方形,并且边长是2的倍数,我们可以通过这一点进行入手,当k非常大的时候,我们自己可能用手写不出来,但是,当k=1时,也就是一个2×2的棋盘,正好可以使用4种L型骨牌中的一种刚好把棋盘覆盖,我们是不是可以这么想,无论你的棋盘有多大,通过不停的二分法,将一个大的棋盘拆分成无数个2×2的棋盘,也就是分而治之,这完全符合分治算法的理念。

    当k=2时,我们再来分析一下,在棋盘里只有一块特殊的方格,而且棋盘的大小也比较特殊,2的K次方,非常适合切分成一半。又因为棋盘是个方形的,所以思路可以使将棋盘分成大小相同的四份。当我们将有特殊方格的棋盘分割成4个相同的子棋盘时,4个棋盘分成两类:有特殊方格和没有特殊方格。我们用到的L型骨牌刚好是三个方格的,也就是说可以用一个L型骨牌将其余的三个没有特殊方格的棋盘变成有特殊方格的。

    在进行算法设计的时候,我们首先要明白,这个特殊的方格(红色),在一个棋盘中可能出现的位置有4k种,所以,我们必须自己指定这个特殊方格所在的位置,只要是在这个棋盘中,这个特殊方格都可以存放到任何位置,这里我们使用变量dr代表特殊方格横坐标,变量dc代表特殊方格纵坐标。

    public class CheckerBoard {
        private static int num = 0;                      //用于存放L型骨牌编号
        private static int[][] arr = new int[100][100];  //用于存放棋盘数组信息
    
        public static void main(String[] args) {
            //设置棋盘大小
            int k = 2;
            int size = (int) Math.pow(2.0, k);
    
            //开始棋牌覆盖
            checkerBoard(0, 0, size - 1, size - 1, size);
    
            //打印二维数组
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    System.out.print(arr[i][j] + " ");
                }
                System.out.println();
            }
        }
    
        /**
         * 棋盘覆盖
         *
         * @param tr   当前棋盘左上角的行号
         * @param tc   当前棋盘左上角的列号
         * @param dr   特殊方格所在的行号
         * @param dc   特殊方格所在的列号
         * @param size 当前棋盘的大小2^k
         */
        public static void checkerBoard(int tr, int tc, int dr, int dc, int size) {
            int s, t;               //临时变量
            if (size == 1) return;  //临界条件
            s = size / 2;           //分割棋盘
            t = ++num;              //骨牌编号
    
            //覆盖左上角子棋盘
            if (dr < tr + s && dc < tc + s) {
                //特殊方格在此棋盘中
                checkerBoard(tr, tc, dr, dc, s);
            } else {
                //此棋盘中无特殊方格,用t号L型骨牌覆盖右下角
                arr[tr + s - 1][tc + s - 1] = t;
                //覆盖其余方格
                checkerBoard(tr, tc, tr + s - 1, tc + s - 1, s);
            }
    
            //覆盖右上角子棋盘
            if (dr < tr + s && dc >= tc + s) {
                //特殊方格在此棋盘中
                checkerBoard(tr, tc + s, dr, dc, s);
            } else {
                //此棋盘中无特殊方格,用t号L型骨牌覆盖左下角
                arr[tr + s - 1][tc + s] = t;
                //覆盖其余方格
                checkerBoard(tr, tc + s, tr + s - 1, tc + s, s);
            }
    
            //覆盖左下角子棋盘
            if (dr >= tr + s && dc < tc + s) {
                //特殊方格在此棋盘中
                checkerBoard(tr + s, tc, dr, dc, s);
            } else {
                //此棋盘中无特殊方格,用t号L型骨牌覆盖右上角
                arr[tr + s][tc + s - 1] = t;
                //覆盖其余方格
                checkerBoard(tr + s, tc, tr + s, tc + s - 1, s);
            }
    
            //覆盖右下角子棋盘
            if (dr >= tr + s && dc >= tc + s) {
                //特殊方格在此棋盘中
                checkerBoard(tr + s, tc + s, dr, dc, s);
            } else {
                //此棋盘中无特殊方格,用t号L型骨牌覆盖左上角
                arr[tr + s][tc + s] = t;
                //覆盖其余方格
                checkerBoard(tr + s, tc + s, tr + s, tc + s, s);
            }
        }
    }
    
    2 2 3 3 
    2 1 1 3 
    4 1 5 5 
    4 4 5 0 
    

    第七章 动态规划介绍

    动态规划(dynamic programming,dp)的核心思想是:将大问题划分为若干小问题进行解决,从而一步步获取最优解的处理算法。动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要他被计算过,就将其结果填入表中,这就是动态规划算法的基本思路。

    第八章 动态规划应用

    8.1、零一背包

    【描述】

    一个旅行者有一个最多能装 M 公斤的背包,现在有 N 件物品,他们的重量分别是W1,W2,…,Wn,他们的价值分别为C1,C2,…,Cn,求旅行者能获得的最大总价值。

    【输入】

    第一行:两个整数,M(背包容量,M<=200)和N(物品数量,N<=30);
    
    第2..N+1行:每行二个整数Wi,Ci,表示每个物品的重量和价值。
    

    【输出】

    仅一行,一个数,表示最大总价值。
    

    【输入样例】

    10 4
    2 1
    3 3
    4 5
    7 9
    

    【输出样例】

    12
    

    【题目分析】

    第一步:根据题意建立对应表格,用来存放处理的解。

    第二步:根据已知数据填表,推断出通用的递推表达式。

    • 填写第0行,默认全部为0,已经给出;
    • 填写第0列,默认全部为0,已经给出;

    • 填写dp[1][1],当前列的背包容量是1,而当前行的重量w为2,显然装不下,因此价值c为0;
    • 填写dp[1][2],当前列的背包容量是2,而当前行的重量w为2,显然装得下,但是只有一个,因此价值c为1;
    • 填写dp[1][3],当前列的背包容量是3,而当前行的重量w为2,显然装得下,但是只有一个,因此价值c为1;
    • 填写dp[1][4],当前列的背包容量是4,而当前行的重量w为2,显然装得下,但是只有一个,因此价值c为1;
    • 填写dp[1][5],当前列的背包容量是5,而当前行的重量w为2,显然装得下,但是只有一个,因此价值c为1;
    • 填写dp[1][6],当前列的背包容量是6,而当前行的重量w为2,显然装得下,但是只有一个,因此价值c为1;
    • 填写dp[1][7],当前列的背包容量是7,而当前行的重量w为2,显然装得下,但是只有一个,因此价值c为1;
    • 填写dp[1][8],当前列的背包容量是8,而当前行的重量w为2,显然装得下,但是只有一个,因此价值c为1;
    • 填写dp[1][9],当前列的背包容量是9,而当前行的重量w为2,显然装得下,但是只有一个,因此价值c为1;
    • 填写dp[1][10],当前列的背包容量是10,而当前行的重量w为2,显然装得下,但是只有一个,因此价值c为1;

    • 填写dp[2][1],背包容量是1,重量w为3,显然装不下,此时上边还有一个重量为2的物品,这个装得下,因此价值c为dp[2-1][1]=dp[1][1]=0
    • 填写dp[2][2],背包容量是2,重量w为3,显然装不下,此时上边还有一个重量为2的物品,这个装得下,因此价值c为dp[2-1][2]=dp[1][2]=1
    • 填写dp[2][3],背包容量是3,重量w为3,显然装得下,此时上边还有一个重量为2的物品,3+2>背包容量,因此价值c为3。
    • 填写dp[2][4],背包容量是4,重量w为3,显然装得下,此时上边还有一个重量为2的物品,3+2>背包容量,因此价值c为3。
    • 填写dp[2][5],背包容量是5,重量w为3,显然装得下,此时上边还有一个重量为2的物品,3+2=背包容量,因此价值c为dp[2-1][5-3]+3=4
    • 填写dp[2][6],背包容量是6,重量w为3,显然装得下,此时上边还有一个重量为2的物品,3+2<背包容量,因此价值c为dp[2-1][6-3]+3=4
    • 填写dp[2][7],背包容量是7,重量w为3,显然装得下,此时上边还有一个重量为2的物品,3+2<背包容量,因此价值c为dp[2-1][7-3]+3=4
    • 填写dp[2][8],背包容量是8,重量w为3,显然装得下,此时上边还有一个重量为2的物品,3+2<背包容量,因此价值c为dp[2-1][8-3]+3=4
    • 填写dp[2][9],背包容量是9,重量w为3,显然装得下,此时上边还有一个重量为2的物品,3+2<背包容量,因此价值c为dp[2-1][9-3]+3=4
    • 填写dp[2][10],背包容量是10,重量w为3,显然装得下,此时上边还有一个重量为2的物品,3+2<背包容量,因此价值c为dp[2-1][10-3]+3=4

    填表格到了这里,我们就该发现一些规律了:

    • w[i]> 当前列背包重量j,说明当前物品w的重量装不进去,所以用上一行对应列计算结果,也就是:dp[i][j]=dp[i-1][j]
    • w[i]<=当前列背包重量j,说明当前物品w的重量装得进去,但有没有可能加上以前的重物,也就是:max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])

    第一条规则比较好理解,第二条规则是什么鬼呢?当w[i]<=当前列背包重量j,说明此时的这个物品是可以装进背包中的,j-w[i]的意思是从当前背包中减去当前行w[i]的重量,dp[i-1][j-w[i]]看看剩下的容量在上一行中的计算的最大价值是多少,剩余的容量正好对应上一行的下标,然后在这个基础上加上当前行重物的价值c[i]。选出最大值max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])填充到对应位置。按照这个策略依次进行下去,最终dp[n][m]存的就是旅行者能获得的最大总价值。

    【代码实现】

    public class Backpacker {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();              //获取背包容量
            int n = scanner.nextInt();              //获取物品数量
            int[] w = new int[n + 1];               //定义重量数组
            int[] c = new int[n + 1];               //定义价值数组
            int[][] dp = new int[n + 1][m + 1];     //存储中间结果
    
            for (int i = 1; i <= n; i++) {
                w[i] = scanner.nextInt();           //接收物品重量
                c[i] = scanner.nextInt();           //接收物品价值
            }
    
            for (int i = 1; i <= n; i++) {          //动态规划处理
                for (int j = 1; j <= m; j++) {
                    if (w[i] > j) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);
                    }
                }
            }
    
            System.out.println(dp[n][m]);           //输出最终结果
        }
    }
    

    【代码运行】

    10 4
    2 1
    3 3
    4 5
    7 9
    12
    

    【代码优化】

    我们发现虽然使用了一个二维数组存储了每次运行的结果,但是当前行的结果会依赖上一行某列的结果,不依赖上上行或者上上上行某列的结果,那么,我们是不是可以使用一个一维数组来存储每次运行的结果,这显然是可行的,但是在存储的时候,我们不能从头按照顺序存储,因为那样会覆盖上一行某列的结果值,默认我们从后往前存储,这样就不会破坏上一行某列的结果值了,这样的代码优化,并没有减少时间复杂度,只是减少了空间复杂度,由于一维数组默认全部是0,这就为我们初始化好了第0行的结果了,具体代码只需要把关于dp[i]的下标全部删除,然后内层循环改为从后向前依次存储即可,最后dp[m]为最终解。

    public class Backpacker2 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();              //获取背包容量
            int n = scanner.nextInt();              //获取物品数量
            int[] w = new int[n + 1];               //定义重量数组
            int[] c = new int[n + 1];               //定义价值数组
            int[] dp = new int[m + 1];              //存储中间结果
    
            for (int i = 1; i <= n; i++) {
                w[i] = scanner.nextInt();           //接收物品重量
                c[i] = scanner.nextInt();           //接收物品价值
            }
    
            for (int i = 1; i <= n; i++) {          //动态规划处理
                for (int j = m; j >= 1; j--) {
                    if (w[i] > j) {
                        dp[j] = dp[j];
                    } else {
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + c[i]);
                    }
                }
            }
    
            System.out.println(dp[m]);              //输出最终结果
        }
    }
    

    我们观察if (w[i] > j)这一句的判断是不是可以省去了,因为和Math.max(dp[j], dp[j - w[i]] + c[i])重复了,所以简化后:

    public class Backpacker2 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();              //获取背包容量
            int n = scanner.nextInt();              //获取物品数量
            int[] w = new int[n + 1];               //定义重量数组
            int[] c = new int[n + 1];               //定义价值数组
            int[] dp = new int[m + 1];              //存储中间结果
    
            for (int i = 1; i <= n; i++) {
                w[i] = scanner.nextInt();           //接收物品重量
                c[i] = scanner.nextInt();           //接收物品价值
            }
    
            for (int i = 1; i <= n; i++) {          //动态规划处理
                for (int j = m; j >= 1; j--) {
                    if (w[i] <= j) {
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + c[i]);
                    }
                }
            }
    
            System.out.println(dp[m]);              //输出最终结果
        }
    }
    

    【代码运行】

    10 4
    2 1
    3 3
    4 5
    7 9
    12
    

    8.2、完全背包

    【题目描述】

    设有 N 种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为 M,今从 N 种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于 M,而价值的和为最大。

    【输入】

    第一行:两个整数,M(背包容量,M≤200)和N(物品数量,N≤30);
    
    第2..N+1行:每行二个整数Wi,Ci,表示每个物品的重量和价值。
    

    【输出】

    仅一行,一个数,表示最大总价值。
    

    【输入样例】

    10 4
    2 1
    3 3
    4 5
    7 9
    

    【输出样例】

    12
    

    【题目分析】

    我们已经学过了零一背包问题,但是在零一背包中,每件物品要不可以拿,要不可以不拿,就只有这两种选择。而完全背包强调的是每件物品是无限的,也就是说,我们尽量选择物品最重的,价值最大的,这样,每次我们就不用选择上一行某列计算的价值,而是使用背包容量减去当前重物w的重量,剩余的重量不去上一行的某列数据取值,而是在当前行某列数据取值,因此推导公式需要修改,具体对比:

    【代码实现】

    public class Backpacker3 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();              //获取背包容量
            int n = scanner.nextInt();              //获取物品数量
            int[] w = new int[n + 1];               //定义重量数组
            int[] c = new int[n + 1];               //定义价值数组
            int[] dp = new int[m + 1];              //存储中间结果
    
            for (int i = 1; i <= n; i++) {
                w[i] = scanner.nextInt();           //接收物品重量
                c[i] = scanner.nextInt();           //接收物品价值
            }
    
            for (int i = 1; i <= n; i++) {          //动态规划处理
                for (int j = 1; j <= m; j++) {
                    if (w[i] <= j) {
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + c[i]);
                    }
                }
            }
    
            System.out.println(dp[m]);              //输出最终结果
        }
    }
    

    【代码运行】

    10 4
    2 1
    3 3
    4 5
    7 9
    12
    

    第九章 贪心算法介绍

    贪心算法(greedy algorithm)又称贪婪算法,是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择。

    第十章 贪心算法应用

    10.1、分发饼干

    【题目描述】

    有一群孩子和一堆饼干,每个孩子有一个饥饿度,每个饼干都有一个大小。每个孩子只能吃最多一个饼干,且只有饼干的大小大于孩子的饥饿度时,这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

    【输入】

    输入两个数组,分别代表孩子的饥饿度和饼干的大小。
    

    【输出】

    输出最多有多少孩子可以吃饱的数量。
    

    【样例1】

    输入: g = [1,2,3], s = [1,1]
    输出: 1
    解释: 
    你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
    虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
    所以你应该输出1

    【样例2】

    输入: g = [1,2], s = [1,2,3]
    输出: 2
    解释: 
    你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
    你拥有的饼干数量和尺寸都足以让所有孩子满足。
    所以你应该输出2

    【题目分析】

    因为饥饿度最小的孩子最容易吃饱,所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子,所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后,我们采取同样的策略,考虑剩下孩子里饥饿度最小的孩子,直到没有满足条件的饼干存在。简而言之,这里的贪心策略是,给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。至于具体实现,因为我们需要获得大小关系,一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发,计算有多少个对孩子可以满足条件。

    【代码实现】

    public class AssignCookies {
        public static void main(String[] args) {
            int[] g1 = {1, 2, 3};
            int[] s1 = {1, 1};
            System.out.println(findContentChildren(g1, s1));
    
            int[] g2 = {1, 2};
            int[] s2 = {1, 2, 3};
            System.out.println(findContentChildren(g2, s2));
        }
    
        //核心代码
        public static int findContentChildren(int[] children, int[] cookies) {
            Arrays.sort(children);  //从小到大升序排序孩子饥饿度
            Arrays.sort(cookies);   //从小到大升序排序饼干的大小
            int child = 0;          //能吃饱的孩子下标
            int cookie = 0;         //被分配的饼干下标
    
            while (child < children.length && cookie < cookies.length) {
                if (children[child] <= cookies[cookie++]) {
                    child++;
                }
            }
    
            return child;
        }
    }
    

    【代码运行】

    1
    2
    

    10.2、广播覆盖

    【题目描述】

    假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。如何选择最少的广播台,让所有的地区都可以接收到信号。

    通过上述广播台和覆盖地区的对应关系,可以获取所有覆盖地区:北京,上海,天津,广州,深圳,成都,杭州,大连

    【题目分析】

    【代码实现】

    public class BroadcastCoverage {
        public static void main(String[] args) {
            //创建广播电台集合
            HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
    
            //将各个电台存起来
            HashSet<String> broadcast1 = new HashSet<>();
            broadcast1.add("北京");
            broadcast1.add("上海");
            broadcast1.add("天津");
            broadcasts.put("K1", broadcast1);
            HashSet<String> broadcast2 = new HashSet<>();
            broadcast2.add("广州");
            broadcast2.add("北京");
            broadcast2.add("深圳");
            broadcasts.put("K2", broadcast2);
            HashSet<String> broadcast3 = new HashSet<>();
            broadcast3.add("成都");
            broadcast3.add("上海");
            broadcast3.add("杭州");
            broadcasts.put("K3", broadcast3);
            HashSet<String> broadcast4 = new HashSet<>();
            broadcast4.add("上海");
            broadcast4.add("天津");
            broadcasts.put("K4", broadcast4);
            HashSet<String> broadcast5 = new HashSet<>();
            broadcast5.add("杭州");
            broadcast5.add("大连");
            broadcasts.put("K5", broadcast5);
    
            //存放被覆盖的地区
            HashSet<String> allAreas = new HashSet<String>();
            allAreas.addAll(broadcast1);//会自动去除重复元素
            allAreas.addAll(broadcast2);//会自动去除重复元素
            allAreas.addAll(broadcast3);//会自动去除重复元素
            allAreas.addAll(broadcast4);//会自动去除重复元素
            allAreas.addAll(broadcast5);//会自动去除重复元素
    
            //输出最后选择结果
            System.out.println(selectBroadcasts(broadcasts, allAreas));
        }
    
        //核心代码
        public static ArrayList<String> selectBroadcasts(HashMap<String, HashSet<String>> broadcasts, HashSet<String> allAreas) {
            ArrayList<String> selects = new ArrayList<>();      //存放选择电台集合
            HashSet<String> tempSet = new HashSet<>();          //存放电台覆盖地区和当前还没有覆盖地区的交集
            while (allAreas.size() != 0) {                      //只要当前的地区集合没有被全部覆盖就接着循环
                String maxKey = null;                           //存放能够覆盖最大未覆盖的地区对应电台的key
                for (String key : broadcasts.keySet()) {
                    tempSet.clear();                            //清空掉tempSet
                    HashSet<String> areas = broadcasts.get(key);
                    tempSet.addAll(areas);                      //添加到tempSet
                    tempSet.retainAll(allAreas);                //获取tempSet和allAreas的交集然后放到tempSet
                    if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                        maxKey = key;
                    }
                }
                if (maxKey != null) {                           //如果这次找到最大key
                    selects.add(maxKey);                        //添加到选择电台集合
                    allAreas.removeAll(broadcasts.get(maxKey)); //删除已覆盖电台地区
                }
            }
            return selects;
        }
    }
    

    【代码运行】

    [K1, K2, K3, K5]
    
    展开全文
  • diff算法_diff算法介绍

    2020-11-21 16:00:44
    diff算法的作用计算出Virtual DOM中真正变化的部分,并只针对该部分进行原生DOM操作,而非重新渲染整个页面。传统diff算法通过循环递归对节点进行依次对比,算法复杂度达到 O(n^3) ,n是树的节点数,这个有多可怕呢...
  • 涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 深度学习在其发展中起到了中流砥柱的作用,尽管拥有强大的模拟预测能力,深度学习还面临着超大计算量的问题。在硬件层面上,GPU,ASIC,FPGA都是解决庞大计算量的方案。本文将阐释深度学习和FPGA各自的结构特点以及...
  • 这段代码介绍了迷宫的非递归求解算法,有助于理解用栈非递归的作用
  • 算法权威指南

    2019-01-07 10:28:37
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 算法导论答案

    2018-11-21 10:12:06
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 算法导论中文

    2015-05-09 13:53:20
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 计算机算法导论

    2013-12-22 00:53:17
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 算法导论扫描版

    2018-09-18 20:20:36
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 二叉树线索化和遍历的算法

    千次阅读 2017-11-29 21:50:34
    这个算法和前面总结过递归法遍历二叉树都算是数据结构里面难度系数比栈,队列,线性表那些大的算法。限定时间内要写出来还是有些难度,最好是能有所总结,才能做到得心应手。先序:先序线索化void PreThreading...
  • 算法导论中文版

    2017-10-22 22:57:47
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 算法导论 美国

    2012-07-13 11:08:46
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 算法导论.epub

    2017-09-17 18:48:05
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 算法导论 》

    2015-03-17 09:55:32
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 算法精讲.mobi

    2015-07-12 10:47:52
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • c/c++常用算法(7) -- 基本算法思想

    千次阅读 2013-12-20 09:53:47
    概述  在实际应用中,不同问题解题思想也往往不同。如果找不到一个合适...穷举算法思想递推算法思想递归算法思想分治算法思想概率算法思想 还有贫心算法思想、回溯思想、动态规则思想(本篇就不做介绍了)。 1.
  • 涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间...
  • 算法推荐书籍

    千次阅读 2014-05-12 19:08:11
    涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 280
精华内容 112
关键字:

介绍递归算法的作用