程序设计--浅谈编程解决实际问题的常见思想
现实⽣活中有很多问题，⼈为不好解决，但利⽤计算机速度快，不出错的特性，可以很⽅便的解决这些问题，下⾯简单说说我在程序设计中解决实际问题的⼀些常见思想，⾼⼿可以忽略掉，我也是⽆聊了随便写写⽽已。
1.枚举最优解时的情况
有很多问题初看很棘⼿，但经过仔细的分析，可以得出⼀些显然的结论。
⽐如下⾯这个问题：平⾯内有上千个点，⽤⼀个半径为R的圆去覆盖，最多能覆盖多少点？
很多程序员最暴⼒的思想就是枚举，当然，利⽤计算机枚举确实是⼀种很有效的⽅法，特别是在数据很⼩的情况下，不过对于上述问题，如何枚举？枚举圆的位置吗？
确实可以枚举圆的位置，如果不经过思考的话可以再⼆维正交系内枚举每个点为圆⼼，然后判断这个圆能覆盖多少圆，最后结果取最⼤。这个确实是⼀种⽅法，不过枚举圆⼼如何操作？圆⼼的位置是连续的，不⼀定是整点这种离散位置。在数据量⼩并且精度要求不⾼的情况下，直接枚举圆⼼位置不失为⼀种好⽅法。不过稍微分析⼀下，可以得出这样⼀个结论，最优解的圆，也就是覆盖点数最多的R半径圆，圆上⼀定有2个点。
假设最优解的圆上没有2个点，如上图，那么通过微量的平移操作，可以使圆接触平⾯上的2个点，并且园内的点数不会减少，它的结果不会⽐圆上没有2个点的情况差，因为只要求最多覆盖多少点，我们可以枚举任意2个点，这样这个半径为R的圆的位置就确定了（在这2点中垂线上，2中情况），再判断下这个圆能覆盖多少点，两两点枚举后取最⼤，这是⼀个O(n^3)的算法，1秒内出结果，已经⽐较⾼效了。
所以很多时候我们可以分析出最优解是满⾜哪种情况的，然后利⽤计算机特性枚举最优解，逆向思维解决问题。
2.动态规划思想
动态规划是⼀种⾮常⾼效的⽅法，这个编程⾥⾯⾮常⾮常常见的，不会搜索和动态规划，基本就不会编程。如果能够把⼀个⼤的问题划分成若⼲同类型的⼩问题，⼩问题⼜可以划分为更⼩的问题，直到问题程度⼩到⼀眼就能看出来，那么可以把⼩问题先求出保存起来，再求⼤问题，这样的例⼦相当多，⽽且利⽤递归的写法，记忆化深度搜索，很容易实现这种思想。经典的动态规划还有很多，最长上升⼦序列，背包问题等等。
如果还有同学不明⽩动态规划，看下⾯这⼀段C语⾔代码，相信能体会到⼀些。
/******************
Author: lxglbk
Function : Get the fibonacci number fib(n) (n>=0) 求n的阶乘
fib(0)=fib(1)=1
fib(n)=fib(n-1)+fib(n-2) n>1
****/
//完成动态规划⼀般2种思路
//1.记忆化深搜
int fib[MAXN]
int F(int n)
{
  if(n<2) return1;
  if(fib[n]) return fib[n];
  return fib[n]=F(n-1)+F(n-2);
}什么是编程举个例子
//2.规划⽅向后求解
int fib[MAXN],i;
fib[0]=fib[1]=1;
for(i=2;i<=N;i++) fib[i]=fib[i-1]+fib[i-2];
3.排序思想
排序是⼀个很重要的步骤，有很多问题通过排序预处理后可以更加⽅便的解决，⽐如有很多张钞票，⾯值不同，从中选出m张使它们价值最⼤，⼀个做法当然是对着些钞票按照⾯值从⼤到⼩排序，然后取钱m张就⾏了。很多时候，上述的动态规划需要对变量按照⼀定规则排序后才能操作，有⼀定顺序了之后，问题⼀般更容易解决。
说到排序，不得不说到贪⼼算法。贪⼼算法就是如果整个⼤问题要到达⼀个最优解，在构成⼤问题的⼩问题中每次取最优的，⼤问题就能到达最优情况，当然，这种策略需要经过证明正确性后才能实现。很多贪⼼过程前也要有排序的⼯作，⽐如著名的Kruscal最⼩⽣成树算法，要先对边进⾏排序，所以排序是个很重要的过程，以⾄于它被收录到各种语⾔的库函数中，可以⽅便的被⽤户调⽤。
4.⼆分，三分。
前⼏天听同学说，现在8K已经招不到会写⼆分的程序员了，当然这句话有夸张的成分啦，^-^ 可见⼆分在程序设计中的常⽤性。
其实这个可以并列到枚举算法那中，只是这种枚举效率很⾼，很多地⽅⽐如SQL数据库⾥⾯的查⽅式就是⼆分，⼆分枚举，三分枚举，时间复杂度都是对数级的，在程序设计中是相当⾼效的算法。
⼆分的条件：数据的单调性。⽐如在⼀组从⼩到⼤排序的数中寻数x 这样就可以⼆分枚举每次可以把范围缩⼩⼀半，⽆论数据多⼤，就算超出int类型，都能很快出来。
⽐如求函数8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == K 在区间[0,100]的解由于这个函数在[0,100]是单调递增的，所以⼆分是个不错的选择。
三分的条件: 数据的有凸性。
⽐如求函数6*x^7 + 8*x^6 + 7*x^3 + 5*x^2 - K*x 在区间[0,100]的最⼩值
这个函数在[0,100]是⼀个先减后增(或者完全单调，主要看K)的函数，所以三分求解。
当然这个问题可以转换为⼆分，将函数求导，⼆分其在0的位置即可，这个涉及到⾼等数学，不赘述了。
具体过程可以去查资料⼆分前⼀般也需要排序操作的。
5.随机算法
很多时候在要解决的问题没有任何思路，枚举数据量⼜太⼤的情况下，可以使⽤⼀些随机算法。
常见的随机算法，蚁算法，模拟退⽕等等。
简单说说模拟退⽕（后⾯我打算专门写⼀篇模拟退⽕的随笔）
⽐如平⾯内有成千上万个点，要在平⾯选⼀个圆，覆盖所有点，问最⼩的半径是多少？
第⼀次接触这个问题的时候我有想到⼀种做法（不敢保证正确）：
根据1 还是可以得出结论，最优情况圆上⾯⼀定有2个点，否则的话可以把圆继续缩⼩平移，使它上⾯有2个点，结果更优。
所以枚举任意2个点，圆⼼⼀定在这2点中垂线上，这⾥是对的。然后假设这个圆⼼在在中垂线上移动，如果满⾜要求，包围了所有点。
那么我猜测这个圆在移动过程中半径先减⼩后增⼤。(感觉⽽已，未证明，也未测试，太⿇烦了。) 这⾥可以使⽤上述的三分枚举，因为半径函数是下凸性的。
我上⾯这个⽅法正确性先不说，复杂度是有⼀点的，枚举2点，再三分。O(n^2*logV) 当然，数据很⼩的情况下，⽐如只有⼏千个点的话，结果秒出，数据⼤了，效率降低了。
这⾥说⼀下模拟退⽕的思想。⼤概依照⼀个这样的理论，假设现在有1个位置pos，如果最优解圆⼼位置在pos上⾯，那么如果往pos下⾯搜，搜到的圆⼼⼀定⽐在pos的位置时候⼤。
依照这个理论，我们就可以现在平⾯内随机⽣成⼀些点，然后贪⼼的随机移动它们，直到达到⼀定程度停⽌。这个算法在时间复杂度上是
O(n)的正确性很⾼，运⾏也相当的快。
6.最后⼀个问题转化
有的时候遇到问题，不能⽴即想出策略，这个时候尝试下将这个问题转化为常见的模型，利⽤常见模型和经典的算法解决它。
最常见的还是⼀些图论上的问题，将实际问题转化为流⽹络或者⼆分图。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。