精华内容
下载资源
问答
  • Java实现寻找和为定值的多个数

    万次阅读 多人点赞 2019-07-21 20:52:20
    输入两个整数nsum,要求从数列1,2,3,…,n中随意取出几个数,使得它们的等于sum,请将其中所有可能的组合列出来。 2 解决方案 上述问题是典型的背包问题的应用,即先找出n个数的所有组合,再在这些组合中寻找组合...

    1 问题描述
    输入两个整数n和sum,要求从数列1,2,3,…,n中随意取出几个数,使得它们的和等于sum,请将其中所有可能的组合列出来。

    2 解决方案
    上述问题是典型的背包问题的应用,即先找出n个数的所有组合,再在这些组合中寻找组合数相加之和等于sum的组合,并依次输出这些组合中的数。

    package com.liuzhen.array_2;
    
    public class ManySumN {
        /*
         * 函数功能:以字符串形式返回1~n个数的所有子集,其中0代表不包含其中数字i,1代表 包含其中数字i
         * 此段代码是运用反射格雷码的思想,具体解释详见:算法笔记_019:背包问题(Java)
    */
        public String[] getAllGroup(int n){
            int len = (int) Math.pow(2, n);
            String[] result = new String[len];
            if(n == 1){
                result[0] = "0";
                result[1] = "1";
                return result;
            }
            String[] temp = getAllGroup(n-1);
            for(int i = 0;i < temp.length;i++){
                result[i] = "0" + temp[i];
                result[len-1-i] = "1" + temp[i];
            }
            return result;
        }
        /*
         * 参数n:代表有1~n的n个不同整数
         * 函数功能:打印出1~n中所有随机组合的几个数,其相加的和等于sum
         */
        public void printManySumN(int n,int sum){
            System.out.println("1~"+n+"个数中,相加之和等于"+sum+"的所有组合数为:");
            String[] allGroup = getAllGroup(n);
            for(int i = 0;i < allGroup.length;i++){
                char[] temp = allGroup[i].toCharArray();
                int tempSum = 0;
                for(int j = 0;j < temp.length;j++){
                    if(temp[j] == '1')
                        tempSum += (j+1);
                }
                if(tempSum == sum){
                    for(int j = 0;j < temp.length;j++){
                        if(temp[j] == '1')
                            System.out.print((j+1)+" ");
                    }
                    System.out.println();
                }
            }
        }
        
        public static void main(String[] args){
            ManySumN test = new ManySumN();
            test.printManySumN(10, 16);
        }
    }
    

    运行结果:

    1~10个数中,相加之和等于16的所有组合数为:
    9 
    10 
    5 7 
    4 9 
    5 8 
    6 7 
    3 5 6 
    3 4 7 
    4 10 
    5 9 
    6 8 
    2 6 7 
    2 5 8 
    2 4 9 
    2 3 4 6 
    2 3 10 
    3 5 7 
    3 4 8 
    4 5 6 
    5 10 
    6 9 
    7 8
    
    展开全文
  • 1 寻找和为定值的两个数 题目:输入一个数组一个数字,在数组中查找两个数,使得它们的正好是输入的那个数字。 example: 例如输入数组1、2、4、7、11、15数字15。由于4+11=15,因此输出411。 思路1:...
    1 寻找和为定值的两个数
    题目:输入一个数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。
    example:  例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

    思路1: 若数组无序,首先用快排排序O(n*log n)
    然后从头遍历每个数, 对其互补的数用二分查找,因为二分查找的时间复杂度是O(log n),所以总的时间复杂度也就是O(n*log n)

    思路2 :构造hash表的思想,hash查找的特点:可以快速查找到给定的数字是否在表中,以及在表中的位置。
    当构造好hash表后, 查找其互补的数字的时间复杂度就不是O(n),而是O(1)了
    缺点:构造hash额外增加了O(N)的空间

    思路3(可能是最优思路): 
    排序后得到的原始序列:1、 2、 4、 7、11、15     用输入数字15减一下各个数,得到对应的序列为:
    对应序列:14、13、11、8、4、 0     

    要达到O(N)的复杂度,第一个数组以一指针i 从数组最左端开始向右扫描,第二个数组以一指针j 从数组最右端开始向左扫描,首先初始i指向元素1,j指向元素0, 谁指的元素小,谁先移动 ,由于1(i)>0(j),所以i不动,j向左移动。然后j移动到元素4发现大于元素1,故而停止移动j,开始移动i,直到i指向4,这时,i指向的元素与j指向的元素相等,故而判断4是满足条件的第一个数;然后同时移动i,j再进行判断,直到它们到达边界

    排序后,时间复杂度由二分查找的O(n*log n)降为O(n)

    ----------------------------------------------------------

    2 寻找和为定值的多个数

    编程求解:
    输入两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数,
    使其和等于 m ,要求将其中所有的可能组合列出来。

    这个问题就是典型的0,1背包问题了,设函数f(n,m)就是最终的结果,那么
    f(n,m)无非由以下两种情况构成:
    1.n包含在最优解中,即:放n,n-1个数填满sum-n   f(n,m)= f(n-1,sum-n) 并 n
    2.n不包含在最优解中,即:不放n, n-1个数填满sum   f(n,m) = f(n-1, sum)


    展开全文
  • Algorithm:C+语言实现之数组相关算法(和为定值的两个数、和为定值的m个数、荷兰国旗、长度2n的洗牌算法、任意长度数组的洗牌算法) 目录 数组 1、寻找和为定值的两个数 2、和为定值的m个数 3、荷兰国旗...

    Algorithm:C+语言实现之数组相关算法(和为定值的两个数、和为定值的m个数、荷兰国旗、长度为2n的洗牌算法、任意长度数组的洗牌算法)

     

     

    目录

    数组

    1、寻找和为定值的两个数

    2、和为定值的m个数

    3、荷兰国旗问题

    展开全文
  • C++求数组中和为定值的组合

    千次阅读 2017-05-11 17:08:38
    回溯法求矩阵中和为定值的组合题目描述: 给定整数数组A,求和sum的所有组合,并输出。还有一种类似题目是,求所有组合的个数。 要求:输出子数组不能改变元素在原始数组中的相对位置。 题目要求不能改变相对...

    回溯法求矩阵中和为定值的组合

    题目描述:
    给定整数数组A,求和为sum的所有组合,并输出。还有一种类似题目是,求所有组合的个数。
    要求:输出子数组不能改变元素在原始数组中的相对位置。
    题目要求不能改变相对位置表示不能对原始数组排序。
    C++实现如下:

    void sumn(vector<int> &A,int start,int end,int sum,vector<int> &tmp,vector<vector<int>> &res){
        if (start == end && sum == 0)
        {
            res.push_back(tmp);
        }
        else if (start == end) return;
        else{
            if (sum >= A[start]){
                tmp.push_back(A[start]);
                sumn(A, start + 1, end, sum - A[start], tmp, res);
                tmp.pop_back();
            }
            sumn(A, start + 1, end, sum, tmp, res);
        }
    }
    展开全文
  • 在数组中,求和为定值的元素组合

    千次阅读 2015-06-21 20:13:53
    实现思路已注释在代码当中,如下: // 存储可行结果 ... 程序员编程艺术:第五章、寻找满足和为定值的两个或多个数 http://blog.csdn.net/v_JULY_v/article/details/6419466
  • 求数组中和给定的所有子序列

    千次阅读 2017-09-20 09:53:46
    import java.util.ArrayList; import java.util.Arrays;... * 求数组中和给定的所有子序列 * * 如:数组[1,2,3,4,5,6],sum=7时,满足条件的子数组有[1,2,4],[3,4],[2,5],[1,6]; * * @author zxt * */ p
  • 问题在于只用C语言,递归回溯都不太懂,希望给个大概的思路,初学语言,谢谢了!
  • 电力系统中的定值区是什么意思

    千次阅读 2017-11-06 11:15:17
    1、定值区的概念是指继电保护装置在运行中,由于运行方式的变化,需要改变其定值,而在微机保护装置中设置多个区域,存放相似的定值,可以只有几项定值不同。而满足系统设备的不同运行方式。举例说明:某个变电站的...
  • @function:定义函数,求输入数字的,平均,最大,最小值(要求使用不长参数) 实现思路: 1)输出参数,用逗号分隔 2)将分隔出来的参数转换成整形,以便处理 3)将列表传参进函数,(问题遗留:...
  • 不可变数组实现案例 public class Test { static int[] flag = new int[100]; static int index = 0;// 记录当前 ... public static void numGroup(int[] arr, int start, int length, int sum) { ...
  • 所有特征大于零的矩阵一定是正定阵吗?

    万次阅读 多人点赞 2018-10-12 21:08:38
    A 的特征值为12,各阶主子式也大于零。但是取 x = [ 1    − 1 ] T x = [1 \;-1]^T x = [ 1 − 1 ] T , x T A x = [ 1      − 1 ] [ 1 0 4 2 ] [ 1 − 1 ] = − 1 < 0 , \\x^...
  • python中如何利用蒙特卡洛平均法求积分? 二、解决方法 (1)基本理论与操作说明 1、蒙特卡洛 (Monte Carlo) 求积分概述 蒙特卡洛方法也称统计模拟方法、随机抽样技术,是基于“随机数”、概率统计理论基础的...
  • 给定一个整数数组 nums一个目标 target,请你在该数组中找出和为目标的那两个整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给.....
  • 平均法计算积分

    千次阅读 2015-12-11 12:56:12
    //用平均计算积分 //a区间左端点,b区间右端点,nx取值次数 double Integration( double a, double b, int n) { static RandomNumber rnd; double y = 0 ; for ( int i= 1 ; i; i++) ...
  • 1、计算π  问题描述  设有一半径r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数k。由于所投入的点在正方形上均匀分布,因而所投入的点落入圆内的概率 。所以当n足够大时,k与n之比...
  • 以函数f(x)=sin(x)/x例,求解其在[0,1]区间的积分。 #include #include #include #include #include using namespace std; const int inf=0x3f3f3f3f; double f(double x)//定义修改函数f(x) { if...
  • 任意矩阵A (mxn), 都能被奇异分解: 其中, U是mxm的正交矩阵, V是nxn的正交矩阵, Σr是由r个沿对角线从大到小排列的奇异组成的方阵. r就是矩阵A的秩. 2. Moore-Pseudo逆 任意矩阵A, 若存在矩阵X, ...
  • 蒙特卡洛估算积分的第二种方法本文首发于个人微信公众号“我将在南极找寻你”平均法前几天,我们利用蒙特卡洛的随机投点法实现了y=x^2在0到1上的积分的估算(传送门),今天,我们介绍另一种蒙特卡洛估算...
  • 用了libSVM作为工具,预测交通流量,用t-2,t-1,t时刻的数据作为输入,t+1作为输出,80个向量训练集,40个测试集,做了数据归一化,但是预测的结果是一个定值,想请问下问题出在哪儿?是模型参数的问题,还是别的...
  • 一组测定值中与平均值的偏差超过两倍标准差的测定值,与平均值的偏差超过三倍标准差的测定值,称为高度异常的异常值。【百度百科】 缺失值(missing value):是指粗糙数据中由于缺少信息而造成的数据的聚类、...
  • 用matlab画(求)没有原函数的不定积分图像(积分)问题描述求积分画原函数图像具体实例结论 问题描述 一般情况,用matlab的int函数可以很方便求解一个不定积分或者积分,并且通过plot画出其图像,但是...
  • 6-5 求自类型元素的最大(10 分)本题要求实现一个函数,求N个集合元素S[]中的最大,其中集合元素的类型自定义的ElementType。函数接口定义:ElementType Max( ElementType S[], int N ); 其中给定集合...
  • tp判断数组里面是否存在某个定值

    千次阅读 2019-12-12 19:07:59
    <?php $people = array("Bill", "Steve", "Mark", "David"); if (in_array("Mark", $people)) { echo "匹配已找到"; } else { echo "匹配未找到"; } ?> 这样就OK了
  • 这是一张照片,像素高度450*宽度333。 我们都知道,图片实际上对应着一个矩阵,矩阵的大小就是像素大小,比如这张图对应的矩阵阶数就是450*333,矩阵上每个元素的数值对应着像素.我们记这个.
  • 机器学习(十五)SVD(特征分解奇异分解的区别)

    万次阅读 多人点赞 2018-04-14 18:47:49
    首先从意义上理解:作者:赵文和链接:https://www.zhihu.com/question/19666954/answer/54788626来源:知乎著作权归...以Ax = b例,x是m维向量,b是n维向量,m,n可以相等也可以不相等,表示矩阵可以将一个向量线...
  • 1.给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 重要一点(关于在函数中static的用法) 第一、在修饰变量的时候,static修饰的静态局部变量只执行一次,而且延长了...
  • 所谓的特征值和特征向量

    万次阅读 多人点赞 2017-07-31 20:36:36
    所谓的特征值和特征向量,最重要的是理解“特征”这两个字,在纯数学的定义下,并不能很明白地理解到底什么叫做特征值和特征向量。但是举一个应用例子,可能就容易理解多了。 在图像处理中,有一种方法就是特征...
  • 设半径R的球面S的球心在球面x^2+y^2+z^2=a^2(a>0)上,问R取何时,球面s在球面内的面积最大?
  • 1、使用最容易理解的遍历数组进行查找 def solution(nums,target): #如果列表长度小于2,则直接结束 if len(nums) &... #循环两次列表对应的时间复杂度O(n²) for i in range(0, len(...
  • test : 待提取的字段名 example.txt : 需要处理的json文件   Tips: 1.此种方法只能适用于 简单类型的提取,并且数据是字符串类型,也就是 " " (双引号)括起来 的数据 , a1字段 不满足要求 。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,932,331
精华内容 1,172,932
关键字:

和为定值