1、三角数塔问题 设有一个三角形的数塔,顶点为根结点,每个结点有一个整数值。从顶点出发,可以向左走或向右走,如图所示:
要求从根结点开始,请找出一条路径,使路径之和最大,只要输出路径的和。 【代码】 // // 例题1 三角数字塔问题 // // #include <stdio.h> #include <stdlib.h>
#define MAXN 101
int n,d[MAXN][MAXN]; int a[MAXN][MAXN];
void fnRecursive(int,int); //递推方法函数声明 int fnMemorySearch(int,int); //记忆化搜索函数声明
int main() { int i,j; printf("输入三角形的行数n(n=1-100):\n"); scanf("%d",&n); printf("按行输入数字三角形上的数(1-100):\n"); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d",&a[i][j]); for(i=1; i<=n; i++) for(j=1; j<=i; j++) d[i][j]=-1;//初始化指标数组 printf("递推方法:1\n记忆化搜索方法:2\n"); int select; scanf("%d",&select); if(select==1) { fnRecursive(i,j);//调用递推方法 printf("\n%d\n",d[1][1]); } if(select==2) { printf("\n%d\n",fnMemorySearch(1,1));//调用记忆化搜索方法 } else printf("输入错误!");
return 0; }
void fnRecursive(int i,int j) //递推方法实现过程 { for(j=1; j<=n; j++) d[n][j]=a[n][j]; for(i=n-1; i>=1; i--) for(j=1; j<=i; j++) d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]); }
int fnMemorySearch(int i,int j) //记忆化搜索实现过程 { if(d[i][j]>=0) return d[i][j]; if(i==n) return(d[i][j]=a[i][j]); if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1)) return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j))); else return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1))); }
2、硬币问题 问题描述:有n种硬币,面值分别为V1,V2,…,Vn, 每种有无限多。给定非负整数S,可以选用多少硬币,使得面值之和恰好为S,输出硬币数目的最小值和最大值。(1<=n<=100,0<=S<=10000,1<=Vi<=S) 【代码】 // // 例题1 硬币问题 // // #include <stdio.h> #include <stdlib.h>
#define INF 100000000 #define MAXNUM 10000 #define MONEYKIND 100
int n,S; int V[MONEYKIND]; int min[MAXNUM],max[MAXNUM];
void dp(int*,int*); //递推方法函数声明 void print_ans(int*,int); //输出函数声明
int main() { |