"算法设计与分析基础知识点"
**算法设计与分析基础**
算法设计与分析是计算机科学的核心内容之一，涉及到解决问题的方法和步骤。下面是对算法设计与分析基础的知识点总结：
**gcd(m,n)=gcd(n,mmodn)**
gcd(m,n)函数是计算两个正整数m和n的最大公约数的函数。根据除法的定义，不难证明：如果d整除u和v，那么d一定能整除u±v；如果d整除u，那么d也能够整除u的任何整数倍ku。因此，对于任意一对正整数m和n，若d能整除m和n，那么d一定能整除n和r=mmodn=m-qn。显然，若d能整除n和r，也一定能整除m=r+qn和n。数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)。
**欧几里得算法**
欧几里得算法是计算两个正整数的最大公约数的一种方法。对于任何形如0<=m<n的一对数字，Euclid算法在第一次叠代时交换m和n，即gcd(m,n)=gcd(n,m)。并且这种交换处理只发生一次。在处理这种输入的过程中，Euclid算法最多会发生一次交换处理。
**欧几里得算法的时间复杂度**
对于所有1≤m,n≤10的输入，Euclid算法最少要做1次除法，最大要做5次除法。
**二次方程的解**
对于任意实系数a,b,c，某个算法能求方程ax^2+bx+c=0的实根。该算法可以写成伪代码：
```
算法Quadratic(a,b,c)
//求方程ax^2+bx+c=0的实根的算法
//输入:实系数a,b,c
//输出:实根或者无解信息
If a≠0
D←b*b-4*a*c
If D>0
temp←2*a
x1←(-b+sqrt(D))/temp
x2←(-b-sqrt(D))/temp
return x1, x2
elseif D=0
return –b/(2*a)
else
return “norealroots”
else //a=0
if b≠0
return –c/b
else //a=b=0
if c=0
return “norealnumbers”
else
return “norealroots”
```
**十进制整数到二进制整数的转换**
将十进制整数转换为二进制整数的算法可以用文字描述和伪代码描述：
文字描述：将十进制整数转换为二进制整数的算法可以通过除法和取余数的方式实现。具体来说，对于一个十进制整数n，可以通过不断除以2并取余数来获得二进制表示。
伪代码描述：
```
算法 DecimalToBinary(n)
//将十进制整数n转换为二进制整数
//输入:十进制整数n
//输出:二进制整数
binary←“”
while n>0
binary←str(n mod 2) + binary
n←n div 2
return binary
```
这些知识点涵盖了算法设计与分析的基础知识，包括gcd函数、欧几里得算法、二次方程的解和十进制整数到二进制整数的转换等。
我的内容管理
展开
