什么是算法?
算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
用数学量描述问题
计算机处理的是数学量。若要用计算机解决实际问题，需要把实际问题抽象为数学量，或者数字。比如，记事本把文字按 ASCII 码表转换为数字储存起来，极品飞车把赛车的性能表示为数字，来权衡赛车的好坏。一个漂亮的算法，需要用数学量表示出来。
任务：现有两个软件工程的制作任务，你的团队可以接手其中任意一个。现要在两个中选择一个，需要考虑制作成本，制作成功的可能性，可获得经济收益的多少，对你的团队知名度的影响等等因素。你如何量化地分析和解决这个问题?
提示：需要把每一项都转化为数值，必要时加入权值、计算期望。如果只考虑以上四个因素，可以得到以下数学式：
综合收益=制作成功的概率*[(可获得经济收益-制作成本)*经济效益的权值+团队知名度的影响*社会效益的权值]。
其中概率和两个权值是需要估计的值。
用图形描述问题
有时，我们需要用更直观的图形来描述实际问题。图论就是一个绝佳的方法。图是一种表示离散量间关系的形式，它也是一种思想，常被用于建模。同时，前人也为我们提供了很多现成的图论算法，能够解决很多常见问题，这些将在之后被提到。矩阵也是一种常见的方法。有时矩阵被表示成三角形的形式，比如“杨辉三角”。矩阵常常和数学有关，在计算机计算时常常利用矩阵的递推式。
模拟计算过程
模拟方法是最常见、最直接的算法构建方法。
任务：编程实现欧几里得算法（辗转相除法，求两个数的最大公约数 gcd(a,b)）
提示：欧几里得算法原理：gcd(a,b)=gcd(b,a mod b)，其图形描述如下：
1. 写下两个数
2. 将两数相除，余数写在较大的数下面
3. 将每列最下面的数相除，余数写在被除数下面
4. 重复步骤3直至整除，此时最后写下的余数即为开始时两数的最大公约数
这是一个简单的模拟算法，实际过程中，量间的关系往往比这复杂得多，因而，模拟算法可以是很复杂的。有些模拟算法还涉及到图形和其他复杂的数据结构，这需要我们熟练地运用语言，巧妙地把其他关系转化为数学量间关系。
模拟时的优化
如果处理不当，模拟方法写出的程序会非常长。这要求我们在模拟是将相似的步骤合为一体，适时利用函数简化程序。
以上面的欧几里得算法为例:
这个实例主要体现模拟算法的简化过程。虽然在这样小的程序段中，这样的简化作用不大，但遇到复杂的模拟问题，这种利用相似性的简化便非常有用了。应当重视这样的代码优化。
高精度计算算法
由于计算机运算是有模运算，数据范围的表示有一定限制，如整型int(C++中int 与long相同)表达范围是(-2^31~2^31-1)，unsigned long(无符号整数)是(0~2^32-1)，都约为几十亿。如果采用实数型，则能保存最大的double只能提供15~16位的有效数字，即只能精确表达数百万亿的数。因此，在计算位数超过十几位的数时，不能采用现有类型，只能自己编程计算。
高精度计算通用方法：高精度计算时一般用一个数组来存储一个数，数组的一个元素对应于数的一位（为了加快计算速度，也可用数组的一个元素表示数的多位数字），表示时，由于数计算时可能要进位，因此为了方便，将数由低位到高位依次存在数组下标对应由低到高位置上，另外，我们申请数组大小时，一般考虑了最大的情况，在很多情况下，表示有富余，即高位有很多0，可能造成无效的运算和判断，因此，我们一般将数组的第0个下标对应位置来存储该数的位数。
如数：3485(三千四百八十五)，表达在数组a[10]上情况是：
具体在计算加减乘除时方法就是小学时采用的列竖式方法。
注：高精度计算时一般用正数，对于负数，通过处理符号位的修正。
高精度数的存储
1.如对数采用的字符串输入
#include <iostream>
#include <cstring>
using namespace std;
const int N=100;//最多100位
int main()
{
int a[N+1],i;
string s1;
cin>>s1;//数s1
memset(a,0,sizeof(a)); //数组清0
a[0]=s1.length(); //位数
for(i=1;i<=a[0];i++) a[i]=s1[a[0]-i]-‘0’;//将字符转为数字并倒序存储
return 0;
}
2. 直接读入
#include <iostream>
using namespace std;
const int N=100;//最多100位
int main()
{
int a[N+1],i,s,key;
cin>>key;//数key
memset(a,0,sizeof(a)); //数组清0
i=0;//第0位
while(key) //当key大于0
{
a[++i]=key%10;//取第i位的数
key=key/10;
}
a[0]=i; //共i位数
return 0;
}
3.直接初始化(用a[]存储)
初始化为0: memset(a,0,sizeof(a));
初始化为1: memset(a,0,sizeof(a));a[0]=1;a[1]=1;
(以下程序都只写函数，不写完整程序，所有高精度数存储都满足上述约定。)
高精度数比较
int compare(int a[],int b[]) //比较a和b的大小关系，若a>b则为1，a<b则为-1,a=b则为0
{int i;
if (a[0]>b[0]) return 1;//a的位数大于b则a比b大
if (a[0]<b[0]) return -1;//a的位数小于b则a比b小
for(i=a[0];i>0;i–) //从高位到低位比较
{if (a[i]>b[i])return 1;
if(a[i]<b[i]) return -1;}
return 0;//各位都相等则两数相等
}
高精度加法
int plus(int a[],int b[]) //计算a=a+b
{int i,k;
k=a[0]>b[0]?a[0]:b[0]; //k是a和b中位数最大的一个的位数
for(i=1;i<=k;i++)
{a[i+1]+=(a[i]+b[i])/10; //若有进位，则先进位
a[i]=(a[i]+b[i])%10;} //计算当前位数字,注意：这条语句与上一条不能交换
if(a[k+1]>0) a[0]=k+1; //修正新的a的位数（a+b最多只能的一个进位）
elsea[0]=k;
return 0;
}
高精度减法
int gminus(int a[],int b[]);//计算a=a-b，返加符号位0:正数 1:负数
{ int flag,i
flag=compare(a,b); //调用比较函数判断大小
if (falg==0)//相等
{memset(a,0,sizeof(a));return0;} //若a=b，则a=0,也可在return前加一句a[0]=1,表示是 1位数0
if(flag==1) //大于
{ for(i=1;i<=a[0];i++)
{ if(a[i]<b[i]){a[i+1]–;a[i]+=10;} //若不够减则向上借一位
a[i]=a[i]-b[i];}
while(a[a[0]]==0)a[0]–; //修正a的位数
return 0;}
if (flag==-1)//小于 则用a=b-a,返回-1
{for(i=1;i<=b[0];i++)
{ if(b[i]<a[i]){b[i+1]–;b[i]+=10;} //若不够减则向上借一位
a[i]=b[i]-a[i];}
a[0]=b[0];
while(a[a[0]]==0)a[0]–; //修正a的位数
return -1;}
}
高精度乘法(高精度乘单精度数，单精度数是指通常的整型数)
int multi1(int a[],long key)//a=a*key,key是单精度数
{int i,k;
if (key==0){memset(a,0,sizeof(a));a[0]=1;return0;} //单独处理key=0
for(i=1;i<=a[0];i++)a[i]=a[i]*key;//先每位乘起来
for(i=1;i<=a[0];i++){a[i+1]+=a[i]/10;a[i]%=10;}//进位
//注意上一语句退出时i=a[0]+1
while(a[i]>0){a[i+1]=a[i]/10;a[i]=a[i]%10;i++;a[0]++];} //继续处理超过原a[0]位数的进位,修正a的位数
return 0;
}
支付宝扫一扫
