OpenJudge算法设计与分析习题解答

习题11.图论诞生于七桥问题。

出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。

七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图1.7是这条河以及河上的两个岛和七座桥的草图。

请将该问题的数据模型抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。

输入：一个起点 输出：相同的点 1， 一次步行2， 经过七座桥，且每次只经历过一次 3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。

另一类是只有二个奇点的图形。

2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。

请用伪代码描述这个版本的欧几里德算法 1.r=m-n2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。

要求分别给出伪代码和C ++描述。

//采用分治法//对数组先进行快速排序 //在依次比较相邻的差 #include <iostream> using namespace std;int partions(int b[],int low,int high) {图1.7 七桥问题int prvotkey=b[low];b[0]=b[low];while (low<high){while (low<high&&b[high]>=prvotkey)--high;b[low]=b[high];while (low<high&&b[low]<=prvotkey)++low;b[high]=b[low];}b[low]=b[0];return low;}void qsort(int l[],int low,int high){int prvotloc;if(low<high){prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1qsort(l,prvotloc+1,high); //递归调用排序由 prvotloc+1到 high}}void quicksort(int l[],int n){qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个}int main(){int a[11]={0,2,32,43,23,45,36,57,14,27,39};int value=0;//将最小差的值赋值给valuefor (int b=1;b<11;b++)cout<<a[b]<<' ';cout<<endl;quicksort(a,11);for(int i=0;i!=9;++i){if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) )value=a[i+1]-a[i];elsevalue=a[i+2]-a[i+1];}cout<<value<<endl;return 0;}4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。

算法设计与分析第二版课后习题及解答算法设计与分析基础课后练习答案习题1.14.设计一个计算的算法,n是任意正整数。

除了赋值和比较运算,该算法只能用到基本的四则运算操作。

算法求 //输入:一个正整数n2//输出:。

step1:a1; step2:若a*an 转step 3,否则输出a; step3:aa+1转step 2;5. a.用欧几里德算法求gcd(31415,14142)。

b. 用欧几里德算法求gcd(31415,14142),比检查min{m,n}和gcd(m,n)间连续整数的算法快多少倍?请估算一下。

a. gcd31415, 14142 gcd14142, 3131 gcd3131, 1618 gcd1618, 1513 gcd1513, 105 gcd1513, 105 gcd105, 43 gcd43, 19 gcd19, 5 gcd5, 4 gcd4, 1 gcd1, 0 1.b.有a可知计算gcd(31415,14142)欧几里德算法做了11次除法。

连续整数检测算法在14142每次迭代过程中或者做了一次除法,或者两次除法,因此这个算法做除法的次数鉴于1?14142 和 2?14142之间,所以欧几里德算法比此算法快1?14142/11 ≈1300 与2?14142/11 ≈ 2600 倍之间。

6.证明等式gcdm,ngcdn,m mod n对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和rm mod nm-qn;显然,若d能整除n和r,也一定能整除mr+qn和n。

数对m,n和n,r具有相同的公约数的有限非空集,其中也包括了最大公约数。

故gcdm,ngcdn,r7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0mn的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcdm,ngcdn,m并且这种交换处理只发生一次.8.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?1次b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?5次gcd5,8习题1.21.农夫过河P?农夫W?狼 G?山羊 C?白菜2.过桥问题1,2,5,10---分别代表4个人, f?手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c0的实根,写出上述算法的伪代码可以假设sqrtx是求平方根的函数算法Quadratica,b,c//求方程ax^2+bx+c0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D0temp←2*ax1←-b+sqrtD/tempx2←-b-sqrtD/tempreturn x1,x2else if D0 return ?b/2*ael se return “no real roots”else //a0if b≠0 return ?c/belse //ab0if c0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答:a.将十进制整数转换为二进制整数的算法输入:一个正整数n输出:正整数n相应的二进制数第一步:用n除以2,余数赋给Kii0,1,2,商赋给n第二步:如果n0,则到第三步,否则重复第一步第三步:将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBinn//将十进制整数n转换为二进制整数的算法//输入:正整数n//输出:该正整数相应的二进制数,该数存放于数组Bin[1n]中i1while n!0 doBin[i]n%2;nintn/2;i++;while i!0 doprint Bin[i];i--;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.算法略对这个算法做尽可能多的改进.算法 MinDistanceA[0..n-1]//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements 习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.古老的七桥问题第2章习题2.17.对下列断言进行证明:如果是错误的,请举例a. 如果tn∈Ogn,则gn∈Ωtnb.α0时,Θαgn Θgn解:a这个断言是正确的。

