• 关于 数表示法出问题什么情况 的搜索结果

回答

算法是比较复杂又基础的学科,每个学编程的人都会学习大量的算法。而根据统计,以下这18个问题是面试中最容易遇到的,本文给出了一些基本答案,供算法方向工程师或对此感兴趣的程序员参考。 1)请简单解释算法是什么? 算法是一个定义良好的计算过程,它将一些值作为输入并产生相应的输出值。简单来说,它是将输入转换为输出的一系列计算步骤。 2)解释什么是快速排序算法? 快速排序算法能够快速排序列表或查询。它基于分割交换排序的原则,这种类型的算法占用空间较小,它将待排序列表分为三个主要部分: ·小于Pivot的元素 ·枢轴元素Pivot(选定的比较值) ·大于Pivot的元素 3)解释算法的时间复杂度? 算法的时间复杂度表示程序运行完成所需的总时间,它通常用大O表示法来表示。 4)请问用于时间复杂度的符号类型是什么? 用于时间复杂度的符号类型包括: ·Big Oh:它表示小于或等于目标多项式 ·Big Omega:它表示大于或等于目标多项式 ·Big Theta:它表示与目标多项式相等 ·Little Oh:它表示小于目标多项式 ·Little Omega:它表示大于目标多项式 5)解释二分法检索如何工作? 在二分法检索中,我们先确定数组的中间位置,然后将要查找的值与数组中间位置的值进行比较,若小于数组中间值,则要查找的值应位于该中间值之前,依此类推,不断缩小查找范围,直至得到最终结果。 6)解释是否可以使用二分法检索链表? 由于随机访问在链表中是不可接受的,所以不可能到达O(1)时间的中间元素。因此,对于链表来说,二分法检索是不可以的(对顺序链表或排序后的链表是可以用的)。 7)解释什么是堆排序? 堆排序可以看成是选择排序的改进,它可以定义为基于比较的排序算法。它将其输入划分为未排序和排序的区域,通过不断消除最小元素并将其移动到排序区域来收缩未排序区域。 8)说明什么是Skip list? Skip list数据结构化的方法,它允许算法在符号表或字典中搜索、删除和插入元素。在Skip list中,每个元素由一个节点表示。搜索函数返回与key相关的值的内容。插入操作将指定的键与新值相关联,删除操作可删除指定的键。 9)解释插入排序算法的空间复杂度是多少? 插入排序是一种就地排序算法,这意味着它不需要额外的或仅需要少量的存储空间。对于插入排序,它只需要将单个列表元素存储在初始数据的外侧,从而使空间复杂度为O(1)。 10)解释什么是“哈希算法”,它们用于什么? “哈希算法”是一个哈希函数,它使用任意长度的字符串,并将其减少为唯一的固定长度字符串。它用于密码有效性、消息和数据完整性以及许多其他加密系统。 11)解释如何查找链表是否有循环? 要知道链表是否有循环,我们将采用两个指针的方法。如果保留两个指针,并且在处理两个节点之后增加一个指针,并且在处理每个节点之后,遇到指针指向同一个节点的情况,这只有在链表有循环时才会发生。 12)解释加密算法的工作原理? 加密是将明文转换为称为“密文”的密码格式的过程。要转换文本,算法使用一系列被称为“键”的位来进行计算。密钥越大,创建密文的潜在模式数越多。大多数加密算法使用长度约为64到128位的固定输入块,而有些则使用流方法。 13)列出一些常用的加密算法? 一些常用的加密算法是: ·3-way ·Blowfish ·CAST ·CMEA ·GOST ·DES 和Triple DES ·IDEA ·LOKI等等 14)解释一个算法的最佳情况和最坏情况之间有什么区别? ·最佳情况:算法的最佳情况解释为算法执行最佳的数据排列。例如,我们进行二分法检索,如果目标值位于正在搜索的数据中心,则这就是最佳情况,最佳情况时间复杂度为0。 ·最差情况:给定算法的最差输入参考。例如快速排序,如果选择关键值的子列表的最大或最小元素,则会导致最差情况出现,这将导致时间复杂度快速退化到O(n2)。 15)解释什么是基数排序算法? 基数排序又称“桶子法”,是通过比较数字将其分配到不同的“桶里”来排序元素的。它是线性排序算法之一。 16)解释什么是递归算法? 递归算法是一个解决复杂问题的方法,将问题分解成较小的子问题,直到分解的足够小,可以轻松解决问题为止。通常,它涉及一个调用自身的函数。 17)提到递归算法的三个定律是什么? 所有递归算法必须遵循三个规律: ·递归算法必须有一个基点 ·递归算法必须有一个趋向基点的状态变化过程 ·递归算法必须自我调用 18)解释什么是冒泡排序算法? 冒泡排序算法也称为下沉排序。在这种类型的排序中,要排序的列表的相邻元素之间互相比较。如果它们按顺序排列错误,将交换值并以正确的顺序排列,直到最终结果“浮”出水面。 满意记得采纳哈

玄学酱 2019-12-02 01:18:44 0 浏览量 回答数 0

回答

