1. 动态规划 备忘录法
备忘录方法采用自顶向下方式,为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解。
/*
@author: jarg
@TODO 动态规划 - 备忘录法 求解二项式系数
*/
import java.io.*;
import java.util.*;
public class Binomial
{
/*
Map<K,V>中K,V说明
K: n,m组成的字符串
V: value求解出的值
demo: 备忘录,保存已经求解出的子问题的解
*/
public static Vector<Map> demo = new Vector<Map>();
public static void main(String[] args)
{
InputStreamReader ir = new InputStreamReader(System.in);
try
{
System.out.print("输入参数n: ");
int n = Integer.parseInt("" + (char)ir.read());
/* 过滤输入参数n时,末尾的回车,换行 */
if((char)ir.read() == '\r' || (char)ir.read() == '\n')
{
ir.read();
}
System.out.print("输入参数m: ");
int m = Integer.parseInt("" + (char)ir.read());
System.out.println("Binomial("+ n + "," + m +")=" + Binomial(n,m));
}
catch(Exception e)
{
System.out.println("invalid input.");
}
}
/* 求二项式系数 */
public static int Binomial(int n,int m)
{
/* 边界条件 */
if(n==m || m==0)
{
return 1;
}
int date = readDate(n,m);
if(date>0)
{
/*
子问题已经计算过
读取保存在备忘录中的数据
*/
return date;
}
else
{
/*
子问题未计算过
解出子问题,将数据保存在备忘录中
*/
int result = Binomial(n-1,m) + Binomial(n-1,m-1);
writeDate(n,m,result);
return result;
}
}
/* 从备忘录中读取数据 */
public static int readDate(int n,int m)
{
for(int i=0;i<demo.size();i++)
{
Map<String,Integer> date = new HashMap<String,Integer>();
date = demo.get(i);
if(date.get("" + n + m) != null)
{
return date.get("" + n + m);
}
}
return 0;
}
/* 向备忘录中写入数据 */
public static void writeDate(int n,int m,int value)
{
Map<String,Integer> date = new HashMap<String,Integer>();
date.put("" + n + m,value);
demo.add(date);
}
}
2. 动态规划 迭代法:
迭代法采用自底向上方式,保存已求解的子问题,需要时取出,消除对某些子问题的重复求解.
/*
@author: jarg
@TODO: 动态规划 - 求解二项式系数
*/
import java.io.InputStreamReader;
public class Binomial
{
public static void main(String[] args)
{
InputStreamReader ir = new InputStreamReader(System.in);
try
{
System.out.print("输入参数n: ");
int n = Integer.parseInt("" + (char)ir.read());
/* 过滤输入参数n时,末尾的回车,换行 */
if((char)ir.read() == '\r' || (char)ir.read() == '\n')
{
ir.read();
}
System.out.print("输入参数m: ");
int m = Integer.parseInt("" + (char)ir.read());
System.out.println("Binomial("+ n + "," + m +")=" + binomial(n,m));
}
catch(Exception e)
{
System.out.println("invalid input.");
}
}
/* 求二项式系数 */
public static int binomial(int n, int m)
{
int value[] = new int[n+1];
for(int i=0;i<=n;i++)
{
value[i] = 1;
/* 边界条件m=0,n=m的情况 */
for(int j=i-1;j>0;j--)
{
value[j] = value[j] + value[j-1];
}
}
return value[m];
}
}
分享到:
相关推荐
完整代码 博文链接:https://jarg.iteye.com/blog/859391
杨辉三角是中国古代数学的杰出研究成果之一,它把二项式系数图形化,把组合数内在的一些代数性质直观地从图形中体现出来,是一种 离散型的数与形 的结合 :spade_suit: 代码实现 题目的要求是:设计代码,实现打印...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 浮点数转换为...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
数据结构篇 042 插入排序 043 希尔排序 044 冒泡排序 045 快速排序 046 选择排序 047 堆排序 048 归并排序 049 基数排序 050 二叉搜索树操作 051 二项式系数递归 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
然后使用通货膨胀率的马尔可夫转移概率构造一个n周期非重组二项式树。 终端节点值是使用递归计算的(因为该过程是自回归的)。 然后,以所有转移概率为概率测度,对所有终端节点取期望值。 结果值是预期的通货膨胀率...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 浮点数转换为...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 ...