基础算法(二)

jopen 9年前

主要内容:

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'&≤ngth(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;  }
</div>

来自: http://www.cnblogs.com/czhwust/p/algorithm_and_ds2.html