迭代法  迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。   迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。   利用迭代算法解决问题,需要做好以下三个方面的工作:   一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。   二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。   三、对迭代过程进行控制。在什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。   例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。   分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有   u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,……   根据这个规律,可以归纳出下面的递推公式:   u n = u n - 1 × 2 (n ≥ 2)   对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系:   y=x*2   x=y   让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下:   cls   x=1   for i=2 to 12   y=x*2   x=y   next i   print y   end   例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 220,220个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。   分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴2^ 20 个”,即阿米巴分裂 15 次以后得到的个数是 2^20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2^20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。   设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有   x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1)   因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式:   x=x/2 ( x 的初值为第 15 次分裂之后的个数 2^20 )   让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下:   cls   x=2^20   for i=1 to 15   x=x/2   next i   print x   end   ps:java中幂的算法是Math.pow(2, 20);返回double,稍微注意一下   例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。   要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。   分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是:   if n 为偶数 then   n=n/2   else   n=n*3+1   end if   这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下:   cls   input "Please input n=";n   do until n=1   if n mod 2=0 then   rem 如果 n 为偶数,则调用迭代公式 n=n/2   n=n/2   print "—";n;   else   n=n*3+1   print "—";n;   end if   loop   end   迭代法   迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行:   (1) 选一个方程的近似根,赋给变量x0;   (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;   (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。   若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:   【算法】迭代法求方程的根   { x0=初始近似根;   do {   x1=x0;   x0=g(x1); /*按特定的方程计算新的近似根*/   } while ( fabs(x0-x1)>Epsilon);   printf(“方程的近似根是%f\n”,x0);   }   迭代算法也常用于求方程组的根,令   X=(x0,x1,…,xn-1)   设方程组为:   xi=gi(X) (I=0,1,…,n-1)   则求方程组根的迭代算法可描述如下:   【算法】迭代法求方程组的根   { for (i=0;i   x=初始近似根;   do {   for (i=0;i   y=x;   for (i=0;i   x=gi(X);   for (delta=0.0,i=0;i   if (fabs(y-x)>delta) delta=fabs(y-x);   } while (delta>Epsilon);   for (i=0;i   printf(“变量x[%d]的近似根是 %f”,I,x);   printf(“\n”);   }   具体使用迭代法求根时应注意以下两种可能发生的情况:   (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制;   (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。   递归   递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。   能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。   【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。   斐波那契数列为:0、1、1、2、3、……,即:   fib(0)=0;   fib(1)=1;   fib(n)=fib(n-1)+fib(n-2) (当n>1时)。   写成递归函数有:   int fib(int n)   { if (n==0) return 0;   if (n==1) return 1;   if (n>1) return fib(n-1)+fib(n-2);   }   递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。   在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。   在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。   由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。   【问题】 组合问题   问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1   (4)5、3、2 (5)5、3、1 (6)5、2、1   (7)4、3、2 (8)4、3、1 (9)4、2、1   (10)3、2、1   分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。   【程序】   # include   # define MAXN 100   int a[MAXN];   void comb(int m,int k)   { int i,j;   for (i=m;i>=k;i--)   { a[k]=i;   if (k>1)   comb(i-1,k-1);   else   { for (j=a[0];j>0;j--)   printf(“%4d”,a[j]);   printf(“\n”);   }   }   }   void main()   { a[0]=3;   comb(5,3);   }   【问题】 背包问题   问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。   设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。   对于第i件物品的选择考虑有两种可能:   (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。   (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。   按以上思想写出递归算法如下:   try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv)   { /*考虑物品i包含在当前方案中的可能性*/   if(包含物品i是可以接受的)   { 将物品i包含在当前方案中;   if (i   try(i+1,tw+物品i的重量,tv);   else   /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   恢复物品i不包含状态;   }   /*考虑物品i不包含在当前方案中的可能性*/   if (不包含物品i仅是可男考虑的)   if (i   try(i+1,tw,tv-物品i的价值);   else   /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   }

沉默术士 2019-12-02 01:25:10 0 浏览量 回答数 0

回答

迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法,即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法(Iterative Method)。 一般可以做如下定义:对于给定的线性方程组x=Bx+f(这里的x、B、f同为矩阵,任意线性方程组都可以变换成此形式),用公式x(k+1)=Bx(k)+f(括号中为上标,代表迭代k次得到的x,初始时k=0)逐步带入求近似解的方法称为迭代法(或称一阶定常迭代法)。如果k趋向无穷大时limx(k)存在,记为x*,称此迭代法收敛。显然x*就是此方程组的解,否则称为迭代法发散。 跟迭代法相对应的是直接法(或者称为一次解法),即一次性的快速解决问题,例如通过开方解决方程x +3= 4。一般如果可能,直接解法总是优先考虑的。但当遇到复杂问题时,特别是在未知量很多,方程为非线性时,我们无法找到直接解法(例如五次以及更高次的代数方程没有解析解,参见阿贝耳定理),这时候或许可以通过迭代法寻求方程(组)的近似解。 最常见的迭代法是牛顿法。其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、线性规划、非线性规划、单纯型法、惩罚函数法、斜率投影法、遗传算法、模拟退火等等。 利用迭代算法解决问题,需要做好以下三个方面的工作: 确定迭代变量 在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 建立迭代关系式 所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以顺推或倒推的方法来完成。 对迭代过程进行控制 在 什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数 是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需 要进一步分析出用来结束迭代过程的条件。 举例 例 1 :一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。 分析:这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,…… 根据这个规律,可以归纳出下面的递推公式: u n = u(n - 1)× 2 (n ≥ 2) 对应 u n 和 u(n - 1),定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系: y=x*2 x=y 让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下: cls x=1 for i=2 to 12 y=x*2 x=y next i print y end 例 2 :阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 220,220个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。 分析:根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴2^ 20 个”,即阿米巴分裂 15 次以后得到的个数是 2^20。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2^20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。 设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有 x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1) 因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式: x=x/2 (x 的初值为第 15 次分裂之后的个数 2^20) 让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下: cls x=2^20 for i=1 to 15 x=x/2 next i print x end ps:java中幂的算法是Math.pow(2,20);返回double,稍微注意一下 例 3 :验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1。如此经过有限次运算后,总可以得到自然数 1。人们把谷角静夫的这一发现叫做“谷角猜想”。 要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。 分析:定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1。用 QBASIC 语言把它描述出来就是: if n 为偶数 then n=n/2 else n=n*3+1 end if 这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为:n=1。参考程序如下: cls input "Please input n=";n do until n=1 if n mod 2=0 then rem 如果 n 为偶数,则调用迭代公式 n=n/2 n=n/2 print "—";n; else n=n*3+1 print "—";n; end if loop end 迭代法开平方: #include<stdio.h> #include<math.h> void main() { double a,x0,x1; printf("Input a:\n"); scanf("%lf",&a);//为什么在VC6.0中不能写成“scanf("%f",&a);”。 if(a<0) printf("Error!\n"); else { x0=a/2; x1=(x0+a/x0)/2; do { x0=x1; x1=(x0+a/x0)/2; }while(fabs(x0-x1)>=1e-6); } printf("Result:\n"); printf("sqrt(%g)=%g\n",a,x1); } 求平方根的迭代公式:x1=1/2*(x0+a/x0)。 算法:1.先自定一个初值x0,作为a的平方根值,在我们的程序中取a/2作为a的初值;利用迭代公式求出一个x1。此值与真正的a的平方根值相比,误差很大。 ⒉把新求得的x1代入x0中,准备用此新的x0再去求出一个新的x1. ⒊利用迭代公式再求出一个新的x1的值,也就是用新的x0又求出一个新的平方根值x1,此值将更趋近于真正的平方根值。 ⒋比较前后两次求得的平方根值x0和x1,如果它们的差值小于我们指定的值,即达到我们要求的精度,则认为x1就是a的平方根值,去执行步骤5;否则执行步骤2,即循环进行迭代。 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: ⑴ 选一个方程的近似根,赋给变量x0; ⑵ 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; ⑶ 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤⑵的计算。 若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: 【算法】迭代法求方程的根 { x0=初始近似根; do { x1=x0; x0=g(x1); /*按特定的方程计算新的近似根*/ } while (fabs(x0-x1)>Epsilon); printf(“方程的近似根是%f\n”,x0); } 迭代算法也常用于求方程组的根,令 X=(x0,x1,…,xn-1) 设方程组为: xi=gi(X) (I=0,1,…,n-1) 则求方程组根的迭代算法可描述如下: 【算法】迭代法求方程组的根 { for (i=0;i x=初始近似根; do { for (i=0;i y=x; for (i=0;i x=gi(X); for (delta=0.0,i=0;i if (fabs(y-x)>delta) delta=fabs(y-x); } while (delta>Epsilon); for (i=0;i printf(“变量x[%d]的近似根是 %f”,I,x); printf(“\n”); } 具体使用迭代法求根时应注意以下两种可能发生的情况: ⑴ 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; ⑵ 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。 递归 递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 斐波那契数列为:0、1、1、2、3、……,即: fib(0)=0; fib⑴=1; fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 写成递归函数有: int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问 题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算 fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib⑴和fib(0),分别能 立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。 在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib⑴和fib(0)后,返回得到fib⑵的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 【问题】 组合问题 问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为:⑴5、4、3 ⑵5、4、2 ⑶5、4、1 ⑷5、3、2 ⑸5、3、1 ⑹5、2、1 ⑺4、3、2 ⑻4、3、1 ⑼4、2、1 ⑽3、2、1 分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递 归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。 【程序】 # include # define MAXN 100 int a[MAXN]; void comb(int m,int k) { int i,j; for (i=m;i>=k;i--) { a[k]=i; if (k>1) comb(i-1,k-1); else { for (j=a[0];j>0;j--) printf(“%4d”,a[j]); printf(“\n”); } } } void main() { a[0]=3; comb(5,3); } 【问题】 背包问题 问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。 设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并 保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达 到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止 当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 对于第i件物品的选择考虑有两种可能: ⑴ 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 ⑵ 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 按以上思想写出递归算法如下: try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) { /*考虑物品i包含在当前方案中的可能性*/ if(包含物品i是可以接受的) { 将物品i包含在当前方案中; if (i try(i+1,tw+物品i的重量,tv); else /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; 恢复物品i不包含状态; } /*考虑物品i不包含在当前方案中的可能性*/ if (不包含物品i仅是可男考虑的) if (i try(i+1,tw,tv-物品i的价值); else /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; } 为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: 物品 0 1 2 3 重量 5 3 2 1 价值 4 4 3 1 并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 按上述算法编写函数和程序如下: 【程序】 # include # define N 100 double limitW,totV,maxV; int option[N],cop[N]; struct { double weight; double value; }a[N]; int n; void find(int i,double tw,double tv) { int k; /*考虑物品i包含在当前方案中的可能性*/ if (tw+a.weight<=limitW) { cop=1; if (i else { for (k=0;k option[k]=cop[k]; maxv=tv; } cop=0; } /*考虑物品i不包含在当前方案中的可能性*/ if (tv-a.value>maxV) if (i else { for (k=0;k option[k]=cop[k]; maxv=tv-a.value; } } void main() { int k; double w,v; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入各物品的重量和价值\n”); for (totv=0.0,k=0;k { scanf(“%1f%1f”,&w,&v); a[k].weight=w; a[k].value=v; totV+=V; } printf(“输入限制重量\n”); scanf(“%1f”,&limitV); maxv=0.0; for (k=0;k find(0,0.0,totV); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是 从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选 解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在 候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。 对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。 【程序】 # include # define N 100 double limitW; int cop[N]; struct ele { double weight; double value; } a[N]; int k,n; struct { int ; double tw; double tv; }twv[N]; void next(int i,double tw,double tv) { twv.=1; twv tw=tw; twv tv=tv; } double find(struct ele *a,int n) { int i,k,f; double maxv,tw,tv,totv; maxv=0; for (totv=0.0,k=0;k totv+=a[k].value; next(0,0.0,totv); i=0; While (i>=0) { f=twv.; tw=twv tw; tv=twv tv; switch(f) { case 1: twv.++; if (tw+a.weight<=limitW) if (i { next(i+1,tw+a.weight,tv); i++; } else { maxv=tv; for (k=0;k cop[k]=twv[k].!=0; } break; case 0: i--; break; default: twv.=0; if (tv-a.value>maxv) if (i { next(i+1,tw,tv-a.value); i++; } else { maxv=tv-a.value; for (k=0;k cop[k]=twv[k].!=0; } break; } } return maxv; } void main() { double maxv; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入限制重量\n”); scanf(“%1f”,&limitW); printf(“输入各物品的重量和价值\n”); for (k=0;k scanf(“%1f%1f”,&a[k].weight,&a[k].value); maxv=find(a,n); printf(“\n选中的物品为\n”); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); }

云篆 2019-12-02 01:25:10 0 浏览量 回答数 0

海外云虚拟主机包年25元/月起

海外独享虚拟主机全面上线,助力构建海外网站,提升公司国际形象;全球有效覆盖,超高性价比;建站入门首选,助力出口,适合跨境贸易企业。

回答

关于二十四点游戏的编程思路与基本算法 漫长的假期对于我来说总是枯燥无味的,闲来无聊便和同学玩起童年时经常玩的二十四点牌游戏来。此游戏说来简单,就是利用加减乘除以及括号将给出的四张牌组成一个值为24的表达式。但是其中却不乏一些有趣的题目,这不,我们刚玩了一会儿,便遇到了一个难题——3、6、6、10(其实后来想想,这也不算是个太难的题,只是当时我们的脑筋都没有转弯而已,呵呵)。 问题既然出现了,我们当然要解决。冥思苦想之际,我的脑中掠过一丝念头——何不编个程序来解决这个问题呢。文曲星中不就有这样的程序吗。所以这个想法应该是可行。想到这里我立刻开始思索这个程序的算法,最先想到的自然是穷举法(后来发现我再也想不到更好的方法了,悲哀呀,呵呵),因为在这学期我曾经写过一个小程序——计算有括号的简单表达式。只要我能编程实现四个数加上运算符号所构成的表达式的穷举,不就可以利用这个计算程序来完成这个计算二十四点的程序吗。确定了这个思路之后,我开始想这个问题的细节。 首先穷举的可行性问题。我把表达式如下分成三类—— 1、 无括号的简单表达式。 2、 有一个括号的简单表达式。 3、 有两个括号的较复4、 杂表达式。 穷举的开始我对给出的四个数进行排列,其可能的种数为4*3*2*1=24。我利用一个嵌套函数实现四个数的排列,算法如下: /* ans[] 用来存放各种排列组合的数组 */ /* c[] 存放四张牌的数组 */ /* k[] c[]种四张牌的代号,其中k[I]=I+1。 用它来代替c[]做处理,考虑到c[]中有可能出现相同数的情况 */ /* kans[] 暂存生成的排列组合 */ /* j 嵌套循环的次数 */ int fans(c,k,ans,kans,j) int j,k[],c[];char ans[],kans[]; { int i,p,q,r,h,flag,s[4],t[4][4]; for(p=0,q=0;p<4;p++) { for(r=0,flag=0;r if(k[p]!=kans[r]) flag++; if(flag==j) t[j][q++]=k[p]; } for(s[j]=0;s[j]<4-j;s[j]++) { kans[j]=t[j][s[j>; if(j==3) { for(h=0;h<4;h++) ans[2*h]=c[kans[h]-1]; /* 调整生成的排列组合在最终的表 达式中的位置 */ for(h=0;h<3;h++) symbol(ans,h); /* 在表达式中添加运算符号 */ } else { j++; fans(c,k,ans,kans,j); j--; } } } 正如上面函数中提到的,在完成四张牌的排列之后,在表达式中添加运算符号。由于只有四张牌,所以只要添加三个运算符号就可以了。由于每一个运算符号可重复,所以计算出其可能的种数为4*4*4=64种。仍然利用嵌套函数实现添加运算符号的穷举,算法如下: /* ans[],j同上。sy[]存放四个运算符号。h为表达式形式。*/ int sans(ans,sy,j,h) char ans[],sy[];int j,h; { int i,p,k[3],m,n; char ktans[20]; for(k[j]=0;k[j]<4;k[j]++) { ans[2*j+1]=sy[k[j>; /* 刚才的四个数分别存放在0、2、4、6位 这里的三个运算符号分别存放在1、3、5位*/ if(j==2) { ans[5]=sy[k[j>; /* 此处根据不同的表达式形式再进行相应的处理 */ } else } } 好了,接下来我再考虑不同表达式的处理。刚才我已经将表达式分为三类,是因为添加三个括号对于四张牌来说肯定是重复的。对于第一种,无括号自然不用另行处理;而第二种情况由以下代码可以得出其可能性有六种,其中还有一种是多余的。 for(m=0;m<=4;m+=2) for(n=m+4;n<=8;n+=2) 这个for循环给出了添加一个括号的可能性的种数,其中m、n分别为添加在表达式中的左右括号的位置。我所说的多余的是指m=0,n=8,也就是放在表达式的两端。这真是多此一举,呵呵。最后一种情况是添加两个括号,我分析了一下,发现只可能是这种形式才不会是重复的——(a b)(c d)。为什么不会出现嵌套括号的情况呢。因为如果是嵌套括号,那么外面的括号肯定是包含三个数字的(四个没有必要),也就是说这个括号里面包含了两个运算符号,而这两个运算符号是被另外一个括号隔开的。那么如果这两个运算符号是同一优先级的,则肯定可以通过一些转换去掉括号(你不妨举一些例子来试试),也就是说这一个括号没有必要;如果这两个运算符号不是同一优先级,也必然是这种形式((a+-b)*/c)。而*和/在这几个运算符号中优先级最高,自然就没有必要在它的外面添加括号了。 综上所述,所有可能的表达式的种数为24*64*(1+6+1)=12288种。哈哈,只有一万多种可能性(这其中还有重复),这对于电脑来说可是小case哟。所以,对于穷举的可行性分析和实现也就完成了。 接下来的问题就是如何对有符号的简单表达式进行处理。这是栈的一个著名应用,那么什么是栈呢。栈的概念是从日常生活中货物在货栈种的存取过程抽象出来的,即最后存放入栈的货物(堆在靠出口处)先被提取出去,符合“先进后出,后进先出”的原则。这种结构犹如子弹夹。 在栈中,元素的插入称为压入(push)或入栈,元素的删除称为弹出(pop)或退栈。 栈的基本运算有三种,其中包括入栈运算、退栈运算以及读栈顶元素,这些请参考相关数据结构资料。根据这些基本运算就可以用数组模拟出栈来。 那么作为栈的著名应用,表达式的计算可以有两种方法。 第一种方法—— 首先建立两个栈,操作数栈OVS和运算符栈OPS。其中,操作数栈用来记忆表达式中的操作数,其栈顶指针为topv,初始时为空,即topv=0;运算符栈用来记忆表达式中的运算符,其栈顶指针为topp,初始时,栈中只有一个表达式结束符,即topp=1,且OPS(1)=‘;’。此处的‘;’即表达式结束符。 然后自左至右的扫描待处理的表达式,并假设当前扫描到的符号为W,根据不同的符号W做如下不同的处理: 1、 若W为操作数 2、 则将W压入操作数栈OVS 3、 且继续扫描下一个字符 4、 若W为运算符 5、 则根据运算符的性质做相应的处理: (1)、若运算符为左括号或者运算符的优先级大于运算符栈栈顶的运算符(即OPS(top)),则将运算符W压入运算符栈OPS,并继续扫描下一个字符。 (2)、若运算符W为表达式结束符‘;’且运算符栈栈顶的运算符也为表达式结束符(即OPS(topp)=’;’),则处理过程结束,此时,操作数栈栈顶元素(即OVS(topv))即为表达式的值。 (3)、若运算符W为右括号且运算符栈栈顶的运算符为左括号(即OPS(topp)=’(‘),则将左括号从运算符栈谈出,且继续扫描下一个符号。 (4)、若运算符的右不大于运算符栈栈顶的运算符(即OPS(topp)),则从操作数栈OVS中弹出两个操作数,设先后弹出的操作数为a、b,再从运算符栈OPS中弹出一个运算符,设为+,然后作运算a+b,并将运算结果压入操作数栈OVS。本次的运算符下次将重新考虑。 第二种方法—— 首先对表达式进行线性化,然后将线性表达式转换成机器指令序列以便进行求值。 那么什么是表达式的线性化呢。人们所习惯的表达式的表达方法称为中缀表示。中缀表示的特点是运算符位于运算对象的中间。但这种表示方式,有时必须借助括号才能将运算顺序表达清楚,而且处理也比较复杂。 1929年,波兰逻辑学家Lukasiewicz提出一种不用括号的逻辑符号体系,后来人们称之为波兰表示法(Polish notation)。波兰表达式的特点是运算符位于运算对象的后面,因此称为后缀表示。在对波兰表达式进行运算,严格按照自左至右的顺序进行。下面给出一些表达式及其相应的波兰表达式。 表达式 波兰表达式 A-B AB- (A-B)*C+D AB-C*D+ A*(B+C/D)-E*F ABCD/+*EF*- (B+C)/(A-D) BC+AD-/ OK,所谓表达式的线性化是指将中缀表达的表达式转化为波兰表达式。对于每一个表达式,利用栈可以把表达式变换成波兰表达式,也可以利用栈来计算波兰表达式的值。 至于转换和计算的过程和第一种方法大同小异,这里就不再赘述了。 下面给出转换和计算的具体实现程序—— /* first函数给出各个运算符的优先级,其中=为表达式结束符 */ int first(char c) { int p; switch(c) { case '*': p=2; break; case '/': p=2; break; case '+': p=1; break; case '-': p=1; break; case '(': p=0; break; case '=': p=-1; break; } return(p); } /* 此函数实现中缀到后缀的转换 */ /* M的值宏定义为20 */ /* sp[]为表达式数组 */ int mid_last() { int i=0,j=0; char c,sm[M]; c=s[0]; sm[0]='='; top=0; while(c!='\0') { if(islower(c)) sp[j++]=c; else switch(c) { case '+': case '-': case '*': case '/': while(first(c)<=first(sm[top])) sp[j++]=sm[top--]; sm[++top]=c; break; case '(': sm[++top]=c; break; case ')': while(sm[top]!='(') sp[j++]=sm[top--]; top--; break; default :return(1); } c=s[++i]; } while(top>0) sp[j++]=sm[top--]; sp[j]='\0'; return(0); } /* 由后缀表达式来计算表达式的值 */ int calc() { int i=0,sm[M],tr; char c; c=sp[0]; top=-1; while(c!='\0') { if(islower(c)) sm[++top]=ver[c-'a'];/*在转换过程中用abcd等来代替数, 这样才可以更方便的处理非一位数, ver数组中存放着这些字母所代替的数*/ else switch(c) { case '+': tr=sm[top--]; sm[top]+=tr; break; case '-': tr=sm[top--]; sm[top]-=tr; break; case '*': tr=sm[top--]; sm[top]*=tr; break; case '/': tr=sm[top--];sm[top]/=tr;break; default : return(1); } c=sp[++i]; } if(top>0) return(1); else } 这样这个程序基本上就算解决了,回过头来拿这个程序来算一算文章开始的那个问题。哈哈,算出来了,原来如此简单——(6-3)*10-6=24。 最后我总结了一下这其中容易出错的地方—— 1、 排列的时候由于一个数只能出现一次, 所以必然有一个判断语句。但是用什么来判断,用大小显然不行,因为有可能这四个数中有两个或者以上的数是相同的。我的方法是给每一个数设置一个代号,在排列结束时,通过这个代号找到这个数。 2、在应用嵌套函数时,需仔细分析程序的执行过程,并对个别变量进行适当的调整(如j的值),程序才能正确的执行。 3、在分析括号问题的时候要认真仔细,不要错过任何一个可能的机会,也要尽量使程序变得简单一些。不过我的分析可能也有问题,还请高手指点。 4、在用函数对一个数组进行处理的时候,一定要注意如果这个数组还需要再应用,就必须将它先保存起来,否则会出错,而且是很严重的错误。 5、在处理用户输入的表达式时,由于一个十位数或者更高位数是被分解成各位数存放在数组中,所以需对它们进行处理,将它们转化成实际的整型变量。另外,在转化过程中,用一个字母来代替这个数,并将这个数存在一个数组中,且它在数组中的位置和代替它的这个字母有一定的联系,这样才能取回这个数。 6、由于在穷举过程难免会出现计算过程中有除以0的计算,所以我们必须对calc函数种对于除的运算加以处理,否则程序会因为出错而退出(Divide by 0)。 7、最后一个问题,本程序尚未解决。对于一些比较著名的题目,本程序无法解答。比如说5、5、5、1或者8、8、3、3。这是由于这些题目在计算的过程用到了小数,而本程序并没有考虑到小数。

知与谁同 2019-12-02 01:22:19 0 浏览量 回答数 0

问题

【算法】五分钟算法小知识:动态规划设计:最长递增子序列

游客ih62co2qqq5ww 2020-05-11 07:22:50 26 浏览量 回答数 1

回答

  迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。   利用迭代算法解决问题,需要做好以下三个方面的工作:   一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。   二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。   三、对迭代过程进行控制。在什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。   例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。   分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有   u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,……   根据这个规律,可以归纳出下面的递推公式:   u n = u n - 1 × 2 (n ≥ 2)   对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系:   y=x*2   x=y   让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下:   cls   x=1   for i=2 to 12   y=x*2   x=y   next i   print y   end   例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 2 20 个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。   分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴 2 20 个”,即阿米巴分裂 15 次以后得到的个数是 2 20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2 20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。   设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有   x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1)   因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式:   x=x/2 ( x 的初值为第 15 次分裂之后的个数 2 20 )   让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下:   cls   x=2^20   for i=1 to 15   x=x/2   next i   print x   end   例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。   要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。   分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是:   if n 为偶数 then   n=n/2   else   n=n*3+1   end if   这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下:   cls   input "Please input n=";n   do until n=1   if n mod 2=0 then   rem 如果 n 为偶数,则调用迭代公式 n=n/2   n=n/2   print "—";n;   else   n=n*3+1   print "—";n;   end if   loop   end   迭代法   迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行:   (1) 选一个方程的近似根,赋给变量x0;   (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;   (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。   若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:   【算法】迭代法求方程的根   { x0=初始近似根;   do {   x1=x0;   x0=g(x1); /*按特定的方程计算新的近似根*/   } while ( fabs(x0-x1)>Epsilon);   printf(“方程的近似根是%f\n”,x0);   }   迭代算法也常用于求方程组的根,令   X=(x0,x1,…,xn-1)   设方程组为:   xi=gi(X) (I=0,1,…,n-1)   则求方程组根的迭代算法可描述如下:   【算法】迭代法求方程组的根   { for (i=0;i   x=初始近似根;   do {   for (i=0;i   y=x;   for (i=0;i   x=gi(X);   for (delta=0.0,i=0;i   if (fabs(y-x)>delta) delta=fabs(y-x);   } while (delta>Epsilon);   for (i=0;i   printf(“变量x[%d]的近似根是 %f”,I,x);   printf(“\n”);   }   具体使用迭代法求根时应注意以下两种可能发生的情况:   (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制;   (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。   递归   递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。   能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。   【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。   斐波那契数列为:0、1、1、2、3、……,即:   fib(0)=0;   fib(1)=1;   fib(n)=fib(n-1)+fib(n-2) (当n>1时)。   写成递归函数有:   int fib(int n)   { if (n==0) return 0;   if (n==1) return 1;   if (n>1) return fib(n-1)+fib(n-2);   }   递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。   在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。   在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。   由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。   【问题】 组合问题   问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1   (4)5、3、2 (5)5、3、1 (6)5、2、1   (7)4、3、2 (8)4、3、1 (9)4、2、1   (10)3、2、1   分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。   【程序】   # include   # define MAXN 100   int a[MAXN];   void comb(int m,int k)   { int i,j;   for (i=m;i>=k;i--)   { a[k]=i;   if (k>1)   comb(i-1,k-1);   else   { for (j=a[0];j>0;j--)   printf(“%4d”,a[j]);   printf(“\n”);   }   }   }   void main()   { a[0]=3;   comb(5,3);   }   【问题】 背包问题   问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。   设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。   对于第i件物品的选择考虑有两种可能:   (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。   (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。   按以上思想写出递归算法如下:   try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv)   { /*考虑物品i包含在当前方案中的可能性*/   if(包含物品i是可以接受的)   { 将物品i包含在当前方案中;   if (i   try(i+1,tw+物品i的重量,tv);   else   /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   恢复物品i不包含状态;   }   /*考虑物品i不包含在当前方案中的可能性*/   if (不包含物品i仅是可男考虑的)   if (i   try(i+1,tw,tv-物品i的价值);   else   /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   }   为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表:   物品 0 1 2 3   重量 5 3 2 1   价值 4 4 3 1   并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。   按上述算法编写函数和程序如下:   【程序】   # include   # define N 100   double limitW,totV,maxV;   int option[N],cop[N];   struct { double weight;   double value;   }a[N];   int n;   void find(int i,double tw,double tv)   { int k;   /*考虑物品i包含在当前方案中的可能性*/   if (tw+a.weight<=limitW)   { cop=1;   if (i   else   { for (k=0;k   option[k]=cop[k];   maxv=tv;   }   cop=0;   }   /*考虑物品i不包含在当前方案中的可能性*/   if (tv-a.value>maxV)   if (i   else   { for (k=0;k   option[k]=cop[k];   maxv=tv-a.value;   }   }   void main()   { int k;   double w,v;   printf(“输入物品种数\n”);   scanf((“%d”,&n);   printf(“输入各物品的重量和价值\n”);   for (totv=0.0,k=0;k   { scanf(“%1f%1f”,&w,&v);   a[k].weight=w;   a[k].value=v;   totV+=V;   }   printf(“输入限制重量\n”);   scanf(“%1f”,&limitV);   maxv=0.0;   for (k=0;k find(0,0.0,totV);   for (k=0;k   if (option[k]) printf(“%4d”,k+1);   printf(“\n总价值为%.2f\n”,maxv);   }   作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。   【程序】   # include   # define N 100   double limitW;   int cop[N];   struct ele { double weight;   double value;   } a[N];   int k,n;   struct { int ;   double tw;   double tv;   }twv[N];   void next(int i,double tw,double tv)   { twv.=1;   twv.tw=tw;   twv.tv=tv;   }   double find(struct ele *a,int n)   { int i,k,f;   double maxv,tw,tv,totv;   maxv=0;   for (totv=0.0,k=0;k   totv+=a[k].value;   next(0,0.0,totv);   i=0;   While (i>=0)   { f=twv.;   tw=twv.tw;   tv=twv.tv;   switch(f)   { case 1: twv.++;   if (tw+a.weight<=limitW)   if (i   { next(i+1,tw+a.weight,tv);   i++;   }   else   { maxv=tv;   for (k=0;k   cop[k]=twv[k].!=0;   }   break;   case 0: i--;   break;   default: twv.=0;   if (tv-a.value>maxv)   if (i   { next(i+1,tw,tv-a.value);   i++;   }   else   { maxv=tv-a.value;   for (k=0;k   cop[k]=twv[k].!=0;   }   break;   }   }   return maxv;   }   void main()   { double maxv;   printf(“输入物品种数\n”);   scanf((“%d”,&n);   printf(“输入限制重量\n”);   scanf(“%1f”,&limitW);   printf(“输入各物品的重量和价值\n”);   for (k=0;k   scanf(“%1f%1f”,&a[k].weight,&a[k].value);   maxv=find(a,n);   printf(“\n选中的物品为\n”);   for (k=0;k   if (option[k]) printf(“%4d”,k+1);   printf(“\n总价值为%.2f\n”,maxv);   }   递归的基本概念和特点   程序调用自身的编程技巧称为递归( recursion)。   一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。   一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。   注意:   (1) 递归就是在过程或函数里调用自身;   (2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。

小哇 2019-12-02 01:25:19 0 浏览量 回答数 0

回答

迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 利用迭代算法解决问题,需要做好以下三个方面的工作: 一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。 例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。 分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,…… 根据这个规律,可以归纳出下面的递推公式: u n = u n - 1 × 2 (n ≥ 2) 对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系: y=x*2 x=y 让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下: cls x=1 for i=2 to 12 y=x*2 x=y next i print y end 例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 2 20 个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。 分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴 2 20 个”,即阿米巴分裂 15 次以后得到的个数是 2 20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2 20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。 设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有 x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1) 因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式: x=x/2 ( x 的初值为第 15 次分裂之后的个数 2 20 ) 让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下: cls x=2^20 for i=1 to 15 x=x/2 next i print x end 例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。 要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。 分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是: if n 为偶数 then n=n/2 else n=n*3+1 end if 这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下: cls input "Please input n=";n do until n=1 if n mod 2=0 then rem 如果 n 为偶数,则调用迭代公式 n=n/2 n=n/2 print "—";n; else n=n*3+1 print "—";n; end if loop end 迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: (1) 选一个方程的近似根,赋给变量x0; (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。 若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: 【算法】迭代法求方程的根 { x0=初始近似根; do { x1=x0; x0=g(x1); /*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon); printf(“方程的近似根是%f\n”,x0); } 迭代算法也常用于求方程组的根,令 X=(x0,x1,…,xn-1) 设方程组为: xi=gi(X) (I=0,1,…,n-1) 则求方程组根的迭代算法可描述如下: 【算法】迭代法求方程组的根 { for (i=0;i x=初始近似根; do { for (i=0;i y=x; for (i=0;i x=gi(X); for (delta=0.0,i=0;i if (fabs(y-x)>delta) delta=fabs(y-x); } while (delta>Epsilon); for (i=0;i printf(“变量x[%d]的近似根是 %f”,I,x); printf(“\n”); } 具体使用迭代法求根时应注意以下两种可能发生的情况: (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。 递归 递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 斐波那契数列为:0、1、1、2、3、……,即: fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 写成递归函数有: int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。 在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 【问题】 组合问题 问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1 (4)5、3、2 (5)5、3、1 (6)5、2、1 (7)4、3、2 (8)4、3、1 (9)4、2、1 (10)3、2、1 分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。 【程序】 # include # define MAXN 100 int a[MAXN]; void comb(int m,int k) { int i,j; for (i=m;i>=k;i--) { a[k]=i; if (k>1) comb(i-1,k-1); else { for (j=a[0];j>0;j--) printf(“%4d”,a[j]); printf(“\n”); } } } void main() { a[0]=3; comb(5,3); } 【问题】 背包问题 问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。 设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 对于第i件物品的选择考虑有两种可能: (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 按以上思想写出递归算法如下: try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) { /*考虑物品i包含在当前方案中的可能性*/ if(包含物品i是可以接受的) { 将物品i包含在当前方案中; if (i try(i+1,tw+物品i的重量,tv); else /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; 恢复物品i不包含状态; } /*考虑物品i不包含在当前方案中的可能性*/ if (不包含物品i仅是可男考虑的) if (i try(i+1,tw,tv-物品i的价值); else /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; } 为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: 物品 0 1 2 3 重量 5 3 2 1 价值 4 4 3 1 并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 按上述算法编写函数和程序如下: 【程序】 # include # define N 100 double limitW,totV,maxV; int option[N],cop[N]; struct { double weight; double value; }a[N]; int n; void find(int i,double tw,double tv) { int k; /*考虑物品i包含在当前方案中的可能性*/ if (tw+a.weight<=limitW) { cop=1; if (i else { for (k=0;k option[k]=cop[k]; maxv=tv; } cop=0; } /*考虑物品i不包含在当前方案中的可能性*/ if (tv-a.value>maxV) if (i else { for (k=0;k option[k]=cop[k]; maxv=tv-a.value; } } void main() { int k; double w,v; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入各物品的重量和价值\n”); for (totv=0.0,k=0;k { scanf(“%1f%1f”,&w,&v); a[k].weight=w; a[k].value=v; totV+=V; } printf(“输入限制重量\n”); scanf(“%1f”,&limitV); maxv=0.0; for (k=0;k find(0,0.0,totV); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。 【程序】 # include # define N 100 double limitW; int cop[N]; struct ele { double weight; double value; } a[N]; int k,n; struct { int ; double tw; double tv; }twv[N]; void next(int i,double tw,double tv) { twv.=1; twv.tw=tw; twv.tv=tv; } double find(struct ele *a,int n) { int i,k,f; double maxv,tw,tv,totv; maxv=0; for (totv=0.0,k=0;k totv+=a[k].value; next(0,0.0,totv); i=0; While (i>=0) { f=twv.; tw=twv.tw; tv=twv.tv; switch(f) { case 1: twv.++; if (tw+a.weight<=limitW) if (i { next(i+1,tw+a.weight,tv); i++; } else { maxv=tv; for (k=0;k cop[k]=twv[k].!=0; } break; case 0: i--; break; default: twv.=0; if (tv-a.value>maxv) if (i { next(i+1,tw,tv-a.value); i++; } else { maxv=tv-a.value; for (k=0;k cop[k]=twv[k].!=0; } break; } } return maxv; } void main() { double maxv; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入限制重量\n”); scanf(“%1f”,&limitW); printf(“输入各物品的重量和价值\n”); for (k=0;k scanf(“%1f%1f”,&a[k].weight,&a[k].value); maxv=find(a,n); printf(“\n选中的物品为\n”); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 递归的基本概念和特点 程序调用自身的编程技巧称为递归( recursion)。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。 注意: (1) 递归就是在过程或函数里调用自身; (2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。

马铭芳 2019-12-02 01:24:44 0 浏览量 回答数 0

问题

图解九大数据结构 6月13日 【今日算法】

游客ih62co2qqq5ww 2020-06-17 13:17:00 29 浏览量 回答数 1

问题

图解!24张图彻底弄懂九大常见数据结构! 7月22日 【今日算法】

游客ih62co2qqq5ww 2020-07-27 13:19:32 6 浏览量 回答数 1

问题

经典动态规划:高楼扔鸡蛋 6月2日 【今日算法】

游客ih62co2qqq5ww 2020-06-02 16:06:52 3 浏览量 回答数 1

问题

【算法】五分钟算法小知识:学习数据结构和算法的框架思维

游客ih62co2qqq5ww 2020-04-17 09:56:03 10 浏览量 回答数 1

回答

呼叫 @中山野鬼######叫我做什么?这些都是教科书的东西。哈。。。基本无视。答的好的未必干的好,干的好的未必答的好。中国有中国的国情。如果要我回答,没有什么异议的我就不说了,我说说可能和标准答案结果不对的我的态度(当然我也不知道标准答案)。 第1题,我没什么异议。不过,在中国,非语言传递的信息,能有5%是可靠的就不错了。纸面上的东西无论再怎么正确,客户决策者的态度,不会在纸面上摆着,不吃饭,不吹牛,怎么摸的清楚? 第2题,比较扯淡,标准学院派的。因为“缺陷”的定义是动态的。同样的问题,对于不同的客户关注点是不同的。例如OA系统,报表是个大头,但对于数据库,LOG足够。即便有BUG,重要性才决定它是否算是个缺陷。这种动态的东西怎么可能后面有个基本排序原则。   例如,第4题,更接近实际情况的是a,进度问题。但我不知道上面的标准答案是什么。 例如第7题,这个题目称述有问题,因为客户在扩大项目范围时,项目经理要做的是递烟,泡澡,塞纸钱而使得甲方另起项目,而不是在原有项目中扩充,或修改合同。项目经理看到的并不是个计划的实施,而是一个合同。对合同外的描述内容,应该以增补和另立合同为主此已经超出了项目经理的职权范围。项目范围扩大65%,成本增加4倍(也就老外想的出,项目范围扩大4倍,成本增加65%倒更贴近实际,否则更本就是不能接的单子),这就不是一个项目内可接受的现实。如果甲方非要如此,还是上面的三个步骤,不然就死破脸走官司路线。公司就是关门,也不能自己贴钱这么给甲方耍,没底线的乙方,是做不成甲方认可的东西的,也是活不长久的乙方。 第8题表示,整个题目是老外出的,哈。以我的经验,大头是项目计划实施。 简答题中,第5题也是有问题的,至少我有很大异议,原型更本就不应该在项目中出现。除非原型设计就是项目本身,此时也就不存在针对项目的原型一说。 国内,很多问题不是问题,只要问题本身不是人的问题。是问题的,都是人的思想问题。国内从老板到一线员工,出了问题,感性的很多,就是屁股决定意识的很多。所以国内做项目经理,最要紧的还是靠嘴巴说。要么中国怎么“厚黑”能成个学问呢。######主要想看你对简答那块的经验######如果是简答题,上面没有说的题目我补充一下,也当给这里的朋友提点片面的意见,以后要面试或许能用上,无论正面还是反面。 1、这个题目比较虚。得看什么类型的项目。但无非是计划、实施(执行),验收,三个环节。我说了,不能出现变更,当然实际情况不能没有变更。项目经理和其他人员要和甲方互动到,形式变更实质没变更的程度才行。项目实施不存在规划问题,这个是售前的事情。计划属于售前规划后的细化。实施是计划的落地和推进。验收这块存在调整,但在计划和实施中需要提前和甲方互动,项目实施的整体其实就围绕一个核心,就是合同的履行,所以所有工作都是围绕验收来忙。 2、这个问题很小白。工期是计划时间表,工作量是执行量。两个东西毛关系没有。而且工作量和业务本身的形态有关,有些东西先进场,有些东西后才到,比如你代码没写好,测个毛啊?当然这里说的不是测试代码本身的构造,只是基于测试代码已经存在的情况。工期和工作量没有对等关系。 3、这个问题问的比较好。就我的经验,明确谈什么,这是第一。明确想要什么,这是第二。余下就是开会。开会其实有三种。一种是传达信息。一种是说服别人,一种是汇总信息。每种不一样。传达信息,确认大家明确就OK。说服别人重点不在于用谁的意见说服,重点在于大家一致认可。汇总信息重点在明确大家说清楚了该说的内容。 4、这个我个人觉得是挺白痴的问题,可能对有些企业有些项目经理的考核是需要的。这个问题如同有次我去算法的面试,有人问我XX版本管理工具会不会?确实不会。当时不仅有种弱智感,同时还有种BS惜BS的感觉。我还没无聊到靠工具来维护自己的技术水平证明的低级趣味阶段。 6、这个问题,只有一个结论。就是硬抗过去。没有它法。因为资源不足,你分包,或者卖掉都不切合实际。 7、项目经理主要做哪些内容,其实也很简单,首先是协调,组内协调,甲乙双方的协调。其次是决策调整,根据组内和甲乙双方的情况调整规划和审核内容,最后是审核阶段情况。 不能反过来做,先审核内部,再去协调和和调整。项目实施是有时间期限的,多拖一天,公司多投入一份,回款的变数也多一份。好的项目经理在于先能搞清楚哪些是需要拖的问题,哪些是需要解决的问题。前者尽快留资源准备,后者尽量掩盖以回避。 虽然上面有些话说的很负面,但实际上都是中立的话。做事情就是做事情。把事情做好皆大欢喜,而不存在什么吭蒙拐骗一说。而好和不好,对乙方就是少投入,收回款。对甲方就是保护好甲方投入的价值存在。 后面一句话可能很多人又不理解了。我先说个做人的道理,你不考虑对方,对方就不会考虑你。再简单举个例子:比如客户要上个项目,那么你搞不清楚客户上项目的更本动力在哪,你就无法从客户的角度来判断,你所带的项目,哪些是能给你客户带来价值的。哪些对他是没价值的。客户投钱,不是你的钱,也只是给你所在公司的,但是既然你是做项目经理,你就要对这笔钱的投入保护好,也就是让该展现的展现。什么是该展现的?不是客户的某个代表认为有价值的,而是确实对客户有价值的。 如果你只以客户的某个代表的喜好来判断客户(抽象的)投入的价值点,那么迟早会倒霉。如果你真从客户的角度来判断价值点,你也迟早会说服客户。###### 引用来自“中山野鬼”的答案 如果是简答题,上面没有说的题目我补充一下,也当给这里的朋友提点片面的意见,以后要面试或许能用上,无论正面还是反面。 1、这个题目比较虚。得看什么类型的项目。但无非是计划、实施(执行),验收,三个环节。我说了,不能出现变更,当然实际情况不能没有变更。项目经理和其他人员要和甲方互动到,形式变更实质没变更的程度才行。项目实施不存在规划问题,这个是售前的事情。计划属于售前规划后的细化。实施是计划的落地和推进。验收这块存在调整,但在计划和实施中需要提前和甲方互动,项目实施的整体其实就围绕一个核心,就是合同的履行,所以所有工作都是围绕验收来忙。 2、这个问题很小白。工期是计划时间表,工作量是执行量。两个东西毛关系没有。而且工作量和业务本身的形态有关,有些东西先进场,有些东西后才到,比如你代码没写好,测个毛啊?当然这里说的不是测试代码本身的构造,只是基于测试代码已经存在的情况。工期和工作量没有对等关系。 3、这个问题问的比较好。就我的经验,明确谈什么,这是第一。明确想要什么,这是第二。余下就是开会。开会其实有三种。一种是传达信息。一种是说服别人,一种是汇总信息。每种不一样。传达信息,确认大家明确就OK。说服别人重点不在于用谁的意见说服,重点在于大家一致认可。汇总信息重点在明确大家说清楚了该说的内容。 4、这个我个人觉得是挺白痴的问题,可能对有些企业有些项目经理的考核是需要的。这个问题如同有次我去算法的面试,有人问我XX版本管理工具会不会?确实不会。当时不仅有种弱智感,同时还有种BS惜BS的感觉。我还没无聊到靠工具来维护自己的技术水平证明的低级趣味阶段。 6、这个问题,只有一个结论。就是硬抗过去。没有它法。因为资源不足,你分包,或者卖掉都不切合实际。 7、项目经理主要做哪些内容,其实也很简单,首先是协调,组内协调,甲乙双方的协调。其次是决策调整,根据组内和甲乙双方的情况调整规划和审核内容,最后是审核阶段情况。 不能反过来做,先审核内部,再去协调和和调整。项目实施是有时间期限的,多拖一天,公司多投入一份,回款的变数也多一份。好的项目经理在于先能搞清楚哪些是需要拖的问题,哪些是需要解决的问题。前者尽快留资源准备,后者尽量掩盖以回避。 虽然上面有些话说的很负面,但实际上都是中立的话。做事情就是做事情。把事情做好皆大欢喜,而不存在什么吭蒙拐骗一说。而好和不好,对乙方就是少投入,收回款。对甲方就是保护好甲方投入的价值存在。 后面一句话可能很多人又不理解了。我先说个做人的道理,你不考虑对方,对方就不会考虑你。再简单举个例子:比如客户要上个项目,那么你搞不清楚客户上项目的更本动力在哪,你就无法从客户的角度来判断,你所带的项目,哪些是能给你客户带来价值的。哪些对他是没价值的。客户投钱,不是你的钱,也只是给你所在公司的,但是既然你是做项目经理,你就要对这笔钱的投入保护好,也就是让该展现的展现。什么是该展现的?不是客户的某个代表认为有价值的,而是确实对客户有价值的。 如果你只以客户的某个代表的喜好来判断客户(抽象的)投入的价值点,那么迟早会倒霉。如果你真从客户的角度来判断价值点,你也迟早会说服客户。 请问先生,这些知识或者叫经验,你是怎么学到的,或者说知道的? 我想学习你的学习能力。 ######我奇怪的是如果世上所有的项目经理都是这个标准来考核那将没有经理可言,因为这些题都是针对那些有丰富经验的项目经理,刚上任的经理能答出这些题目算见鬼了。######对单选题表示无语。###### 引用来自“李渊”的答案 引用来自“中山野鬼”的答案 如果是简答题,上面没有说的题目我补充一下,也当给这里的朋友提点片面的意见,以后要面试或许能用上,无论正面还是反面。 1、这个题目比较虚。得看什么类型的项目。但无非是计划、实施(执行),验收,三个环节。我说了,不能出现变更,当然实际情况不能没有变更。项目经理和其他人员要和甲方互动到,形式变更实质没变更的程度才行。项目实施不存在规划问题,这个是售前的事情。计划属于售前规划后的细化。实施是计划的落地和推进。验收这块存在调整,但在计划和实施中需要提前和甲方互动,项目实施的整体其实就围绕一个核心,就是合同的履行,所以所有工作都是围绕验收来忙。 2、这个问题很小白。工期是计划时间表,工作量是执行量。两个东西毛关系没有。而且工作量和业务本身的形态有关,有些东西先进场,有些东西后才到,比如你代码没写好,测个毛啊?当然这里说的不是测试代码本身的构造,只是基于测试代码已经存在的情况。工期和工作量没有对等关系。 3、这个问题问的比较好。就我的经验,明确谈什么,这是第一。明确想要什么,这是第二。余下就是开会。开会其实有三种。一种是传达信息。一种是说服别人,一种是汇总信息。每种不一样。传达信息,确认大家明确就OK。说服别人重点不在于用谁的意见说服,重点在于大家一致认可。汇总信息重点在明确大家说清楚了该说的内容。 4、这个我个人觉得是挺白痴的问题,可能对有些企业有些项目经理的考核是需要的。这个问题如同有次我去算法的面试,有人问我XX版本管理工具会不会?确实不会。当时不仅有种弱智感,同时还有种BS惜BS的感觉。我还没无聊到靠工具来维护自己的技术水平证明的低级趣味阶段。 6、这个问题,只有一个结论。就是硬抗过去。没有它法。因为资源不足,你分包,或者卖掉都不切合实际。 7、项目经理主要做哪些内容,其实也很简单,首先是协调,组内协调,甲乙双方的协调。其次是决策调整,根据组内和甲乙双方的情况调整规划和审核内容,最后是审核阶段情况。 不能反过来做,先审核内部,再去协调和和调整。项目实施是有时间期限的,多拖一天,公司多投入一份,回款的变数也多一份。好的项目经理在于先能搞清楚哪些是需要拖的问题,哪些是需要解决的问题。前者尽快留资源准备,后者尽量掩盖以回避。 虽然上面有些话说的很负面,但实际上都是中立的话。做事情就是做事情。把事情做好皆大欢喜,而不存在什么吭蒙拐骗一说。而好和不好,对乙方就是少投入,收回款。对甲方就是保护好甲方投入的价值存在。 后面一句话可能很多人又不理解了。我先说个做人的道理,你不考虑对方,对方就不会考虑你。再简单举个例子:比如客户要上个项目,那么你搞不清楚客户上项目的更本动力在哪,你就无法从客户的角度来判断,你所带的项目,哪些是能给你客户带来价值的。哪些对他是没价值的。客户投钱,不是你的钱,也只是给你所在公司的,但是既然你是做项目经理,你就要对这笔钱的投入保护好,也就是让该展现的展现。什么是该展现的?不是客户的某个代表认为有价值的,而是确实对客户有价值的。 如果你只以客户的某个代表的喜好来判断客户(抽象的)投入的价值点,那么迟早会倒霉。如果你真从客户的角度来判断价值点,你也迟早会说服客户。 请问先生,这些知识或者叫经验,你是怎么学到的,或者说知道的? 我想学习你的学习能力。 吹水的说一句,无论你信不信,曾经在一家公司,我只是个技术人员。做算法写代码。不过平时对于公司管理的东西也带这思考。公司整体的每月运营支出,我的估算和外面朋友做的调研基本上接近。我觉得没什么刻意学吧,如同你对数字感兴趣,对很多数学问题就会很敏感。如果你对管理有兴趣,对很多组织化的东西就会很敏感。沉淀久了,多少也能算水多。。。 ######学习了######请参考 信息系统项目管理师 这本教材,虽然这是理论,现实项目中不一定这样,但是你要去应聘一个比较大的项目的项目经理时,还是要有一定的理论支撑的,项目越大作用越明显######哈。水平的深度是由理论的高度决定的嘛。希望我关于对学院派的鄙夷不要误导大家理解理论。######嗯 项目越大越明显######PMP例题?######这个是考试题,不是面试题######回复 @dedenj : 呵呵 专业的PM 这是基础######个人觉得,如果我去应聘PM,别人甩一张这个试卷来,我直接闪人。至少说明一点,这个公司的HR不知道到底如果招聘PM。。 我们不是来考PM证的,要考证至少要加几题,PM主要职责是什么,关键路径和成本控制,沟通原则,呵呵######就是面试时做的一份简单试卷

kun坤 2020-06-08 11:13:54 0 浏览量 回答数 0

问题

【Java学习全家桶】1460道Java热门问题,阿里百位技术专家答疑解惑

管理贝贝 2019-12-01 20:07:15 27612 浏览量 回答数 19

回答

    using System;     using System.Collections.Generic;     using System.Linq;     using System.Text;    namespace test{    class QuickSort    {        static void Main(string[] args)        {            int[] array = { 49, 38, 65, 97, 76, 13, 27 };            sort(array, 0, array.Length - 1);            Console.ReadLine();        }        /**一次排序单元,完成此方法,key左边都比key小,key右边都比key大。         **@param array排序数组          **@param low排序起始位置          **@param high排序结束位置         **@return单元排序后的数组 */        private static int sortUnit(int[] array, int low, int high)        {            int key = array[low];            while (low < high)            {                /*从后向前搜索比key小的值*/                while (array[high] >= key && high > low)                    --high;                 /*比key小的放左边*/                array[low] = array[high];                   /*从前向后搜索比key大的值,比key大的放右边*/                while (array[low] <= key && high > low)                    ++low;                 /*比key大的放右边*/                array[high] = array[low];            }            /*左边都比key小,右边都比key大。//将key放在游标当前位置。//此时low等于high */            array[low] = key;            foreach (int i in array)            {                Console.Write({0}\t, i);            }            Console.WriteLine();            return high;        }            /**快速排序 *@paramarry *@return */        public static void sort(int[] array, int low, int high)        {            if (low >= high)                return;             /*完成一次单元排序*/            int index = sortUnit(array, low, high);             /*对左边单元进行排序*/            sort(array, low, index - 1);            /*对右边单元进行排序*/            sort(array, index + 1, high);        }    }} 运行结果:27 38 13 49 76 97 6513 27 38 49 76 97 65  13 27 38 49 65 76 97快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序{27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。{76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。图示 快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。”随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描,使没有交换的情况下主元保留在原位置。 QUICKSORT(A,p,r)1 if p<r2 then q ←PARTITION(A,p,r)3 QUICKSORT(A,p,q-1)4 QUICKSORT(A,q+1,r)为排序一个完整的数组A,最初的调用是QUICKSORT(A,1,length[A])。快速排序算法的关键是PARTITION过程,它对子数组A[p..r]进行就地重排:PARTITION(A,p,r)1 x←A[r]2 i←p-13 for j←p to r-14 do if A[j]≤x5 then i←i+16 exchange A[i]←→A[j]7 exchange A[i+1]←→A[r]8 return i+1 对PARTITION和QUICKSORT所作的改动比较小。在新的划分过程中,我们在真正进行划分之前实现交换:(其中PARTITION过程同快速排序伪代码(非随机))RANDOMIZED-PARTITION(A,p,r)1 i← RANDOM(p,r)2 exchange A[r]←→A[i]3 return PARTITION(A,p,r)新的快速排序过程不再调用PARTITION,而是调用RANDOMIZED-PARTITION。RANDOMIZED-QUICKSORT(A,p,r)1 if p<r2 then q← RANDOMIZED-PARTITION(A,p,r)3 RANDOMIZED-QUICKSORT(A,p,q-1)4 RANDOMIZED-QUICKSORT(A,q+1,r) 这里为方便起见,我们假设算法Quick_Sort的范围阈值为1(即一直将线性表分解到只剩一个元素),这对该算法复杂性的分析没有本质的影响。我们先分析函数partition的性能,该函数对于确定的输入复杂性是确定的。观察该函数,我们发现,对于有n个元素的确定输入L[p..r],该函数运行时间显然为θ(n)。最坏情况无论适用哪一种方法来选择pivot,由于我们不知道各个元素间的相对大小关系(若知道就已经排好序了),所以我们无法确定pivot的选择对划分造成的影响。因此对各种pivot选择法而言,最坏情况和最好情况都是相同的。我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候(设输入的表有n个元素)。下面我们暂时认为该猜测正确,在后文我们再详细证明该猜测。对于有n个元素的表L[p..r],由于函数Partition的计算时间为θ(n),所以快速排序在序坏情况下的复杂性有递归式如下:T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n) (1)用迭代法可以解出上式的解为T(n)=θ(n2)。这个最坏情况运行时间与插入排序是一样的。下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。设T(n)是过程Quick_Sort作用于规模为n的输入上的最坏情况的时间,则T(n)=max(T(q)+T(n-q))+θ(n),其中1≤q≤n-1 (2)我们假设对于任何k<n,总有T(k)≤ck,其中c为常数;显然当k=1时是成立的。将归纳假设代入(2),得到:T(n)≤max(cq2+c(n-q)2)+θ(n)=c*max(q2+(n-q)2)+θ(n)因为在[1,n-1]上q2+(n-q)2关于q递减,所以当q=1时q2+(n-q)2有最大值n2-2(n-1)。于是有:T(n)≤cn2-2c(n-1)+θ(n)≤cn2只要c足够大,上面的第二个小于等于号就可以成立。于是对于所有的n都有T(n)≤cn。这样,排序算法的最坏情况运行时间为θ(n2),且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。时间复杂度为o(n2)。最好情况如果每次划分过程产生的区间大小都为n/2,则快速排序法运行就快得多了。这时有:T(n)=2T(n/2)+θ(n),T(1)=θ(1) (3)解得:T(n)=θ(nlogn)快速排序法最佳情况下执行过程的递归树如下图所示,图中lgn表示以10为底的对数,而本文中用logn表示以2为底的对数.由于快速排序法也是基于比较的排序法,其运行时间为Ω(nlogn),所以如果每次划分过程产生的区间大小都为n/2,则运行时间θ(nlogn)就是最好情况运行时间。但是,是否一定要每次平均划分才能达到最好情况呢。要理解这一点就必须理解对称性是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分,乍一看该划分很不对称。我们可以得到递归式:T(n)=T(n/10)+T(9n/10)+θ(n),T(1)=θ(1) (4)请注意树的每一层都有代价n,直到在深度log10n=θ(logn)处达到边界条件,以后各层代价至多为n。递归于深度log10/9n=θ(logn)处结束。这样,快速排序的总时间代价为T(n)=θ(nlogn),从渐进意义上看就和划分是在中间进行的一样。事实上,即使是99:1的划分时间代价也为θ(nlogn)。其原因在于,任何一种按常数比例进行划分所产生的递归树的深度都为θ(nlogn),其中每一层的代价为O(n),因而不管常数比例是什么,总的运行时间都为θ(nlogn),只不过其中隐含的常数因子有所不同。(关于算法复杂性的渐进阶,请参阅算法的复杂性)平均情况快速排序的平均运行时间为θ(nlogn)。我们对平均情况下的性能作直觉上的分析。要想对快速排序的平均情况有个较为清楚的概念,我们就要对遇到的各种输入作个假设。通常都假设输入数据的所有排列都是等可能的。后文中我们要讨论这个假设。当我们对一个随机的输入数组应用快速排序时,要想在每一层上都有同样的划分是不太可能的。我们所能期望的是某些划分较对称,另一些则很不对称。事实上,我们可以证明,如果选择L[p..r]的第一个元素作为支点元素,Partition所产生的划分80%以上都比9:1更对称,而另20%则比9:1差,这里证明从略。平均情况下,Partition产生的划分中既有“好的”,又有“差的”。这时,与Partition执行过程对应的递归树中,好、差划分是随机地分布在树的各层上的。为与我们的直觉相一致,假设好、差划分交替出现在树的各层上,且好的划分是最佳情况划分,而差的划分是最坏情况下的划分。在根节点处,划分的代价为n,划分出来的两个子表的大小为n-1和1,即最坏情况。在根的下一层,大小为n-1的子表按最佳情况划分成大小各为(n-1)/2的两个子表。这儿我们假设含1个元素的子表的边界条件代价为1。在一个差的划分后接一个好的划分后,产生出三个子表,大小各为1,(n-1)/2和(n-1)/2,代价共为2n-1=θ(n)。一层划分就产生出大小为(n-1)/2+1和(n-1)/2的两个子表,代价为n=θ(n)。这种划分差不多是完全对称的,比9:1的划分要好。从直觉上看,差的划分的代价θ(n)可被吸收到好的划分的代价θ(n)中去,结果是一个好的划分。这样,当好、差划分交替分布划分都是好的一样:仍是θ(nlogn),但θ记号中隐含的常数因子要略大一些。关于平均情况的严格分析将在后文给出。在前文从直觉上探讨快速排序的平均性态过程中,我们已假定输入数据的所有排列都是等可能的。如果输入的分布满足这个假设时,快速排序是对足够大的输入的理想选择。但在实际应用中,这个假设就不会总是成立。解决的方法是,利用随机化策略,能够克服分布的等可能性假设所带来的问题。一种随机化策略是:与对输入的分布作“假设”不同的是对输入的分布作“规定”。具体地说,在排序输入的线性表前,对其元素加以随机排列,以强制的方法使每种排列满足等可能性。事实上,我们可以找到一个能在O(n)时间内对含n个元素的数组加以随机排列的算法。这种修改不改变算法的最坏情况运行时间,但它却使得运行时间能够独立于输入数据已排序的情况。另一种随机化策略是:利用前文介绍的选择支点元素pivot的第四种方法,即随机地在L[p..r]中选择一个元素作为支点元素pivot。实际应用中通常采用这种方法。快速排序的随机化版本有一个和其他随机化算法一样的有趣性质:没有一个特别的输入会导致最坏情况性态。这种算法的最坏情况性态是由随机数产生器决定的。你即使有意给出一个坏的输入也没用,因为随机化排列会使得输入数据的次序对算法不产生影响。只有在随机数产生器给出了一个很不巧的排列时,随机化算法的最坏情况性态才会出现。事实上可以证明几乎所有的排列都可使快速排序接近平均情况性态,只有非常少的几个排列才会导致算法的近最坏情况性态。一般来说,当一个算法可按多条路子做下去,但又很难决定哪一条保证是好的选择时,随机化策略是很有用的。如果大部分选择都是好的,则随机地选一个就行了。通常,一个算法在其执行过程中要做很多选择。如果一个好的选择的获益大于坏的选择的代价,那么随机地做一个选择就能得到一个很有效的算法。我们在前文已经了解到,对快速排序来说,一组好坏相杂的划分仍能产生很好的运行时间 。因此我们可以认为该算法的随机化版本也能具有较好的性态。

liujae 2019-12-02 01:18:45 0 浏览量 回答数 0

回答

线性同余方程 在数论中,线性同余方程是最基本的同余方程,“线性”表示方程的未知数次数是一次,即形如: 的方程。此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除(记作 gcd(a,n) | b)。这时,如果 x0 是方程的一个解,那么所有的解可以表示为: 其中d 是a 与 n 的最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中,恰有 d 个解。 目录 1 例子 2 求特殊解 3 线性同余方程组 4 参见 例子 在方程 3x ≡ 2 (mod 6) 中, d = gcd(3,6) = 3 ,3 不整除 2,因此方程无解。 在方程 5x ≡ 2 (mod 6) 中, d = gcd(5,6) = 1,1 整除 2,因此方程在{0,1,2,3,4,5} 中恰有一个解: x=4。 在方程 4x ≡ 2 (mod 6) 中, d = gcd(4,6) = 2,2 整除 2,因此方程在{0,1,2,3,4,5} 中恰有两个解: x=2 and x=5。 求特殊解 对于线性同余方程 ax ≡ b (mod n) (1) 若d = gcd(a, n 整除 b ,那么为整数。由裴蜀定理,存在整数对 (r,s) (可用辗转相除法求得)使得 ar+sn=d,因此 是方程 (1) 的一个解。其他的解都关于与 x 同余。 举例来说,方程 12x ≡ 20 (mod 28) 中d = gcd(12,28) = 4 。注意到 ,因此 是一个解。对模 28 来说,所有的解就是 {4,11,18,25} 。 线性同余方程组 线性同余方程组的求解可以分解为求若干个线性同余方程。比如,对于线性同余方程组: 2x ≡ 2 (mod 6) 3x ≡ 2 (mod 7) 2x ≡ 4 (mod 8) 首先求解第一个方程,得到x ≡ 1 (mod 3),于是令x = 3k + 1,第二个方程就变为: 9k ≡ 1 (mod 7) 解得k ≡ 3 (mod 7)。于是,再令k = 7l + 3,第三个方程就可以化为: 42l ≡ 16 (mod 8) 解出:l ≡ 0 (mod 4),即 l = 4m。代入原来的表达式就有 x = 21(4m) + 10 = 84m + 10,即解为: x≡ 10 (mod 84) 对于一般情况下是否有解,以及解得情况,则需用到数论中的中国剩余定理。 参见 二次剩余 中国剩余定理 谈谈解线性同余方程 因为ACM/ICPC中有些题目是关于数论的,特别是解线性同余方程,所以有必要准备下这方面的知识。关于这部分知识,我先后翻看过很多资料,包括陈景润的《初等数论》、程序设计竞赛例题解、“黑书”和很多网上资料,个人认为讲的最好最透彻的是《算法导论》中的有关章节,看了之后恍然大悟。经过几天的自学,自己觉得基本掌握了其中的“奥妙”。拿出来写成文章。 那么什么是线性同余方程。对于方程:ax≡b(mod m),a,b,m都是整数,求解x 的值。 解题例程:pku1061 青蛙的约会 解题报告 符号说明: mod表示:取模运算 ax≡b(mod m)表示:(ax - b) mod m = 0,即同余 gcd(a,b)表示:a和b的最大公约数 求解ax≡b(mod n)的原理: 对于方程ax≡b(mod n),存在ax + by = gcd(a,b),x,y是整数。而ax≡b(mod n)的解可以由x,y来堆砌。具体做法,见下面的MLES算法。 第一个问题:求解gcd(a,b) 定理一:gcd(a,b) = gcd(b,a mod b) 实现:古老的欧几里德算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附:取模运算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二个问题:求解ax + by = gcd(a,b) 定理二:gcd(b,a mod b) = b * x' + (a mod b) * y' = b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则:x = y' y = x' - a / b * y' 实现: triple Extended_Euclid(int a,int b) { triple result; if(b == 0) { result.d = a; result.x = 1; result.y = 0; } else { triple ee = Extended_Euclid(b,mod(a,b)); result.d = ee.d; result.x = ee.y; result.y = ee.x - (a/b)*ee.y; } return result; } 附:三元组triple的定义 struct triple { int d,x,y; }; 第三个问题:求解ax≡b(mod n) 实现:由x,y堆砌方程的解 int MLES(int a,int b,int n) { triple ee = Extended_Euclid(a,n); if(mod(b,ee.d) == 0) return mod((ee.x * (b / ee.d)),n / ee.d); else return -1; }//返回-1为无解,否则返回的是方程的最小解 说明:ax≡b(mod n)解的个数: 如果ee.d 整除 b 则有ee.d个解; 如果ee.d 不能整除 b 则无解。 求采纳

玄学酱 2019-12-02 01:20:27 0 浏览量 回答数 0

问题

换个角度理解正则表达式

jagen 2019-12-01 22:08:13 22795 浏览量 回答数 9

问题

时间复杂度 7月1日 【今日算法】

游客ih62co2qqq5ww 2020-07-02 23:54:51 6 浏览量 回答数 1

问题

备战大厂每日挑战算法,坚持打卡更有社区定制周边奖品等你赢!

被纵养的懒猫 2020-04-07 11:41:45 5309 浏览量 回答数 5

问题

详解递归 6月18日【今日算法】

游客ih62co2qqq5ww 2020-06-20 12:04:38 2 浏览量 回答数 0

问题

经典动态规划:高楼扔鸡蛋(进阶篇) 6月3日【今日算法】

游客ih62co2qqq5ww 2020-06-03 15:10:38 7 浏览量 回答数 1

回答

遍历一个 List 有哪些不同的方式?每种方法的实现原理是什么?Java 中 List 遍历的最佳实践是什么? 遍历方式有以下几种: for 循环遍历,基于计数器。在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后停止。 迭代器遍历,Iterator。Iterator 是面向对象的一个设计模式,目的是屏蔽不同数据集合的特点,统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。 foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现,使用时不需要显式声明 Iterator 或计数器。优点是代码简洁,不易出错;缺点是只能做简单的遍历,不能在遍历过程中操作数据集合,例如删除、替换。 最佳实践:Java Collections 框架中提供了一个 RandomAccess 接口,用来标记 List 实现是否支持 Random Access。 如果一个数据集合实现了该接口,就意味着它支持 Random Access,按位置读取元素的平均时间复杂度为 O(1),如ArrayList。如果没有实现该接口,表示不支持 Random Access,如LinkedList。 推荐的做法就是,支持 Random Access 的列表可用 for 循环遍历,否则建议用 Iterator 或 foreach 遍历。 说一下 ArrayList 的优缺点 ArrayList的优点如下: ArrayList 底层以数组实现,是一种随机访问模式。ArrayList 实现了 RandomAccess 接口,因此查找的时候非常快。ArrayList 在顺序添加一个元素的时候非常方便。 ArrayList 的缺点如下: 删除元素的时候,需要做一次元素复制操作。如果要复制的元素很多,那么就会比较耗费性能。插入元素的时候,也需要做一次元素复制操作,缺点同上。 ArrayList 比较适合顺序添加、随机访问的场景。 如何实现数组和 List 之间的转换? 数组转 List:使用 Arrays. asList(array) 进行转换。List 转数组:使用 List 自带的 toArray() 方法。 代码示例: ArrayList 和 LinkedList 的区别是什么? 数据结构实现:ArrayList 是动态数组的数据结构实现,而 LinkedList 是双向链表的数据结构实现。随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高,因为 LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。增加和删除效率:在非首尾的增加和删除操作,LinkedList 要比 ArrayList 效率要高,因为 ArrayList 增删操作要影响数组内的其他数据的下标。内存空间占用:LinkedList 比 ArrayList 更占内存,因为 LinkedList 的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。线程安全:ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全; 综合来说,在需要频繁读取集合中的元素时,更推荐使用 ArrayList,而在插入和删除操作较多时,更推荐使用 LinkedList。 补充:数据结构基础之双向链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 ArrayList 和 Vector 的区别是什么? 这两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合 线程安全:Vector 使用了 Synchronized 来实现线程同步,是线程安全的,而 ArrayList 是非线程安全的。性能:ArrayList 在性能方面要优于 Vector。扩容:ArrayList 和 Vector 都会根据实际的需要动态的调整容量,只不过在 Vector 扩容每次会增加 1 倍,而 ArrayList 只会增加 50%。 Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。 Arraylist不是同步的,所以在不需要保证线程安全时时建议使用Arraylist。 插入数据时,ArrayList、LinkedList、Vector谁速度较快?阐述 ArrayList、Vector、LinkedList 的存储性能和特性? ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢。 Vector 中的方法由于加了 synchronized 修饰,因此 Vector 是线程安全容器,但性能上较ArrayList差。 LinkedList 使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但插入数据时只需要记录当前项的前后项即可,所以 LinkedList 插入速度较快。 多线程场景下如何使用 ArrayList? ArrayList 不是线程安全的,如果遇到多线程场景,可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样: 为什么 ArrayList 的 elementData 加上 transient 修饰? ArrayList 中的数组定义如下: private transient Object[] elementData; 再看一下 ArrayList 的定义: public class ArrayList extends AbstractList implements List<E>, RandomAccess, Cloneable, java.io.Serializable 可以看到 ArrayList 实现了 Serializable 接口,这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化,重写了 writeObject 实现: 每次序列化时,先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素,然后遍历 elementData,只序列化已存入的元素,这样既加快了序列化的速度,又减小了序列化之后的文件大小。 List 和 Set 的区别 List , Set 都是继承自Collection 接口 List 特点:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。 Set 特点:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。 另外 List 支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。 Set和List对比 Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。 List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变 Set接口 说一下 HashSet 的实现原理? HashSet 是基于 HashMap 实现的,HashSet的值存放于HashMap的key上,HashMap的value统一为PRESENT,因此 HashSet 的实现比较简单,相关 HashSet 的操作,基本上都是直接调用底层 HashMap 的相关方法来完成,HashSet 不允许重复的值。 HashSet如何检查重复?HashSet是如何保证数据不可重复的? 向HashSet 中add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles 方法比较。 HashSet 中的add ()方法会使用HashMap 的put()方法。 HashMap 的 key 是唯一的,由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。 以下是HashSet 部分源码: hashCode()与equals()的相关规定: 如果两个对象相等,则hashcode一定也是相同的 两个对象相等,对两个equals方法返回true 两个对象有相同的hashcode值,它们也不一定是相等的 综上,equals方法被覆盖过,则hashCode方法也必须被覆盖 hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。 ** ==与equals的区别** ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同 ==是指对内存地址进行比较 equals()是对字符串的内容进行比较3.==指引用是否相同 equals()指的是值是否相同 HashSet与HashMap的区别 Queue BlockingQueue是什么? Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。 在 Queue 中 poll()和 remove()有什么区别? 相同点:都是返回第一个元素,并在队列中删除返回的对象。 不同点:如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。 代码示例: Queue queue = new LinkedList (); queue. offer("string"); // add System. out. println(queue. poll()); System. out. println(queue. remove()); System. out. println(queue. size()); Map接口 说一下 HashMap 的实现原理? HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 HashMap的数据结构: 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。 HashMap 基于 Hash 算法实现的 当我们往Hashmap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。理解了以上过程就不难明白HashMap是如何解决hash冲突的问题,核心就是使用了数组的存储方式,然后将冲突的key的对象放入链表中,一旦发现冲突就在链表中做进一步的对比。 需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn) HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做拉链法的方式可以解决哈希冲突。 JDK1.8之前 JDK1.8之前采用的是拉链法。拉链法:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。 JDK1.8之后 相比于之前的版本,jdk1.8在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。 JDK1.7 VS JDK1.8 比较 JDK1.8主要解决或优化了一下问题: resize 扩容优化引入了红黑树,目的是避免单条链表过长而影响查询效率,红黑树算法请参考解决了多线程死循环问题,但仍是非线程安全的,多线程时可能会造成数据丢失问题。 HashMap的put方法的具体流程? 当我们put的时候,首先计算 key的hash值,这里调用了 hash方法,hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作,高16bit补0,一个数和0异或不变,所以 hash 函数大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或,目的是减少碰撞。按照函数注释,因为bucket数组大小是2的幂,计算下标index = (table.length - 1) & hash,如果不做 hash 处理,相当于散列生效的只有几个低 bit 位,为了减少散列的碰撞,设计者综合考虑了速度、作用、质量之后,使用高16bit和低16bit异或来简单处理减少碰撞,而且JDK8中用了复杂度 O(logn)的树结构来提升碰撞下的性能。 putVal方法执行流程图 ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容; ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③; ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals; ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤; ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可; ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。 HashMap的扩容操作是怎么实现的? ①.在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容; ②.每次扩展的时候,都是扩展2倍; ③.扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。 在putVal()中,我们看到在这个函数里面使用到了2次resize()方法,resize()方法表示的在进行第一次初始化时会对其进行扩容,或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发,这也是JDK1.8版本的一个优化的地方,在1.7中,扩容之后需要重新去计算其Hash值,根据Hash值对其进行分发,但在1.8版本中,则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0,重新进行hash分配后,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上 HashMap是怎么解决哈希冲突的? 答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行; 什么是哈希? Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 所有散列函数都有如下一个基本特性**:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同**。 什么是哈希冲突? 当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)。 HashMap的数据结构 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突: 这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化 hash()函数 上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下: static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或) } 这比在JDK 1.7中,更为简洁,相比在1.7中的4次位运算,5次异或运算(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动); JDK1.8新增红黑树 通过上面的链地址法(使用散列表)和扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时,加入我们某个bucket下对应的链表有n个元素,那么遍历时间复杂度就为O(n),为了针对这个问题,JDK1.8在HashMap中新增了红黑树的数据结构,进一步使得遍历复杂度降低至O(logn); 总结 简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的: 使用链地址法(使用散列表)来链接拥有相同hash值的数据;使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;引入红黑树进一步降低遍历的时间复杂度,使得遍历更快; **能否使用任何类作为 Map 的 key? **可以使用任何类作为 Map 的 key,然而在使用之前,需要考虑以下几点: 如果类重写了 equals() 方法,也应该重写 hashCode() 方法。 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。 如果一个类没有使用 equals(),不应该在 hashCode() 中使用它。 用户自定义 Key 类最佳实践是使之为不可变的,这样 hashCode() 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变,这样就会解决与可变相关的问题了。 为什么HashMap中String、Integer这样的包装类适合作为K? 答:String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况 内部已重写了equals()、hashCode()等方法,遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程),不容易出现Hash值计算错误的情况; 如果使用Object作为HashMap的Key,应该怎么办呢? 答:重写hashCode()和equals()方法 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞; 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性; HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标 答:hashCode()方法返回的是int整数类型,其范围为-(2 ^ 31)~(2 ^ 31 - 1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)~2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置; 那怎么解决呢? HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均; 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题; HashMap 的长度为什么是2的幂次方 为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 这个算法应该如何设计呢? 我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。 那为什么是两次扰动呢? 答:这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的; HashMap 与 HashTable 有什么区别? 线程安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!); 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它; 对Null key 和Null value的支持: HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null,直接抛NullPointerException。 **初始容量大小和每次扩充容量大小的不同 **: ①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。 推荐使用:在 Hashtable 的类注释可以看到,Hashtable 是保留类不建议使用,推荐在单线程环境下使用 HashMap 替代,如果需要多线程使用则用 ConcurrentHashMap 替代。 如何决定使用 HashMap 还是 TreeMap? 对于在Map中插入、删除和定位元素这类操作,HashMap是最好的选择。然而,假如你需要对一个有序的key集合进行遍历,TreeMap是更好的选择。基于你的collection的大小,也许向HashMap中添加元素会更快,将map换为TreeMap进行有序key的遍历。 HashMap 和 ConcurrentHashMap 的区别 ConcurrentHashMap对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用lock锁进行保护,相对于HashTable的synchronized锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。) HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。 ConcurrentHashMap 和 Hashtable 的区别? ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。 底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的; 实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。 两者的对比图: HashTable: JDK1.7的ConcurrentHashMap: JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点): 答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 底层具体实现知道吗?实现原理是什么? JDK1.7 首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。 在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下: 一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个HashEntry数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment的锁。 该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。 JDK1.8 在JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发,效率又提升N倍。 结构如下: 如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount; 辅助工具类 Array 和 ArrayList 有何区别? Array 可以存储基本数据类型和对象,ArrayList 只能存储对象。Array 是指定固定大小的,而 ArrayList 大小是自动扩展的。Array 内置方法没有 ArrayList 多,比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。 对于基本类型数据,集合使用自动装箱来减少编码工作量。但是,当处理固定大小的基本数据类型的时候,这种方式相对比较慢。 如何实现 Array 和 List 之间的转换? Array 转 List: Arrays. asList(array) ;List 转 Array:List 的 toArray() 方法。 comparable 和 comparator的区别? comparable接口实际上是出自java.lang包,它有一个 compareTo(Object obj)方法用来排序comparator接口实际上是出自 java.util 包,它有一个compare(Object obj1, Object obj2)方法用来排序 一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo方法或compare方法,当我们需要对某一个集合实现两种排序方式,比如一个song对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的Collections.sort(). 方法如何比较元素? TreeSet 要求存放的对象所属的类必须实现 Comparable 接口,该接口提供了比较元素的 compareTo()方法,当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。 Collections 工具类的 sort 方法有两种重载的形式, 第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较; 第二种不强制性的要求容器中的元素必须可比较,但是要求传入第二个参数,参数是Comparator 接口的子类型(需要重写 compare 方法实现元素的比较),相当于一个临时定义的排序规则,其实就是通过接口注入比较元素大小的算法,也是对回调模式的应用(Java 中对函数式编程的支持)。

剑曼红尘 2020-03-24 14:41:57 0 浏览量 回答数 0

问题

【精品问答】Python二级考试题库

珍宝珠 2019-12-01 22:03:38 1146 浏览量 回答数 2

回答

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法对算法本身的速度要求很高。 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将给出详细的说明。 对于排序的算法我想先做一点简单的介绍,也是给这篇文章理一个提纲。 我将按照算法的复杂度,从简单到难来分析算法。 第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有使用word,所以无法打出上标和下标)。 第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念,所以这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的(甚至有最慢的),但是算法本身比较奇特,值得参考(编程的角度)。同时也可以让我们从另外的角度来认识这个问题。 第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序(抱歉,里面使用了一些论坛专家的呢称)。 现在,让我们开始吧: 一、简单排序算法 由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境 下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么 问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。 1.冒泡法: 这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡: #include <iostream.h> void BubbleSort(int* pData,int Count) { int iTemp; for(int i=1;i<Count;i++) { for(int j=Count-1;j>=i;j--) { if(pData[j]<pData[j-1]) { iTemp = pData[j-1]; pData[j-1] = pData[j]; pData[j] = iTemp; } } } } void main() { int data[] = {10,9,8,7,6,5,4}; BubbleSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换, 显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。 现在注意,我们给出O方法的定义: 若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没 学好数学呀,对于编程数学是非常重要的。。。) 现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换),复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因,我们通常都是通过循环次数来对比算法。 2.交换法: 交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。 #include <iostream.h> void ExchangeSort(int* pData,int Count) { int iTemp; for(int i=0;i<Count-1;i++) { for(int j=i+1;j<Count;j++) { if(pData[j]<pData[i]) { iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; } } } } void main() { int data[] = {10,9,8,7,6,5,4}; ExchangeSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次) 第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。 3.选择法: 现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下)这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中选择最小的与第二个交换,这样往复下去。 #include <iostream.h> void SelectSort(int* pData,int Count) { int iTemp; int iPos; for(int i=0;i<Count-1;i++) { iTemp = pData[i]; iPos = i; for(int j=i+1;j<Count;j++) { if(pData[j]<iTemp) { iTemp = pData[j]; iPos = j; } } pData[iPos] = pData[i]; pData[i] = iTemp; } } void main() { int data[] = {10,9,8,7,6,5,4}; SelectSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次) 第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次) 循环次数:6次 交换次数:2次 其他: 第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次) 第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n 所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。 4.插入法: 插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张 #include <iostream.h> void InsertSort(int* pData,int Count) { int iTemp; int iPos; for(int i=1;i<Count;i++) { iTemp = pData[i]; iPos = i-1; while((iPos>=0) && (iTemp<pData[iPos])) { pData[iPos+1] = pData[iPos]; iPos--; } pData[iPos+1] = iTemp; } } void main() { int data[] = {10,9,8,7,6,5,4}; InsertSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7(交换1次)(循环1次) 第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次) 第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次) 循环次数:6次 交换次数:3次 其他: 第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次) 第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次) 第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次) 循环次数:4次 交换次数:2次 上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是, 因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单 排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似 选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’ 而这里显然多了一些,所以我们浪费了时间。 最终,我个人认为,在简单排序算法中,选择法是最好的。 二、高级排序算法: 高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。 它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后 把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使 用这个过程(最容易的方法——递归)。 1.快速排序: #include <iostream.h> void run(int* pData,int left,int right) { int i,j; int middle,iTemp; i = left; j = right; middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); } void QuickSort(int* pData,int Count) { run(pData,0,Count-1); } void main() { int data[] = {10,9,8,7,6,5,4}; QuickSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况 1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。 2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。 第一层递归,循环n次,第二层循环2*(n/2)...... 所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n 所以算法复杂度为O(log2(n)*n) 其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变 成交换法(由于使用了递归,情况更糟)。但是你认为这种情况发生的几率有多大。。呵呵,你完全 不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。 如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢于快速排序(因为要重组堆)。 三、其他排序 1.双向冒泡: 通常的冒泡是单向的,而这里是双向的,也就是说还要进行反向的工作。 代码看起来复杂,仔细理一下就明白了,是一个来回震荡的方式。 写这段代码的作者认为这样可以在冒泡的基础上减少一些交换(我不这么认为,也许我错了)。 反正我认为这是一段有趣的代码,值得一看。 #include <iostream.h> void Bubble2Sort(int* pData,int Count) { int iTemp; int left = 1; int right =Count -1; int t; do { //正向的部分 for(int i=right;i>=left;i--) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } left = t+1; //反向的部分 for(i=left;i<right+1;i++) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } right = t-1; }while(left<=right); } void main() { int data[] = {10,9,8,7,6,5,4}; Bubble2Sort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 2.SHELL排序 这个排序非常复杂,看了程序就知道了。 首先需要一个递减的步长,这里我们使用的是9、5、3、1(最后的步长必须是1)。 工作原理是首先对相隔9-1个元素的所有内容排序,然后再使用同样的方法对相隔5-1个元素的排序 以次类推。 #include <iostream.h> void ShellSort(int* pData,int Count) { int step[4]; step[0] = 9; step[1] = 5; step[2] = 3; step[3] = 1; int iTemp; int k,s,w; for(int i=0;i<4;i++) { k = step[i]; s = -k; for(int j=k;j<Count;j++) { iTemp = pData[j]; w = j-k;//求上step个元素的下标 if(s ==0) { s = -k; s++; pData[s] = iTemp; } while((iTemp<pData[w]) && (w>=0) && (w<=Count)) { pData[w+k] = pData[w]; w = w-k; } pData[w+k] = iTemp; } } } void main() { int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1}; ShellSort(data,12); for (int i=0;i<12;i++) cout<<data[i]<<" "; cout<<"\n"; } 呵呵,程序看起来有些头疼。不过也不是很难,把s==0的块去掉就轻松多了,这里是避免使用0 步长造成程序异常而写的代码。这个代码我认为很值得一看。 这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法:“由于复杂的数学原因 避免使用2的幂次步长,它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并 “超出本书讨论范围”的原因(我也不知道过程),我们只有结果了。 四、基于模板的通用排序: 这个程序我想就没有分析的必要了,大家看一下就可以了。不明白可以在论坛上问。 MyData.h文件 /////////////////////////////////////////////////////// class CMyData { public: CMyData(int Index,char* strData); CMyData(); virtual ~CMyData(); int m_iIndex; int GetDataSize(){ return m_iDataSize; }; const char* GetData(){ return m_strDatamember; }; //这里重载了操作符: CMyData& operator =(CMyData &SrcData); bool operator <(CMyData& data ); bool operator >(CMyData& data ); private: char* m_strDatamember; int m_iDataSize; }; //////////////////////////////////////////////////////// MyData.cpp文件 //////////////////////////////////////////////////////// CMyData::CMyData(): m_iIndex(0), m_iDataSize(0), m_strDatamember(NULL) { } CMyData::~CMyData() { if(m_strDatamember != NULL) delete[] m_strDatamember; m_strDatamember = NULL; } CMyData::CMyData(int Index,char* strData): m_iIndex(Index), m_iDataSize(0), m_strDatamember(NULL) { m_iDataSize = strlen(strData); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,strData); } CMyData& CMyData::operator =(CMyData &SrcData) { m_iIndex = SrcData.m_iIndex; m_iDataSize = SrcData.GetDataSize(); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,SrcData.GetData()); return *this; } bool CMyData::operator <(CMyData& data ) { return m_iIndex<data.m_iIndex; } bool CMyData::operator >(CMyData& data ) { return m_iIndex>data.m_iIndex; } /////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////// //主程序部分 #include <iostream.h> #include "MyData.h" template <class T> void run(T* pData,int left,int right) { int i,j; T middle,iTemp; i = left; j = right; //下面的比较都调用我们重载的操作符函数 middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); } template <class T> void QuickSort(T* pData,int Count) { run(pData,0,Count-1); } void main() { CMyData data[] = { CMyData(8,"xulion"), CMyData(7,"sanzoo"), CMyData(6,"wangjun"), CMyData(5,"VCKBASE"), CMyData(4,"jacky2000"), CMyData(3,"cwally"), CMyData(2,"VCUSER"), CMyData(1,"isdong") }; QuickSort(data,8); for (int i=0;i<8;i++) cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n"; cout<<"\n"; }

沉默术士 2019-12-02 01:19:06 0 浏览量 回答数 0

问题

初识Floyd算法 7月7日 【今日算法】

游客ih62co2qqq5ww 2020-07-07 07:07:36 0 浏览量 回答数 0

回答

追加:目测代码逻辑完全没错,只是K值的问题,long类型的K值因为不断的相乘,超过long的上限值,恭喜,在某一次相乘的时候,k值duang一下变成0了,所以,换一种方法吧,题主可以自己断点测试一下,最后k是变成0的######回复 @月生无界 : 客气客气######回复 @月影南溪 : 感谢提出######数据溢出不会变0的###### 月生无界正确地说出了long 型的取值范围。特此,我将从前写的代码展示如下, 来表明JAVA不同类型的变量的取值范围: public class Limits{        public static void main(String args[]){ /* 打印六种数字基本类型变量的最大值和最小值 */   System.out.println("长型最大值 LONG_Max: " + Long.MAX_VALUE); System.out.println("长型最小值 LONG_Min: " + Long.MIN_VALUE); System.out.println("整型最大值 Int_Max: " + Integer.MAX_VALUE); System.out.println("整型最小值 Int_Min: " + Integer.MIN_VALUE); System.out.println("短型最大值 SHORT_Max: " + Short.MAX_VALUE); System.out.println("短型最小值 SHORT_Min: " + Short.MIN_VALUE); System.out.println("字节型最大值 BYTE_Max: " + Byte.MAX_VALUE); System.out.println("字节型最小值 BYTE_Min: " + Byte.MIN_VALUE); //System.out.println("浮点型最大值 FLOAT_Max: " + Float.MAX_VALUE); //System.out.println("浮点型最小值 FLOAT_Min: " + Float.MIN_VALUE); //System.out.println("双精度型最大值 DOUBLE_Max: " + Double.MAX_VALUE); //System.out.println("双精度型最小值 DOUBLE_Min: " + Double.MIN_VALUE);        } } 输出:   长型最大值 LONG_Max: 9223372036854775807 长型最小值 LONG_Min: -9223372036854775808 整型最大值 Int_Max: 2147483647 整型最小值 Int_Min: -2147483648 短型最大值 SHORT_Max: 32767 短型最小值 SHORT_Min: -32768 字节型最大值 BYTE_Max: 127 字节型最小值 BYTE_Min: -128 ..........   就拿计算阶乘为例,以下代码,可以检查JAVA 输出数据的有效性。 public class Factoria { public static void main(String args[]) { //主方法代码块开始 int iFactoria=1;    //用整型存储阶乘 long lFactoria=1; //用长型存储阶乘 for (int i=1; i<17;i++){ //用for循环语句输出1到16的阶乘    iFactoria *=i;  //将i的阶乘存入整型变量    lFactoria *=i;  //将i的阶乘存入长型变量    /* 分别输出存于整型变量和长型变量的阶乘 */    System.out.printf(" %d 的阶乘:\t %10d(int), %15d(long)\n",        i, iFactoria, lFactoria);        }    System.out.printf("最大整型:%12d, 最大长型: %d\n",        Integer.MAX_VALUE,Long.MAX_VALUE);   }  //主方法 main 代码块结束结束 }  // 类 Factoria 定义结束   输出:   1 的阶乘:                1(int),               1(long)  2 的阶乘:                2(int),               2(long)  3 的阶乘:                6(int),               6(long)  4 的阶乘:               24(int),              24(long)  5 的阶乘:              120(int),             120(long)  6 的阶乘:              720(int),             720(long)  7 的阶乘:             5040(int),            5040(long)  8 的阶乘:            40320(int),           40320(long)  9 的阶乘:           362880(int),          362880(long)  10 的阶乘:         3628800(int),         3628800(long)  11 的阶乘:        39916800(int),        39916800(long)  12 的阶乘:       479001600(int),       479001600(long)  13 的阶乘:      1932053504(int),      6227020800(long)  14 的阶乘:      1278945280(int),     87178291200(long)  15 的阶乘:      2004310016(int),   1307674368000(long)  16 的阶乘:      2004189184(int),  20922789888000(long) 最大整型:  2147483647, 最大长型: 9223372036854775807   这里, *      阶乘指从1乘以2乘以3乘以4一直乘到所要求的数。N的阶乘可表示为n!=1×2×3×……×n 或 n!=n×(n-1)! *      用整型(int), 13的阶乘是: 6227020800,超过了 整型变量 int可以表示的最大正整数: 2147483647。 因此,13 或更大的阶乘数据,不能用整型int 表示。以上输出结果表明,用整型int变量存储的阶乘数据,若阶数超过12, 均不正确。 *      以上用长型变量输出的阶乘,尚且是正确的。但,它也有个限度, 17以上的阶乘, 就是“垃圾”了。 *     数学家定义,0!=1,所以0!=1! ######算法有问题,怎么判断素数,这个数学问题先搞清楚,然后再写程序,要不然全是乱的###### package test; public class Test { public static void main(String[] args) { String num = "素数:"; for(int i=2;i<=1000;i++){ //特殊值处理 if(i == 2){ num += i+","; //System.out.println("素数:"+i); }else{ //素数判断条件,从2开始除,取余,如果余值为0,表示不是素数,跳出这个数的循环判断, for(int j=2;j<i;j++){ if(i%j == 0){ break; } //判断是否是素数,能除到比该值小一,且余数不为0,肯定是素数 if(i%j != 0 && j == i-1){ num += i+","; //System.out.println("素数:"+i); } } } } System.out.println(num); } } //好人都是直接贴代码的 ###### 埃拉托色尼筛选法(Sieve of Eratosthenes) 也可以尝试。 import java.util.*; public class Eratosthenes{ // 埃拉托色尼筛选法 public static void main(String args[]){ int i,j; boolean b[]=new boolean[50]; for(i=0;i<b.length;i++) b[i]=true; //将数组的元素全部赋以true for ( i = 2; i < b.length; i++ ) // 从下标2开始递增循环 if ( b[ i ] ==true){// 每次找到值为true的元素 for (j =i+1;j < b.length;j++ ){ /* 就用其下标作为除数,去除往后余下的元素的下标*/ if (j%i == 0 ) //一旦能除尽 b[j] = false;// 将对应的元素值改为false } } for (i=2;i<b.length;i++ )//从2起,打印50以内的质数 if (b[ i ]) //若元素值为true System.out.printf("%4d", i);// 打印出该元素的下标 } } ###### 我已经将 tcxu 和 月生无界 所出示的代码,翻译成 PHP, 运行结果证明两种算法有效。 http://www.oschina.net/code/snippet_2756874_56652 ###### 查看楼主的代码发现, 你应当把 7 行的右花括号”}“,移到17行后边。这样,你的意向就对了: 从 第 9 行 至 第 17 行 处理 (k==0)的情况。从 18行 至 21 行,处理的是 (k != 0 的情况) ######k*(i%j)数值过大溢出了。 for(long j=2;j<i;j++){ k=i%j if(k==0) System.out.print(" "+i+"不是素数,有约数:"); break } ###### 不明白 ”k*(i%j)数值过大溢出了” 的情况 是什么情况? 指的是 这里的数值过大? 超过了 long型所能存储的最大数值 (2的63次方减 1)? 这里的数值并不大呀。 我这里没有安装Java环境,所以,参照楼主的代码,写出java脚本 代码,JavaScript 如下: 测试证明,楼主确实应当把 11 行 的 右花括号 ’ } ‘,移到 17 行:System.out.println(); 的后面。 <html> <head> <meta charset="gb2312"> <title>求1000以内的素数</title> <style> </style> </head> <body> <script>  var n=1; for (var i=1; i<1000;i++){ var k=1; for (var j=2;j<i;j++){ k=k*(i%j); } if (k==0){ //处理 不是素数的情况 document.write( i + " 不是素数,有约数: "); for (var j=2;j<i;j++) if (i%j==0){ document.write( j + " "); } document.write("<br>"); } else if (k !=0){ //处理素数的情况 document.write( "第 " + n +  " 个素数是:" + i + "<br>"); n++; } } </script> </body> </html> ######long取值范围:-9223372036854775808 -到9223372036854775807,明天再测试一下,long的最大值再乘其他数在代码中是否会变成0返回###### 引用来自“tcxu”的评论 月生无界正确地说出了long 型的取值范围。特此,我将从前写的代码展示如下, 来表明JAVA不同类型的变量的取值范围: public class Limits{        public static void main(String args[]){ /* 打印六种数字基本类型变量的最大值和最小值 */   System.out.println("长型最大值 LONG_Max: " + Long.MAX_VALUE); System.out.println("长型最小值 LONG_Min: " + Long.MIN_VALUE); System.out.println("整型最大值 Int_Max: " + Integer.MAX_VALUE); System.out.println("整型最小值 Int_Min: " + Integer.MIN_VALUE); System.out.println("短型最大值 SHORT_Max: " + Short.MAX_VALUE); System.out.println("短型最小值 SHORT_Min: " + Short.MIN_VALUE); System.out.println("字节型最大值 BYTE_Max: " + Byte.MAX_VALUE); System.out.println("字节型最小值 BYTE_Min: " + Byte.MIN_VALUE); //System.out.println("浮点型最大值 FLOAT_Max: " + Float.MAX_VALUE); //System.out.println("浮点型最小值 FLOAT_Min: " + Float.MIN_VALUE); //System.out.println("双精度型最大值 DOUBLE_Max: " + Double.MAX_VALUE); //System.out.println("双精度型最小值 DOUBLE_Min: " + Double.MIN_VALUE);        } } 输出:   长型最大值 LONG_Max: 9223372036854775807 长型最小值 LONG_Min: -9223372036854775808 整型最大值 Int_Max: 2147483647 整型最小值 Int_Min: -2147483648 短型最大值 SHORT_Max: 32767 短型最小值 SHORT_Min: -32768 字节型最大值 BYTE_Max: 127 字节型最小值 BYTE_Min: -128 ..........   就拿计算阶乘为例,以下代码,可以检查JAVA 输出数据的有效性。 public class Factoria { public static void main(String args[]) { //主方法代码块开始 int iFactoria=1;    //用整型存储阶乘 long lFactoria=1; //用长型存储阶乘 for (int i=1; i<17;i++){ //用for循环语句输出1到16的阶乘    iFactoria *=i;  //将i的阶乘存入整型变量    lFactoria *=i;  //将i的阶乘存入长型变量    /* 分别输出存于整型变量和长型变量的阶乘 */    System.out.printf(" %d 的阶乘:\t %10d(int), %15d(long)\n",        i, iFactoria, lFactoria);        }    System.out.printf("最大整型:%12d, 最大长型: %d\n",        Integer.MAX_VALUE,Long.MAX_VALUE);   }  //主方法 main 代码块结束结束 }  // 类 Factoria 定义结束   输出:   1 的阶乘:                1(int),               1(long)  2 的阶乘:                2(int),               2(long)  3 的阶乘:                6(int),               6(long)  4 的阶乘:               24(int),              24(long)  5 的阶乘:              120(int),             120(long)  6 的阶乘:              720(int),             720(long)  7 的阶乘:             5040(int),            5040(long)  8 的阶乘:            40320(int),           40320(long)  9 的阶乘:           362880(int),          362880(long)  10 的阶乘:         3628800(int),         3628800(long)  11 的阶乘:        39916800(int),        39916800(long)  12 的阶乘:       479001600(int),       479001600(long)  13 的阶乘:      1932053504(int),      6227020800(long)  14 的阶乘:      1278945280(int),     87178291200(long)  15 的阶乘:      2004310016(int),   1307674368000(long)  16 的阶乘:      2004189184(int),  20922789888000(long) 最大整型:  2147483647, 最大长型: 9223372036854775807   这里, *      阶乘指从1乘以2乘以3乘以4一直乘到所要求的数。N的阶乘可表示为n!=1×2×3×……×n 或 n!=n×(n-1)! *      用整型(int), 13的阶乘是: 6227020800,超过了 整型变量 int可以表示的最大正整数: 2147483647。 因此,13 或更大的阶乘数据,不能用整型int 表示。以上输出结果表明,用整型int变量存储的阶乘数据,若阶数超过12, 均不正确。 *      以上用长型变量输出的阶乘,尚且是正确的。但,它也有个限度, 17以上的阶乘, 就是“垃圾”了。 *     数学家定义,0!=1,所以0!=1! 真有耐心,我只做了一个简单的测试,发现一些有趣的事情,希望得到正确的解答 上代码 long min = -9223372036854775808L; long max = 9223372036854775807L; System.out.println(min*1+","+min*2+","+min*3+","+min*4); System.out.println(max*1+","+max*2+","+max*3+","+max*4); 结果:-9223372036854775808,0,-9223372036854775808,0 9223372036854775807,-2,9223372036854775805,-4 long的最小最大值从1乘到4,会出现各种结果,不是很懂其中的原理

爱吃鱼的程序员 2020-06-03 16:40:47 0 浏览量 回答数 0

问题

干货分享:DBA专家门诊一期:索引与sql优化问题汇总

xiaofanqie 2019-12-01 21:24:21 74007 浏览量 回答数 38

回答

回2楼啊里新人的帖子 在日常的业务开发中,常见使用到索引的地方大概有两类: 第一类.做业务约束需求,比如需要保证表中每行的单个字段或者某几个组合字段是唯一的,则可以在表中创建唯一索引; 比如:需要保证test表中插入user_id字段的值不能出现重复,则在设计表的时候,就可以在表中user_id字段上创建一个唯一索引: CREATE TABLE `test` (   `id` int(11) NOT NULL AUTO_INCREMENT,   `user_id` int(11) NOT NULL,   `gmt_create` datetime DEFAULT NULL,   PRIMARY KEY (`id`),   UNIQUE KEY `uk_userid` (`user_id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 ; 第二类.提高SQL语句执行速度,可以根据SQL语句的查询条件在表中创建合适的索引,以此来提升SQL语句的执行速度; 此过程好比是去图书找一本书,最慢的方法就是从图书馆的每一层楼每一个书架一本本的找过去;快捷一点的方法就是先通过图书检索来确认这一本书在几楼那个书架上,然后直接去找就可以了;当然创建这个索引也需要有一定的代价,需要存储空间来存放,需要在数据行插入,更新,删除的时候维护索引: 例如: CREATE TABLE `test_record` (   `id` int(11) NOT NULL AUTO_INCREMENT,   `user_id` int(11) NOT NULL,   `gmt_create` datetime DEFAULT NULL,   PRIMARY KEY (`id`) ) ENGINE=InnoDB AUTO_INCREMENT=5635996 DEFAULT CHARSET=utf8 该表有500w的记录,我需要查询20:00后插入的记录有多少条记录: mysql> select count(*) from test_record where gmt_create>'2014-12-17 20:00:00'; +----------+ | count(*) | +----------+ |        1 | +----------+ 1 row in set (1.31 sec) 可以看到查询耗费了1.31秒返回了1行记录,如果我们在gmt_create字段上添加索引: mysql> alter table test_record add index ind_gmt_create(gmt_create); Query OK, 0 rows affected (21.87 sec) Records: 0  Duplicates: 0  Warnings: 0 mysql> select count(*) from test_record where gmt_create>'2014-12-17 20:00:00'; +----------+ | count(*) | +----------+ |        1 | +----------+ 1 row in set (0.01 sec) 查询只消耗了0.01秒中就返回了记录. 总的来说,为SQL语句(select,update,delete)创建必要的索引是必须的,这样虽然有一定的性能和空间消耗,但是是值得,尤其是在大并发的请求下,大量的数据被扫描造成系统IO和CPU资源消耗完,进而导致整个数据库不可服务. ------------------------- 怎么学好数据库是一个比较大题目,数据库不仅仅是写SQL那么简单,即使知道了SQL怎么写,还需要很清楚的知道这条SQL他大概扫描了多少数据,返回多少数据,是否需要创建索引。至于SQL优化是一个比较专业的技术活,但是可以通过学习是可以掌握的,你可以把一条sql从执行不出来优化到瞬间完成执行,这个过程的成就感是信心满满的。学习的方法可以有以下一些过程:1、自己查资料,包括书本,在线文档,google,别人的总结等等,试图自己解决2、多做实验,证明自己的想法以及判断3、如果实在不行,再去论坛问,或者问朋友4、如果问题解决了,把该问题的整个解决方法记录下来,以备后来的需要5、多关注别人的问题,或许以后自己就遇到了,并总是试图去多帮助别人6、习惯从多个方面去考虑问题,并且养成良好的总结习惯 下面是一些国内顶级数据库专家学习数据库的经验分享给大家: http://www.eygle.com/archives/2005/08/ecinieoracleouo.html 其实学习任何东西都是一样,没有太多的捷径可走,必须打好了坚实的基础,才有可以在进一步学习中得到快速提高。王国维在他的《人间词话》中曾经概括了为学的三种境界,我在这里套用一下: 古今之成大事业、大学问者,罔不经过三种之境界。"昨夜西风凋碧树。独上高楼,望尽天涯路。"此第一境界也。"衣带渐宽终不悔,为伊消得人憔悴。"此第二境界也。"众里寻他千百度,蓦然回首,那人却在灯火阑珊处。"此第三境界也。 学习Oracle,这也是你必须经历的三种境界。 第一层境界是说,学习的路是漫漫的,你必须做好充分的思想准备,如果半途而废还不如不要开始。 这里,注意一个"尽"字,在开始学习的过程中,你必须充分阅读Oracle的基础文档,概念手册、管理手册、备份恢复手册等(这些你都可以在http://tahiti.oracle.com 上找到);OCP认证的教材也值得仔细阅读。打好基础之后你才具备了进一步提升的能力,万丈高楼都是由地而起。 第二层境界是说,尽管经历挫折、打击、灰心、沮丧,也都要坚持不放弃,具备了基础知识之后,你可以对自己感兴趣或者工作中遇到的问题进行深入的思考,由浅入深从来都不是轻而易举的,甚至很多时候你会感到自己停滞不前了,但是不要动摇,学习及理解上的突破也需要时间。 第三次境界是说,经历了那么多努力以后,你会发现,那苦苦思考的问题,那百思不得其解的算法原理,原来答案就在手边,你的思路豁然开朗,宛如拨云见月。这个时候,学习对你来说,不再是个难题,也许是种享受,也许成为艺术。 所以如果你想问我如何速成,那我是没有答案的。 不经一番寒彻骨,哪得梅花扑鼻香。 当然这三种境界在实际中也许是交叉的,在不断的学习中,不断有蓦然回首的收获。 我自己在学习的过程中,经常是采用"由点及面法"。 当遇到一个问题后,一定是深入下去,穷究根本,这样你会发现,一个简单的问题也必定会带起一大片的知识点,如果你能对很多问题进行深入思考和研究,那么在深处,你会发现,这些面逐渐接合,慢慢的延伸到oracle的所有层面,逐渐的你就能融会贯通。这时候,你会主动的去尝试全面学习Oracle,扫除你的知识盲点,学习已经成为一种需要。 由实践触发的学习才最有针对性,才更能让你深入的理解书本上的知识,正所谓:" 纸上得来终觉浅,绝知此事要躬行"。实践的经验于我们是至为宝贵的。 如果说有,那么这,就是我的捷径。 想想自己,经常是"每有所获,便欣然忘食", 兴趣才是我们最好的老师。 Oracle的优化是一门学问,也是一门艺术,理解透彻了,你会知道,优化不过是在各种条件之下做出的均衡与折中。 内存、外存;CPU、IO...对这一切你都需要有充分的认识和相当的了解,管理数据库所需要的知识并不单纯。 作为一个数据库管理人员,你需要做的就是能够根据自己的知识以及经验在各种复杂情况下做出快速正确的判断。当问题出现时,你需要知道使用怎样的手段发现问题的根本;找到问题之后,你需要运用你的知识找到解决问题的方法。 这当然并不容易,举重若轻还是举轻若重,取决于你具备怎样的基础以及经验积累。 在网络上,Howard J. Rogers最近创造了一个新词组:Voodoo Tuning,用以形容那些没有及时更新自己的知识技能的所谓的Oracle技术专家。由于知识的陈旧或者理解的肤浅,他们提供的很多调整建议是错误的、容易使人误解的,甚至是荒诞的。他们提供的某些建议在有些情况下也许是正确的,如果你愿意回到Oracle5版或者6版的年代;但是这些建议在Oracle7.0,8.0 或者 Oracle8i以后往往是完全错误的。 后来基于类似问题触发了互联网内Oracle顶级高手的一系列深入讨论,TOM、Jonathan Lewis、HJR等人都参与其中,在我的网站上(www.eygle.com )上对这些内容及相关链接作了简要介绍,有兴趣的可以参考。 HJR给我们提了很好的一个提示:对你所需要调整的内容,你必须具有充分的认识,否则你做出的判断就有可能是错误的。 这也是我想给自己和大家的一个建议: 学习和研究Oracle,严谨和认真必不可少。 当然 你还需要勤奋,我所熟悉的在Oracle领域有所成就的技术人员,他们共同的特点就是勤奋。 如果你觉得掌握的东西没有别人多,那么也许就是因为,你不如别人勤奋。 要是你觉得这一切过于复杂了,那我还有一句简单的话送给大家: 不积跬步,无以至千里。学习正是在逐渐积累过程中的提高。 现在Itpub给我们提供了很好的交流场所,很多问题都可以在这里找到答案,互相讨论,互相学习。这是我们的幸运,我也因此非常感谢这个网络时代。 参考书籍: 如果是一个新人可以先买一些基本的入门书籍,比如MySQL:《 深入浅出MySQL——数据库开发、优化与管理维护 》,在进阶一点的就是《 高性能MySQL(第3版) 》 oracle的参考书籍: http://www.eygle.com/archives/2006/08/oracle_fundbook_recommand.html 最后建议不要在数据库中使用外键,让应用程序来保证。 ------------------------- Re:回 9楼(千鸟) 的帖子 我有一个问题想问问,现在在做一个与图书有关的项目,其中有一个功能是按图书书名搜索相似图书列表,问题不难,但是想优化一下,有如下问题想请教一下: 1、在图书数据库数据表的书名字段里,按图书书名进行关键字搜索,如何快速搜索相关的图书?   现在由于数据不多,直接用的like模糊查找验证功能而已; 如果数据量不大,是可以在数据库中完成搜索的,可以在搜索字段上创建索引,然后进行搜索查询: CREATE TABLE `book` (   `book_id` int(11) NOT NULL AUTO_INCREMENT,   `book_name` varchar(100) NOT NULL,   .............................   PRIMARY KEY (`book_id`),   KEY `ind_name` (`book_name`) ) ENGINE=InnoDB select book.*  from book , (select book_id from book where book_name like '%算法%')  book_search_id  where book.book_id=book_search_id.book_id; 但是当数据量变得很大后,就不在适合了,可以采用一些其他的第三方搜索技术比如sphinx; 2、如何按匹配的关键度进行快速排序?比如搜索“算法”,有一本书是《算法》,另一本书是《算法设计》,要求前者排在更前面。 现在的排序是根据数据表中的主键序号id进行的排序,没有达到想要的效果。 root@127.0.0.1 : test 15:57:12> select book_id,book_name from book_search where book_name like '%算%' order by book_name; +---------+--------------+ | book_id | book_name    | +---------+--------------+ |       2 | 算法       | |       1 | 算法设计 | ------------------------- 回 10楼(大黑豆) 的帖子 模糊查询分为半模糊和全模糊,也就是: select * from book where name like 'xxx%';(半模糊) select * from book where name like '%xxx%';(全模糊) 半模糊可以可以使用到索引,全模糊在上面场景是不能使用到索引的,但可以进行一些改进,比如: select book.*  from book , (select book_id from book where book_name like '%算法%')  book_search_id   where book.book_id=book_search_id.book_id; 注意这里book_id是主键,同时在book_name上创建了索引 上面的sql语句可以利用全索引扫描来完成优化,但是性能不会太好;特别在数据量大,请求频繁的业务场景下不要在数据库进行模糊查询; 非得使用数据库的话 ,建议不要在生产库进行查询,可以在只读节点进行查询,避免查询造成主业务数据库的资源消耗完,导致故障. 可以使用一些开源的搜索引擎技术,比如sphinx. ------------------------- 回 11楼(蓝色之鹰) 的帖子 我想问下,sql优化一般从那几个方面入手?多表之间的连接方式:Nested Loops,Hash Join 和 Sort Merge Join,是不是Hash Join最优连接? SQL优化需要了解优化器原理,索引的原理,表的存储结构,执行计划等,可以买一本书来系统的进行学习,多多实验; 不同的数据库优化器的模型不一样,比如oracle支持NL,HJ,SMJ,但是mysql只支持NL,不通的连接方式适用于不同的应用场景; NL:对于被连接的数据子集较小的情况,嵌套循环连接是个较好的选择 HJ:对于列连接是做大数据集连接时的常用方式 SMJ:通常情况下散列连接的效果都比排序合并连接要好,然而如果行源已经被排过序,在执行排序合并连接时不需要再排序了,这时排序合并连接的性能会优于散列连接 ------------------------- Re:回 19楼(原远) 的帖子 有个问题:分类表TQueCategory,问题表TQuestion(T-SQL) CREATE TABLE TQueCategory ( ID INT IDENTITY(1,1) PRIMARY KEY,        --问题分类ID NAME VARCHAR(20)        --问题分类名称 ) CREATE TABLE TQuestion ( ID INT IDENTITY(1,1) PRIMARY KEY,        --问题ID CateID INT NOT NULL,        --问题分类ID TITLE VARCHAR(50),        --问题标题 CONTENT VARCHAR(500)        --问题内容 ) 当前要统计某个分类下的问题数,有两种方式: 1.每次统计,在TQuestion通过CateID进行分组统计 SELECT CateID,COUNT(1) AS QueNum FROM TQuestion GROUP BY CateID WHERE 1=1 2.在TQueCategory表增加字段QueNum,用于标识该分类下的问题数量 ALTER TABLE TQueCategory ADD QueNum INT SELECT CateID,QueNum FROM TQueCategory 问:在哪种业务应用场景下采用上面哪种方式性能比较好,为什么? ############################################################################################### 方案 一 需要对 TQuestion 的 CateID字段 进行分组 ,可以在 CateID上创建一个索引,这样就可以索引扫描来完成查询; 方案 二 需要对 TQueCategory 进行扫描就可以得出结果,但是必须在问题表有插入,删除的时候维护quenum数量; 单单从SQL的性能来看, 分类表的数量应该是远远小于问题表的数量的,所以方案二的性能会比较好; 但是如果 TQuestion 的插入非常频繁的话,会带来对 TQueCategory的频繁更新,一次 TQuestion 的 insert或deleted就会带来一次 TQueCategory 的update,这个代价其实是蛮高的; 如果这个分类统计的查询不是非常频繁的话,建议还是使用方案一; 同时还可能还会其他的业务逻辑统计需求(例如: CateID +时间),这个时候在把逻辑放到 TQueCategory就不合适了。 ------------------------- 回 20楼(原远) 的帖子 经验之谈,仅供参考 使用外键在开发上确实省去了很多功夫,但是把业务逻辑交由数据库来完成,对后期的维护来说是很麻烦的事情,不利于维护. ------------------------- 回 21楼(玩站网) 的帖子 无关技术方面: 咨询一下,现在mysql新的版本,5.5.45后貌似修改了开源协议。 是否意味着今后我们商业化使用mysql将受到限制? 如果甲骨文真周到那一步,rds是否会受到影响? 一个疑惑: 为什么很少见到有人用mysql正则匹配?性能不好还是什么原因? ######################################## MySQL有商业版 和 社区版,RDS的MySQL采用开源的社区版进行改进,由专门的RDS MySQL源码团队来维护,国内TOP 10的mysql源码贡献者大部分都在RDS,包括了@丁奇 ,@彭立勋 ,@印风 等; 不在数据库中做业务计算,是保证数据库运行稳定的一个好的设计经验; 是否影响性能与你的sql的执行频率,需要参与的计算数据量相关,当然了还包括数据库所在主机的IO,cpu,内存等资源,离开了这些谈性能是没有多大意义的; ------------------------- 回 22楼(比哥) 的帖子 分页该怎么优化才行??? ######################### 可以参考这个链接,里面有很多的最佳实践,其中就包括了分页语句的优化: http://bbs.aliyun.com/read/168647.html?spm=5176.7114037.1996646101.1.celwA1&pos=1 普通写法: select  *  from t where sellerid=100 limit 100000,20 普通limit M,N的翻页写法,往往在越往后翻页的过程中速度越慢,原因 mysql会读取表中的前M+N条数据,M越大,性能就越差: 优化写法: select t1.* from  t t1,             (select id from t  sellerid=100 limit 100000,20) t2 where t1.id=t2.id; 优化后的翻页写法,先查询翻页中需要的N条数据的主键id,在根据主键id 回表查询所需要的N条数据,此过程中查询N条数据的主键ID在索引中完成 注意:需要在t表的sellerid字段上创建索引 create index ind_sellerid on t(sellerid); 案例: user_A (21:42:31): 这个sql该怎么优化,执行非常的慢: | Query   |   51 | Sending data | select id, ... from t_buyer where sellerId = 765922982 and gmt_modified >= '1970-01-01 08:00:00' and gmt_modified <= '2013-06-05 17:11:31' limit 255000, 5000 SQL改写:selectt2.* from (selectid from t_buyer where sellerId = 765922982   andgmt_modified >= '1970-01-01 08:00:00'   andgmt_modified <= '2013-06-05 17:11:31' limit255000, 5000)t1,t_buyer t2 where t1.id=t2.id index:seller_id,gmt_modified user_A(21:58:43): 好像很快啊。神奇,这个原理是啥啊。牛!!! user_A(21:59:55): 5000 rows in set (4.25 sec), 前面要90秒。 ------------------------- 回 27楼(板砖大叔) 的帖子 这里所说的索引都是普通的b-tree索引,mysql,sqlserver,oracle 的关系数据库都是默认支持的; ------------------------- 回 32楼(veeeye) 的帖子 可以详细说明一下“最后建议不要在数据库中使用外键,让应用程序来保证。 ”的原因吗?我们公司在项目中经常使用外键,用程序来保证不是相对而言更加复杂了吗? 这里的不建议使用外键,主要考虑到 : 第一.维护成本上,把一些业务逻辑交由数据库来保证,当业务需求发生改动的时候,需要同时考虑应用程序和数据库,有时候一些数据库变更或者bug,可能会导致外键的失效;同时也给数据库的管理人员带来维护的麻烦,不便于管理。 第二.性能上考虑,当大量数据写入的时候,外键肯定会带来一定的性能损耗,当出现这样的问题时候,再来改造去除外键,真的就不值得了; 最后,不在数据库中参与业务的计算(存储过程,函数,触发器,外键),是保证数据库运行稳定的一个好的最佳实践。 ------------------------- 回 33楼(优雅的固执) 的帖子 ReDBA专家门诊一期:索引与sql优化 十分想请大师分享下建立索引的经验 我平时简历索引是这样的 比如订单信息的话 建立 订单号  唯一聚集索引 其他的比如   客户编号 供应商编号 商品编号 这些建立非聚集不唯一索引   ################################################## 建立索引,需要根据你的SQL语句来进行创建,不是每一个字段都需要进行创建,也不是一个索引都不创建,,可以把你的SQL语句,应用场景发出来看看。 索引的创建确实是一个非常专业的技术活,需要掌握:表的存储方式,索引的原理,数据库的优化器,统计信息,最后还需要能够读懂数据库的执行计划,以此来判断索引是否创建正确; 所以需要进行系统的学习才能掌握,附件是我在2011年的时候的一次公开课的ppt,希望对你有帮助,同时可以把你平时遇到的索引创建的疑惑发到论坛上来,大家可以一起交流。 ------------------------- 回 30楼(几几届) 的帖子 我也是这样,简单的会,仔细写也会写出来,但是就是不知道有没有更快或者更好的 #################################################### 多写写SQL,掌握SQL优化的方法,自然这些问题不在话下了。 ------------------------- 回 40楼(小林阿小林) 的帖子 mysql如何查询需要优化的语句,比如慢查询的步奏,如何找出需要通知程序员修改或者优化的sql语句 ############################################################ 可以将mysql的慢日志打开,就可以记录执行时间超过指定阀值的慢SQL到本地文件或者数据库的slow_log表中; 在RDS中默认是打开了慢日志功能的:long_query_time=1,表示会记录执行时间>=1秒的慢sql; 如何快速找到mysql瓶颈: 简单一点的方法,可以通过监控mysql所在主机的性能(CPU,IO,load等)以及mysql本身的一些状态值(connections,thread running,qps,命中率等); RDS提供了完善的数据库监控体系,包括了CPU,IOPS,Disk,Connections,QPS,可以重点关注cpu,IO,connections,disk 4个 指标; cpu,io,connections主要体现在了性能瓶颈,disk主要体现了空间瓶颈; 有时候一条慢sql语句的频繁调用,也可能导致整个实例的cpu,io,connections达到100%;也有可能一条排序的sql语句,消耗大量的临时空间,导致实例的空间消耗完。 ------------------------- 下面是分析一个cpu 100%的案例分析:该实例的cpu已经到达100% 查看当前数据库的活动会话信息:当前数据库有较多的活跃线程在数据库中执行查看当前数据库正在执行的sql: 可以看到这条sql执行的非常缓慢:[tr=rgb(100, 204, 255)]delete from task_process where task_id='1801099' 查看这个表的索引: CREATE TABLE `task_process` (  `id` int(11) NOT NULL AUTO_INCREMENT,    ................  `task_id` int(11) NOT NULL DEFAULT '0' COMMENT '??????id',   ................  PRIMARY KEY (`id`),  KEY `index_over_task` (`is_over`,`task_id`),  KEY `index_over` (`is_over`,`is_auto`) USING BTREE,  KEY `index_process_sn` (`process_sn`,`is_over`) USING BTREE) ENGINE=InnoDB AUTO_INCREMENT=32129710; 可以看到这个表有3KW的数据,但是没有task_id字段开头的索引,导致该sql语句删除需要进行全表扫描: 在我们的诊断报告中已经将该sql语句捕获到,同时给你提出该怎样进行索引的添加。 广告:诊断报告将会在1月底发布到控制台,到时候用户可以直接查看诊断建议,来完成你的数据库优化。 ------------------------- 回 45楼(dentrite) 的帖子 datetime和int都是占用数据库4个字节,所以在空间上没有什么差别;但是为了可读性,建议还是使用datetime数据类型。 ------------------------- 回 48楼(yuantel) 的帖子 麻烦把ecs_brand和ecs_goods的表结构发出来一下看看 。 ------------------------- 回 51楼(小林阿小林) 的帖子 普通的 ECS服务器上目前还没有这样的慢SQL索引建议的工具。 不过后续有IDBCloud将会集成这样的sql诊断功能,使用他来管理ECS上的数据库就可以使用这样的功能了 。

玄惭 2019-12-02 01:16:11 0 浏览量 回答数 0

问题

【阿里云产品公测】简单日志服务SLS使用评测含教程

mr_wid 2019-12-01 21:08:11 36639 浏览量 回答数 20

回答

共享锁(S):SELECT * FROM table_name WHERE ... LOCK IN SHARE MODE 排他锁(X):SELECT * FROM table_name WHERE ... FOR UPDATE 锁的类别有两种分法: 1. 从数据库系统的角度来看:分为独占锁(即排它锁),共享锁和更新锁 MS-SQL Server 使用以下资源锁模式。 锁模式 描述 共享 (S) 用于不更改或不更新数据的操作(只读操作),如 SELECT 语句。 更新 (U) 用于可更新的资源中。防止当多个会话在读取、锁定以及随后可能进行的资源更新时发生常见形式的死锁。 排它 (X) 用于数据修改操作,例如 INSERT、UPDATE 或 DELETE。确保不会同时同一资源进行多重更新。 意向锁 用于建立锁的层次结构。意向锁的类型为:意向共享 (IS)、意向排它 (IX) 以及与意向排它共享 (SIX)。 架构锁 在执行依赖于表架构的操作时使用。架构锁的类型为:架构修改 (Sch-M) 和架构稳定性 (Sch-S)。 大容量更新 (BU) 向表中大容量复制数据并指定了 TABLOCK 提示时使用。 共享锁 共享 (S) 锁允许并发事务读取 (SELECT) 一个资源。资源上存在共享 (S) 锁时,任何其它事务都不能修改数据。一旦已经读取数据,便立即释放资源上的共享 (S) 锁,除非将事务隔离级别设置为可重复读或更高级别,或者在事务生存周期内用锁定提示保留共享 (S) 锁。 更新锁 更新 (U) 锁可以防止通常形式的死锁。一般更新模式由一个事务组成,此事务读取记录,获取资源(页或行)的共享 (S) 锁,然后修改行,此操作要求锁转换为排它 (X) 锁。如果两个事务获得了资源上的共享模式锁,然后试图同时更新数据,则一个事务尝试将锁转换为排它 (X) 锁。共享模式到排它锁的转换必须等待一段时间,因为一个事务的排它锁与其它事务的共享模式锁不兼容;发生锁等待。第二个事务试图获取排它 (X) 锁以进行更新。由于两个事务都要转换为排它 (X) 锁,并且每个事务都等待另一个事务释放共享模式锁,因此发生死锁。 若要避免这种潜在的死锁问题,请使用更新 (U) 锁。一次只有一个事务可以获得资源的更新 (U) 锁。如果事务修改资源,则更新 (U) 锁转换为排它 (X) 锁。否则,锁转换为共享锁。 排它锁 排它 (X) 锁可以防止并发事务对资源进行访问。其它事务不能读取或修改排它 (X) 锁锁定的数据。 意向锁 意向锁表示 SQL Server 需要在层次结构中的某些底层资源上获取共享 (S) 锁或排它 (X) 锁。例如,放置在表级的共享意向锁表示事务打算在表中的页或行上放置共享 (S) 锁。在表级设置意向锁可防止另一个事务随后在包含那一页的表上获取排它 (X) 锁。意向锁可以提高性能,因为 SQL Server 仅在表级检查意向锁来确定事务是否可以安全地获取该表上的锁。而无须检查表中的每行或每页上的锁以确定事务是否可以锁定整个表。 意向锁包括意向共享 (IS)、意向排它 (IX) 以及与意向排它共享 (SIX)。 锁模式 描述 意向共享 (IS) 通过在各资源上放置 S 锁,表明事务的意向是读取层次结构中的部分(而不是全部)底层资源。 意向排它 (IX) 通过在各资源上放置 X 锁,表明事务的意向是修改层次结构中的部分(而不是全部)底层资源。IX 是 IS 的超集。 与意向排它共享 (SIX) 通过在各资源上放置 IX 锁,表明事务的意向是读取层次结构中的全部底层资源并修改部分(而不是全部)底层资源。允许顶层资源上的并发 IS 锁。例如,表的 SIX 锁在表上放置一个 SIX 锁(允许并发 IS 锁),在当前所修改页上放置 IX 锁(在已修改行上放置 X 锁)。虽然每个资源在一段时间内只能有一个 SIX 锁,以防止其它事务对资源进行更新,但是其它事务可以通过获取表级的 IS 锁来读取层次结构中的底层资源。 独占锁:只允许进行锁定操作的程序使用,其他任何对他的操作均不会被接受。执行数据更新命令时,SQL Server会自动使用独占锁。当对象上有其他锁存在时,无法对其加独占锁。 共享锁:共享锁锁定的资源可以被其他用户读取,但其他用户无法修改它,在执行Select时,SQL Server会对对象加共享锁。 更新锁:当SQL Server准备更新数据时,它首先对数据对象作更新锁锁定,这样数据将不能被修改,但可以读取。等到SQL Server确定要进行更新数据操作时,他会自动将更新锁换为独占锁,当对象上有其他锁存在时,无法对其加更新锁。 数据库锁定机制简单来说,就是数据库为了保证数据的一致性,而使各种共享资源在被并发访问变得有序所设计的一种规则。对于任何一种数据库来说都需要有相应的锁定机制,所以MySQL自然也不能例外。MySQL数据库由于其自身架构的特点,存在多种数据存储引擎,每种存储引擎所针对的应用场景特点都不太一样,为了满足各自特定应用场景的需求,每种存储引擎的锁定机制都是为各自所面对的特定场景而优化设计,所以各存储引擎的锁定机制也有较大区别。MySQL各存储引擎使用了三种类型(级别)的锁定机制:表级锁定,行级锁定和页级锁定。 1.表级锁定(table-level) 表级别的锁定是MySQL各存储引擎中最大颗粒度的锁定机制。该锁定机制最大的特点是实现逻辑非常简单,带来的系统负面影响最小。所以获取锁和释放锁的速度很快。由于表级锁一次会将整个表锁定,所以可以很好的避免困扰我们的死锁问题。 当然,锁定颗粒度大所带来最大的负面影响就是出现锁定资源争用的概率也会最高,致使并大度大打折扣。 使用表级锁定的主要是MyISAM,MEMORY,CSV等一些非事务性存储引擎。 2.行级锁定(row-level) 行级锁定最大的特点就是锁定对象的颗粒度很小,也是目前各大数据库管理软件所实现的锁定颗粒度最小的。由于锁定颗粒度很小,所以发生锁定资源争用的概率也最小,能够给予应用程序尽可能大的并发处理能力而提高一些需要高并发应用系统的整体性能。 虽然能够在并发处理能力上面有较大的优势,但是行级锁定也因此带来了不少弊端。由于锁定资源的颗粒度很小,所以每次获取锁和释放锁需要做的事情也更多,带来的消耗自然也就更大了。此外,行级锁定也最容易发生死锁。 使用行级锁定的主要是InnoDB存储引擎。 3.页级锁定(page-level) 页级锁定是MySQL中比较独特的一种锁定级别,在其他数据库管理软件中也并不是太常见。页级锁定的特点是锁定颗粒度介于行级锁定与表级锁之间,所以获取锁定所需要的资源开销,以及所能提供的并发处理能力也同样是介于上面二者之间。另外,页级锁定和行级锁定一样,会发生死锁。 在数据库实现资源锁定的过程中,随着锁定资源颗粒度的减小,锁定相同数据量的数据所需要消耗的内存数量是越来越多的,实现算法也会越来越复杂。不过,随着锁定资源颗粒度的减小,应用程序的访问请求遇到锁等待的可能性也会随之降低,系统整体并发度也随之提升。 使用页级锁定的主要是BerkeleyDB存储引擎。 总的来说,MySQL这3种锁的特性可大致归纳如下: 表级锁:开销小,加锁快;不会出现死锁;锁定粒度大,发生锁冲突的概率最高,并发度最低; 行级锁:开销大,加锁慢;会出现死锁;锁定粒度最小,发生锁冲突的概率最低,并发度也最高; 页面锁:开销和加锁时间界于表锁和行锁之间;会出现死锁;锁定粒度界于表锁和行锁之间,并发度一般。 适用:从锁的角度来说,表级锁更适合于以查询为主,只有少量按索引条件更新数据的应用,如Web应用;而行级锁则更适合于有大量按索引条件并发更新少量不同数据,同时又有并发查询的应用,如一些在线事务处理(OLTP)系统。 -------------MYSQL处理------------------ 表级锁定 由于MyISAM存储引擎使用的锁定机制完全是由MySQL提供的表级锁定实现,所以下面我们将以MyISAM存储引擎作为示例存储引擎。 1.MySQL表级锁的锁模式 MySQL的表级锁有两种模式:表共享读锁(Table Read Lock)和表独占写锁(Table Write Lock)。锁模式的兼容性: 对MyISAM表的读操作,不会阻塞其他用户对同一表的读请求,但会阻塞对同一表的写请求; 对MyISAM表的写操作,则会阻塞其他用户对同一表的读和写操作; MyISAM表的读操作与写操作之间,以及写操作之间是串行的。当一个线程获得对一个表的写锁后,只有持有锁的线程可以对表进行更新操作。其他线程的读、写操作都会等待,直到锁被释放为止。 2.如何加表锁 MyISAM在执行查询语句(SELECT)前,会自动给涉及的所有表加读锁,在执行更新操作(UPDATE、DELETE、INSERT等)前,会自动给涉及的表加写锁,这个过程并不需要用户干预,因此,用户一般不需要直接用LOCK TABLE命令给MyISAM表显式加锁。 3.MyISAM表锁优化建议 对于MyISAM存储引擎,虽然使用表级锁定在锁定实现的过程中比实现行级锁定或者页级锁所带来的附加成本都要小,锁定本身所消耗的资源也是最少。但是由于锁定的颗粒度比较到,所以造成锁定资源的争用情况也会比其他的锁定级别都要多,从而在较大程度上会降低并发处理能力。所以,在优化MyISAM存储引擎锁定问题的时候,最关键的就是如何让其提高并发度。由于锁定级别是不可能改变的了,所以我们首先需要尽可能让锁定的时间变短,然后就是让可能并发进行的操作尽可能的并发。 (1)查询表级锁争用情况 MySQL内部有两组专门的状态变量记录系统内部锁资源争用情况: mysql> show status like 'table%'; +----------------------------+---------+ | Variable_name | Value | +----------------------------+---------+ | Table_locks_immediate | 100 | | Table_locks_waited | 10 | +----------------------------+---------+ 这里有两个状态变量记录MySQL内部表级锁定的情况,两个变量说明如下: Table_locks_immediate:产生表级锁定的次数; Table_locks_waited:出现表级锁定争用而发生等待的次数; 两个状态值都是从系统启动后开始记录,出现一次对应的事件则数量加1。如果这里的Table_locks_waited状态值比较高,那么说明系统中表级锁定争用现象比较严重,就需要进一步分析为什么会有较多的锁定资源争用了。 (2)缩短锁定时间 如何让锁定时间尽可能的短呢?唯一的办法就是让我们的Query执行时间尽可能的短。 a)尽两减少大的复杂Query,将复杂Query分拆成几个小的Query分布进行; b)尽可能的建立足够高效的索引,让数据检索更迅速; c)尽量让MyISAM存储引擎的表只存放必要的信息,控制字段类型; d)利用合适的机会优化MyISAM表数据文件。 (3)分离能并行的操作 说到MyISAM的表锁,而且是读写互相阻塞的表锁,可能有些人会认为在MyISAM存储引擎的表上就只能是完全的串行化,没办法再并行了。大家不要忘记了,MyISAM的存储引擎还有一个非常有用的特性,那就是ConcurrentInsert(并发插入)的特性。 MyISAM存储引擎有一个控制是否打开Concurrent Insert功能的参数选项:concurrent_insert,可以设置为0,1或者2。三个值的具体说明如下: concurrent_insert=2,无论MyISAM表中有没有空洞,都允许在表尾并发插入记录; concurrent_insert=1,如果MyISAM表中没有空洞(即表的中间没有被删除的行),MyISAM允许在一个进程读表的同时,另一个进程从表尾插入记录。这也是MySQL的默认设置; concurrent_insert=0,不允许并发插入。 可以利用MyISAM存储引擎的并发插入特性,来解决应用中对同一表查询和插入的锁争用。例如,将concurrent_insert系统变量设为2,总是允许并发插入;同时,通过定期在系统空闲时段执行OPTIMIZE TABLE语句来整理空间碎片,收回因删除记录而产生的中间空洞。 (4)合理利用读写优先级 MyISAM存储引擎的是读写互相阻塞的,那么,一个进程请求某个MyISAM表的读锁,同时另一个进程也请求同一表的写锁,MySQL如何处理呢? 答案是写进程先获得锁。不仅如此,即使读请求先到锁等待队列,写请求后到,写锁也会插到读锁请求之前。 这是因为MySQL的表级锁定对于读和写是有不同优先级设定的,默认情况下是写优先级要大于读优先级。 所以,如果我们可以根据各自系统环境的差异决定读与写的优先级: 通过执行命令SET LOW_PRIORITY_UPDATES=1,使该连接读比写的优先级高。如果我们的系统是一个以读为主,可以设置此参数,如果以写为主,则不用设置; 通过指定INSERT、UPDATE、DELETE语句的LOW_PRIORITY属性,降低该语句的优先级。 虽然上面方法都是要么更新优先,要么查询优先的方法,但还是可以用其来解决查询相对重要的应用(如用户登录系统)中,读锁等待严重的问题。 另外,MySQL也提供了一种折中的办法来调节读写冲突,即给系统参数max_write_lock_count设置一个合适的值,当一个表的读锁达到这个值后,MySQL就暂时将写请求的优先级降低,给读进程一定获得锁的机会。 这里还要强调一点:一些需要长时间运行的查询操作,也会使写进程“饿死”,因此,应用中应尽量避免出现长时间运行的查询操作,不要总想用一条SELECT语句来解决问题,因为这种看似巧妙的SQL语句,往往比较复杂,执行时间较长,在可能的情况下可以通过使用中间表等措施对SQL语句做一定的“分解”,使每一步查询都能在较短时间完成,从而减少锁冲突。如果复杂查询不可避免,应尽量安排在数据库空闲时段执行,比如一些定期统计可以安排在夜间执行 三、行级锁定 行级锁定不是MySQL自己实现的锁定方式,而是由其他存储引擎自己所实现的,如广为大家所知的InnoDB存储引擎,以及MySQL的分布式存储引擎NDBCluster等都是实现了行级锁定。考虑到行级锁定君由各个存储引擎自行实现,而且具体实现也各有差别,而InnoDB是目前事务型存储引擎中使用最为广泛的存储引擎,所以这里我们就主要分析一下InnoDB的锁定特性。 1.InnoDB锁定模式及实现机制 考虑到行级锁定君由各个存储引擎自行实现,而且具体实现也各有差别,而InnoDB是目前事务型存储引擎中使用最为广泛的存储引擎,所以这里我们就主要分析一下InnoDB的锁定特性。 总的来说,InnoDB的锁定机制和Oracle数据库有不少相似之处。InnoDB的行级锁定同样分为两种类型,共享锁和排他锁,而在锁定机制的实现过程中为了让行级锁定和表级锁定共存,InnoDB也同样使用了意向锁(表级锁定)的概念,也就有了意向共享锁和意向排他锁这两种。 当一个事务需要给自己需要的某个资源加锁的时候,如果遇到一个共享锁正锁定着自己需要的资源的时候,自己可以再加一个共享锁,不过不能加排他锁。但是,如果遇到自己需要锁定的资源已经被一个排他锁占有之后,则只能等待该锁定释放资源之后自己才能获取锁定资源并添加自己的锁定。而意向锁的作用就是当一个事务在需要获取资源锁定的时候,如果遇到自己需要的资源已经被排他锁占用的时候,该事务可以需要锁定行的表上面添加一个合适的意向锁。如果自己需要一个共享锁,那么就在表上面添加一个意向共享锁。而如果自己需要的是某行(或者某些行)上面添加一个排他锁的话,则先在表上面添加一个意向排他锁。意向共享锁可以同时并存多个,但是意向排他锁同时只能有一个存在。所以,可以说InnoDB的锁定模式实际上可以分为四种:共享锁(S),排他锁(X),意向共享锁(IS)和意向排他锁(IX),我们可以通过以下表格来总结上面这四种所的共存逻辑关系 如果一个事务请求的锁模式与当前的锁兼容,InnoDB就将请求的锁授予该事务;反之,如果两者不兼容,该事务就要等待锁释放。 意向锁是InnoDB自动加的,不需用户干预。对于UPDATE、DELETE和INSERT语句,InnoDB会自动给涉及数据集加排他锁(X);对于普通SELECT语句,InnoDB不会加任何锁;事务可以通过以下语句显示给记录集加共享锁或排他锁。 共享锁(S):SELECT * FROM table_name WHERE ... LOCK IN SHARE MODE 排他锁(X):SELECT * FROM table_name WHERE ... FOR UPDATE 用SELECT ... IN SHARE MODE获得共享锁,主要用在需要数据依存关系时来确认某行记录是否存在,并确保没有人对这个记录进行UPDATE或者DELETE操作。 但是如果当前事务也需要对该记录进行更新操作,则很有可能造成死锁,对于锁定行记录后需要进行更新操作的应用,应该使用SELECT... FOR UPDATE方式获得排他锁。 2.InnoDB行锁实现方式 InnoDB行锁是通过给索引上的索引项加锁来实现的,只有通过索引条件检索数据,InnoDB才使用行级锁,否则,InnoDB将使用表锁 在实际应用中,要特别注意InnoDB行锁的这一特性,不然的话,可能导致大量的锁冲突,从而影响并发性能。下面通过一些实际例子来加以说明。 (1)在不通过索引条件查询的时候,InnoDB确实使用的是表锁,而不是行锁。 (2)由于MySQL的行锁是针对索引加的锁,不是针对记录加的锁,所以虽然是访问不同行的记录,但是如果是使用相同的索引键,是会出现锁冲突的。 (3)当表有多个索引的时候,不同的事务可以使用不同的索引锁定不同的行,另外,不论是使用主键索引、唯一索引或普通索引,InnoDB都会使用行锁来对数据加锁。 (4)即便在条件中使用了索引字段,但是否使用索引来检索数据是由MySQL通过判断不同执行计划的代价来决定的,如果MySQL认为全表扫描效率更高,比如对一些很小的表,它就不会使用索引,这种情况下InnoDB将使用表锁,而不是行锁。因此,在分析锁冲突时,别忘了检查SQL的执行计划,以确认是否真正使用了索引。 3.间隙锁(Next-Key锁) 当我们用范围条件而不是相等条件检索数据,并请求共享或排他锁时,InnoDB会给符合条件的已有数据记录的索引项加锁; 对于键值在条件范围内但并不存在的记录,叫做“间隙(GAP)”,InnoDB也会对这个“间隙”加锁,这种锁机制就是所谓的间隙锁(Next-Key锁)。 例: 假如emp表中只有101条记录,其empid的值分别是 1,2,...,100,101,下面的SQL: mysql> select * from emp where empid > 100 for update; 是一个范围条件的检索,InnoDB不仅会对符合条件的empid值为101的记录加锁,也会对empid大于101(这些记录并不存在)的“间隙”加锁。 InnoDB使用间隙锁的目的: (1)防止幻读,以满足相关隔离级别的要求。对于上面的例子,要是不使用间隙锁,如果其他事务插入了empid大于100的任何记录,那么本事务如果再次执行上述语句,就会发生幻读; (2)为了满足其恢复和复制的需要。 很显然,在使用范围条件检索并锁定记录时,即使某些不存在的键值也会被无辜的锁定,而造成在锁定的时候无法插入锁定键值范围内的任何数据。在某些场景下这可能会对性能造成很大的危害。 除了间隙锁给InnoDB带来性能的负面影响之外,通过索引实现锁定的方式还存在其他几个较大的性能隐患: (1)当Query无法利用索引的时候,InnoDB会放弃使用行级别锁定而改用表级别的锁定,造成并发性能的降低; (2)当Query使用的索引并不包含所有过滤条件的时候,数据检索使用到的索引键所只想的数据可能有部分并不属于该Query的结果集的行列,但是也会被锁定,因为间隙锁锁定的是一个范围,而不是具体的索引键; (3)当Query在使用索引定位数据的时候,如果使用的索引键一样但访问的数据行不同的时候(索引只是过滤条件的一部分),一样会被锁定。 因此,在实际应用开发中,尤其是并发插入比较多的应用,我们要尽量优化业务逻辑,尽量使用相等条件来访问更新数据,避免使用范围条件。 还要特别说明的是,InnoDB除了通过范围条件加锁时使用间隙锁外,如果使用相等条件请求给一个不存在的记录加锁,InnoDB也会使用间隙锁。 4.死锁 MyISAM表锁是deadlock free的,这是因为MyISAM总是一次获得所需的全部锁,要么全部满足,要么等待,因此不会出现死锁。但在InnoDB中,除单个SQL组成的事务外,锁是逐步获得的,当两个事务都需要获得对方持有的排他锁才能继续完成事务,这种循环锁等待就是典型的死锁。 在InnoDB的事务管理和锁定机制中,有专门检测死锁的机制,会在系统中产生死锁之后的很短时间内就检测到该死锁的存在。当InnoDB检测到系统中产生了死锁之后,InnoDB会通过相应的判断来选这产生死锁的两个事务中较小的事务来回滚,而让另外一个较大的事务成功完成。 那InnoDB是以什么来为标准判定事务的大小的呢?MySQL官方手册中也提到了这个问题,实际上在InnoDB发现死锁之后,会计算出两个事务各自插入、更新或者删除的数据量来判定两个事务的大小。也就是说哪个事务所改变的记录条数越多,在死锁中就越不会被回滚掉。 但是有一点需要注意的就是,当产生死锁的场景中涉及到不止InnoDB存储引擎的时候,InnoDB是没办法检测到该死锁的,这时候就只能通过锁定超时限制参数InnoDB_lock_wait_timeout来解决。 需要说明的是,这个参数并不是只用来解决死锁问题,在并发访问比较高的情况下,如果大量事务因无法立即获得所需的锁而挂起,会占用大量计算机资源,造成严重性能问题,甚至拖跨数据库。我们通过设置合适的锁等待超时阈值,可以避免这种情况发生。 通常来说,死锁都是应用设计的问题,通过调整业务流程、数据库对象设计、事务大小,以及访问数据库的SQL语句,绝大部分死锁都可以避免。下面就通过实例来介绍几种避免死锁的常用方法: (1)在应用中,如果不同的程序会并发存取多个表,应尽量约定以相同的顺序来访问表,这样可以大大降低产生死锁的机会。 (2)在程序以批量方式处理数据的时候,如果事先对数据排序,保证每个线程按固定的顺序来处理记录,也可以大大降低出现死锁的可能。 (3)在事务中,如果要更新记录,应该直接申请足够级别的锁,即排他锁,而不应先申请共享锁,更新时再申请排他锁,因为当用户申请排他锁时,其他事务可能又已经获得了相同记录的共享锁,从而造成锁冲突,甚至死锁。 (4)在REPEATABLE-READ隔离级别下,如果两个线程同时对相同条件记录用SELECT...FOR UPDATE加排他锁,在没有符合该条件记录情况下,两个线程都会加锁成功。程序发现记录尚不存在,就试图插入一条新记录,如果两个线程都这么做,就会出现死锁。这种情况下,将隔离级别改成READ COMMITTED,就可避免问题。 (5)当隔离级别为READ COMMITTED时,如果两个线程都先执行SELECT...FOR UPDATE,判断是否存在符合条件的记录,如果没有,就插入记录。此时,只有一个线程能插入成功,另一个线程会出现锁等待,当第1个线程提交后,第2个线程会因主键重出错,但虽然这个线程出错了,却会获得一个排他锁。这时如果有第3个线程又来申请排他锁,也会出现死锁。对于这种情况,可以直接做插入操作,然后再捕获主键重异常,或者在遇到主键重错误时,总是执行ROLLBACK释放获得的排他锁。 5.什么时候使用表锁 对于InnoDB表,在绝大部分情况下都应该使用行级锁,因为事务和行锁往往是我们之所以选择InnoDB表的理由。但在个别特殊事务中,也可以考虑使用表级锁: (1)事务需要更新大部分或全部数据,表又比较大,如果使用默认的行锁,不仅这个事务执行效率低,而且可能造成其他事务长时间锁等待和锁冲突,这种情况下可以考虑使用表锁来提高该事务的执行速度。 (2)事务涉及多个表,比较复杂,很可能引起死锁,造成大量事务回滚。这种情况也可以考虑一次性锁定事务涉及的表,从而避免死锁、减少数据库因事务回滚带来的开销。 应用中这两种事务不能太多,否则,就应该考虑使用MyISAM表了。 在InnoDB下,使用表锁要注意以下两点。 (1)使用LOCK TABLES虽然可以给InnoDB加表级锁,但必须说明的是,表锁不是由InnoDB存储引擎层管理的,而是由其上一层──MySQL Server负责的,仅当autocommit=0、InnoDB_table_locks=1(默认设置)时,InnoDB层才能知道MySQL加的表锁,MySQL Server也才能感知InnoDB加的行锁,这种情况下,InnoDB才能自动识别涉及表级锁的死锁,否则,InnoDB将无法自动检测并处理这种死锁。 (2)在用 LOCK TABLES对InnoDB表加锁时要注意,要将AUTOCOMMIT设为0,否则MySQL不会给表加锁;事务结束前,不要用UNLOCK TABLES释放表锁,因为UNLOCK TABLES会隐含地提交事务;COMMIT或ROLLBACK并不能释放用LOCK TABLES加的表级锁,必须用UNLOCK TABLES释放表锁。

1006541099824509 2019-12-02 03:14:39 0 浏览量 回答数 0

回答

1.字符串转义序列转义字符 描述(在行尾时) 续行符\ 反斜杠符号' 单引号" 双引号a 响铃b 退格(Backspace)e 转义000 空n 换行v 纵向制表符t 横向制表符r 回车f 换页oyy 八进制数yy代表的字符,例如:o12代表换行xyy 十进制数yy代表的字符,例如:x0a代表换行other 其它的字符以普通格式输出 2.字符串格式化 3.操作符 一、算术运算符 注意: 双斜杠 // 除法总是向下取整。 从符点数到整数的转换可能会舍入也可能截断,建议使用math.floor()和math.ceil()明确定义的转换。 Python定义pow(0, 0)和0 ** 0等于1。 二、比较运算符 运算符 描述< 小于<= 小于或等于 大于= 大于或等于== 等于 != 不等于is 判断两个标识符是不是引用自一个对象is not 判断两个标识符是不是引用自不同对象注意: 八个比较运算符优先级相同。 Python允许x < y <= z这样的链式比较,它相当于x < y and y <= z。 复数不能进行大小比较,只能比较是否相等。 三、逻辑运算符 运算符 描述 备注x or y if x is false, then y, elsex x andy if x is false, then x, elsey not x if x is false, then True,elseFalse 注意: or是个短路运算符,它只有在第一个运算数为False时才会计算第二个运算数的值。 and也是个短路运算符,它只有在第一个运算数为True时才会计算第二个运算数的值。 not的优先级比其他类型的运算符低,所以not a == b相当于not (a == b),而 a == not b是错误的。 四、位运算符 运算符 描述 备注x | y 按位或运算符 x ^ y 按位异或运算符 x & y 按位与运算符 x << n 左移动运算符 x >> n 右移动运算符 ~x 按位取反运算符 五、赋值运算符 复合赋值运算符与算术运算符是一一对应的: 六、成员运算符 Python提供了成员运算符,测试一个元素是否在一个序列(Sequence)中。 运算符 描述in 如果在指定的序列中找到值返回True,否则返回False。not in 如果在指定的序列中没有找到值返回True,否则返回False。 4.关键字总结 Python中的关键字包括如下: and del from not while as elif global or with assert else if pass yield break except import print class exec in raise continue finally is return def for lambda try你想看看有哪些关键字?OK,打开一个终端,就像这样~ long@zhouyl:~$ pythonPython 2.7.3 (default, Jan 2 2013, 16:53:07) [GCC 4.7.2] on linux2Type "help", "copyright", "credits" or "license" for more information. import keywordkeyword.kwlist ['and', 'as', 'assert', 'break', 'class', 'continue', 'def', 'del', 'elif', 'else', 'except', 'exec', 'finally', 'for', 'from', 'global', 'if', 'import', 'in', 'is', 'lambda', 'not', 'or', 'pass', 'print', 'raise', 'return', 'try', 'while', 'with', 'yield'] ============================== 华丽的 正文分隔符 ======================================== 看到这些关键字你还能记得多少?你不妨自己一个一个对照想想它的用法,下面是我总结的,我根据前面的学习笔记将上述关键字分为以下几类: 1.判断、循环 对于Python的循环及判断主要包括这些关键字: if elif else for while break continue and or is not in 这几个关键字在前面介绍 if 语法、while语法、for语法以及and...or语法中已有介绍,下面再一笔带过: 1.1 if 语法 if语法与C语言、shell脚本之下的非常类似,最大的区别就是冒号以及严格的缩进,当然这两点也是Python区别于其他语言的地方: if condition1: do something elif condition2: do another thing else: also do something 1.2 while 语法 Python的while语法区别于C、shell下的while除了冒号及缩进之外,还有一点就是while可以携带一个可选的else语句: while condition: do something else: do something 注:else语句是可选的,但是使用while语句时一定要注意判断语句可以跳出! 1.3 for 语法 与while类似,Python的for循环也包括一个可选的else语句(跳出for循环时执行,但是如果是从break语句跳出则不执行else语句块中的代码!),而且for 加上 关键字in就组成了最常见的列表解析用法(以后会写个专门的博客)。 下面是for的一般用法: for i in range(1,10,2): do something if condition: break else: do something for的列表解析用法: for items in list: print items 1.4 and...or 语法 Python的and/or操作与其他语言不同的是它的返回值是参与判断的两个值之一,所以我们可以通过这个特性来实现Python下的 a ? b : c ! 有C语言基础的知道 “ a ? b : c ! ” 语法是判断 a,如果正确则执行b,否则执行 c! 而Python下我们可以这么用:“ a and b or c ”(此方法中必须保证b必须是True值),python自左向右执行此句,先判断a and b :如果a是True值,a and b语句仍需要执行b,而此时b是True值!所以a and b的值是b,而此时a and b or c就变成了b or c,因b是True值,所以b or c的结果也是b;如果a是False值,a and b语句的结果就是a,此时 a and b or c就转化为a or c,因为此时a是 False值,所以不管c是True 还是Flase,a or c的结果就是c!!!捋通逻辑的话,a and b or c 是不是就是Python下的a ? b : c ! 用法? 1.5 is ,not is 和 is not 是Python下判断同一性的关键字,通常用来判断 是 True 、False或者None(Python下的NULL)! 比如 if alue is True : ... (不记得本节的童鞋罚复习:python 学习笔记 2 -- 判断语句) 2.函数、模块、类 对于Python的函数及模块主要包括这些关键字: from import as def pass lambda return class 那么你还能记得它们么?下面简单介绍一下: 2.1 模块 Python的编程通常大量使用标准库中的模块,使用方法就是使用import 、from以及as 关键字。 比如: import sys # 导入sys模块 from sys import argv # 从sys模块中导入argv ,这个在前面介绍脚本传参数时使用到 import cPickle as p # 将cPickle模块导入并在此将它简单命名为p,此后直接可以使用p替代cPickle模块原名,这个在介绍文件输入输出时的存储器中使用到 2.2 函数 Python中定义函数时使用到def关键字,如果你当前不想写入真实的函数操作,可以使用pass关键字指代不做任何操作: def JustAFunction: pass 当然,在需要给函数返回值时就用到了return关键字,这里简单提一下Python下的函数返回值可以是多个(接收返回值时用相应数量的变量接收!)! 此外Python下有个神奇的Lambda函数,它允许你定义单行的最小函数,这是从Lisp中借用来的,可以用在任何需要函数的地方。比如: g = lambda x : x*2 # 定义一个Lambda函数用来计算参数的2倍并返回! print g(2) # 使用时使用lambda函数返回的变量作为这个函数的函数名,括号中带入相应参数即可! (不记得本节的童鞋罚复习:python 学习笔记 4 -- 函数篇) 3.异常 对于Python的异常主要包括这些关键字: try except finally raise 异常这一节还是比较简单的,将可能出现的异常放在 try: 后面的语句块中,使用except关键字捕获一定的异常并在接下来的语句块中做相应操作,而finally中接的是无论出现什么异常总在执行最后做finally: 后面的语句块(比如关闭文件等必要的操作!) raise关键字是在一定的情况下引发异常,通常结合自定义的异常类型使用。 (不记得本节的童鞋罚复习:python 学习笔记 6 -- 异常处理) 4.其他 上面的三类过后,还剩下这些关键字: print del global with assert yield exec 首先print 在前面的笔记或者任何地方你都能见到,所以还是比较熟悉的,此处就不多介绍了!del 关键字在前面的笔记中已有所涉及,比如删除列表中的某项,我们使用 “ del mylist[0] ” 可能这些剩下来的关键字你比较陌生,所以下面来介绍一下: 4.1.global 关键字 当你在函数定义内声明变量的时候,它们与函数外具有相同名称的其他变量没有任何关系,即变量名称对于函数来说是 局部 的。这称为变量的 作用域 。所有变量的作用域是它们被定义的块,从它们的名称被定义的那点开始。 eg. ? 1 2 3 4 5 6 7 8 9 10 11 !/usr/bin/python Filename: func_local.py def func(x): print'x is', x x = 2 print'Changed local x to', x x = 50 func(x) print'x is still', x 运行的结果是这样的:? 1 2 3 4 $ python func_local.py x is 50 # 运行func函数时,先打印x的值,此时带的值是作为参数带入的外部定义的50,所以能正常打印 x=50 Changed local x to 2 # 在func函数中将x赋2,并打印 x is still 50 # 运行完func函数,打印x的值,此时x的值仍然是之前赋给的50,而不是func函数中修改过的2,因为在函数中修改的只是函数内的局部变量 那么为什么我们要在这提到局部变量呢?bingo,聪明的你一下就猜到这个global就是用来定义全局变量的。也就是说如果你想要为一个在函数外定义的变量赋值,那么你就得告诉Python这个变量名不是局部的,而是 全局 的。我们使用global语句完成这一功能。没有global语句,是不可能为定义在函数外的变量赋值的。eg.? 1 2 3 4 5 6 7 8 9 10 11 12 !/usr/bin/python Filename: func_global.py def func(): global x print'x is', x x = 2 print'Changed local x to', x x = 50 func() print'Value of x is', x 运行的结果是这样的:? 1 2 3 4 $ python func_global.py x is 50 Changed global x to 2 Value of x is 2 # global语句被用来声明x是全局的——因此,当我们在函数内把值赋给x的时候,这个变化也反映在我们在主块中使用x的值的时候。 你可以使用同一个global语句指定多个全局变量。例如global x, y, z。 4.2.with 关键字 有一些任务,可能事先需要设置,事后做清理工作。对于这种场景,Python的with语句提供了一种非常方便的处理方式。一个很好的例子是文件处理,你需要获取一个文件句柄,从文件中读取数据,然后关闭文件句柄。如果不用with语句,打开一个文件并读文件的代码如下:? 1 2 3 file = open("/tmp/foo.txt") data = file.read() file.close() 当然这样直接打开有两个问题:一是可能忘记关闭文件句柄;二是文件读取数据发生异常,没有进行任何处理。下面是添加上异常处理的版本:? 1 2 3 4 5 file = open("/tmp/foo.txt") try: data = file.read() finally: file.close() 虽然这段代码运行良好,但是太冗余了。这时候就是with一展身手的时候了。除了有更优雅的语法,with还可以很好的处理上下文环境产生的异常。下面是with版本的代码:? 1 2 with open("/tmp/foo.txt") as file: data = file.read() 这看起来充满魔法,但不仅仅是魔法,Python对with的处理还很聪明。基本思想是with所求值的对象必须有一个__enter__()方法,一个__exit__()方法。with语句的执行逻辑如下:紧跟with后面的语句被求值后,返回对象的__enter__()方法被调用,这个方法的返回值将被赋值给as后面的变量。当with后面的代码块全部被执行完之后,将调用前面返回对象的__exit__()方法。 下面例子可以具体说明with如何工作:? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 !/usr/bin/python with_example01.py classSample: def __enter__(self): print"In __enter__()" return"Foo" def __exit__(self, type, value, trace): print"In __exit__()" def get_sample(): returnSample() with get_sample() as sample: print"sample:", sample 运行代码,输出如下? 1 2 3 4 $python with_example01.py In __enter__() # __enter__()方法被执行 sample: Foo # __enter__()方法返回的值 - 这个例子中是"Foo",赋值给变量'sample',执行代码块,打印变量"sample"的值为"Foo" In __exit__() # __exit__()方法被调用 4.3.assert 关键字 assert语句是一种插入调试断点到程序的一种便捷的方式。assert语句用来声明某个条件是真的,当assert语句失败的时候,会引发一AssertionError,所以结合try...except我们就可以处理这样的异常。 mylist # 此时mylist是有三个元素的列表['a', 'b', 'c']assert len(mylist) is not None # 用assert判断列表不为空,正确无返回assert len(mylist) is None # 用assert判断列表为空 Traceback (most recent call last): File "", line 1, in AssertionError # 引发AssertionError异常 4.4.yield 关键字 我们先看一个示例:? 1 2 3 4 5 6 7 8 def fab(max): n, a, b = 0,0,1 whilen < max: yield b # print b a, b = b, a + b n = n + 1 ''' 使用这个函数:? 1 2 3 4 5 6 7 8 forn in fab(5): ... print n ... 1 1 2 3 5 简单地讲,yield 的作用就是把一个函数变成一个 generator(生成器),带有 yield 的函数不再是一个普通函数,Python 解释器会将其视为一个 generator,调用 fab(5) 不会执行 fab 函数,而是返回一个 iterable(可迭代的)对象!在 for 循环执行时,每次循环都会执行 fab 函数内部的代码,执行到 yield b 时,fab 函数就返回一个迭代值,下次迭代时,代码从 yield b 的下一条语句继续执行,而函数的本地变量看起来和上次中断执行前是完全一样的,于是函数继续执行,直到再次遇到 yield。也可以手动调用 fab(5) 的 next() 方法(因为 fab(5) 是一个 generator 对象,该对象具有 next() 方法),这样我们就可以更清楚地看到 fab 的执行流程:? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 f = fab(5) f.next() 1 f.next() 1 f.next() 2 f.next() 3 f.next() 5 f.next() Traceback (most recent call last): File"", line 1, in StopIteration 当函数执行结束时,generator 自动抛出 StopIteration 异常,表示迭代完成。在 for 循环里,无需处理 StopIteration 异常,循环会正常结束。 我们可以得出以下结论:一个带有 yield 的函数就是一个 generator,它和普通函数不同,生成一个 generator 看起来像函数调用,但不会执行任何函数代码,直到对其调用 next()(在 for 循环中会自动调用 next())才开始执行。虽然执行流程仍按函数的流程执行,但每执行到一个 yield 语句就会中断,并返回一个迭代值,下次执行时从 yield 的下一个语句继续执行。看起来就好像一个函数在正常执行的过程中被 yield 中断了数次,每次中断都会通过 yield 返回当前的迭代值。 yield 的好处是显而易见的,把一个函数改写为一个 generator 就获得了迭代能力,比起用类的实例保存状态来计算下一个 next() 的值,不仅代码简洁,而且执行流程异常清晰。 注:如果看完此段你还未明白yield,没问题,因为yield是初学者的一个难点,那么你下一步需要做的就是……看一看下面参考资料中给的关于yield的博文! 4.5.exec 关键字 官方文档对于exec的解释: "This statement supports dynamic execution of Python code."也就是说使用exec可以动态执行Python代码(也可以是文件)。? 1 2 3 4 5 6 7 8 9 10 11 12 13 longer = "print "Hello World ,my name is longer"" # 比如说我们定义了一个字符串 longer 'print "Hello World ,my name is longer"' exec(longer) # 使用exec 动态执行字符串中的代码 Hello World ,my name is longer exec(sayhi) # 使用exec直接打开文件名(指定sayhi,sayhi.py以及"sayhi.py"都会报一定的错,但是我觉得直接带sayhi报错非常典型) Traceback (most recent call last): File"", line 1, in TypeError: exec: arg 1must be a string, file, or code object # python IDE报错,提示exec的第一个参 数必须是一个字符串、文件或者一个代码对象 f = file("sayhi.py") # 使用file打开sayhi.py并创建f实例 exec(f) # 使用exec直接运行文件描述符f,运行正常!! Hi,thisis [''] script 上述给的例子比较简单,注意例子中exec语句的用法和eval_r(), execfile()是不一样的. exec是一个关键字(要不然我怎么会在这里介绍呢~~~), 而eval_r()和execfile()则是内建函数。更多关于exec的使用请详看引用资料或者Google之 在需要在字符中使用特殊字符时,python用反斜杠()转义字符。 原始字符串 有时我们并不想让转义字符生效,我们只想显示字符串原来的意思,这就要用r和R来定义原始字符串。如: print r’tr’ 实际输出为“tr”。 转义字符 描述 (在行尾时) 续行符 反斜杠符号 ’ 单引号 ” 双引号 a 响铃 b 退格(Backspace) e 转义 000 空 n 换行 v 纵向制表符 t 横向制表符 r 回车 f 换页 oyy 八进制数yy代表的字符,例如:o12代表换行 xyy 十进制数yy代表的字符,例如:x0a代表换行 other 其它的字符以普通格式输出

xuning715 2019-12-02 01:10:21 0 浏览量 回答数 0
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 云栖号物联网 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 2020阿里巴巴研发效能峰会 企业建站模板 云效成长地图 高端建站 云栖号弹性计算 阿里云云栖号 云栖号案例 云栖号直播