精华内容
下载资源
问答
  • 1.例子引入  在数学归纳法的使用过程中...首先给出一个定义:如果a和b是两个不等的正整数,我们定义max(a,b)是a,b中较大的一个。如果a=b,我们令max(a,b)=a=b。例如max(3,5)=max(5,3)=5,而max(4,4)=4。 现在让An是这

    1.例子引入

      在数学归纳法的使用过程中,必须严格遵守数学归纳法的证明步骤,每个步骤都不能忽略数学归纳法所满足的条件。如果忽略了这些条件,可以引出下面这样的荒谬结果。例如下面这个例子,导致出错的原因究竟是什么呢?

    表述一:
    首先给出一个定义:如果a和b是两个不等的正整数,我们定义max(a,b)是a,b中较大的一个。如果a=b,我们令max(a,b)=a=b。
    例如max(3,5)=max(5,3)=5,而max(4,4)=4。 
    
    现在让An是这样的命题:如果a,b是使max(a,b)=n的任意两个正整数,则a=b。 (显然是伪命题)
    
    则用数学归纳法证明: 
    
    a) 假设Ar成立。设a,b是任意两个使得max(a,b)=r+1的正整数。考虑两个正整数 
        α=a-1,
        β=b-1,
        则max(α,β)=r,又由于我们假设Ar成立,因此α=β,由此a=b。因此Ar+1成立。 
    
    b) A1显然成立。因为如果max(a,b)=1,则由于a,b假设是正整数,所以都必须等于1。 
    
        因此按数学归纳法,An对任意的n成立。 
    
    现在如果a和b是两个不管什么样的正整数,用r表示max(a,b),由于已证明了对任意的n, An是成立的,特别Ar是成立的,因此a=b。 
    

      上面这个例子是摘自R .柯朗的《什么是数学》。这个例子还有 另外一个表述方式 ,如下:

    表述二:
    首先给出一个定义:如果a和b是两个不等的正整数,我们定义max(a,b)是a,b中较大的一个。如果a=b,我们令max(a,b)=a=b。
    例如max(3,5)=max(5,3)=5,而max(4,4)=4。 
    
    现在让An是这样的命题:如果a,b是使max(a,b)=n的任意两个正整数,则a=b。 (显然是伪命题)
    
    则用数学归纳法证明:
    
    a) A1显然成立。因为如果max(a, b)=1,则由于a, b都是正整数,所以必然有a=b=1;
    b) 假设Ar成立。设a, b是任意两个使得max(a, b)=r的正整数。那么设:
        α=a+1,
        β=b+1,
        则max(α, β)=r+1。又由于Ar成立,因此a=b;由此知α=β,因此A(r+1)成立。
    
    由于a和b是任意两个正整数,因此原命题得证。
    

    2.荒谬解读

      在表述一的证明过程中,a,b是两个任意的正整数,令α=a-1,β=b-1后,α和β未必是正整数(可能为0),所以证明过程不严谨,这是一个很表面的错误。在表述二的证明过程中,这个“表面”错误得到了完善,但最终还是导致了荒谬的结论。所以根本错误还没有找到,还需进一步探索。
      在上面两种证明的过程中,a和b是两个任意的正整数,但α和β是由a和b通过计算得到的,所以α和β都不是真正意义上的“两个任意正整数”。(用过C语言里rand()函数产生随机数的人不难理解,rand()产生的随机数之间是通过指定的算法推算来的,不是真正意义的随机数,被称为“伪随机数”。还有一种理解方式是:我们可以说x是随机数,变化没有任何规律,x相对与任何其他变量都是无规律的。但是x+1,虽然也是实数范围内取值,但是x+1的产生总是依赖x。)


    转载请注明出处:http://blog.csdn.net/so_geili/article/details/54562167

    展开全文
  • 使用strcmp函数判断两个字符串是否相等

    在这里插入图片描述

    1.Introduction

    有时写代码时会立Flag,

    “ 今天不解决这个BUG,就不吃饭了!还不信了!”

    “ 真香!代码明天再说吧 ”

    呸呸,是真的Flag,标识符啦。通过Flag判断当前程序状态,进行下一步的逻辑块。那么这时,Flag的变量类型一般会用数值型,只需要用 == 逻辑符进行判断就好了,但是数值往往指示不明。

    比如,下面这行代码,你能完全不知道1和0代表什么,那么换成字符怎么表达 相等 呢?

    if ( Flag == 1 )
        gift = 'Mac口红';
    elseif( Flag == 0 )
        gift = 'Mac电脑';
    end
    

    2.Materials and methods

    我们用到的函数是 strcmp ,看一下描述,不就是两个字符串相等的话,就返回逻辑值1嘛,简单~

    在这里插入图片描述
    开始改造上面的代码,构建函数实现程序功能:如果是男生的话礼物送Mac电脑,女生送Mac口红。

    function [gift] = flagStrcmp(personType)
    
    if ( strcmp(personType,'girl') )
        gift = 'Mac口红';
    elseif( strcmp(personType,'boy') )
        gift = 'Mac电脑';
    end
    
    
    end
    
    

    3. Results and discussion

    运行下结果看看~
    在这里插入图片描述

    4. Conclusion

    这个功能,只要找对了函数就好简单,没啥说的,开始写下一篇吧~

    猜你喜欢:👇🏻
    【Matlab】判断是否为空?是否为NaN?
    【Matlab】如何确定数组中存在哪几个数?
    【Matlab】如何提取矩阵中特定位置的元素?

    在这里插入图片描述

    展开全文
  • [LeetCode] Delete Operation for Two Strings 两个字符串的删除操作 求最大子序列的长度, 然后总长度减去 2*序列长度 ...两个字符不相等的时候就是 dp[i][j]= Math.max(dp[i-1][j], dp[i][j-1]) i个字符和j...

    [LeetCode] Delete Operation for Two Strings 两个字符串的删除操作

    求最大子序列的长度, 然后总长度减去 2*子序列长度

    两种情形求子序列 dp[i][j] = dp[i-1][j-1] + 1 好理解吧 就是当前两个字符相等

    两个字符不相等的时候就是 dp[i][j]= Math.max(dp[i-1][j], dp[i][j-1]) i个字符和j-1 也就是j之前的那些字符 以及 j-1和i个字符比较

    Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

    Example 1:

    Input: "sea", "eat"
    Output: 2
    Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
    

     

    Note:

    1. The length of given words won't exceed 500.
    2. Characters in given words can only be lower-case letters.

     

    这道题给了我们两个单词,问我们最少需要多少步可以让两个单词相等,每一步我们可以在任意一个单词中删掉一个字符。那么我们分析怎么能让步数最少呢,是不是知道两个单词最长的相同子序列的长度,并乘以2,被两个单词的长度之和减,就是最少步数了。其实这道题就转换成求Longest Common Subsequence最长相同子序列的问题,令博主意外的是,LeetCode中竟然没有这道题,这与包含万物的LeetCode的作风不符啊。不过没事,有这道题也行啊,对于这种玩字符串,并且是求极值的问题,十有八九都是用dp来解的,曾经有网友问博主,如何确定什么时候用greedy,什么时候用dp?其实博主也不不太清楚,感觉dp要更tricky一些,而且出现的概率大,所以博主一般会先考虑dp,如果实在想不出递推公式,那么就想想greedy能做不。如果有大神知道更好的区分方法,请一定留言告知博主啊,多谢!那么决定了用dp来做,就定义一个二维的dp数组,其中dp[i][j]表示word1的前i个字符和word2的前j个字符组成的两个单词的最长公共子序列的长度。下面来看递推式dp[i][j]怎么求,首先来考虑dp[i][j]和dp[i-1][j-1]之间的关系,我们可以发现,如果当前的两个字符相等,那么dp[i][j] = dp[i-1][j-1] + 1,这不难理解吧,因为最长相同子序列又多了一个相同的字符,所以长度加1。由于我们dp数组的大小定义的是(n1+1) x (n2+1),所以我们比较的是word1[i-1]和word2[j-1]。那么我们想如果这两个字符不相等呢,难道我们直接将dp[i-1][j-1]赋值给dp[i][j]吗,当然不是,我们还要错位相比嘛,比如就拿题目中的例子来说,"sea"和"eat",当我们比较第一个字符,发现's'和'e'不相等,下一步就要错位比较啊,比较sea中第一个's'和eat中的'a',sea中的'e'跟eat中的第一个'e'相比,这样我们的dp[i][j]就要取dp[i-1][j]跟dp[i][j-1]中的较大值了,最后我们求出了最大共同子序列的长度,就能直接算出最小步数了,参见代码如下:

    解法一:

    class Solution {
        //这道题转换为求最大共同子序列的问题
        public int minDistance(String word1, String word2) {
            int m = word1.length(), n = word2.length();
            //dp表示的是word1前i个字符  和  word2前j个字符中相等子序列的最大长度
    //这里的dp[0][0]就是0了 当都为空的时候默认公共长度就是0
            int[][] dp = new int[m+1][n+1];
            for(int i = 1; i <= m; i++){
                for(int j = 1; j <= n; j++){
                    if(word1.charAt(i - 1) == word2.charAt(j - 1))
                        //如果i j处相等 长度等于之前的+1
                        dp[i][j] = dp[i-1][j-1] + 1;
                    else
    // 如果不等,那么难道我们直接将dp[i-1][j-1]赋值给dp[i][j]吗,
    当然不是,我们还要错位相比嘛,比如就拿题目中的例子来说,"sea"和"eat",
    当我们比较第一个字符,发现's'和'e'不相等,下一步就要错位比较啊,
    比较sea中第一个's'和eat中的'a',sea中的'e'跟eat中的第一个'e'相比,
    这样我们的dp[i][j]就要取dp[i-1][j]跟dp[i][j-1]中的较大值了,
    最后我们求出了最大共同子序列的长度,就能直接算出最小步数了,
    我觉得这个解释不太号 比如 abcde abcf
    假如最后一位不相等了 就是第4位不等,剩下的最大数组长度只可能是下面这两种情况
     那么我们考虑的范围可以是abcd  abc相比较 或者 abc abc相比较
                        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
            return (m + n) - 2 * dp[m][n];
        }
    }

    第二次

    class Solution {
        public int minDistance(String word1, String word2) {
            int m = word1.length(), n = word2.length();
            int[][] dp = new int[m+1][n+1];
            for(int i = 1; i <= m; i++){
                for(int j = 1;j <= n; j++){
                    if(word1.charAt(i-1) == word2.charAt(j-1))
                        dp[i][j] = dp[i-1][j-1] + 1;
                    else
                        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
            return (m+n)-dp[m][n] * 2;
        }
    }

     

    展开全文
  • 这算是编程之美上面一道很经典题目,不过题目还是有几种变形,一种是要求两边有相同个数的元素(开始元素数保证为偶数,编程之美上的原题),另一道限制较宽松,对两边数组的元素数没有要求,只要元素和之间尽...

    这算是编程之美上面一道很经典题目,不过题目还是有几种变形,一种是要求两边有相同个数的元素(开始元素个数保证为偶数,编程之美上的原题),另一道限制较宽松,对两边子数组的元素个数没有要求,只要元素和之间尽可能的接近;

           这道题目不是具有很严格的最优子结构,但是按照下面所摘录的博客思路增大一维的状态空间 逼近一个不确定的目标值,(而不是固定的sum/2)可以对应到动态规划求解,但是觉得这种思路不太优雅,而且在元素值比较大时算法复杂度太大(O(n*sum)  sum>>n),其实按照作者思路稍微变通一下,舍去扫描一个元素更新整个状态空间的,直接将已有的状态值加上当前元素插入新状态就好,因为这样我们记录所有可达的状态,不用去优化任意一个状态S(1-sum/2)的逼近值,算法效率会大大提升;

            综上所述,我们可以按题目中的两种要求分别设计方案:

    1.对元素个数没有限制 : 只需使用set记录所有当前可达的部分和状态即可(如果要求出一个最优解的话使用map,key为状态值,val为前驱状态值,回溯回去可得一个可行序列)

    	set<int> partialSumSet;//元素每一趟扫描,不能一个个插入新值,只能在一趟更新结束后一次性加入
    	set<int> newStateSet;
    
    
    	for(int i=0; i<sizeof(A)/sizeof(A[0]); i++)
    	{
    		for(set<int>::iterator it=partialSumSet.begin(); it!=partialSumSet.end(); it++)
    			newStateSet.insert(*it+A[i]);
    		newStateSet.insert(A[i]);//别忘了插入单个元素值,在一开始插入一个0等效
    		//一次性插入新元素
    		for(set<int>::iterator it=newStateSet.begin(); it!=newStateSet.end(); it++)
    			partialSumSet.insert(*it);
    		newStateSet.clear();
    	}


    如果要保证元素相同可以考虑同时记录每个状态对应的元素个数(可能有多个值,用set记录)map<int sum, set<val_num> >,具体代码类似

     




         下面的讨论引自一篇文章,作者分析的很到位,但是还是有不少逻辑不严密的地方,算法复杂度也偏大,但分析思路值得借鉴的,原帖地址:http://blog.csdn.net/ultrani/article/details/7409584


     在iteye看到一个问答(iteye被csdn收编了,该不算广告吧),大致是:给出一个数组和一个数字target,问数组那几个数之和与target相等。

            问题看起来还挺简单。不过代码却不是一步到位立马能写出的。想着想着,突然发现这个问题和我之前发的博文中描述的问题基本是同一个类型的问题(见回溯算法复习)。于是由自然而然的想用回溯进行穷举了。不过在这个问题的回答者中,有一个人回答说用动态规划解即可,这时就勾起我的兴趣了,难道这类题本来就可以通过动态规划解答?而本文后续给出的答案表明,这是肯定的。

            在介绍该题解答之前,首先简单回顾下动态规划是怎么解题的。根据算法导论所介绍,该算法一般分为4个步骤:

    1. 定义最优解结构
    2. 递归定义最优解的值
    3. 自底向上计算最优解的值
    4. 由计算出的结果构造一个最优解
            下面简单的解释下这4个步骤。
            1. 定义最优解结构。一个问题的最优解总包含了子问题的一个最优解,或者说一个问题的最优解由子问题的最优解组成,那么就说这个问题具有最优子结构( optimal substructure)。比如,求二叉树高度的问题中(该问题本来可以只通过递归遍历数结构皆可求解,这里为例子说明方便就不用遍历方式求解,并且树结构以链表方式保存在内存中——每个子结点有引用指向父结点),一棵二叉树中根结点距离哪个叶子结点路径最长的解,就由去掉根结点后各个子树的最长路径的解组成;每个子树又具有这个最优子机构,又可以继续分解出各个子树的解。
            2. 递归定义最优解得值。在了解了最优子结构组成,那肯定就需要有个工具判断哪个子解更有可能成为总最优解的一部分,所以可以递归的定义解和子解的关系,以及子解的选取依据。在上面说的二叉树最深路径问题中可以得到这么一个公式: H父结点a =max( H子结点a1 H子结点a2 ) + 1。Hx表明x作为根结点时树的最深高度。第二部反映了两方面的内容,一个是解和子解间的关系,二是哪个比哪个好得评判标准。
            3. 自底向上计算最优解的值。有了问题的解和子解的关系以及评判尺度,那么,我们完全可以从最底层出发,自底向上计算出所有的解了。最低层的子解可以通过边界条件来计算获得。比如最底层的子树肯定就是深度为1或者深度为二的解了。在计算期间,还体现了动态规划的另一个特点,就是 保存计算过的值,以后再遇到相同的计算式直接引用之前的结果。这样有效避免了重复计算的资源浪费,提高效率。
            4. 构造最优解结构。经过了第3步,我们已经可以对每个结点,根据公式能选取最优的子解了。这样只需要自上而下,我们就可以把总得最优解结构构造出来了。对于二叉树深度的例子而言,就是每个根结点依据公式,都知道哪个子结点具有最深的深度,自然就知道选择哪个结点往下走了。

            所以,从上面4个步骤中可以看到,就想算法导论里面说到的,要应用动态规划,那问题就需要有2个特点。 一是具有最优子结构,二是具有重复子问题。上面二叉树高度的例子中,假设父结点a到叶子结点最长路径Pa落在子节点a1上,那么,a1结点到叶子结点的最长路径也一定蕴含在Pa里面,所以说其具有最优子结构。而每个结点的最高高度肯定会在求其祖先结点被引用到(其实其结果在整个计算过程中只被引用一次,这里用二叉树高度来具有不是非常恰当),也算是有重复子问题。所以二叉树高度也可以用动态规划来解决。

            那回到本文一开始的问题中,我们的数组该怎么选着其元素让所选元素之和恰好等于target值呢?我们先看下这个问题是否能用动态规划来解决,也就看是否具有上面上所说的最优子结构和重复子问题是否蕴含在题目之中。先定义下相关约定:设数组 A的每个元素为 Ai(i=1..n) 目标target值为 T,要求解的元素集合为 X
            
            我们先看下能不能定义一个最优子结构。我一开是想到的是假设 W (i)定义为从A取i个元素中某几个元素之和,使该和在前i个元素中最接近 T 。显然,我们的目标是找出 W (n)- T =0 的元素组合 X 。这时我们尝试找出父子问题的关系: W (j)=APPR { W (j-1)+ A j,  W (j-1) } ,W(j)是前j个元素中能选出的最接近T的和, W (j-1) 是j-1元素中能选出的最接近T的和,APPR{} 表示从大括号里面比较看哪个值更接近target值。该公式尝试定义这么一个关系:前j个元素中能构成最接近T的元素之和,等于2个子问题 W (j-1)+ A j和 W (j-1)中最接近 T 的那一个。但实际情况是,该等式是不成立的。因为当W(j-1)最接近T的时候, W(j-1)+Aj不一定最能最接近T,就是说,该候选解不具备最优子结构。只有当W(j-1)最接近T-Aj时候,W(j-1)+Aj才会存在最优。
            所以我们应该把前i个元素中被选元素最接近某个值的和也加入到 W 的参数中。可以定义: W (s,j)的值为选取前i个元素中某几个元素的和,使该和与s最接近。这样, W(s,j)=APPR {W(s-Aj, j-1)+Aj, W(s,j-1) } W (s-Aj, j-1)+ A j表明在选择 A j作为 X 的元素之一的情况下所能达到最接近s的值, W (s,j-1)表明在不选择 A j作为 X 的元素时所达到最接近s的值,二者最接近 s 的就作为 W (s,j)的值。这样,当各个子问题求出最优解时,父问题就迎刃而解了。目标就是求 W ( T , j)时候 X 的组合。

            找出最优子结构,并且给予递归定义后,我们就可以从下往上地进行计算了。从 W 的参数可以看出,构造保存计算结果的矩阵大小为s x j。
            递归边界条件:(1)s>=1,j>=1; 
                                        (2)当j=1是, W (s, 1)= A 1;          (1)(2)推得:W(i, 1)=A1 (i=1..n)
                                        (3)当 s< A j 时 W (s- A j, j-1)   = 0; 
                                        (4) s= A j 时, W (s,j)=s= A j 。
            迭代计算过程如下:
    [plain]  view plain copy
    1.     对每个j循环for (j=2..n)  
    2.              对每个s循环for(s=1..Sum(A))  
    3.                     if (s=Aj)  W[s][j] = Aj 并到下一个s  
    4.                     if (s<Aj)   
    5.                          set 选择Aj的最接近和=Aj  
    6.                     else   
    7.                          set 选择Aj的最接近和=W[s-Aj][j-1]+ Aj;  
    8.                     end if  
    9.                     set 不选择Aj的最接近和=W[s][j-1]  
    10.                     if (选择Aj使得更接近s) {  
    11.                          set W[s][j]=不选择Aj的最接近和  
    12.                     else  
    13.                          set W[s][j]=选择Aj的最接近和  
    14.                     end if  
    15.              end for  
    16.     end for  
            经过计算后 W ( T , j)就是最接近 T 的值,假如 W ( T , j)= T ,那么此时的 X 就是所求元素的组合

             结果有了,但是X的具体最优解元素时那几个数呢?这是,W矩阵已经填充了数值,只要再根据 W (s,j)=APPR { W (s- A j, j-1)+ A j,  W (s,j-1) } ,即可在每次计算中判断是否选择第j个元素了。

            具体实现代码在文章最后给出。

            问题解决了,但是,这个父子关系的递归式只有这一个吗?为什么用s参数和j参数来限定子问题?类似的,我们还可以用下面这个递归式表示:

         W(s, {M})=APPR {W(s-Ai, {M-Ai})+Ai : Ai属于{M})

            其中{M}表示一个若干Ai的集合。这个递归式定义W(s,{M})为从{M}中取若干个元素使其相加最接近s时的和。这个和原来的其实很像,但是区别在于,后者中每个拥有n个元素{M}的父问题都有n-1个子问题。这样递归到最底层就有n!个子问题需要解决。而本质上原问题假使用穷举的方法枚举所有可能性,也只有2的n次方个问题,说明第二种子结构的划分要解决大量重复的子问题。因为W(s, {M})中引入的集合具有无序性,而第一个W(s,j)却利用了有序性,由此可见不同的子结构在解决问题的范围还是有很大差异,关键是要提高子问题在甄别问题的解的效率。关于这个问题可以参考下面这篇文章:http://mindhacks.cn/2010/11/14/the-importance-of-knowing-why-part2/。其实文章所讨论的问题的解决思路也是借鉴于这篇文章的^_^。

            附程序(该程序求解是回溯算法复习里面的题目,原理一样,本篇文章开头问题的代码就不另外贴出了):

    [java]  view plain copy
    1. package puzzle;  
    2.   
    3.   
    4. /** 
    5.  * 给出一个数组,要怎么划分成2个数组使得2数组和之差最少<br/> 
    6.  * 本质上就是,从数组中如何取数使其和等于某个target值,这里分割后的2个数组的平均值就是target值 
    7.  * @author nizen 
    8.  * 
    9.  */  
    10. public class ArrayCutting {  
    11.   
    12.     private int avg;  
    13.       
    14.     private int[][] k;  
    15.       
    16.     private void checkit(int[] array){  
    17.         if (array == null || array.length==0) {  
    18.             throw new IllegalArgumentException();  
    19.         }  
    20.     }  
    21.     // 初始化定义target值和边界值  
    22.     private void init(int[] array) {  
    23.         int sum = 0;  
    24.         for(int i=0;i<array.length;i++) {  
    25.             sum += array[i];  
    26.         }  
    27.         avg = Math.round(sum / 2);  
    28.           
    29.         k = new int[avg+1][array.length+1];  
    30.           
    31.         for (int w=1; w<=avg; w++) {  
    32.             for(int j=1; j<=array.length; j++) {  
    33.                 if (j==1){  
    34.                     k[w][j]=getValueJ(array,j);  
    35.                     continue;  
    36.                 }  
    37.             }  
    38.         }  
    39.     }  
    40.       
    41.     public int[] cutit(int[] array) {  
    42.         checkit(array);  
    43.           
    44.         init(array);  
    45.           
    46.                 // 自底向上构造矩阵  
    47.         for (int j=2; j<=array.length; j++) {  
    48.             for (int w=1; w<=avg; w++) {  
    49.                 int valueAfterCutJ = w-getValueJ(array,j);  
    50.                 int lastJ = j-1;  
    51.                   
    52.                 if (valueAfterCutJ == 0) {  
    53.                     k[w][j] = getValueJ(array,j);   //选择J后差值为0则选择J为结果值  
    54.                     continue;  
    55.                 }  
    56.                 int valueChooseJ = 0;  
    57.                 if (valueAfterCutJ < 0) {  
    58.                     valueChooseJ = getValueJ(array, j); //期望值比J小则取J为选择J后的值  
    59.                 } else {  
    60.                     valueChooseJ = k[valueAfterCutJ][lastJ] + getValueJ(array,j);  
    61.                 }  
    62.                   
    63.                 if (Math.abs(k[w][lastJ]-w) < Math.abs(valueChooseJ-w)  ) {  
    64.                     k[w][j]=k[w][lastJ];  
    65.                 } else {  
    66.                     k[w][j]=valueChooseJ;  
    67.                 }  
    68.             }  
    69.         }  
    70.           
    71.         return findPath(array);  
    72.     }  
    73.       
    74.         // 最后一步:构造出最优解  
    75.     private int[] findPath(int[] array) {  
    76.         int[] result = new int[array.length];  
    77.         int p=0;  
    78.         int j=array.length;  
    79.         int w=avg;  
    80.         while(j>0){  
    81.             int valueAfterCutJ = w-getValueJ(array,j);  
    82.             int lastJ = j-1;  
    83.               
    84.             if (valueAfterCutJ == 0) {  //清0跳出  
    85.                 result[p++]=getValueJ(array,j);  
    86.                 w=w-getValueJ(array,j);  
    87.                 break;  
    88.             }  
    89.             int valueChooseJ = 0;  
    90.             if (valueAfterCutJ < 0) {  
    91.                 valueChooseJ = getValueJ(array, j); //期望值比J小则取J为选择J后的值  
    92.             } else {  
    93.                 valueChooseJ = k[valueAfterCutJ][lastJ] + getValueJ(array,j);  
    94.             }  
    95.               
    96.             if (Math.abs(k[w][lastJ]-w) > Math.abs(valueChooseJ-w)  ) {  
    97.                 result[p++]=getValueJ(array,j);  
    98.                 w=w-getValueJ(array,j);  
    99.             }  
    100.             j=j-1;  
    101.         }  
    102.         return result;  
    103.     }  
    104.   
    105.     public static void main(String[] args) {  
    106.         ArrayCutting ac = new ArrayCutting();  
    107.         int[] r = ac.cutit(new int[]{87,54,51,7,1,12,32,15,65,78});  
    108.         int selectedSum = 0;  
    109.         for (int i=0;i<r.length;i++){  
    110.             if (r[i]>0){  
    111.                 selectedSum +=r[i];  
    112.                 System.out.print(r[i]+"+");  
    113.             }  
    114.         }  
    115.         System.out.println("="+selectedSum+" Target="+ac.avg);  
    116.     }  
    117.       
    118.         // 返回第j个数组元素  
    119.     private int getValueJ(int[]array, int j){  
    120.         return array[j-1];  
    121.     }  

    展开全文
  • 动态规划 求两个序列A,B中所有的最长公共序列 第一部分、什么是动态规划算法 动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足...
  • 什么是二阶行列

    千次阅读 2019-03-20 14:01:28
    文章转载至人工智能中文网 二阶行列式,用于快速解二元线性方程组。例如,下面这个二元线性方程组: ...此时可见,式子中的 x2的系数相同,此时可用第一个式子减去第二个式子,就可消去 x2...
  • 4基本空间

    千次阅读 2014-07-04 21:05:38
    前面我们已经介绍过矩阵的两个重要空间:列空间和零空间,今天继续介绍矩阵的另外两个重要空间:行空间和左零空间。A的行空间就是AT的列空间,A的左零空间就是AT的零...,但我们还是从A的角度去看待这两个子空间。 4
  • 两个数的平均值

    千次阅读 2018-04-10 00:31:50
    一、我们一般都会想到求两个平均值是(a+b)/ 2,可是当a和b是两个非常大的整数,显然会超过int的最大范围,所以这种方式不合理。...b 这个表达式其实是求得两个数二进制bit位对应位相同的0或者1,当两个数...
  • 0x00 前言 现代密码学实验之一,偏基础,原理简单,但是本次实验在用python写的时候出现了一些阻碍,也是一直以来对进制的理解出现了... 如果两个数位数不同,那么高位不变,等待位数相同再进行计算,下面给出几个...
  • 两个对象重复意味着这两个对象的内容相同、hashcode值也相同。 (1)两个对象A和B内容相同,表示A.equals(B)的值为true。 (不重写的话,默认equals()方法是调用”=="进行判断的,”=="判断的是两个对象的引用是否...
  • 两个句子之间语义相似度项目

    千次阅读 热门讨论 2018-04-15 20:13:01
    项目内容:本次项目提供一系列的英文句子对,每个句子对的两个句子,在语义上具有一定的相似性;每个句子对,获得一个在0-5之间的分值来衡量两个句子的语义相似性,打分越高说明两者的语义越相近。 项目提供数据为...
  • ...​tmp = [val for val in a if val in b] #列表推导求的两个列表的交集 ​print tmp #[2, 5] #方法二 ​ print list(set(a).intersection(set(b))) #列用集合的取交集方法2. 获取两个li...
  • 用父私钥推导私钥,可以推导出种子私钥,一种是普通的私钥,一种是增强型私钥。而题目里说的相同公钥其实只是普通的公钥。也就是说,用父公钥是无法推导出相同公钥的。 用普通父私钥推导私钥的...
  • 空间能用种方式描述。第一,我们可以给出一生成空间的向量集合。(例如:列生成列空间)第二,我们可以给出空间中的向量必须满足什么条件。(例如:零空间包含满足Ax=0Ax=0 的所有向量)第一描述可能包含无用的...
  • 假设给定两个字符串str1和str2,如果我们想把str1变为str2,这一过程中所需的最少的插入、删除和替换等基本操作的个数称为str1与str2之间的编辑距离。比如如果想把字符串abandon变为aband最好的方案是删除on这两个...
  • 两个数的最大公因数和最小公倍数

    千次阅读 多人点赞 2018-09-20 21:12:49
     首先不急着写代码,这个题主要点就在于怎么求最大公因数和最小公倍数,所以我们先来分析一下求这两个数的方法 ,假设这里两个数a,b;下面是我的解题思路: 最大公因数 我先随便给ab赋值,我们先来看看这个测试 ...
  • 本系列其他文章见:《响应Spring的道法术器》。 前情提要:响应流 | lambda与函数 | Reactor快速上手 1.3.3 Spring WebFlux Spring WebFlux是随Spring 5推出的响应Web框架。 1)服务端技术栈 ...
  • Python3实现两个Excel文件内容比对

    千次阅读 2018-07-03 17:49:09
    最近在工作中,需要人工比对大量的excel格式报表,刚好刚学了Pyhon入门基础知识,想着写东西练练手,不但能提高代码编写能力,还能减轻工作量,提高工作效率。说干就干,简单的理了逻辑。首先,将目标表和源表的...
  • 三相有功功率表的工作原理与单相有功功率表的相同,在结构上分为二元三相...接线时应遵循下列两条原则。  图1 二元三相功率表的内部线路  图2 二元三相功率  a.两个电流线圈At、A3可以任意串联接入被 表
  • 最近做题遇到一算法题,让求两个正整数的最大公约数和最小公倍数,一想,只要求出两个数的公共质因子就可以求出来了最大公约数了,然后再用两数的积除以最大公约数就可以得到最小公倍数了。 可是当数比较大时,消耗...
  • 如果你熟悉c++,那么你可能知道一叫做”spirit”的parser库。它利用c++的模板元编程能力,使用c++语言本身提供了一递归下降文法解析的框架。我这里介绍的jparsec库,就是一java里面的递归下降文法解析框架。...
  • 解递归种方法(代换+递归树)

    千次阅读 2018-05-12 23:40:12
    算法设计中经常会用到递归,利用递归的方法可以清晰地显示算法的整个过程,而对于分析算法的复杂度,解...现在,我们看下面例子:我们先假设一结论T(n) = O(lg(n - b)),并且假设对T(n / 2上取整)成立(这...
  • 管理(segmentation),是指把一程序分成若干段(segment)进行存储,每段都是一逻辑实体(logical entity),程序员需要知道并使用它。它的产生是与程序的模块化直接有关的。段管理是通过段表进行的...
  • 使用system函数时应该忽略两个信号

    千次阅读 2013-05-11 16:48:34
    在8.13节,我们展示了一system函数的实现。然而,那个版本没有处理信号。POSIX.1要求system忽略 SIGINT和SIGQUIT并阻塞SIGCHLD。在展示正确处理这些信号的版本之前,我们看下为什么需要担心这些信号的处理。 ...
  • 一、程序通过编译,并实现两个命题的各种逻辑运算 二、任意输入字符串P和Q逻辑表达式的合法性检查 三、利用真值表方法验证他们的等价性
  • SpringBoot声明事务的简单运用

    万次阅读 多人点赞 2018-06-27 14:01:56
    Spring声明事物的实现,有种方式;第一种是配置xml,第二种是使用相关注解(这种方式可详见《程序员成长笔记(一)》的相关章节)。SpringBoot中默认配置了第二种方式,所以,SpringBoot直接使用注解即可。下面...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 222,137
精华内容 88,854
关键字:

下面两个式子相等的是