算法设计与分析习题解答第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。

若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。

由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。

必要性。

同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。

2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。

由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。

3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。

证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。

4）log(n!)= Θ(nlogn)证明：由于log(n!)=∑=ni i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。

由于对所有的偶数n 有，log(n!)= ∑=ni i 1log ≥∑=nn i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。

openjudge题库答案及解析作为一名程序员，我们时常需要刷LeetCode或者openjudge等算法题库来提升我们的编程能力。

然而，有时候面对一些看似极难的题目，我们可能会感到无从下手。

这时候，有一份题库答案及解析就可以帮助我们更快地理解和解决这些问题。

首先，让我们来了解一下openjudge。

openjudge是清华大学出品的一个在线评测系统，提供了大量的算法、编程题目，帮助学生提升编程能力。

除了编程题目，openjudge还提供了大量的在线课程、测试和编程教程。

如果你是一位大学生，openjudge将是你最好的练习场所。

那么，如何获取openjudge题库的答案及解析呢？其实很简单，我们可以通过搜索引擎或者各类算法社区来查找。

如果你已经解决了某个题目，但是还不是很确定自己的答案是否正确，可以直接搜索这道题目的题名+openjudge，一般就可以找到题目的解答及解析。

许多大神也会在网上写一些关于openjudge的算法题解，如果你想更深入地学习，这些题解也是非常有价值的。

接下来，我想给大家分享一些openjudge题目的答案及解析。

这些题目涵盖了一些基础的算法和数据结构，对于初学者是非常有帮助的。

第一个题目是“递归实现二分查找”。

这道题目比较基础，但是对于初学者来说还是有一定难度的。

我们可以直接通过递归函数来实现二分查找，代码如下：```python# 递归实现二分查找def binary_search(lst, val, l, r):if l > r:return -1mid = (l + r) // 2if lst[mid] == val:return midelif lst[mid] > val:return binary_search(lst, val, l, mid - 1)else:return binary_search(lst, val, mid + 1, r)```在这个递归函数当中，我们需要传入一个列表、要查找的值val、以及列表的左右边界l和r。

算法实现题3-7 数字三角形问题问题描述：给定一个由n行数字组成的数字三角形，如图所示。

试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

编程任务：对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。

数据输入：有文件input.txt提供输入数据。

文件的第1行是数字三角形的行数n，1<=n<=100。

接下来的n行是数字三角形各行的数字。

所有数字在0-99之间。

结果输出：程序运行结束时，将计算结果输出到文件output.txt中。

文件第1行中的数是计算出的最大值。

输入文件示例输出文件示例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5源程序：#include "stdio.h" voidmain(){ intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量in=fopen("input.txt","r");fscanf(in,"%d",&n);//将行数n读入到变量n中for(i=0;i<n;i++)//将各行数值读入到数组triangle中for(j=0;j<=i;j++)fscanf(in,"%d",&triangle[i][j]);for(int row=n-2;row>=0;row--)//从上往下递归计算for(int col=0;col<=row;col++)if(triangle[row+1][col]>triangle[row+1][col+1])triangle[row][col]+=triangle[row+1][col];elsetriangle[row][col]+=triangle[row+1][col+1];out=fopen("output.txt","w");fprintf(out,"%d",triangle[0][0]);//将最终结果输出到output.txt中 }算法实现题4-9 汽车加油问题问题描述：一辆汽车加满油后可行驶nkm。

Openjudge幼儿园足球题解析介绍幼儿园足球题是一个针对幼儿园学生的足球问题，主要考察幼儿对基本足球规则和运动技能的理解。

