编程的50种基础算法(编程零基础该怎么学)
大家好，今天给各位分享编程的50种基础算法的一些知识，其中也会对编程零基础该怎么学进行解释，文章篇幅可能偏长，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在就马上开始吧！
编程的5种基础算法
1、递归算法：在程序中不断反复调用自身来达到求解问题的方法。递归算法代码简洁、可读型号，但是并没有减少代码规模好节省内存空间。
2、快速排序算法：快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来。
3、二分查找算法：二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
4、递推算法：是一种理性思维的代表，根据已有的数据和关系，逐步推导而得到结果。根据已知结果和关系，求解中间结果，判断是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果；如果达到要求，则表示找到了一个正确的结果。
5、分治算法：将一个计算复杂的问题分为规模较小、计算简单的小问题求解，然后综合各个小问题，得到最终问题答案。确定一个规模为n的难解决问题难以直接解决。将该问题分解为m个规模较小的子问题a，a们之间相互独立，与原问题形式相同。递归地解决这些小问题，即一个一个解决。然后，将各子问题的解合并到原问题的解。
算法怎么学
贪心算法的定义：
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
解题的一般步骤是：
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的局部最优解合成原来问题的一个解。
如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。
话不多说，我们来看几个具体的例子慢慢理解它：
1.活动选择问题
这是《算法导论》上的例子，也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。
考虑使用贪心算法的解法。为了方便，我们用不同颜色的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝色的线条表示我们已经选择的活动；红色的线条表示我们没有选择的活动。如果我们每次都选择开始时间最早的活动，不能得到最优解：
如果我们每次都选择持续时间最短的活动，不能得到最优解：
可以用数学归纳法证明，我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int N;
struct Act
{
int start;
int end;
}act[100010];
bool cmp(Act a,Act b)
{
return a.end<b.end;
}
int greedy_activity_selector()
{
int num=1,i=1;
for(int j=2;j<=N;j++)
{
if(act[j].start>=act[i].end)
{
i=j;
2.钱币找零问题
这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。
}
3.再论背包问题
从零开始学动态规划
中我们已经谈过三种最基本的背包问题：零一背包，部分背包，完全背包。很容易证明，背包问题不能使用贪心算法。然而我们考虑这样一种背包问题：在选择物品i装入背包时，可以选择物品的一部分，而不一定要全部装入背包。这时便可以使用贪心算法求解了。计算每种物品的单位重量价值作为贪心选择的依据指标，选择单位重量价值最高的物品，将尽可能多的该物品装入背包，依此策略一直地进行下去，直到背包装满为止。在零一背包问题中贪心选择之所以不能得到最优解原因是贪心选择无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。在程序中已经事先将单位重量价值按照从大到小的顺序排好。
}
4.多机调度问题 n个作业组成的作业集，可由m台相同机器加工处理。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。作业不能拆分成更小的子作业；每个作业均可在任何一台机器上加工处理。这个问题是NP完全问题，还没有有效的解法(求最优解)，但是可以用贪心选择策略设计出较好的近似算法(求次优解)。当n<=m时，只要将作业时间区间分配给作业即可；当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为止。如果我们每次是将需要处理时间最短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况，这样势必效率较低。在下面的代码中没有讨论n和m的大小关系，把这两种情况合二为一了。
5.小船过河问题 POJ1700是一道经典的贪心算法例题。题目大意是只有一艘船，能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，问把n个人运到对岸，最少需要多久。先将所有人过河所需的时间按照升序排序，我们考虑把单独过河所需要时间最多的两个旅行者送到对岸去，有两种方式： 1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，所需时间为：t[0]+2*t[1]+t[n-1]； 2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来，所需时间为：2*t[0]+t[n-2]+t[n-1]。算一下就知道，除此之外的其它情况用的时间一定更多。每次都运送耗时最长的两人而不影响其它人，问题具有贪心子结构的性质。 AC代码：
}
6.区间覆盖问题 POJ1328是一道经典的贪心算法例题。题目大意是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。对于每个小岛，我们可以计算出一个雷达所在位置的区间。
问题转化为如何用尽可能少的点覆盖这些区间。先将所有区间按照左端点大小排序，初始时需要一个点。如果两个区间相交而不重合，我们什么都不需要做；如果一个区间完全包含于另外一个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。 AC代码：
//按区间左端点排序
double s=point[0].y;
//区间右端点
for(int i=1;i<n;i++)
{
if(point[i].x>s)
//如果两个区间没有重合,增加雷达数目并更新右端点
{
counting++;
s=point[i].y;
}
else if(point[i].y<s)
//如果第二个区间被完全包含于第一个区间,更新右端点
{
s=point[i].y;
}
}
}
cout<<"Case"<<num<<':'<<''<<counting<<endl;
num++;
}
}
7.销售比赛在学校OJ上做的一道比较好的题，这里码一下。假设有偶数天，要求每天必须买一件物品或者卖一件物品，只能选择一种操作并且不能不选，开始手上没有这种物品。现在给你每天的物品价格表，要求计算最大收益。首先要明白，第一天必须买，最后一天必须卖，并且最后手上没有物品。那么除了第一天和最后一天之外我们每次取两天，小的买大的卖，并且把卖的价格放进一个最小堆。如果买的价格比堆顶还大，就交换。这样我们保证了卖的价格总是大于买的价格，一定能取得最大收益。
#include<queue>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long int price[100010],t,n,res;
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
cin>>n;
priority_queue<long long int, vector<long long int>, greater<long long int>> q;
res=0;
for(int i=1;i<=n;i++)
{
cin>>price[i];
}
res-=price[1];
res+=price[n];
for(int i=2;i<=n-1;i=i+2)
{
long long int buy=min(price[i],price[i+1]);
long long int sell=max(price[i],price[i+1]);
if(!q.empty())
{
if(buy>q.top())
{
res=res-2*q.top()+buy+sell;
q.pop();
q.push(buy);
q.push(sell);
}
else
{
res=res-buy+sell;
q.push(sell);
}
}
else
{
res=res-buy+sell;
q.push(sell);
}
}
cout<<res<<endl;
}
}
下面我们结合数据结构中的知识讲解几个例子。 8.Huffman编码这同样是《算法导论》上的例子。Huffman编码是广泛用于数据文件压缩的十分有效的编码方法。我们可以有多种方式表示文件中的信息，如果用01串表示字符，采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300000位；采用变长编码表示，给频率高的字符较短的编码，频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000位，由此可见，变长码比定长码方案好，总码长减小约25%。
对每一个字符规定一个01串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀，这种编码称为前缀码。可能无前缀码是一个更好的名字，但是前缀码是一致认可的标准术语。编码的前缀性质可以使译码非常简单：例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。译码过程需要方便的取出编码的前缀，为此可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的路标。
从上图可以看出，最优前缀编码码的二叉树总是一棵完全二叉树，而定长编码的二叉树不是一棵完全二叉树。给定编码字符集C及频率分布f，C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为dT(c)，dT(c)也是字符c的前缀码长。则平均码长定义为：
使平均码长达到最小的前缀码编码方案称为C的最优前缀码。 Huffman编码的构造方法：先合并最小频率的2个字符对应的子树，计算合并后的子树的频率；重新排序各个子树；对上述排序后的子树序列进行合并；重复上述过程，将全部结点合并成1棵完整的二叉树；对二叉树中的边赋予0、1，得到各字符的变长编码。
POJ3253一道就是利用这一思想的典型例题。题目大意是有把一块无限长的木板锯成几块给定长度的小木板，每次锯都需要一定费用，费用就是当前锯的木板的长度。给定各个要求的小木板的长度以及小木板的个数，求最小的费用。以要求3块长度分别为5,8,5的木板为例：先从无限长的木板上锯下长度为21的木板，花费21；再从长度为21的木板上锯下长度为5的木板，花费5；再从长度为16的木板上锯下长度为8的木板，花费8；总花费=21+5+8=34。利用Huffman思想，要使总费用最小，那么每次只选取最小长度的两块木板相加，再把这些和累加到总费用中即可。为了提高效率，使用优先队列优化，并且还要注意使用long long int保存结果。 AC代码：
#include<queue>
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
long long int sum;
int i,n,t,a,b;
while(~scanf("%d",&n))
{
priority_queue<int,vector<int>,greater<int>>q;
for(i=0;i<n;i++)
{
scanf("%d",&t);
q.push(t);
}
sum=0;
if(q.size()==1)
{
a=q.top();
sum+=a;
q.pop();
}
while(q.size()>1)
{
a=q.top();
q.pop();
b=q.top();
q.pop();
t=a+b;
sum+=t;
q.push(t);
}
printf("%lld
",sum);
}
}
9.Dijkstra算法 Dijkstra算法是由E.W.Dijkstra于1959年提出，是目前公认的最好的求解最短路径的方法，使用的条件是图中不能存在负边。算法解决的是单个源点到其他顶点的最短路径问题，其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点，简单的说就是bfs+贪心算法的思想。
#include<iostream>
#include<algorithm>
#define INF 1000
#define MAX_V 100
using namespace std;
int main()
{
int V,E;
int i,j,m,n;
int cost[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
cin>>V>>E;
fill(d,d+V+1,INF);
fill(used,used+V,false);
for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
{
if(i==j) cost[i][j]=0;
else cost[i][j]=INF;
}
}
for(m=0;m<E;m++)
{
cin>>i>>j>>cost[i][j];
cost[j][i]=cost[i][j];
}
cin>>n;
d[n]=0;
//源点
while(true)
{
int v=V;
for(m=0;m<V;m++)
{
if((!used[m])&&(d[m]<d[v])) v=m;
}
if(v==V) break;
used[v]=true;
for(m=0;m<V;m++)
{
d[m]=min(d[m],d[v]+cost[v][m]);
}
}
for(i=0;i<V;i++)
{
cout<<"the shortest distance between"<<n<<" and"<<i<<" is"<<d[i]<<endl;
}
}
10.最小生成树算法
设一个网络表示为无向连通带权图G=(V, E), E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树的代价是指生成树上各边权的总和，在G的所有生成树中，耗费最小的生成树称为G的最小生成树。例如在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，最小生成树给出建立通信网络的最经济方案。
构造最小生成树的Kruskal算法和Prim算法都利用了MST(最小生成树)性质：设顶点集U是V的真子集(可以任意选取)，如果(u,v)∈E为横跨点集U和V—U的边，即u∈U，v∈V- U，并且在所有这样的边中，(u,v)的权c[u][v]最小，则一定存在G的一棵最小生成树，它以(u,v)为其中一条边。
使用反证法可以很简单的证明此性质。假设对G的任意一个最小生成树T，针对点集U和V—U，(u,v)∈E为横跨这2个点集的最小权边，T不包含该最小权边<u, v>，但T包括节点u和v。将<u,v>添加到树T中，树T将变为含回路的子图，并且该回路上有一条不同于<u,v>的边<u’,v’>,u’∈U,v’∈V-U。将<u’,v’>删去，得到另一个树T’，即树T’是通过将T中的边<u’,v’>替换为<u,v>得到的。由于这2条边的耗费满足c[u][v]≤c[u’][v’]，故即T’耗费≤T的耗费，这与T是任意最小生成树的假设相矛盾，从而得证。
Prim算法每一步都选择连接U和V-U的权值最小的边加入生成树。
#include<iostream>
#include<algorithm>
#define MAX_V 100
#define INF 1000
using namespace std;
int main()
{
int V,E;
int i,j,m,n;
int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];
cin>>V>>E;
fill(mincost,mincost+V+1,INF);
fill(used,used+V,false);
for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
{
if(i==j) cost[i][j]=0;
else cost[i][j]=INF;
}
}
for(m=0;m<E;m++)
{
cin>>i>>j>>cost[i][j];
cost[j][i]=cost[i][j];
}
mincost[0]=0;
int res=0;
while(true)
{
int v=V;
for(m=0;m<V;m++)
{
if((!used[m])&&(mincost[m]<mincost[v]))
v=m;
}
if(v==V) break;
used[v]=true;
res+=mincost[v];
for(m=0;m<V;m++)
{
mincost[m]=min(mincost[m],cost[v][m]);
}
}
cout<<res<<endl;
} Kruskal算法每一步直接将权值最小的不成环的边加入生成树，我们借助并查集这一数据结构可以完美实现它。
关于贪心算法的基础知识就简要介绍到这里，希望能作为大家继续深入学习的基础。
圆周率的计算方法是什么有多少种计算方法
实验对π值进行估算，这是计算π的的第一阶段。这种对π值的估算基本上都是以观察或实验为根据，是基于对一个圆的周长和直径的实际测量而得出的。在古代世界，实际上长期使用π＝3这个数值。最早见于文字记载的有基督教《圣经》中的章节，其上取圆周率为3。这一段描述的事大约发生在公元前950年前后。其他如巴比伦、印度、中国等也长期使用3这个粗略而简单实用的数值。在我国刘徽之前“圆径一而周三”曾广泛流传。我国第一部《周髀算经》中，就记载有圆“周三径一”这一结论。在我国，木工师傅有两句从古流传下来的口诀：叫做：“周三径一，方五斜七”，意思是说，直径为1的圆，周长大约是3，边长为5的正方形，对角线之长约为7。这正反映了早期人们对圆周率π和√2这两个无理数的粗略估计。东汉时期官方还明文规定圆周率取3为计算面积的标准。后人称之为“古率”。
早期的人们还使用了其它的粗糙方法。如古埃及、古希腊人曾用谷粒摆在圆形上，以数粒数与方形对比的方法取得数值。或用匀重木板锯成圆形和方形以秤量对比取值……由此，得到圆周率的稍好些的值。如古埃及人应用了约四千年的 4(8/9)2= 3.1605。在印度，公元前六世纪，曾取π=√10= 3.162。在我国东、西汉之交，新朝王莽令刘歆制造量的容器――律嘉量斛。刘歆在制造标准容器的过程中就需要用到圆周率的值。为此，他大约也是通过做实验，得到一些关于圆周率的并不划一的近似值。现在根据铭文推算，其计算值分别取为3.1547，3.1992，3.1498，3.2031比径一周三的古率已有所进步。人类的这种探索的结果，当主要估计圆田面积时，对生产没有太大影响，但以此来制造器皿或其它计算就不合适了。
几何法时期
凭直观推测或实物度量，来计算π值的实验方法所得到的结果是相当粗略的。
真正使圆周率计算建立在科学的基础上，首先应归功于阿基米德。他是科学地研究这一常数的第一个人，是他首先提出了一种能够借助数学过程而不是通过测量的、能够把π的值精确到任意精度的方法。由此，开创了圆周率计算的第二阶段。
圆周长大于内接正四边形而小于外切正四边形，因此 2√2＜π＜ 4。
当然，这是一个差劲透顶的例子。据说阿基米德用到了正96边形才算出他的值域。
阿基米德求圆周率的更精确近似值的方法，体现在他的一篇论文《圆的测定》之中。在这一书中，阿基米德第一次创用上、下界来确定π的近似值，他用几何方法证明了“圆周长与圆直径之比小于 3+(1/7)而大于 3+(10/71)”，他还提供了误差的估计。重要的是，这种方法从理论上而言，能够求得圆周率的更准确的值。到公元150年左右，希腊天文学家托勒密得出π＝3.1416，取得了自阿基米德以来的巨大进步。
割圆术。不断地利用勾股定理，来计算正N边形的边长。
在我国，首先是由数学家刘徽得出较精确的圆周率。公元263年前后，刘徽提出著名的割圆术，得出π＝3.14，通常称为“徽率”，他指出这是不足近似值。虽然他提出割圆术的时间比阿基米德晚一些，但其方法确有着较阿基米德方法更美妙之处。割圆术仅用内接正多边形就确定出了圆周率的上、下界，比阿基米德用内接同时又用外切正多边形简捷得多。另外，有人认为在割圆术中刘徽提供了一种绝妙的精加工办法，以致于他将割到192边形的几个粗糙的近似值通过简单的加权平均，竟然获得具有4位有效数字的圆周率π＝3927/1250＝3.1416。而这一结果，正如刘徽本人指出的，如果通过割圆计算得出这个结果，需要割到3072边形。这种精加工方法的效果是奇妙的。这一神奇的精加工技术是割圆术中最为精彩的部分，令人遗憾的是，由于人们对它缺乏理解而被长期埋没了。
恐怕大家更加熟悉的是祖冲之所做出的贡献吧。对此，《隋书·律历志》有如下记载：“宋末，南徐州从事祖冲之更开密法。以圆径一亿为丈，圆周盈数三丈一尺四寸一分五厘九毫二秒七忽，朒数三丈一尺四寸一分五厘九毫二秒六忽，正数在盈朒二限之间。密率：圆径一百一十三，圆周三百五十五。约率，圆径七，周二十二。”
这一记录指出，祖冲之关于圆周率的两大贡献。其一是求得圆周率
3.1415926＜π＜ 3.1415927
其二是，得到π的两个近似分数即：约率为22／7；密率为355／113。
他算出的π的8位可靠数字，不但在当时是最精密的圆周率，而且保持世界记录九百多年。以致于有数学史家提议将这一结果命名为“祖率”。
这一结果是如何获得的呢？追根溯源，正是基于对刘徽割圆术的继承与发展，祖冲之才能得到这一非凡的成果。因而当我们称颂祖冲之的功绩时，不要忘记他的成就的取得是因为他站在数学伟人刘徽的肩膀上的缘故。后人曾推算若要单纯地通过计算圆内接多边形边长的话，得到这一结果，需要算到圆内接正12288边形，才能得到这样精确度的值。祖冲之是否还使用了其它的巧妙办法来简化计算呢？这已经不得而知，因为记载其研究成果的著作《缀术》早已失传了。这在中国数学发展史上是一件极令人痛惜的事。
中国发行的祖冲之纪念邮票
祖冲之的这一研究成果享有世界声誉：巴黎“发现宫”科学博物馆的墙壁上著文介绍了祖冲之求得的圆周率，莫斯科大学礼堂的走廊上镶嵌有祖冲之的大理石塑像，月球上有以祖冲之命名的环形山……
对于祖冲之的关于圆周率的第二点贡献，即他选用两个简单的分数尤其是用密率来近似地表示π这一点，通常人们不会太注意。然而，实际上，后者在数学上有更重要的意义。
密率与π的近似程度很好，但形式上却很简单，并且很优美，只用到了数字1、3、5。数学史家梁宗巨教授验证出：分母小于16604的一切分数中，没有比密率更接近π的分数。在国外，祖冲之死后一千多年，西方人才获得这一结果。
可见，密率的提出是一件很不简单的事情。人们自然要追究他是采用什么办法得到这一结果的呢？他是用什么办法把圆周率从小数表示的近似值化为近似分数的呢？这一问题历来为数学史家所关注。由于文献的失传，祖冲之的求法已不为人知。后人对此进行了各种猜测。
让我们先看看国外历史上的工作，希望能够提供出一些信息。
1573年，德国人奥托得出这一结果。他是用阿基米德成果22／7与托勒密的结果377／120用类似于加成法“合成”的：(377-22)/(120-7)= 355/113。
1585年，荷兰人安托尼兹用阿基米德的方法先求得：333/106＜π＜ 377/120，用两者作为π的母近似值，分子、分母各取平均，通过加成法获得结果：3((15+17)/(106+120)= 355/113。
两个虽都得出了祖冲之密率，但使用方法都为偶合，无理由可言。
在日本，十七世纪关孝和重要著作《括要算法》卷四中求圆周率时创立零约术，其实质就是用加成法来求近似分数的方法。他以3、4作为母近似值，连续加成六次得到祖冲之约率，加成一百十二次得到密率。其学生对这种按部就班的笨办法作了改进，提出从相邻的不足、过剩近似值就近加成的办法，（实际上就是我们前面已经提到的加成法）这样从3、4出发，六次加成到约率，第七次出现25／8，就近与其紧邻的22／7加成，得47／15，依次类推，只要加成23次就得到密率。
钱宗琮先生在《中国算学史》（1931年）中提出祖冲之采用了我们前面提到的由何承天首创的“调日法”或称加权加成法。他设想了祖冲之求密率的过程：以徽率157／50，约率22／7为母近似值，并计算加成权数x=9，于是(157+ 22×，9)/(50+7×9)= 355/113，一举得到密率。钱先生说：“冲之在承天后，用其术以造密率，亦意中事耳。”
另一种推测是：使用连分数法。
由于求二自然数的最大公约数的更相减损术远在《九章算术》成书时代已流行，所以借助这一工具求近似分数应该是比较自然的。于是有人提出祖冲之可能是在求得盈二数之后，再使用这个工具，将3.14159265表示成连分数，得到其渐近分数：3，22／7，333／106，355／113，102573／32650…
最后，取精确度很高但分子分母都较小的355／113作为圆周率的近似值。至于上面圆周率渐近分数的具体求法，这里略掉了。你不妨利用我们前面介绍的方法自己求求看。英国李约瑟博士持这一观点。他在《中国科学技术史》卷三第19章几何编中论祖冲之的密率说：“密率的分数是一个连分数渐近数，因此是一个非凡的成就。”
我国再回过头来看一下国外所取得的成果。
1150年，印度数学家婆什迦罗第二计算出π= 3927/1250= 3.1416。1424年，中亚细亚地区的天文学家、数学家卡西著《圆周论》，计算了3×228＝805,306,368边内接与外切正多边形的周长，求出π值，他的结果是：
π＝3.14159265358979325
有十七位准确数字。这是国外第一次打破祖冲之的记录。
16世纪的法国数学家韦达利用阿基米德的方法计算π近似值，用 6×216正边形，推算出精确到9位小数的π值。他所采用的仍然是阿基米德的方法，但韦达却拥有比阿基米德更先进的工具：十进位置制。17世纪初，德国人鲁道夫用了几乎一生的时间钻研这个问题。他也将新的十进制与早的阿基米德方法结合起来，但他不是从正六边形开始并将其边数翻番的，他是从正方形开始的，一直推导出了有262条边的正多边形，约4,610,000,000,000,000,000边形！这样，算出小数35位。为了记念他的这一非凡成果，在德国圆周率π被称为“鲁道夫数”。但是，用几何方法求其值，计算量很大，这样算下去，穷数学家一生也改进不了多少。到鲁道夫可以说已经登峰造极，古典方法已引导数学家们走得很远，再向前推进，必须在方法上有所突破。
17世纪出现了数学分析，这锐利的工具使得许多初等数学束手无策的问题迎刃而解。π的计算历史也随之进入了一个新的阶段。
分析法时期
这一时期人们开始摆脱求多边形周长的繁难计算，利用无穷级数或无穷连乘积来算π。
1593年，韦达给出
这一不寻常的公式是π的最早分析表达式。甚至在今天，这个公式的优美也会令我们赞叹不已。它表明仅仅借助数字2，通过一系列的加、乘、除和开平方就可算出π值。
接着有多种表达式出现。如沃利斯1650年给出：
1706年，梅钦建立了一个重要的公式，现以他的名字命名：
再利用分析中的级数展开，他算到小数后100位。
这样的方法远比可怜的鲁道夫用大半生时间才抠出的35位小数的方法简便得多。显然，级数方法宣告了古典方法的过时。此后，对于圆周率的计算像马拉松式竞赛，纪录一个接着一个：
1844年，达塞利用公式：
算到200位。
19世纪以后，类似的公式不断涌现，π的位数也迅速增长。1873年，谢克斯利用梅钦的一系列方法，级数公式将π算到小数后707位。为了得到这项空前的纪录，他花费了二十年的时间。他死后，人们将这凝聚着他毕生心血的数值，铭刻在他的墓碑上，以颂扬他顽强的意志和坚韧不拔的毅力。于是在他的墓碑上留下了他一生心血的结晶：π的小数点后707位数值。这一惊人的结果成为此后74年的标准。此后半个世纪，人们对他的计算结果深信不疑，或者说即便怀疑也没有办法来检查它是否正确。以致于在1937年巴黎博览会发现馆的天井里，依然显赫地刻着他求出的π值。
又过了若干年，数学家弗格森对他的计算结果产生了怀疑，其疑问基于如下猜想：在π的数值中，尽管各数字排列没有规律可循，但是各数码出现的机会应该相同。当他对谢克斯的结果进行统计时，发现各数字出现次数过于参差不齐。于是怀疑有误。他使用了当时所能找到的最先进的计算工具，从1944年5月到1945年5月，算了整整一年。1946年，弗格森发现第528位是错的（应为4，误为5）。谢克斯的值中足足有一百多位全都报了销，这把可怜的谢克斯和他的十五年浪费了的光阴全部一笔勾销了。
对此，有人曾嘲笑他说：数学史在记录了诸如阿基米德、费马等人的著作之余，也将会挤出那么一、二行的篇幅来记述1873年前谢克斯曾把π计算到小数707位这件事。这样，他也许会觉得自己的生命没有虚度。如果确实是这样的话，他的目的达到了。
人们对这些在地球的各个角落里作出不懈努力的人感到不可理解，这可能是正常的。但是，对此做出的嘲笑却是过于残忍了。人的能力是不同的，我们无法要求每个人都成为费马、高斯那样的人物。但成为不了伟大的数学家，并不意味着我们就不能为这个社会做出自己有限的贡献。人各有其长，作为一个精力充沛的计算者，谢克斯愿意献出一生的大部分时光从事这项工作而别无报酬，并最终为世上的知识宝库添了一小块砖加了一个块瓦。对此我们不应为他的不懈努力而感染并从中得到一些启发与教育吗？
1948年1月弗格森和伦奇两人共同发表有808位正确小数的π。这是人工计算π的最高记录。
计算机时期
1946年，世界第一台计算机ENIAC制造成功，标志着人类历史迈入了电脑时代。电脑的出现导致了计算方面的根本革命。1949年，ENIAC根据梅钦公式计算到2035（一说是2037）位小数，包括准备和整理时间在内仅用了70小时。计算机的发展一日千里，其记录也就被频频打破。
ENIAC：一个时代的开始
1973年，有人就把圆周率算到了小数点后100万位，并将结果印成一本二百页厚的书，可谓世界上最枯燥无味的书了。1989年突破10亿大关，1995年10月超过64亿位。1999年9月30日，《文摘报》报道，日本东京大学教授金田康正已求到2061.5843亿位的小数值。如果将这些数字打印在A4大小的复印纸上，令每页印2万位数字，那么，这些纸摞起来将高达五六百米。来自最新的报道：金田康正利用一台超级计算机，计算出圆周率小数点后一兆二千四百一十一亿位数，改写了他本人两年前创造的纪录。据悉，金田教授与日立制作所的员工合作，利用目前计算能力居世界第二十六位的超级计算机，使用新的计算方法，耗时四百多个小时，才计算出新的数位，比他一九九九年九月计算出的小数点后二千六百一十一位提高了六倍。圆周率小数点后第一兆位数是二，第一兆二千四百一十一亿位数为五。如果一秒钟读一位数，大约四万年后才能读完。
不过，现在打破记录，不管推进到多少位，也不会令人感到特别的惊奇了。实际上，把π的数值算得过分精确，应用意义并不大。现代科技领域使用的π值，有十几位已经足够。如果用鲁道夫的35位小数的π值计算一个能把太阳系包围起来的圆的周长，误差还不到质子直径的百万分之一。我们还可以引美国天文学家西蒙·纽克姆的话来说明这种计算的实用价值：
“十位小数就足以使地球周界准确到一英寸以内，三十位小数便能使整个可见宇宙的四周准确到连最强大的显微镜都不能分辨的一个量。”
那么为什么数学家们还象登山运动员那样，奋力向上攀登，一直求下去而不是停止对π的探索呢？为什么其小数值有如此的魅力呢？
这其中大概免不了有人类的好奇心与领先于人的心态作怪，但除此之外，还有许多其它原因。
奔腾与圆周率之间的奇妙关系……
1、它现在可以被人们用来测试或检验超级计算机的各项性能，特别是运算速度与计算过程的稳定性。这对计算机本身的改进至关重要。就在几年前，当Intel公司推出奔腾（Pentium）时，发现它有一点小问题，这问题正是通过运行π的计算而找到的。这正是超高精度的π计算直到今天仍然有重要意义的原因之一。
2、计算的方法和思路可以引发新的概念和思想。虽然计算机的计算速度超出任何人的想象，但毕竟还需要由数学家去编制程序，指导计算机正确运算。实际上，确切地说，当我们把π的计算历史划分出一个电子计算机时期时，这并非意味着计算方法上的改进，而只是计算工具有了一个大飞跃而已。因而如何改进计算技术，研究出更好的计算公式，使公式收敛得更快、能极快地达到较大的精确度仍是数学家们面对的一个重要课题。在这方面，本世纪印度天才数学家拉马努扬得出了一些很好的结果。他发现了许多能够迅速而精确地计算π近似值的公式。他的见解开通了更有效地计算π近似值的思路。现在计算机计算π值的公式就是由他得到的。至于这位极富传奇色彩的数学家的故事，在这本小书中我们不想多做介绍了。不过，我希望大家能够明白π的故事讲述的是人类的胜利，而不是机器的胜利。
3、还有一个关于π的计算的问题是：我们能否无限地继续算下去？答案是：不行！根据朱达偌夫斯基的估计，我们最多算1077位。虽然，现在我们离这一极限还相差很远很远，但这毕竟是一个界限。为了不受这一界限的约束，就需要从计算理论上有新的突破。前面我们所提到的计算，不管用什么公式都必须从头算起，一旦前面的某一位出错，后面的数值完全没有意义。还记得令人遗憾的谢克斯吗？他就是历史上最惨痛的教训。
4、于是，有人想能否计算时不从头开始，而是从半截开始呢？这一根本性的想法就是寻找并行算法公式。1996年，圆周率的并行算法公式终于找到，但这是一个16进位的公式，这样很容易得出的1000亿位的数值，只不过是16进位的。是否有10进位的并行计算公式，仍是未来数学的一大难题。
5、作为一个无穷数列，数学家感兴趣的把π展开到上亿位，能够提供充足的数据来验证人们所提出的某些理论问题，可以发现许多迷人的性质。如，在π的十进展开中，10个数字，哪些比较稀，哪些比较密？π的数字展开中某些数字出现的频率会比另一些高吗？或许它们并非完全随意？这样的想法并非是无聊之举。只有那些思想敏锐的人才会问这种貌似简单，许多人司空见惯但却不屑发问的问题。
6、数学家弗格森最早有过这种猜想：在π的数值式中各数码出现的概率相同。正是他的这个猜想为发现和纠正向克斯计算π值的错误立下了汗马功劳。然而，猜想并不等于现实。弗格森想验证它，却无能为力。后人也想验证它，也是苦于已知的π值的位数太少。甚至当位数太少时，人们有理由对猜想的正确性做出怀疑。如，数字0的出现机会在开始时就非常少。前50位中只有1个0，第一次出现在32位上。可是，这种现象随着数据的增多，很快就改变了：100位以内有8个0；200位以内有19个0；……1000万位以内有999，440个0；……60亿位以内有599，963，005个0，几乎占1／10。
其他数字又如何呢？结果显示，每一个都差不多是1／10，有的多一点，有的少一点。虽然有些偏差，但都在1／10000之内。
7、人们还想知道：π的数字展开真的没有一定的模式吗？我们希望能够在十进制展开式中通过研究数字的统计分布，寻找任何可能的模型――如果存在这种模型的话，迄今为止尚未发现有这种模型。同时我们还想了解：π的展开式中含有无穷的样式变化吗？或者说，是否任何形式的数字排列都会出现呢？著名数学家希尔伯特在没有发表的笔记本中曾提出下面的问题：π的十进展开中是否有10个9连在一起？以现在算到的60亿位数字来看，已经出现：连续6个9连在一起。希尔伯特的问题答案似乎应该是肯定的，看来任何数字的排列都应该出现，只是什么时候出现而已。但这还需要更多π的数位的计算才能提供切实的证据。
8、在这方面，还有如下的统计结果：在60亿数字中已出现连在一起的8个8；9个7；10个6；小数点后第710150位与3204765位开始，均连续出现了七个3；小数点52638位起连续出现了14142135这八个数字，这恰是的前八位；小数点后第2747956位起，出现了有趣的数列876543210，遗憾的是前面缺个9；还有更有趣的数列123456789也出现了。
如果继续算下去，看来各种类型的数字列组合可能都会出现。
拾零：π的其它计算方法
在1777年出版的《或然性算术实验》一书中，蒲丰提出了用实验方法计算π。这个实验方法的操作很简单：找一根粗细均匀，长度为 d的细针，并在一张白纸上画上一组间距为 l的平行线（方便起见，常取 l= d/2），然后一次又一次地将小针任意投掷在白纸上。这样反复地投多次，数数针与任意平行线相交的次数，于是就可以得到π的近似值。因为蒲丰本人证明了针与任意平行线相交的概率为 p= 2l/πd。利用这一公式，可以用概率方法得到圆周率的近似值。在一次实验中，他选取 l= d/2，然后投针2212次，其中针与平行线相交704次，这样求得圆周率的近似值为 2212/704= 3.142。当实验中投的次数相当多时，就可以得到π的更精确的值。
1850年，一位叫沃尔夫的人在投掷5000多次后，得到π的近似值为3.1596。目前宣称用这种方法得到最好结果的是意大利人拉兹瑞尼。在1901年，他重复这项实验，作了3408次投针，求得π的近似值为3.1415929，这个结果是如此准确，以致于很多人怀疑其实验的真伪。如美国犹他州奥格登的国立韦伯大学的L·巴杰就对此提出过有力的质疑。
不过，蒲丰实验的重要性并非是为了求得比其它方法更精确的π值。蒲丰投针问题的重要性在于它是第一个用几何形式表达概率问题的例子。计算π的这一方法，不但因其新颖，奇妙而让人叫绝，而且它开创了使用随机数处理确定性数学问题的先河，是用偶然性方法去解决确定性计算的前导。
在用概率方法计算π值中还要提到的是：R·查特在1904年发现，两个随意写出的数中，互素的概率为6／π2。1995年4月英国《自然》杂志刊登文章，介绍英国伯明翰市阿斯顿大学计算机科学与应用数学系的罗伯特·马修斯，如何利用夜空中亮星的分布来计算圆周率。马修斯从100颗最亮的星星中随意选取一对又一对进行分析，计算它们位置之间的角距。他检查了100万对因子，据此求得π的值约为3.12772。这个值与真值相对误差不超过5％。
无穷的神秘气息：纪梵希的男用香水π。广告词是：Explore pi, explore the universe
通过几何、微积分、概率等广泛的范围和渠道发现π，这充分显示了数学方法的奇异美。π竟然与这么些表面看来风马牛不相及的试验，沟通在一起，这的确使人惊讶不已
关于编程的50种基础算法到此分享完毕，希望能帮助到您。