基础算法(二)

主要内容：

1.迭代法

2.蛮力法

3.分治法

4.贪心法

5.动态规划

1.迭代法

迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值得解决问题的方法，一般用于数学计算。它是我们早已熟悉的算法策略，累加、累乘都的迭代算法的基础应用。利用迭代算法策略解决问题，设计工作主要有3步：

1.确定迭代模型：根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。

2.建立迭代关系式：递推数学模型一般是带下标的字母，算法设计中要将其转化为"循环不变式"——迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值得表达式，存储新值得变量称为迭代变量。

3.对迭代过程进行控制：确定在什么时候结束迭代过程。迭代过程的控制通常可分为两种情况：一种是已知或可以计算出所需的迭代次数，通过构建一个固定次数的循环来实现对迭代过程的控制。另一种是所需的迭代次数无法确定，需要分析出迭代过程的结束条件，有时还需考虑得不到目标解的情况，避免出现迭代过程的死循环。

穿越沙漠问题：

一辆吉普车穿越1000km的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/km,由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。若吉普车用最少的耗油量穿越沙漠，应该在哪些地方建立油库，以及各处存储的油量。

对于这个问题，我们从终点开始倒着推解储油点的位置及储油量。根据耗油量最少的目标进行分析，从后（终点）向前（起点）分段讨论：

第一段长度为500km且第一个加油点储油量为500加仑。

第二段中，为了储备油，吉普车在这段行程中必须有往返。这段一共走3次：第一、二次来回耗油量为装载量的2/3，储油量则为装载量的1/3，第三次单向行驶耗油量为装载量的1/3，储油量为装载量的2/3，这样第二个加油点的储油量为1000加仑，长度为500/3km

第三段与第二段思路相同。这一段共走5次：第一、二次来回耗油量为装载量的2/5，储油量为装载量的3/5，第三、四次来回耗油量为装载量的2/5，储油量为装载量的3/5，第五次单向行驶耗油量为装载量的1/5，储油量为装载量的4/5，这样第三个加油点储油量为1500加仑，长度为500/5km

..........

综上分析，从终点开始分别间隔500，500/3，500/5 ...(km)设立储油点，每个储油点的油量为500，1000，1500...   

 #include<stdio.h> int main() {     int dis, k, oil,i;     int distances[10], oilquantities[10];     dis = 500; k = 1; oil = 500;     do     {         distances[k] = 1000 - dis;         oilquantities[k] = oil;         k = k + 1;         dis = dis + 500 / (2 * k - 1);         oil = 500 * k;     } while (dis<1000);     oil = 500 * (k - 1) + (1000 - dis)*(2 * k - 1);     distances[k] = 0;     oilquantities[k] = oil;         for (i = k; i>=1; i--)     {         printf("storepoint: %d,  distance: %d, oilquantity: %d/n", k+1-i, distances[i],oilquantities[i]);     }     return 0; } 

牛顿迭代法：

牛顿迭代公式：Xn+1=Xn-f(Xn)/f'(Xn)

下面给出求形如a*x^3+b*x^2+c*x+d=0方程根的算法，求x在1附近的一个实根。

 #include<stdio.h> #include<math.h>  float f(float a, float b, float c, float d) {     float x1 = 1, x0, f0, f1;     do     {         x0 = x1;         f0 = ((a*x0 + b)*x0 + c)*x0 + d;         f1 = (3 * a*x0 + 2 * b)*x0 + c;         x1 = x0 - f0 / f1;     } while (fabs(x1-x0)>=exp(-4));     return x1; }  int main() {     float a, b, c, d, fx;     printf("输入系数a,b,c,d:");     scanf("%f%f%f%f", &a, &b, &c, &d);     fx = f(a, b, c, d);     printf("方程的根为:%f/n", fx); } 

2.蛮力法

蛮力法是基于计算机运算速度快的特点，在解决问题时采用的一种“懒惰”策略，它几乎不经过思考，把问题的所有情况交给计算机去尝试，从中找出问题的解。蛮力策略的应用范围很广，比如选择排序，冒泡排序，插入排序，顺序查找、朴素的字符串匹配等等。在这里我们简单了解一下蛮力策略中的枚举法。

枚举法就是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解，有时候还需要进一步考虑，排除一些明显不合理的情况，尽量减少问题可能解的列举数目。用枚举法解决问题：

1.找出枚举范围：分析问题所涉及的各种情况

2.找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示

百钱百鸡问题：

鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？

 #include<stdio.h> int main() {     int  x, y, z;     for (x = 1; x <= 20; x++)     {         for (y = 1; y <= 33; y++)         {             z = 100 - x - y;             if (z % 3 == 0 && 5 * x + 3 * y + z / 3 == 100)                 printf("the cock number is %d,the hen number is %d,the chick number is %d/n",x,y,z);         }     } } 

数字谜：

