阶乘设计的演化过程
1 递归方式
public static int factorial(int n){
if (n > 0) return 1;
return n * factorial(n-1);
}
2 封装进一个工具类
public class FactorialUtil{
public static int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n-1);
}
}
3 迭代实现
public class FactorialUtil{
public static int factorial(int n){
int ret = 1;
for (int i = 1; i <= n; ++i) ret *= i;
return ret;
}
}
4 解决返回值超出整型最大值问题
public class FactorialUtil{
public static BigInteger factorial(int n){
BigInteger ret = BigInteger.ONE;
for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
return ret;
}
}
5 加入缓存机制
public class FactorialUtil{
static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();
public static BigInteger factorial(int n){
BigInteger ret;
if (n == 0) return BigInteger.ONE;
if (null != (ret = cache.get(n))) return ret;
ret = BigInteger.valueOf(n).multiply(factorial(n-1));
cache.put(n, ret);
return ret;
}
}
6 使用接口编程,把算法实现推向实现,即使用了策略模式
工具类:
public class FactorialUtil{
private static FactorialUtil singleton;
private FactorialAlgorithm algorithm;
/**
* Default (internal) constructor constructs our default algorithm.
*/
private FactorialUtil()
{
algorithm = new CachedFactorialImplementation();
}
/**
* New initializer which allows selection of the algorithm mechanism
* @param algorithm
*/
public FactorialUtil(FactorialAlgorithm a)
{
algorithm = a;
}
/**
* Default public interface for handling our factorial algorithm. Uses
* the old standard established earlier for calling into our utility class.
* @param n
* @return
*/
public static BigInteger factorial(int n)
{
if (singleton == null) {
// Use default constructor which uses default algorithm
singleton = new FactorialUtil();
}
return singleton.doFactorial(n);
}
/**
* New mechanism which allows us to instantiate individual factorial
* utilitiy classes and invoke customized factorial algorithms directory.
* @param n
* @return
*/
private BigInteger doFactorial(int n)
{
// Defer to our algorithm
return algorithm.factorial(n);
}
}
接口:
public interface FactorialAlgorithm{
BigInteger factorial(int n);
}
缓存实现
public class CachedFactorialImplementation implements FactorialAlgorithm
{
static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();
@Override
public BigInteger factorial(int n)
{
BigInteger ret;
if (n == 0) return BigInteger.ONE;
if (null != (ret = cache.get(n))) return ret;
ret = BigInteger.valueOf(n).multiply(factorial(n-1));
cache.put(n, ret);
return ret;
}
}
循环实现
public class LoopedFactorialImplementation implements FactorialAlgorithm
{
@Override
public BigInteger factorial(int n)
{
BigInteger ret = BigInteger.ONE;
for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
return ret;
}
}
这种方式无法实现运行时动态选择使用哪个实现类。即,无法完成如下的调用。
7 如何实现这种方式的动态调用?
public static void main(String[] args){
System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm");//指定实现方式为cachedAlgorithm
System.out.println("5! = " + FactorialUtil.factorial(5));//系统会使用了cachedAlgorithm方式
}
7.1 用map存储类映射
/**
* Factory class manages the factorial algorithms in our system.
* @author wwoody
*
*/
public class FactorialAlgorithmFactory{//阶乘算法工厂
private static HashMap<String,FactorialAlgorithm> mapping = new HashMap<String,FactorialAlgorithm>();
private static HashMap<String,Class<? extends FactorialAlgorithm>> classMapping = new HashMap<String,Class<? extends FactorialAlgorithm>>();
private static FactorialAlgorithm defaultAlgorithm = new CachedFactorialImplementation();
/** Static initializer registers some of my known classes */
static {
try {
Class.forName("com.chaosinmotion.factorial.LoopedFactorialImplementation");//这个类被注册进了classMapping
Class.forName("com.chaosinmotion.factorial.CachedFactorialImplementation");//这个类被注册进了classMapping
}
catch (ClassNotFoundException e) {
// Should never happen.
}
}
/** Get the default algorithm for computing factorials */
public static FactorialAlgorithm getDefaultAlgorithm()
{
if (defaultAlgorithm == null) {
// Warning: this will fail if for whatever reason CachedFactorialImplementation
// is not in the class path.
defaultAlgorithm = getAlgorithm("cachedAlgorithm");
}
return defaultAlgorithm;
}
/** Get the factorial algorithm specified by name */
public static FactorialAlgorithm getAlgorithm(String name)
{
FactorialAlgorithm f = mapping.get(name);
if (f == null) {
// We haven't created an instance yet. Get it from the class mapping.
Class<? extends FactorialAlgorithm> c = classMapping.get(name);
if (c != null) {
// Create a new instance of the factorial algorithm specified
try {
f = c.newInstance();
mapping.put(name, f);
return f;
}
catch (Exception e) {
// Log the error
Logger.getLogger("com.chaosinmotion.factorial").
warning("Unable to instantiate algorithm " +
c.getCanonicalName() + ", named " + name);
}
}
return getDefaultAlgorithm(); // return something.
}
else return f;
}
/** Register the class so we can construct a new instance if not already initialized */
public static void registerAlgorithm(String name, Class<? extends FactorialAlgorithm> f)
{
classMapping.put(name, f);
}
}
7.2 重写阶乘工具类
public class FactorialUtil{
private static FactorialUtil singleton;
private FactorialAlgorithm algorithm;
/**
* Default (internal) constructor constructs our default algorithm.
*/
private FactorialUtil()
{
String name = System.getProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm");
if (name == null) {
algorithm = FactorialAlgorithmFactory.getDefaultAlgorithm();
} else {
algorithm = FactorialAlgorithmFactory.getAlgorithm(name);
}
}
/**
* New initializer which allows selection of the algorithm mechanism
* @param algorithm
*/
public FactorialUtil(FactorialAlgorithm a)
{
algorithm = a;
}
/**
* Utility to create by name. Calls into FactorialAlgorithmFactory to
* actually get the algorithm.
* @param name
*/
public FactorialUtil(String name)
{
algorithm = FactorialAlgorithmFactory.getAlgorithm(name);
}
/**
* Default public interface for handling our factorial algorithm. Uses
* the old standard established earlier for calling into our utility class.
* @param n
* @return
*/
public static BigInteger factorial(int n)
{
if (singleton == null) {
// Use default constructor which uses default algorithm
singleton = new FactorialUtil();
}
return singleton.doFactorial(n);
}
/**
* New mechanism which allows us to instantiate individual factorial
* utilitiy classes and invoke customized factorial algorithms directory.
* @param n
* @return
*/
private BigInteger doFactorial(int n)
{
// Defer to our algorithm
return algorithm.factorial(n);
}
}
7.3 缓存实现
public class CachedFactorialImplementation implements FactorialAlgorithm
{
static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();
static {
FactorialAlgorithmFactory.registerAlgorithm("cachedAlgorithm", CachedFactorialImplementation.class);//被注册进classMapping
}
@Override
public BigInteger factorial(int n)
{
BigInteger ret;
if (null != (ret = cache.get(n))) return ret;
ret = BigInteger.valueOf(n).multiply(factorial(n-1));
cache.put(n, ret);
return ret;
}
}
7.4 迭代实现
public class LoopedFactorialImplementation implements FactorialAlgorithm
{
static {
FactorialAlgorithmFactory.registerAlgorithm("loopedAlgorithm", LoopedFactorialImplementation.class);//被注册进classMapping
}
@Override
public BigInteger factorial(int n)
{
BigInteger ret = BigInteger.ONE;
for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
return ret;
}
}
7.5 递归实现
public class RecursiveFactorialImplementation implements FactorialAlgorithm
{
static {
FactorialAlgorithmFactory.registerAlgorithm("recursiveAlgorithm", RecursiveFactorialImplementation.class);
}
@Override
public BigInteger factorial(int n)
{
if (n == 0) return BigInteger.ONE;
return BigInteger.valueOf(n).multiply(factorial(n-1));
}
}
7.6 调用例子
public static void main(String[] args){
try {
Class.forName("com.chaosinmotion.factorial.RecursiveFactorialImplementation");
}
catch (ClassNotFoundException e) {
// if this fails, no matter; we'll still use the default implementation.
}
System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "recursiveAlgorithm");
System.out.println("5! = " + FactorialUtil.factorial(5));
}
7.7 总结
程序员想要使用自己的实现类来完成阶乘运算,只需要
- 写一个实现了 FactorialAlgorithm 接口的类
- 在这个类的装载过程里里完成对自己的注册
- 使用
- 装载自己的实现类 Class.forName(…);
- 设置系统属性,供程序从classMap中查找自己的实现类。
8 应用
JDBC Driver 的实现,就是类似方式:
Class.forName("org.gjt.mm.mysql.Driver");
Connection con = DriverManager.getConnection(url,?myLogin", "myPassword");
实际上jdbc driver有一个静态初始化
static {
try {
java.sql.DriverManager.registerDriver(new Driver());
} catch (SQLException E) {
throw new RuntimeException("Can't register driver!");
}
}
参考: http://chaosinmotion.com/blog/?p=622
http://en.wikipedia.org/wiki/Strategy_pattern
Dapple Hou
mmonkeyer@163.com
分享到:
相关推荐
一个实现阶乘功能的JAVA小程序,代码较为简单。
C# 大数阶乘 源程序 用于计算10001以下所有整数的阶乘 删除程序输入数的大小限制 理论上 可用于计算的数可以无限大
"ARM汇编语言程序设计实例解析-阶乘操作" ...ARM汇编语言程序设计-阶乘操作是一个非常重要的知识点,通过这个实例,我们可以了解ARM汇编语言程序设计的思想、流程和实现方法,并且可以应用于各种领域。
java阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘
阶乘算法 阶乘问题 C# 小程序 这个是我用C#写的一个校程序,阶乘问题, 是以前学编程时写的,希望代码对大家有所帮助!
python算阶乘小程序 python算阶乘小程序
在子程序嵌套的情况下,如果一个子程序...递归调用最简单例子是计算阶乘。求N!本身是一个子程序,由于N!是N和(N-1)!的乘积,所以为求(N-1)!必须递归调用求N!的子程序,只是每次调用所使用的参数不同而已。
n的阶乘 C++实现
C++ 阶乘算法实现代码,用C++编写的简单阶乘计算程序。
安徽大学计算机组成原理课程设计微程序实现阶乘
vs2010可以直接打开实现大数阶乘功能,利用数组实现大数阶乘功能。
输入 计算阶乘的数 得到结果 很简单的小程序
自己写的计算阶乘的程序,能近似计算4亿以下的数字的阶乘。并且能精确到100位以上,且可任意设置。希望对你有所帮助
JAVA实现1-10之间的数字的阶乘并且相加。简单的小程序
程序实现在汇编条件下大数的阶乘 代码结合了乘法的实现与通过大数除法输出
求阶乘-c#编写的求阶乘的控制台应用程序,有利于锻炼初学者的逻辑思维能力。
阶乘实现代码,对初学者很有价值,值得看下
这是我用数组实现的大数阶乘,程序并不怎么完善,但是有一定的启发意义,希望可以帮到一些人
这是一个可以求很大的数的阶乘的程序,主要用数组来存取这个很大的数
整数的阶乘(英语:factorial)是所有小于及等于该数的正整数的积,0的阶乘为1。即:n!=1×2×3×…×n。 首先导入math模块,然后调用factorial()函数来计算阶乘。 1 math.factorial(x) import math value = math....