通过这道题目的分析和解析，我们将帮助幼儿更好地理解足球，并提高他们的足球技巧。

题目描述这题目要求幼儿假设自己是一个足球裁判，在比赛过程中需要判断球场上发生的事件，包括球是否出界、球是否进门等。

题目分析1.首先，幼儿需要明确足球比赛的规则，包括球场的尺寸、球的大小、比赛时间等。

2.幼儿需要了解什么情况下球算出界，例如球完全越过界线即算出界。

3.幼儿需要了解什么情况下球算进门，例如球完全越过门线即算进门。

4.幼儿需要学会观察判断球是否出界或进门，例如看球是否完全越过界线或门线。

解题思路1.首先，幼儿需要明确足球比赛的规则。

他们可以通过观看足球比赛、与教练或其他儿童讨论来获得这些知识。

2.幼儿需要学会观察判断球是否出界或进门。

他们可以通过观察标志着界线或门线的边界，以及球是否完全越过这些线来判断球的状态。

3.对于判断球是否出界，幼儿可以注意以下几点：–观察球是否完全越过边界线，而不是仅仅挨着边界线滚动。

–观察球是否碰到了横杆或立柱，如果球完全越过边界线但碰到了横杆或立柱，也算出界。

4.对于判断球是否进门，幼儿可以注意以下几点：–观察球是否完全越过门线，并且进入了球门内部。

–观察球是否从门的上方进入，如果球越过门线但是从门的上方进入，是不算进门的。

5.幼儿应该提醒他们自己保持专注，仔细观察比赛过程中的细节。

心得体会通过这道题目，幼儿可以加深对足球规则和技巧的理解。

同时，他们也可以培养他们观察力和判断力，提高他们在比赛中作为裁判的能力。

此外，幼儿还可以通过练习判断球是否出界和进门，来提高他们的反应速度和足球技巧。

结论幼儿园足球题目是一个帮助幼儿理解足球规则和提高判断力的练习题。

通过观察和判断，幼儿可以学会区分球是否出界和进门。

这道题目不仅可以提高幼儿的足球技巧，还可以培养他们的观察力和判断力。

习题5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d 能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次..对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.(农夫过河)P—农夫 W—狼 G—山羊 C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBin(n).n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法 MinDistance(A[0..n-1])n-1]a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序)hints:a. Replace the ith element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element., 0 for an array of positive numbers ) to mark the ith position is empty. (“lazy deletion”)习题1欧几里得算法的时间复杂度欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式gcd(a, b) = gcd(b, a mod b)其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b的余数. 算法如下:输入: 两个整数a, b输出: a和b的最大公约数function gcd(a, b:integer):integer;if b=0 return a;else return gcd(b, a mod b);end function欧几里得算法是最古老而经典的算法, 理解和掌握这一算法并不难, 但要分析它的时间复杂度却并不容易. 我们先不考虑模运算本身的时间复杂度(算术运算的时间复杂度在Knuth的TAOCP中有详细的讨论), 我们只考虑这样的问题: 欧几里得算法在最坏情况下所需的模运算次数和输入的a和b的大小有怎样的关系?我们不妨设a>b>=1(若a<b我们只需多做一次模运算, 若b=0或a=b模运算的次数分别为0和1), 构造数列{un}: u0=a, u1=b, uk=uk-2 mod uk-1(k>=2), 显然, 若算法需要n次模运算, 则有un=gcd(a, b), un+1=0. 我们比较数列{un}和菲波那契数列{Fn}, F0=1<=un, F1=1<=un-1, 又因为由uk mod uk+1=uk+2, 可得uk>=uk+1+uk+2, 由数学归纳法容易得到uk>=Fn-k, 于是得到a=u0>=Fn, b=u0>=Fn-1. 也就是说如果欧几里得算法需要做n次模运算, 则b必定不小于Fn-1. 换句话说, 若 b<Fn-1, 则算法所需模运算的次数必定小于n. 根据菲波那契数列的性质, 有Fn-1>n/sqrt(5), 即b>n/sqrt(5), 所以模运算的次数为O(lgb)---以b为底数 = O(lg(2)b)---以2为底数，输入规模也可以看作是b的bit位数。

