精华内容
下载资源
问答
  • 递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法 ...1,替代多重循环,特别是对于不同的问题规模有不同的循环次数...
    递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法
    重复事物的过程。例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。(以上定义来自维基百科[递归])
    

    我们写程序用递归时常用于解决一下几种问题:

    1,替代多重循环,特别是对于不同的问题规模有不同的循环次数。
    2,解决本来就是递归定义的问题,相关的数学表达式递归定义的。比如阶乘函数,Fibonacci(斐波那契数列)数列,Ackerman(阿克曼)函数等。
    3,可以将问题规模分解为更小规模进行求解的,或者说该问题的解是由更小规模的解构成的。

    1,替代多重循环:

    N皇后问题:

    输入整数n,要求n个国际象棋的皇后,摆在n*n的棋盘上,互相不能攻击,输出全部可行的摆放方案。
    对于摆放的皇后的位置其要求是:任两个皇后都不能处于同一条横行、纵行或斜线上。8皇后问题-维基百科

    对于这道题,如果是给定的数比较小,我们自然而然的可以想到可能可以使用多重循环的方法,每一层循环判断一个位置符不符合。但是由于n的个数不确定,并且n可能比较大(比如n等于4,对于;使用多重循环都是不可取的了),这样我们就不好判断究竟要使用多少重循环了。

    此时使用递归来替代多重循环就是一个解决这个问题的方案。具体做法可如下:

    1,先摆放第一行的那个皇后,对应n个。此时有n中可能的结果。此时第一行的这个皇后相当于是确定下来的了。
    2,接着摆放第2行的那个皇后,注意此时第二行的这个皇后需要和第一行的皇后满足题目的要求。由于第一行已经确定,那么第二行也会被确定下来。
    3,依次类推,当第k行和第k-1行没有冲突时,则继续往下递归,否则的话应该从头开始进行递归遍历。

    下面是C++的代码实现:

    #include <iostream>
    #include <cmath>
    using namespace std;
    
    int N;		
    //用来存放第i行的皇后放在那一列,里面的值表示哪一列,从0开始 
    int queenPos[100]; 
    
    //表示第k行之前的皇后已经摆放完成了 
    void NQueen(int k);
    
    int main() {
    	cin >> N; 
    	NQueen(0);
    	return 0;
    }
    
    void NQueen(int k) {	//在k-1行摆放好的情况下摆放第k行 
    	if (k == N) {		//k=N则证明找到一个可能的情况,输出
    		for (int i = 0; i < N; i++) {
    			cout << queenPos[i] + 1 << " ";
    		}
    		cout << endl;
    	}
    	for (int i = 0; i < N; i++) {//逐个尝试第K个皇后的位置,这里的i表示的列 
    		int j; 
    		for (j = 0; j < k; j++) {//和已经摆好的k个皇后的位置进行比较,看是否冲突,这里只遍历到k -1
    		 	if (queenPos[j] == i || 
    			 	abs(queenPos[j] - i) == abs(k - j)) {//行之差和列之差相等为对角线,queenPos[j]-i表示列之差,k-j表示行之差。 
    			 		break;
    			 } 	
    		}
    		if (j == k) {	//遍历过程中没有中途退出时则表明第k行中第i列可行
    			queenPos[k] = i;
    			NQueen(k + 1);	//可行则递归k+1
    		} 
    	} 
    }
    

    运行结果:8皇后问题有92总可能的结果,4皇后有2总可能的结果。

    关于递归的其他内容可以查看:
    递归二之:解决递归定义的问题
    递归三之:将问题分解为更小规模

    展开全文
  • Python多重继承说明及应用

    千次阅读 2017-11-27 18:02:40
    Python中没有接口的概念,替代之的是多重继承。而引入多重继承之后,一个新的问题是多个父类之间的继承顺序和方法调用顺序。比如:子类中调用的方法在多个父类中都存在的时候,到底会调用哪个父类的方法?(显然不会...

    Python中没有接口的概念,替代之的是多重继承。而引入多重继承之后,一个新的问题是多个父类之间的继承顺序和方法调用顺序。比如:子类中调用的方法在多个父类中都存在的时候,到底会调用哪个父类的方法?(显然不会把所有父类的方法都调用一遍)

     

    理解MRO

    如果把单重继承理解为是链表结构,那么多重继承则可以认为是树状结构。所以多重继承的向上搜索的规则有2种实现方式:

    1. 深度优先搜索(DFS)
    2. 广度优先搜索(BFS)

    深度优先搜索图解如下:

    这种查找方式的缺点:

    棱形继承时可能会出现父类访问优先于子类访问。如上图中的父类D就优于子类C先被访问到。这会导致子类C中的覆盖方法无法被访问到。

     

    广度优先搜索图解如下:

    这种查找方式的缺点:

    在正常继承时没有按照继承的单调性来查找。

     

    为了解决DFS和BFS的缺陷问题,Python中使用了C3算法,经过调整之后多重继承的查找方式如下:

    C3算法结合了DFS和BFS的优点,当正常继承时使用DFS,当为棱形继承时则使用BFS(DFS是Python2.2以前的算法,Python2.2同时使用了DFS(经典类)、BFS算法(新式类),Python2.3及之后使用C3算法)。最后推测下图中MRO的顺序为何?

     

    父类方法显式调用

    Python2.7版本中,类的定义有2种方式:

     

    • 经典类
    • 新式类

     

    经典类是Python一直都存在的,而新式类是Python2.2中才加入的,而Python3.0中只支持新式类。它们的各自定义如下:

     

    #!/usr/bin/env python
    #coding:utf-8
    
    class oldClass:        #经典类
    	pass
    	
    class newClass(object):   #新式类
    	pass
    	
    print type(oldClass)     #classobj
    print type(newClass)     #type

    从代码可以知道显式的继承自object的则为新式类,不继承任何其它类的为经典类。经典类与新式类除了定义上有区别,在显式调用父类方法时也有些许不同。经典类调用父类代码如下:

     

     

    #!/usr/bin/python
    #encoding: utf-8
    import inspect
    
    class oldBase(object):
        def __init__(self):
            print '%s' % oldBase.__name__
    
    class oldParentA(oldBase):
        def __init__(self):
            print '%s' % oldParentA.__name__
            oldBase.__init__(self)
    
    class oldParentB(oldBase):
        def __init__(self):
            print '%s' % oldParentB.__name__
            oldBase.__init__(self)
    
    class oldChild(oldParentA, oldParentB):
        def __init__(self):
            print '%s' % oldChild.__name__
            oldParentA.__init__(self)
            oldParentB.__init__(self)
    
    if __name__ == '__main__':
        print inspect.getmro(oldChild)     #打印mro中父类的查找顺序
        n = oldChild()

     

    新式类也可以使用经典类的方式调用父类方法,另外还可以使用super类来实现。具体如下:

     

    #!/usr/bin/python
    #encoding: utf-8
    class newBase(object):
        def __init__(self):
            print '%s' % newBase.__name__
    
    class newParentA(newBase):
        def __init__(self):
            print '%s' % newParentA.__name__
            super(newParentA, self).__init__()
    
    class newParentB(newBase):
        def __init__(self):
            print '%s' % newParentB.__name__
            super(newParentB, self).__init__()
    
    class newChild(newParentA, newParentB):
        def __init__(self):
            print '%s' % newChild.__name__
            super(newChild, self).__init__()
    
    if __name__ == '__main__':
        print newChild.__mro__          #打印mro中父类的查找顺序
        n = newChild()

     

    之所以给新式类提供了super类来调用父类的方法,是因为前面介绍的棱形继承的场景。如果使用经典类的方式调用,则公共父类*Base会被调用两次;而如果使用super类的方式则只会调用一次。

     

    另外,在类创建时默认不创建__init__方法时,经典类与新式类的行为也不一样。经典会只调用第一个父类的__init__方法,而新式类与显式使用super的效果是一样的。也就是说如果你使用的是新式类,那么不是初始化__init__也会初始化所有的父类方法。而一旦你定义了__init__方法,则需要自己显式的初始化父类方法。

    多重继承应用

     

     

    更多关于Python的知识,请扫描如下二维码哦!

    展开全文
  • 多重填补

    2020-11-12 10:07:51
    插补方法有多重回归填补(Multiple Regression Imputation)、倾向得分(Propensity Score)和马尔科夫链蒙特卡罗(Markov Chain Monte Carlo,MCMC),由于多重回归填补和倾向得分一般运用在数据呈单调缺失的...

    数据缺失机制的分类

    • 完全随机缺失
      数据的缺失不依赖任何测量值。
      如受试者因为工作原因从一个地方搬到另外一个地方,远离了原来的研究中心而无法继续试验。
    • 随机缺失
      数据的缺失依赖于已经观测到的测量值,而不依赖于未观测到的测量值。
      如受试者在临床试验中因为疗效不好从而退出试验。
    • 非随机缺失
      数据的缺失依赖于未观测到的测量值。
      如受试者在之前的访视中一切良好,然而在某次访视后疾病恶化从而退出试验。

    当数据缺失是完全随机缺失或者随机缺失的时候,根据现有的试验数据做出的统计推断依然是有效的(尽管不会像完整的数据那么有效)。如果数据缺失是非随机缺失的,根据现有的数据做出的统计推断很有可能会产生偏倚。

    数据缺失模式的分类

    在这里插入图片描述

    多重填补(MI)

    给每一个缺失值都构造m个填补值,产生m个完整数据集,对每个完整数据集分别使用相同的方法进行处理,得到m个处理结果,再综合这m个结果,最终得到对目标变量的估计。
    多重插补并没有试图去通过模拟值去估计每个缺失值,而是提出缺失数据值的一个随机样本,借此估计变量的实际后验分布,这反映了缺失值引起的不确定性。
    在这里插入图片描述
    插补方法有多重回归填补法(Multiple Regression Imputation)、倾向得分法(Propensity Score)和马尔科夫链蒙特卡罗法(Markov Chain Monte Carlo,MCMC),由于多重回归填补法和倾向得分法一般运用在数据呈单调缺失的模式中,MCMC 法用于任意缺失模式的连续型变量数据,而临床试验中,临床数据一般是任意缺失的,因此主要运用马尔科夫链蒙特卡罗法
    在这里插入图片描述

    马尔科夫链蒙特卡罗法

    MCMC法是Bayes理论中探索后验概率分布的一种方法,使用MCMC对数据缺失进行多重填补时有以下假设:
    假设数据是随机缺失的、是任意缺失的、服从多元正态分布

    填补步骤:
    (1) 填补步(imputation step)
    每一个迭代过程均以给定的均值μ和协方差矩阵∑开始,从条件分布中为缺失值抽取替代值。

    (2)后验步(posterior step)
    通过填补步中得到的完整数据估算出整体的均值和方差矩阵,将这些新估算出的数值再次循环应用到填补步中。通过填补步和后验步迭代多次后,得到一个比较稳定的数据集,最终通过迭代数次,使得结果收敛,得到一个稳定的分布。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    当没有缺失数据时,填补间方差B=0,B的大小反映了与观察到的数据相比,缺失数据相对包含了多少信息。α和r揭示了Q的估计在多大程度上受到了数据缺失的影响。可依据这些指标选择m。

    展开全文
  • 多重共线性问题的几种解决方法

    万次阅读 多人点赞 2018-01-28 16:45:51
    如果违背这一假定,即线性回归模型中某一个解释变量与其他解释变量间存在线性关系,就称线性回归模型中存在多重共线性。多重共线性违背了解释变量间不相关的古典假设,将给普通最小二乘法带来严重后果。  所谓...

      在多元线性回归模型经典假设中,其重要假定之一是回归模型的解释变量之间不存在线性关系,也就是说,解释变量X1X2……Xk中的任何一个都不能是其他解释变量的线性组合。如果违背这一假定,即线性回归模型中某一个解释变量与其他解释变量间存在线性关系,就称线性回归模型中存在多重共线性。多重共线性违背了解释变量间不相关的古典假设,将给普通最小二乘法带来严重后果。

        所谓多重共线性是指线性回归模型的解释变量之间由于存在精确相关关系或者高度相关关系而使模型评估失真或者不准确。这里,我们总结了8个处理多重共线性问题的可用方法,大家在遇到多重共线性问题时可作参考:

    1、保留重要解释变量,去掉次要或可替代解释变量

        自变量之间存在共线性,说明自变量所提供的信息是重叠的,可以删除不重要的自变量减少重复信息。但从模型中删去自变量时应该注意:从实际经济分析确定为相对不重要并从偏相关系数检验证实为共线性原因的那些变量中删除。如果删除不当,会产生模型设定误差,造成参数估计严重有偏的后果。

    2、改变解释变量的形式

        改变解释变量的形式是解决多重共线性的一种简易方法,例如对于横截面数据采用相对数变量,对于时间序列数据采用增量型变量。

    3、差分法

    4、逐步回归分析

        逐步回归(Stepwise Regression)是一种常用的消除多重共线性、选取“最优”回归方程的方法。其做法是将逐个引入自变量,引入的条件是该自变量经F检验是显著的,每引入一个自变量后,对已选入的变量进行逐个检验,如果原来引入的变量由于后面变量的引入而变得不再显著,那么就将其剔除。引入一个变量或从回归方程中剔除一个变量,为逐步回归的一步,每一步都要进行F 检验,以确保每次引入新变量之前回归方程中只包含显著的变量。这个过程反复进行,直到既没有不显著的自变量选入回归方程,也没有显著自变量从回归方程中剔除为止。

    5、主成份分析

    主成分分析作为多元统计分析的一种常用方法在处理多变量问题时具有其一定的优越性,其降维的优势是明显的,主成分回归方法对于一般的多重共线性问题还是适用的,尤其是对共线性较强的变量之间。

    6、偏最小二乘回归

    7、岭回归

        岭回归估计是通过最小二乘法的改进允许回归系数的有偏估计量存在而补救多重共线性的方法,采用它可以通过允许小的误差而换取高于无偏估计量的精度, 因此它接近真实值的可能性较大。灵活运用岭回归法, 可以对分析各变量之间的作用和关系带来独特而有效的帮助。

    8、增加样本容量

        多重共线性问题的实质是样本信息的不充分而导致模型参数的不能精确估计,因此追加样本信息是解决该问题的一条有效途径。但是,由于资料收集及调查的困难,要追加样本信息在实践中有时并不容易。


    这次我们主要研究逐步回归分析方法是如何处理多重共线性问题的。

    逐步回归分析方法的基本思想是通过相关系数r、拟合优度R2和标准误差三个方面综合判断一系列回归方程的优劣,从而得到最优回归方程。具体方法分为两步:

    第一步,先将被解释变量y对每个解释变量作简单回归:

    对每一个回归方程进行统计检验分析(相关系数r、拟合优度R2和标准误差),并结合经济理论分析选出最优回归方程,也称为基本回归方程。

    第二步,将其他解释变量逐一引入到基本回归方程中,建立一系列回归方程,根据每个新加的解释变量的标准差和复相关系数来考察其对每个回归系数的影响,一般根据如下标准进行分类判别:

    1.如果新引进的解释变量使R2得到提高,而其他参数回归系数在统计上和经济理论上仍然合理,则认为这个新引入的变量对回归模型是有利的,可以作为解释变量予以保留。

    2.如果新引进的解释变量对R2改进不明显,对其他回归系数也没有多大影响,则不必保留在回归模型中。

    3.如果新引进的解释变量不仅改变了R2,而且对其他回归系数的数值或符号具有明显影响,则认为该解释变量为不利变量,引进后会使回归模型出现多重共线性问题。不利变量未必是多余的,如果它可能对被解释变量是不可缺少的,则不能简单舍弃,而是应研究改善模型的形式,寻找更符合实际的模型,重新进行估计。如果通过检验证明回归模型存在明显线性相关的两个解释变量中的其中一个可以被另一个很好地解释,则可略去其中对被解释变量影响较小的那个变量,模型中保留影响较大的那个变量。

    下边我们通过实例来说明逐步回归分析方法在解决多重共线性问题上的具体应用过程。

    具体实例

    例1设某地10年间有关服装消费、可支配收入、流动资产、服装类物价指数、总物价指数的调查数据如表1,请建立需求函数模型。

       表1  服装消费及相关变量调查数据

     

    (1)设对服装的需求函数为

    用最小二乘法估计得估计模型:

    模型的检验量得分,R2=0.998,D·W=3.383,F=626.4634

        R2接近1,说明该回归模型与原始数据拟合得很好。由得出拒绝零假设,认为服装支出与解释变量间存在显著关系。

    (2)求各解释变量的基本相关系数

    上述基本相关系数表明解释变量间高度相关,也就是存在较严重的多重共线性。

    (3)为检验多重共线性的影响,作如下简单回归:

    各方程下边括号内的数字分别表示的是对应解释变量系数的t检验值。

    观察以上四个方程,根据经济理论和统计检验(t检验值=41.937最大,拟合优度也最高),收入Y是最重要的解释变量,从而得出最优简单回归方程

    (4)将其余变量逐个引入,计算结果如下表2:

    表2 服装消费模型的估计


    结果分析:

    ①在最优简单回归方程中引入变量Pc,使R2由0.9955提高到0.9957;根据经济理论分析,正号,负号是合理的。然而t检验不显著(),而从经济理论分析,Pc应该是重要因素。虽然Y与Pc高度相关,但并不影响收入Y回归系数的显著性和稳定性。依照第1条判别标准,Pc可能是“有利变量”,暂时给予保留。

    ②模型中引入变量L,R2由0.9957提高到0.9959,值略有提高。一方面,虽然Y与L,Pc与L均高度相关,但是L的引入对回归系数的影响不大(其中的值由0.1257变为0.1387,值由-0.0361变为-0.0345,变化很小);另一方面,根据经济理论的分析,L与服装支出C之间应该是正相关关系,即的符号应该为正号而非负号,依照第2条判别标准,解释变量L不必保留在模型中。

    ③舍去变量L,加入变量P0,使R2由0.9957提高到0.9980,R2值改进较大。均显著(这三个回归系数的t检验值绝对值均大于),从经济意义上看也是合理的(服装支出C与Y,P0之间呈正相关,而与服装价格Pc之间呈负相关关系)。根据判别标准第1条,可以认为Pc、P0皆为“有利变量”,给予保留。

    ④最后再引入变量L,此时R2=0.9980没有增加(或几乎没有增加),新引入变量对其他三个解释变量的参数系数也没有产生多大影响,可以确定L是多余变量,根据判别标准第2条,解释变量L不必保留在模型中。

    因此我们得到如下结论:回归模型为最优模型。

        通过以上案例的分析,我们从理论和实际问题两方面具体了解了逐步回归分析是如何对多重共线性问题进行处理的。事实上,一般统计软件如SPSS,在回归模型的窗口中都会提供变量逐步进入的选项,勾选后实际上就是选择了运用逐步回归的思想来构建回归模型。运用SPSS软件不需要我们懂得其背后的运行规律,然而作为分析师,了解并理解模型背后的理论知识,将更有助于我们理解模型、解释结论背后的内在含义,从而达到更好地分析问题的目的。

    展开全文
  • 我在程序中开启了多重采样,在屏幕上显示出来的效果确实有抗锯齿。但是当我用FBO离屏渲染,然后保存为BMP图像的时候,发现保存出来的BMP图像并没有抗锯齿效果。 问题产生原因及解决方案: 在默认帧缓冲中启用...
  • 均值插补是利用样本数据平均值或众数作为其替代值对数据进行插值。均值插补的插补值计算方程为: (1) 其中,为是否回答的描述符号表示,表示“是”,表示“否”,是个数 2. 回归插值 回归插值是根据样本中...
  • 多重网格、自适应网格和无网格

    万次阅读 2013-01-19 10:58:43
    多重网格简介(Multi Grid) 转自:http://blog.sina.com.cn/s/blog_4b700c4c0102drjb.html 多重网格是一种用于求解方程组的方法,可用于插值、解微分方程等。 从专业角度讲多重网格实际上是一种多分辨率...
  • 多重共线性:一个变量可以由其他变量求出,例如,学生的总成绩可以由各科成绩求出。 ① 度量多重共线性严重程度的一个重要指标是矩阵的条件数,可以由函数kappa()求出。在R中,函数kappa()计算矩阵的条件数。 注意...
  • 多重插补 spss操作

    万次阅读 2018-02-07 21:27:26
  • 如果违背这一假定,即线性回归模型中某一个解释变量与其他解释变量间存在线性关系,就称线性回归模型中存在多重共线性。多重共线性违背了解释变量间不相关的古典假设,将给普通最小二乘法带来严重后果。 所谓多重共...
  • DirectX中的多重纹理相关技术

    千次阅读 2006-06-04 17:45:00
    多重纹理从原则上讲全部可以被多次渲染所替代,因为多重纹理实际上就是将多次渲染中的每遍中的纹理在一遍中进行操作。因此我们首先介绍一下多次渲染,然后概要介绍一下多重纹理的使用方法和实现的效果。一种复杂的...
  • 如果违背这一假定,即线性回归模型中某一个解释变量与其他解释变量间存在线性关系,就称线性回归模型中存在多重共线性。多重共线性违背了解释变量间不相关的古典假设,将给普通最小二乘法带来严重后果。 所谓多重...
  • Python重试的多重方法

    千次阅读 2019-03-20 20:11:12
    没人能保证自己的的程序没BUG,所以重试非常有必要。 下面说下我知道的几种Python重试方法。 装饰器 这是最最简单的重试方法,而且有现成的轮子,推荐两个: ...两种用法比较类似,我经常用后者,看下 ...
  • 多重纹理从原则上讲全部可以被多次渲染所替代,因为多重纹理实际上就是将多次渲染中的每遍中的纹理在一遍中进行操作。因此我们首先介绍一下多次渲染,然后概要介绍一下多重纹理的使用方法和实现的效果。 一种复杂...
  • 抗锯齿 多重采样 opengl超级宝典

    千次阅读 2012-05-30 09:54:46
    超级采样抗锯齿中使用的采样一般有两种: 顺序栅格超级采样(Ordered Grid Super-Sampling,简称OGSS),采样时选取2个邻近像素。 旋转栅格超级采样(Rotated Grid Super-Sampling,简称RGSS),采样...
  • 我在程序中开启了多重采样,在屏幕上显示出来的效果确实有抗锯齿。但是当我用FBO离屏渲染,然后保存为BMP图像的时候,发现保存出来的BMP图像并没有抗锯齿效果。 问题产生原因及解决方案: 在默认帧缓冲中启用...
  • 解释变量之间的多重共线 解释变量为随机变量,存在内生性 异方差性 线性模型的基本假设中有var(u|x1,x2...xk)=d,即随机干扰项的方差不因自变量的不同而不同。表现在现实的经济生活中,以消费
  • 抗锯齿 多重采样 opengl超级宝典 P177

    千次阅读 2010-08-12 21:54:00
    超级采样抗锯齿中使用的采样一般有两种: 顺序栅格超级采样(Ordered Grid Super-Sampling,简称OGSS),采样时选取2个邻近像素。 旋转栅格超级采样(Rotated Grid Super-Sampling,简称RGSS),...
  • 保留重要解释变量,去掉次要或可替代解释变量 改变解释变量形式 ex:对横截面数据采用相对数变量,对于时间序列数据采用增量型变量 差分 逐步回归分析 逐步回归分析是将逐个引入自变量,引入条件时该自...
  • 面对多重判断,excel有四   一般来说,我们经常会碰到这样的问题,即   需要按照这张mapping表进行数值判断,下面有四种方法:   1 经典:if多重判断 这个就不用多说了,一般来说,...
  • 借汉诺塔理解栈与递归 单调栈 双端单调队列 单调队列优化的背包问题 01背包问题 完全背包问题 多重背包问题 串的定长表示 串的堆分配实现 KMP 一、引子 二、分析总结 三、基本操作 四、原理 五、复杂度分析 ...
  • 近邻简介

    2020-10-07 11:11:49
    在机器学习中,常用的近邻包括近邻、最近邻、K-近邻、剪辑近邻、以及压缩近邻。本篇文章,我们将对这几种方法进行介绍。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,343
精华内容 4,937
热门标签
关键字:

多重替代法