ABCAB*A=DDDDDD

 #include<stdio.h> int main() {     int A, B, C, D;     long E, F;     for (A = 3; A <= 9; A++)         for (D = 1; D <= 9; D++)         {             E = D * 100000 + D * 10000 + D * 1000 + D * 100 + D * 10 + D;             if (E%A == 0)             {                 F = E / A;                 if (F / 10000 == A && (F % 100) / 10 == A)                     if ((F / 1000) % 10 == F % 10)                         printf("%ld*%d=%ld/n", F, A, E);             }         } } 

3 .分治法

分治法求解问题的过程是，将整个问题分成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。

下面是分治法求解的三个步骤：

1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题

2.解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决。

3.合并：将已求解的各子问题的解，逐步合并为原问题的解。

适合用分治法策略的问题：

1.能将n个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题。（1<k<=n）

2.分解得到的子问题与原问题具有相似的结构，便于利用递归或循环机制

3.在求出这些子问题的解之后，就可以推解出原问题的解。

下面给出残缺棋盘和金块问题的问题描述与具体算法，比较经典的分治法解决的问题还有大整数乘法问题，可以自己研究一下。

残缺棋盘

残缺棋盘是一个有2^k*2^k(k>=1)个方格的棋盘，其中恰有一个残缺。用k=1时各种可能的残缺棋盘（三格板）去覆盖更大的残缺棋盘，要求：1.三格板不能重叠2.三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。

 #include<stdio.h> int amount = 0, Board[100][100]; void Cover(int tr, int tc, int dr, int dc, int size) {     int s, t;     if (size < 2) return;     amount = amount + 1;     t = amount;     s = size / 2;      if (dr < tr + s&&dc < tc + s)     {         Cover(tr, tc, dr, dc, s);          Board[tr + s - 1][tc + s] = t;         Board[tr + s][tc + s - 1] = t;         Board[tr + s][tc + s] = t;          Cover(tr, tc + s, tr + s - 1, tc + s, s);         Cover(tr + s, tc, tr + s, tc + s - 1, s);         Cover(tr + s, tc + s, tr + s, tc + s, s);     }     else  if (dr<tr + s&&dc >= tc + s)     {         Cover(tr, tc + s, dr, dc, s);          Board[tr + s - 1][tc + s - 1] = t;         Board[tr + s][tc + s - 1] = t;         Board[tr + s][tc + s] = t;          Cover(tr, tc, tr + s - 1, tc + s - 1, s);         Cover(tr + s, tc, tr + s, tc + s - 1, s);         Cover(tr + s, tc + s, tr + s, tc + s, s);     }     else if (dr >= tr + s&&dc<tc + s)     {         Cover(tr + s, tc, dr, dc, s);          Board[tr + s - 1][tc + s - 1] = t;         Board[tr + s - 1][tc + s] = t;         Board[tr + s][tc + s] = t;          Cover(tr, tc, tr + s - 1, tc + s - 1, s);         Cover(tr, tc + s, tr + s - 1, tc + s, s);         Cover(tr + s, tc + s, tr + s, tc + s, s);     }     else  if (dr >= tr + s&&dc>=tc + s)     {         Cover(tr + s, tc + s, dr, dc, s);          Board[tr + s - 1][tc + s - 1] = t;         Board[tr + s - 1][tc + s] = t;         Board[tr + s][tc + s - 1] = t;          Cover(tr, tc, tr + s - 1, tc + s - 1, s);         Cover(tr, tc + s, tr + s - 1, tc + s, s);         Cover(tr + s, tc, tr + s, tc + s - 1, s);     } } void OutputBoard(int size) {     for (int i = 0; i < size; i++)     {         for (int j = 0; j <size; j++)         {             printf("%6d", Board[i][j]);         }         printf("/n");     } }  int main() {     int size = 1, x, y, i, j, k;     scanf("%d", &k);     for (i =1; i <= k; i++)         size = size * 2;     printf("input incomplete pane/n ");     scanf("%d %d", &x, &y);     Cover(0, 0, x, y, size);     OutputBoard(size);     return 0; } 

金块问题

老板有一袋金块（共n块，n是2的幂，n>=2），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。用最少的比较次数找出最重和最轻的金块。

 #include<stdio.h> #define  N  8 float a[N] = {4.5,2.3,3.4,1.2,6.7,9.8,5,6}; void maxmin(float &fmax, float &fmin, int i, int j) {     int mid;     float lmax, lmin, rmax, rmin;     if (i == j)     {         fmax = a[i];         fmin = a[i];     }     else if(i==j-1)     {         if (a[i] < a[j])         {             fmax = a[j];             fmin = a[i];         }         else         {             fmax = a[i];             fmin = a[j];         }     }     else     {         mid = (i + j) / 2;         maxmin(lmax, lmin,i, mid);         maxmin(rmax, rmin,mid + 1, j);         if (lmax > rmax)             fmax = lmax;         else             fmax = rmax;          if (lmin > rmin)             fmin = rmin;         else             fmin = lmin;     } }  int main() {     float max, min;     maxmin(max, min, 0, N - 1);     printf("Max=%.1f/nMin=%.1f/n", max, min);     return 0; } 

4.贪心法

