yxCoding

I am a coder

算法:下落的金字塔小球

yxjoey posted @ 2008年3月31日 08:57 in C语言 with tags c 程序 , 1538 阅读

题目是这样的:题目大概是这样的,一个金字塔,它的每个位置都有一个数字(如下图所示),顶端有一个小球,小球下落时经过任何位置都是等概率的。现在要求的是小球从顶端下落到低端的路径中,数字和最大的路径


我的解法是用“动态规划法”,用一个二维数组pyrimid表示当前的金字塔,在小球的下落过程中,对于每个位置pyrimid[i]][j],它的前一个位置只有两个选择pyrimid[i-1][j-1]或者pyrimid[i-1][j],因此我的算法就是依次计算每个位置的累计数字值,然后在最后一层选取最大的。下落路径可以一步一步反推回去,它的程序如下:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define N 100
  4. int max(int a, int b){
  5.   return a>b?a:b;
  6. }
  7.  
  8. void printPyrimid(int pyrimid[][N], int height){
  9.   int i,j;
  10.   for(i=0; i<height; i++){
  11.     for(j=height; j>=i; j--)
  12.       printf("  ");
  13.     for(j=0; j<=i; j++){
  14.       printf("%4d", pyrimid[i][j]);
  15.     } 
  16.     printf("\n");
  17.   }
  18. }
  19.  
  20. void printSolution(int pyrimid[][N], int path[][N], int height, int maxIndex){
  21.   int i,j;
  22.  
  23.   int tracer[N];
  24.   tracer[height-1] = maxIndex;
  25.   for(i=height-1; i>0; i--){
  26.     if(path[i][maxIndex]==path[i-1][maxIndex-1]+pyrimid[i][maxIndex])
  27.       tracer[i-1]=maxIndex-1;
  28.     else
  29.       tracer[i-1]=maxIndex;
  30.     maxIndex = tracer[i-1];
  31.   }
  32.  
  33.   for(i=0; i<height; i++){
  34.     for(j=height; j>=i; j--)
  35.       printf("  ");
  36.     for(j=0; j<=i; j++){
  37.       if(j == tracer[i])
  38.         printf("%4d*", path[i][j]);
  39.       else
  40.         printf("%4d", path[i][j]);
  41.     } 
  42.     printf("\n");
  43.   }
  44. }
  45.  
  46. int maxSum(int pyrimid[][N], int height){
  47.   int i, j;
  48.   int path[N][N];
  49.   for(i=0; i<height; i++)
  50.     for(j=0; j<=i; j++){
  51.       if(i==0)
  52.         path[i][j] = pyrimid[i][j];
  53.       else if(j>0&&j<i)
  54.         path[i][j] = max(path[i-1][j-1], path[i-1][j])+pyrimid[i][j];
  55.       else if(j==0)
  56.         path[i][j] = path[i-1][j]+pyrimid[i][j];
  57.       else
  58.         path[i][j] = path[i-1][j-1]+pyrimid[i][j];
  59.     }
  60.  
  61.   int maxIndex = 0;
  62.   for(j=0; j<height; j++){
  63.     if(path[height-1][j]>path[height-1][maxIndex])
  64.       maxIndex = j;
  65.   }
  66.   printSolution(pyrimid, path, height, maxIndex);
  67.   return path[height-1][maxIndex];
  68. }
  69.  
  70.  
  71. int main(int argc, char *argv[]){
  72.   int i,j;
  73.   int pyrimid[N][N];
  74.   int height = 11;
  75.  
  76.   srand((unsigned)time(0));
  77.  
  78.   for(i=0; i<height; i++)
  79.   for(j=0; j<=i; j++){
  80.     pyrimid[i][j] = random()%100;
  81.   }
  82.   printPyrimid(pyrimid, height);
  83.   printf("maxSum:%d \n", maxSum(pyrimid, height));
  84. }

不知道有没有更好的方法,欢迎留言讨论。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter