算法：下落的金字塔小球
题目是这样的：题目大概是这样的，一个金字塔，它的每个位置都有一个数字(如下图所示)，顶端有一个小球，小球下落时经过任何位置都是等概率的。现在要求的是小球从顶端下落到低端的路径中，数字和最大的路径
我的解法是用“动态规划法”，用一个二维数组pyrimid表示当前的金字塔，在小球的下落过程中，对于每个位置pyrimid[i]][j]，它的前一个位置只有两个选择pyrimid[i-1][j-1]或者pyrimid[i-1][j]，因此我的算法就是依次计算每个位置的累计数字值，然后在最后一层选取最大的。下落路径可以一步一步反推回去，它的程序如下：
-
#include <stdio.h>
-
#include <stdlib.h>
-
#define N 100
-
int max(int a, int b){
-
return a>b?a:b;
-
}
-
-
void printPyrimid(int pyrimid[][N], int height){
-
int i,j;
-
for(i=0; i<height; i++){
-
for(j=height; j>=i; j--)
-
for(j=0; j<=i; j++){
-
}
-
}
-
}
-
-
void printSolution(int pyrimid[][N], int path[][N], int height, int maxIndex){
-
int i,j;
-
-
int tracer[N];
-
tracer[height-1] = maxIndex;
-
for(i=height-1; i>0; i--){
-
if(path[i][maxIndex]==path[i-1][maxIndex-1]+pyrimid[i][maxIndex])
-
tracer[i-1]=maxIndex-1;
-
else
-
tracer[i-1]=maxIndex;
-
maxIndex = tracer[i-1];
-
}
-
-
for(i=0; i<height; i++){
-
for(j=height; j>=i; j--)
-
for(j=0; j<=i; j++){
-
if(j == tracer[i])
-
else
-
}
-
}
-
}
-
-
int maxSum(int pyrimid[][N], int height){
-
int i, j;
-
int path[N][N];
-
for(i=0; i<height; i++)
-
for(j=0; j<=i; j++){
-
if(i==0)
-
path[i][j] = pyrimid[i][j];
-
else if(j>0&&j<i)
-
path[i][j] = max(path[i-1][j-1], path[i-1][j])+pyrimid[i][j];
-
else if(j==0)
-
path[i][j] = path[i-1][j]+pyrimid[i][j];
-
else
-
path[i][j] = path[i-1][j-1]+pyrimid[i][j];
-
}
-
-
int maxIndex = 0;
-
for(j=0; j<height; j++){
-
if(path[height-1][j]>path[height-1][maxIndex])
-
maxIndex = j;
-
}
-
printSolution(pyrimid, path, height, maxIndex);
-
return path[height-1][maxIndex];
-
}
-
-
-
int main(int argc, char *argv[]){
-
int i,j;
-
int pyrimid[N][N];
-
int height = 11;
-
-
srand((unsigned)time(0));
-
-
for(i=0; i<height; i++)
-
for(j=0; j<=i; j++){
-
pyrimid[i][j] = random()%100;
-
}
-
printPyrimid(pyrimid, height);
-
}
不知道有没有更好的方法，欢迎留言讨论。
评论 (0)
yxjoey
最新评论
最新留言
友情链接
我的豆瓣收藏
浏览计数器
62367