贪心法是逐步获得最优解，解决最优化问题时的一种简单但适用范围有限的策略。它没有固定的算法框架，算法设计的关键是贪婪策略的选择，选择的贪婪策略要具有无后向性。贪婪策略面对问题仅考虑当前局部信息便做出决策，也就是使用贪婪算法的前提是局部最优策略能导致产生全局最优解。

键盘输入一个高精度的正整数n,去掉其中任意s个数字后剩下的数字按原来左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。

 #include<stdio.h> int length(const char s[]) {     int i = 0;     if (s == NULL)     {         return 0;     }     while (s[i] != '/0')     {         ++i;     }    return i; }  void deleteNum(char* n, int b, int k) {     int i;     for (i = b;i < length(n) - k;i++)         n[i] = n[i + k];     n[i] = '/0'; }  int main() {     char n[100];     int s, i, j, j1, c, data[100], len;     scanf("%s", n);     scanf("%d", &s);     len = length(n);         if (s > len)     {         printf("data error");         return 0;     }     j1 = 0;          for (i = 1;i <= s;i++)     {         for (j = 0; j < length(n); j++)         {             if (n[j] >n[j+1])             {                 deleteNum(n, j, 1);                 if (j >= j1)                     data[i] = j + i;                 else                     data[i] = data[i - 1] - 1;                 j1 = j;                 break;             }             if (j > length(n))                 break;         }     }      for (i = i; i <=s; i++)     {         j = len - i + 1;         deleteNum(n, j, 1);         data[i] = j;     }          while (n[0]=='0'&&length(n)>1)     {         deleteNum(n, 0, 1);     }          printf("/n%s/n", n);     for (i = 1; i <=s; i++)     {         printf("%d ", data[i]);     }     printf("/n"); } 

币种统计问题

某单位给每个职工发工资（精确到元）。为了保证避免临时兑换零钱，且取款的张数最少，发工资前要统计出所有职工的工资所需各种币值（100，50，20，10，5，2，1共7种）的张数。

 #include<stdio.h> int main() {     int i, j, n, GZ, A, B[8] = { 0,100,50,20,10,5,2,1 }, S[8] = { 0,0,0,0,0,0,0,0 };     scanf("%d", &n);     for (i = 1; i <=n;i++)     {         scanf("%d", &GZ);         for (j = 1; j <=7; j++)         {             A = GZ / B[j];             S[j] = S[j] + A;             GZ = GZ - A*B[j];         }     }     for (i = 1; i <=7; i++)     {         printf("%d----%d/n", B[i], S[i]);     }     printf("/n"); } 

埃及分数

设计一个算法，把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为1的分数。如7/8=1/2+1/3+1/24

 #include<stdio.h> int main() {     int a, b, c,i=0;     printf("input a element:");     scanf("%d", &a);     printf("input denominator:");     scanf("%d", &b);     if (a >= b)     {         printf("input error");     }     else     {         if (a == 1 || b%a == 0)         {             printf("%d/%d=%d/%d/n", a, b, 1, b / a);         }         else         {             while (a!=1)             {                 c = b / a + 1;                 a = a*c - b;                 b = b*c;                 printf("1/%d+", c);                  if (b%a == 0 || a == 1)                 {                         printf("1/%d", b / a);                         a = 1;                 }             }             printf("/n");         }     } } 

5.动态规划

动态规划主要针对最优化问题，它的决策不是线性而是全面考虑各种不同的情况分别进行决策，最后通过多阶段的决策逐步找出问题的最终解。

适用条件：

最优化原理（最优子结构）

无后向性（某状态以后过程不会影响以前）

子问题重叠（子问题不独立，一个子问题在下一阶段决策时可能被多次使用到）

基本思想：

把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。

步骤：

划分阶段（划分为无后向性若干子阶段）

选择状态（罗列所出现状态，要满足无后效性）

确定决策并写出状态转移方程

0-1背包问题

给定N个物品和一个背包。物品i的重量是Wi ,其价值为Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得装入背包的物品的总价值为最大？（在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。）

 #include<stdio.h> int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值 int max(int a, int b) {     if (a >= b)      return a;   else return b; }  int KnapSack(int n, int w[], int v[], int x[], int C) {     int i, j;     for (i = 0; i <= n; i++)        V[i][0] = 0;     for (j = 0; j <= C; j++)        V[0][j] = 0;     for (i = 0; i <= n - 1; i++)         for (j = 0; j <= C; j++)             if (j<w[i])                V[i][j] = V[i - 1][j];             else               V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]);             j = C;             for (i = n - 1; i >= 0; i--)             {                 if (V[i][j]>V[i - 1][j])                 {                     x[i] = 1;                j = j - w[i];                 }                 else                     x[i] = 0;             }             printf("选中的物品是:/n");             for (i = 0; i < n; i++)                 if (x[i])                     printf("%d ", i + 1);             printf("/n");             return V[n - 1][C]; } int main() {     int n, i, v[200], w[200], x[200], c;     printf("请输入背包的容量:");     scanf("%d", &c);      printf("请输入物品的个数:");     scanf("%d", &n);      for (i = 0; i < n; i++)     {         scanf("%d%d", &v[i], &w[i]);         x[i] = 0;     }     KnapSack(n, w, v, x, c);     return 0; }