习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理"该算法在处理这种输入的过程中,上述情况最多会发生几次"Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法"(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法"(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗"c.该算法在位吗"解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序)hints:a. Replace the ith element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element(e.g., 0 for an array of positive numbers ) to mark the ith position is empty. (“lazy deletion”)习题2.11欧几里得算法的时间复杂度欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式gcd(a, b) = gcd(b, a mod b)其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b的余数. 算法如下:输入: 两个整数a, b输出: a和b的最大公约数function gcd(a, b:integer):integer;if b=0 return a;else return gcd(b, a mod b);end function欧几里得算法是最古老而经典的算法, 理解和掌握这一算法并不难, 但要分析它的时间复杂度却并不容易. 我们先不考虑模运算本身的时间复杂度(算术运算的时间复杂度在Knuth的TAOCP中有详细的讨论), 我们只考虑这样的问题: 欧几里得算法在最坏情况下所需的模运算次数和输入的a 和b 的大小有怎样的关系"我们不妨设a>b>=1(若a<b 我们只需多做一次模运算, 若b=0或a=b 模运算的次数分别为0和1), 构造数列{un}: u0=a, u1=b, uk=uk-2 mod uk-1(k>=2), 显然, 若算法需要n 次模运算, 则有un=gcd(a, b), un+1=0. 我们比较数列{un}和菲波那契数列{Fn}, F0=1<=un, F1=1<=un-1, 又因为由uk mod uk+1=uk+2, 可得uk>=uk+1+uk+2, 由数学归纳法容易得到uk>=Fn-k, 于是得到a=u0>=Fn, b=u0>=Fn-1. 也就是说如果欧几里得算法需要做n 次模运算, 则b 必定不小于Fn-1. 换句话说, 若 b<Fn-1, 则算法所需模运算的次数必定小于n. 根据菲波那契数列的性质, 有Fn-1>(1.618)n/sqrt(5), 即b>(1.618)n/sqrt(5), 所以模运算的次数为O(lgb)---以b 为底数 = O(lg(2)b)---以2为底数，输入规模也可以看作是b 的bit 位数。

Openjudge-NOI题库-和数题⽬描述 Description给定⼀个正整数序列，判断其中有多少个数，等于数列中其他两个数的和。

⽐如，对于数列1 2 3 4, 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。

输⼊输出格式 Input/output输⼊：共两⾏，第⼀⾏是数列中数的个数n ( 1 <= n <= 100)，第⼆⾏是由n个不⼤于10000的正整数组成的数列，相邻两个整数之间⽤单个空格隔开。

输出：⼀个整数，即数列中等于其他两个数之和的数的个数。

输⼊输出样例 Sample input/output样例测试点#1输⼊样例：241 2 3 453 5 7 9 10输出样例：21思路：可以先将这个数组中所有两个数相加的和存⼊另⼀个数组（两重循环即可），然后再扫描⼀遍这个数组同相加的和的数组⽐较，如果相同则答案++代码如下：1 #include <stdio.h>2int main()3 {4int n,i,j;5int a;6int kk=0;7int aa[102],bb[99999];8int ans=0;9 scanf("%d",&n);10while(n>0)11 {12 scanf("%d",&a);13for(i=0;i<a;i++)14 {15 scanf("%d",&aa[i]);16 }17/*=======================*///将这个数组中的每两个数和全部存⼊bb中18for(i=0;i<a;i++)19 {20for(j=i+1;j<a;j++)21 {22 bb[kk]=aa[i]+aa[j];23 kk++;24 }25 }26/*=======================*///循环判断两个数和的数组中是否有和元素组⼀样的27for(i=0;i<kk;i++)28 {29for(j=0;j<a;j++)30 {31if(bb[i]==aa[j]) ans++;//有，ans++32 }33 }34 printf("%d\n",ans);35 ans=0;//答案归零36 kk=0;//循环变量归零37 n--;//循环条件控制38 }39return0;40 }。