|
| 1 | +--- |
| 2 | +title: 算法 |
| 3 | +date: 2019-02-19 17:01:00 |
| 4 | +categories: ['algorithm','algorithm'] |
| 5 | +tags: ['algorithm'] |
| 6 | +--- |
| 7 | + |
| 8 | +# 算法 |
| 9 | + |
| 10 | +## 算法思想 |
| 11 | + |
| 12 | +### 穷举算法思想 |
| 13 | + |
| 14 | +穷举算法（ExhaustiveAttackmethod)是最简单的一种算法，其依赖于计算机的强大计算能力来穷尽每一种可能的情况，从而达到求解问题的目的。穷举算法效率并不高，但是适应于一些没有明显规律可循的场合。 |
| 15 | + |
| 16 | +#### 基本算法思想 |
| 17 | + |
| 18 | +穷举算法的基本思想就是从所有可能的情况中搜索正确的答案，其执行步骤如下： |
| 19 | + |
| 20 | +1. 对于一种可能的情况，计算其结果。 |
| 21 | +2. 判断结果是否满足要求，如果不满足则执行第（1 ) 步来搜索下一个可能的情况；如果满足要求，则表示寻找到一个正确的答案。 |
| 22 | + |
| 23 | +> 注意：在使用穷举算法时，需要明确问题的答案的范围，这样才可以在指定范围内搜索答案。指定范围之后，就可以使用循环语句和条件判断语句逐步验证候选答案的正确性，从而得到需要的正确答案。 |
| 24 | +
|
| 25 | +#### 经典例子 |
| 26 | + |
| 27 | +《孙子算经》【鸡兔同笼问题】 |
| 28 | +今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？ |
| 29 | +（在一个笼子里关着若干只鸡和若干只兔，从上面数共有 35 个头；从下面数共有 94 只脚。问笼中鸡和兔的数量各是多少？） |
| 30 | + |
| 31 | +``` |
| 32 | +int chickenRabbit(int head,int foot,int *c,int r){ |
| 33 | +int i,j; |
| 34 | +int tag=0;//标志是否有解 |
| 35 | +for(i=0;i<=head;i++){//鸡的个数穷举 |
| 36 | + j=head-i;//兔子的个数 |
| 37 | + if(i2+j*4==foot){//判断是否满足条件 |
| 38 | + tag=1; |
| 39 | + *c=i; |
| 40 | + *r=j; |
| 41 | + } |
| 42 | +} |
| 43 | +return tag; |
| 44 | +} |
| 45 | +int main() |
| 46 | +{ |
| 47 | + int c,r; |
| 48 | + if(chickenRabbit(35,94,&c,&r)==1){//如果有解输出 |
| 49 | + printf("chickens=%d,rabbits=%d\n",c,r); |
| 50 | + }else{//如果无解 |
| 51 | + printf("无解\n"); |
| 52 | + } |
| 53 | + return 0; |
| 54 | +} |
| 55 | +``` |
| 56 | + |
| 57 | +### 递推算法思想 |
| 58 | + |
| 59 | +递推算法是非常常用的算法思想，在数学计算等场合有着广泛的应用。递推算法适合有明显公式规律的场合。 |
| 60 | + |
| 61 | +#### 基本算法思想 |
| 62 | + |
| 63 | +递推算法是一种理性思维模式的代表，根据已有的数据和关系，逐步推导而得到结果。递推算法的执行过程如下： |
| 64 | +(1) 根据已知结果和关系，求解中间结果。 |
| 65 | +(2)判定是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果。如果满足要求，则表示寻找到一个正确的答案。 |
| 66 | + |
| 67 | +【注意】递推算法需要用户知道答案和问题之间的逻辑关系。在许多数学问题中，都有明确的计算公式可以遵循，因此可以采用递推算法来实现。 |
| 68 | + |
| 69 | +#### 经典例子 |
| 70 | + |
| 71 | +斐波那契《算盘书》【兔子产仔问题】 |
| 72 | +如果一对两个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子出生两个月后才可以生小兔子。也就是说，1 月份出生，3 月份才可产仔。那么假定一年内没有产生兔子死亡事件,那 么 1 年后共有多少对兔子呢？ |
| 73 | + |
| 74 | +【规律分析】 |
| 75 | +第一个月：a(1)=1 对兔子； |
| 76 | +第二个月：a(2)=1 对兔子； |
| 77 | +第三个月：a(3)=1+1=2 对兔子； |
| 78 | +第四个月：a(4)=1+2=3 对兔子； |
| 79 | +第五个月：a(5)=2+3=5 对兔子； |
| 80 | +…… |
| 81 | +第 n 个月：a(n)=a(n-1)+a(n-2)对兔子； |
| 82 | + |
| 83 | +``` |
| 84 | +int Fibonacci(int n) |
| 85 | +{ |
| 86 | +int tl,t2; |
| 87 | +if (n==1||n==2)//第1、2个月都只有1对兔子 |
| 88 | +{ |
| 89 | +return 1; |
| 90 | +}else{//采用递归 |
| 91 | +tl=Fibonacci(n-1); |
| 92 | +t2=Fibonacci(n-2); |
| 93 | +return tl+t2;//计算第n个月的兔子对数 |
| 94 | +} |
| 95 | +} |
| 96 | +int main() |
| 97 | +{ |
| 98 | + int n=12; |
| 99 | + printf("%d个月后兔子对数：%d\n",n,Fibonacci(n)); |
| 100 | + return 0; |
| 101 | +} |
| 102 | +``` |
| 103 | + |
| 104 | +### 递归算法思想 |
| 105 | + |
| 106 | +递归算法是非常常用的算法思想。使用递归算法，往往可以简化代码编写，提高程序的可读性。但是，不合适的递归会导致程序的执行效率变低。 |
| 107 | + |
| 108 | +#### 基本算法思想 |
| 109 | + |
| 110 | +递归算法就是在程序中不断反复调用自身来达到求解问题的方法。这里的重点是调用自身，这就要求待求解的问题能够分解为相同问题的一个子问题。这样 ，通过多次递归调用，便可以完成求解。 |
| 111 | +递归调用是一个函数在它的函数体内调用它自身的函数调用方式，这种函数也称为“递归函数”。在递归函数中，主调函数又是被调函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层。 |
| 112 | +函数的递归调用分两种情况：直接递归和间接递归。 |
| 113 | +• 直接递归：即在函数中调用函数本身。 |
| 114 | +• 间接递归：即间接地调用一个函数，如出如 func_a 调 用 func_b, func_b 又调用 func_a。间接递归用得不多。 |
| 115 | + |
| 116 | +【注意】编写递归函数时，必须使用 if 语句强制函数在未执行递归调用前返回。否则，在调用函数后，它永远不会返回，这是一个很容易犯的错误。 |
| 117 | + |
| 118 | +#### 经典例子 |
| 119 | + |
| 120 | +【阶乘】 |
| 121 | + |
| 122 | +``` |
| 123 | +n!=n(n-1)(n-2)……21 |
| 124 | +1 |
| 125 | +long fact(int n){ |
| 126 | +if(n<=1)return 1; |
| 127 | +else |
| 128 | + return nfact(n-1); |
| 129 | +} |
| 130 | +int main() |
| 131 | +{ |
| 132 | + int n=11; |
| 133 | + printf("%d的阶乘是%d\n",n,fact(n)); |
| 134 | + return 0; |
| 135 | +} |
| 136 | +``` |
| 137 | + |
| 138 | +### 分治算法思想 |
| 139 | + |
| 140 | +分治算法是一种化繁为简的算法思想。分治算法往往应用于计算步骤比较复杂的问题，通过将问题简化而逐步得到结果。 |
| 141 | + |
| 142 | +#### 基本算法思想 |
| 143 | + |
| 144 | +分治算法的基本思想是将一个计算复杂的问题分为规模较小，计算简单的小问题求解，然后综合各个小问题，得到最终问题的答案。分治算法的执行过程如下： |
| 145 | +(1)对于一个规模为 N 的问题，若该问题可以容易地解决（比如说规模>^较小），则直接解决,否则执行下面的步骤。 |
| 146 | +(2)将该问题分解为” 个规模较小的子问题，这些子问题互相独立，并且原问题形式相同。 |
| 147 | +(3)递归地解子问题。 |
| 148 | +(4)然后，将各子问题的解合并得到原问题的解。 |
| 149 | + |
| 150 | +【注意】使用分治算法需要待求解问题能够化简为若干个小规模的相同问题，通过逐步划分，达到一个易于求解的阶段而直接进行求解。然后，程序中可以使用递归算法来进行求解。 |
| 151 | + |
| 152 | +#### 经典例子 |
| 153 | + |
| 154 | +【寻找假币问题】 |
| 155 | +一个袋子里有 30 个硬币，其中一枚是假币，并且假币和真币一模- 样，肉眼很难分辨，目前只知道假币比真币重量轻一点。请问如何区分出假币？ |
| 156 | + |
| 157 | +``` |
| 158 | +int falseCoin(int coin[],int low,int high){ |
| 159 | +int i,sum1,sum2,sum3; |
| 160 | +int re; |
| 161 | +sum1=sum2=sum3=0; |
| 162 | +//若只有两个硬币 |
| 163 | +if(low+1==high){ |
| 164 | + if(coin[low]<coin[high]){//第一个硬币是假币 |
| 165 | + re=low+1; |
| 166 | + return re; |
| 167 | +}else{//第二个硬币是假币 |
| 168 | +re=high+1; |
| 169 | +return re; |
| 170 | +} |
| 171 | +} |
| 172 | +//硬币个数大于2 |
| 173 | +if((high-low+1)%2==0){//偶数个硬币 |
| 174 | + for(i=low;i<=low+(high-low)/2;i++){//前半段重量 |
| 175 | + sum1=sum1+coin[i]; |
| 176 | + } |
| 177 | + for(i=low+(high-low)/2+1;i<=high;i++){//后半段重量 |
| 178 | + sum2=sum2+coin[i]; |
| 179 | + } |
| 180 | + if(sum1>sum2){//后半段轻，假币在后半段 |
| 181 | + re=falseCoin(coin,low+(high-low)/2+1,high); |
| 182 | + return re; |
| 183 | + }else if(sum1<sum2){//前半段轻，假币在前半段 |
| 184 | + re=falseCoin(coin,low,low+(high-low)/2); |
| 185 | + return re; |
| 186 | + } |
| 187 | +}else{//奇数个硬币 |
| 188 | +for(i=low;i<=low+(high-low)/2-1;i++){//前半段重量 |
| 189 | + sum1=sum1+coin[i]; |
| 190 | + } |
| 191 | + for(i=low+(high-low)/2+1;i<=high;i++){//后半段重量 |
| 192 | + sum2=sum2+coin[i]; |
| 193 | + } |
| 194 | + sum3=coin[low+(high-low)/2]; |
| 195 | + if(sum1>sum2){//后半段轻，假币在后半段 |
| 196 | + re=falseCoin(coin,low+(high-low)/2+1,high); |
| 197 | + return re; |
| 198 | + }else if(sum1<sum2){//前半段轻，假币在前半段 |
| 199 | + re=falseCoin(coin,low,low+(high-low)/2-1); |
| 200 | + return re; |
| 201 | + } |
| 202 | + if(sum1+sum3==sum2+sum3){//前半段+中间硬币和后半段+中间硬币重量相等，说明中间硬币是假币 |
| 203 | + re=low+(high-low)/2+1; |
| 204 | + return re; |
| 205 | + } |
| 206 | +
|
| 207 | +} |
| 208 | +} |
| 209 | +int main() |
| 210 | +{ |
| 211 | + int n=11,i; |
| 212 | + int a[n]; |
| 213 | + for(i=0;i<n;i++){ |
| 214 | + a[i]=2; |
| 215 | + } |
| 216 | + a[7]=1;//设置第八个为假币 |
| 217 | + printf("假币是第%d个\n", falseCoin(a,0,n-1)); |
| 218 | + return 0; |
| 219 | +} |
| 220 | +``` |
| 221 | + |
| 222 | +### 概率算法思想 |
| 223 | + |
| 224 | +概率算法依照概率统计的思路来求解问题，往往不能得到问题的精确解，但却在数值计算领域得到了广泛的应用。因为很多数学问题，往往没有或者很难计算解析解，这时便需要通过数值计算来求解近似值。 |
| 225 | + |
| 226 | +#### 基本算法思想 |
| 227 | + |
| 228 | +概率算法执行的基本过程如下： |
| 229 | +(1)将问题转化为相应的几何图形 S, S 的面积是容易计算的，问题的结果往往对应几何图形中某一部分 S1 的面积。 |
| 230 | +(2)然后，向几何图形中随机撒点。 |
| 231 | +(3)统计几何图形 S 和 S1 中的点数。根 据 S 的面积和 S1 面积的关系以及各图形中的点数来计算得到结果。 |
| 232 | +(4) 判断上述结果是否在需要的精度之内，如果未达到精度则执行步骤(2)。如果达到精度,则输出近似结果。 |
| 233 | +概率算法大致分为如下 4 种形式。 |
| 234 | + |
| 235 | +• 数值概率算法。 |
| 236 | +• 蒙 特 卡 罗 （MonteCarlo)算法。 |
| 237 | +• 拉 斯 维 加 斯 （Las Vegas)算法。 |
| 238 | +• 舍 伍 德 （Sherwood)算法。 |
| 239 | + |
| 240 | +#### 经典例子 |
| 241 | + |
| 242 | +【蒙特卡罗 PI 概率算法问题】 |
| 243 | +在边长为 1 的正方形内，以 1 为半径画一个 1/4 圆。落入院内的概率为 PI/4？ |
| 244 | +算法思想：在某面积范围内撒点足够多，落在固定区域的点的概率就会将近结果。 |
| 245 | +关键：均匀撒点、区域判断 |
| 246 | + |
| 247 | +``` |
| 248 | +double MontePI(int n){ |
| 249 | +double PI; |
| 250 | +double x,y; |
| 251 | +int i,sum; |
| 252 | +sum=0; |
| 253 | +srand(time(NULL)); |
| 254 | +for(i=1;i<n;i++){ |
| 255 | + x=(double)rand()/RAND_MAX;//在0-1之间产生一个随机数x |
| 256 | + y=(double)rand()/RAND_MAX;//在0-1之间产生一个随机数y |
| 257 | + if((xx+yy)<=1){//判断点是否在圆内 |
| 258 | + sum++;//计数 |
| 259 | + } |
| 260 | +} |
| 261 | + PI=4.0*sum/n;//计算PI |
| 262 | + return PI; |
| 263 | +} |
| 264 | +
|
| 265 | +int main() |
| 266 | +{ |
| 267 | + int n=500000; |
| 268 | + double PI; |
| 269 | +
|
| 270 | + printf("蒙特卡罗概率PI=%f\n", MontePI(n)); |
| 271 | + return 0; |
| 272 | +} |
| 273 | +``` |
0 commit comments