`

递归与分治策略(二):超大阶乘的实现

阅读更多

递归与分支策略:
1.例子一:阶乘
说到递归,不得不提下数学归纳法。数学归纳法是一种通过自身的语汇定义某事物自己的方法。
用自身定义某事物自身的方法看起来像是在绕圈子,但是事实上他是完全正确的(假设有一个基值的情况)

阶乘在概念上和三角数字式类似的,只是用*取代了+而已。
请看下面的式子:
三角数字:f(n)=f(n-)+n;
阶乘:n!=(n-1)!*n;<==>f(n)=f(n-1)*n;

A.阶乘的编程实现:

public long factorial(int n){//关于返回值的类型,小的话用int,long
  if(n==0)
  return 1;
  else
  return factorial(n-1)*n;
}
 



B.补充:求超大数n的阶乘,使用math包下的BigInteger

先介绍下BigInteger和BigDecimal包装类型(没有基本类型),是java.math包下的类,不是java.lang.Math:

Java提供了两个用于高精度计算的类:BigInteger和BigDecimal。虽然它们大体上属于“包装器类”的范畴,但两者都没有对应的基本类型。不过,这两个类包含的方法,提供的操作与对基本类型所能执行的操作相似。也就是说,能作用于int或float的操作,也同样能作用于BigInteger或BigDecimal。只不过必须以方法调用方式取代运算符方式来实现。由于这么做复杂了许多,所以运算速度会比较慢,相比而言,int和float是以速度取代了精度。

BigInteger支持任意精度的整数。也就是说,在运算中,可以准确地表示任何大小的整数值,而不会丢失任何信息。

常用方法:

abs()  //返回其值是此BigInteger的绝对值的BigInteger。
   add(BigInteger val)  //返回其值为(this+val)的BigInteger。
   subtract(BigInteger val)  //返回其值为(this-val)的BigInteger。
   multiply(BigInteger val)  // 返回其值为(this*val)的BigInteger。
   divide(BigInteger val)  //返回其值为(this/val)的BigInteger。
   remainder(BigInteger val)  //返回其值为(this%val)的BigInteger。
   compareTo(BigInteger val)  //将此BigInteger与指定的BigInteger进行比较。返回值1、0、-1分别表示大于、等于、小于
   pow(int exponent)  //返回当前大数的exponent次幂。
   toString()  //返回此BigInteger的十进制字符串表示形式。
   toString(int radix)  //返回此BigInteger的给定基数(radix进制)的字符串表示形式。 
 


BigDecimal支持任何精度的定点数,例如,可以用它进行精确的货币运算。

它可以用来表示任意精度的有符号十进制数。BigDecimal 由任意精度的整数非标度值 和 32 位的小数标度 (scale) 组成。如果为零或正数,则标度是小数点后的位数。BigDecimal 类提供以下操作:算术、标度操作、舍入、比较、哈希算法和格式转换。toString() 方法提供 BigDecimal 的规范表示形式。 BigDecimal 类使用户能完全控制舍入行为

使用例子:

BigDecimal bigDecimal = new BigDecimal(Math.PI);
bigDecimal = bigDecimal.setScale(2,BigDecimal.ROUND_DOWN);//接近零的舍入模式取PI值小数点后面二位
->3.14
 



使用BigInteger实现10000!的算法:

package DataStructures_Algorithm;

import java.math.BigInteger;

public class FactorialBigIntegerTest {

    public static void main(String[] args) {
        System.out.println(factorial(10000));
       
    }
   
    private static final BigInteger factorial(int n){
        BigInteger bigInteger=new BigInteger(""+n);
        if(n==0)
            return BigInteger.ONE;
        else
            return factorial(n-1).multiply(bigInteger);
       
       
    }

}
 



扩展有这样一组数字序列0,1,1,2,3,5,8........,求第100个数是多少!

很明显:第n项的值

           n=1,f(1)=0;
           n=2,f(2)=1;
           n=3,f(3)=f(1)+f(2)=0+1=1;
           n=4,f(4)=f(2)+f(3)=1+1=2;
           n=5,f(5)=f(3)+f(4)=1+1=1+2=3;
           n=6,f(6)=f(4)+f(5)=2+3=5;
           ..........................
           n=n,f(n)=f(n-2)+f(n-1);
编程实现f(100):这里用数组实现,用递归没效率

private static final BigInteger distributePoker(int n) {
        // BigInteger数组
        BigInteger[] resultBigInteger = new BigInteger[n];
        for (int i = 0; i < n; i++) {
            if (i == 0)
                resultBigInteger[i] = BigInteger.ZERO;
            if (i == 1)
                resultBigInteger[i] = BigInteger.ONE;
            if(i>=2)
                resultBigInteger[i] = resultBigInteger[i - 2]
                        .add(resultBigInteger[i - 1]);
        }
        return resultBigInteger[n - 1];

}
 


                                                
C.不使用BigInteger,计算超大数阶乘算法——>用整型数组保存每位数的结果,最后返回字符串,效率最高

private static final String ArrayStringFactorial(int n) {
        int a[] = new int[200];// 确保保存最终运算结果的数组位数足够大,200位的数已经够大了
        int carry = 0;// 进位标志位
        int digit = 1;// 位数
        a[0] = 1;// 将结果先初始化为1
        int temp;// 阶乘的任一元素与临时结果的某位的乘积结果
        StringBuffer resultStr = new StringBuffer();

        for (int i = 2; i <= n; ++i)// 开始阶乘,阶乘元素从2开始依次“登场”
        {
            // 按最基本的乘法运算思想来考虑,将临时结果的每位与阶乘元素相乘
            for (int j = 1; j <= digit; ++j) {
                temp = a[j - 1] * i + carry;// 相应阶乘中的一项与当前所得临时结果的某位相乘(加上进位)
                a[j - 1] = temp % 10;// 更新临时结果的位上信息
                carry = temp / 10; // 看是否有进位
            }
            while (carry!=0?true:false)// 如果有进位
            {
                a[(++digit) - 1] = carry % 10;// 新加一位,添加信息。位数增1
                carry /= 10; // 看还能不能进位
            }
        }
        for (int i = digit; i >= 1; --i) {
            resultStr.append(a[i - 1]);
        }
        return resultStr.toString();

}
 


分治策略 请继续关注下文。。。。。。。。。。

分享到:
评论
14 楼 worldterminator 2010-01-03  
阶乘也有分治策略?,斐波那契数倒有个矩阵乘法的做法
13 楼 supersun 2009-12-18  
我也不明白你在说什么,你这个代码是想干什么呢


我原题是这么说的:扩展这样一组数字序列0,1,1,2,3,5,8........,求第100个数是多少!

           n=1,f(1)=0;
           n=2,f(2)=1;
           n=3,f(3)=f(1)+f(2)=0+1=1;
           n=4,f(4)=f(2)+f(3)=1+1=2;
           n=5,f(5)=f(3)+f(4)=1+1=1+2=3;
           n=6,f(6)=f(4)+f(5)=2+3=5;
           ..........................
           n=n,f(n)=f(n-2)+f(n-1);
编程实现f(100):这里用数组实现,用递归没效率(测试了下用递归比20!更大的话几乎半天不出结果)


   1. private static final BigInteger distributePoker(int n) {
   2.         // BigInteger数组
   3.         BigInteger[] resultBigInteger = new BigInteger[n];
   4.         for (int i = 0; i < n; i++) {
   5.             if (i == 0)
   6.                 resultBigInteger[i] = BigInteger.ZERO;
   7.             if (i == 1)
   8.                 resultBigInteger[i] = BigInteger.ONE;
   9.             if(i>=2)
  10.                 resultBigInteger[i] = resultBigInteger[i - 2]
  11.                         .add(resultBigInteger[i - 1]);
  12.         }
  13.         return resultBigInteger[n - 1];
  14. 
  15. }

这里是用数组实现f(n)=f(n-2)+f(n-1)
12 楼 supersun 2009-12-18  
我也不明白你在说什么,你这个代码是想干什么呢


我原题是这么说的:扩展这样一组数字序列0,1,1,2,3,5,8........,求第100个数是多少!

           n=1,f(1)=0;
           n=2,f(2)=1;
           n=3,f(3)=f(1)+f(2)=0+1=1;
           n=4,f(4)=f(2)+f(3)=1+1=2;
           n=5,f(5)=f(3)+f(4)=1+1=1+2=3;
           n=6,f(6)=f(4)+f(5)=2+3=5;
           ..........................
           n=n,f(n)=f(n-2)+f(n-1);
编程实现f(100):这里用数组实现,用递归没效率(测试了下用递归比20!更大的话几乎半天不出结果)


   1. private static final BigInteger distributePoker(int n) { 
   2.         // BigInteger数组 
   3.         BigInteger[] resultBigInteger = new BigInteger[n]; 
   4.         for (int i = 0; i < n; i++) { 
   5.             if (i == 0) 
   6.                 resultBigInteger[i] = BigInteger.ZERO; 
   7.             if (i == 1) 
   8.                 resultBigInteger[i] = BigInteger.ONE; 
   9.             if(i>=2) 
  10.                 resultBigInteger[i] = resultBigInteger[i - 2] 
  11.                         .add(resultBigInteger[i - 1]); 
  12.         } 
  13.         return resultBigInteger[n - 1]; 
  14.  
  15. }

这里是用数组实现f(n)=f(n-2)+f(n-1)
11 楼 xiaoxinfq8 2009-12-18  
不知道那个BigInteger的数组方式(非递归)实现LZ是怎么个意思,我没理解,我觉得应该是这样的
private static final BigInteger distributePoker(int n) {
		// BigInteger数组
		BigInteger[] resultBigInteger = new BigInteger[n + 1];
		for (int i = 0; i <= n; i++) {
			if (i < 2)
				resultBigInteger[i] = BigInteger.ONE;
			else
				resultBigInteger[i] = resultBigInteger[i - 1]
						.multiply(BigInteger.valueOf(i));
		}
		return resultBigInteger[n];
	}
10 楼 supersun 2009-12-17  
<div class="quote_title">Solstice 写道</div>
<div class="quote_div">
<div class="quote_title">supersun 写道</div>
<div class="quote_div">
<p> </p>
<p>
C.不使用BigInteger,计算超大数阶乘算法——&gt;用整型数组保存每位数的结果,最后返回字符串,效率最高</p>
<pre name="code" class="java">private static final String ArrayStringFactorial(int n) {
        int a[] = new int[200];// 确保保存最终运算结果的数组位数足够大,200位的数已经够大了
        int carry = 0;// 进位标志位
        int digit = 1;// 位数
        a[0] = 1;// 将结果先初始化为1
        int temp;// 阶乘的任一元素与临时结果的某位的乘积结果
        StringBuffer resultStr = new StringBuffer();

        for (int i = 2; i &lt;= n; ++i)// 开始阶乘,阶乘元素从2开始依次“登场”
        {
            // 按最基本的乘法运算思想来考虑,将临时结果的每位与阶乘元素相乘
            for (int j = 1; j &lt;= digit; ++j) {
                temp = a[j - 1] * i + carry;// 相应阶乘中的一项与当前所得临时结果的某位相乘(加上进位)
                a[j - 1] = temp % 10;// 更新临时结果的位上信息
                carry = temp / 10; // 看是否有进位
            }
            while (carry!=0?true:false)// 如果有进位
            {
                a[(++digit) - 1] = carry % 10;// 新加一位,添加信息。位数增1
                carry /= 10; // 看还能不能进位
            }
        }
        for (int i = digit; i &gt;= 1; --i) {
            resultStr.append(a[i - 1]);
        }
        return resultStr.toString();

}</pre>
 
<p><br><span style="color: #ff0000;">分治策略</span>
请继续关注下文。。。。。。。。。。</p>
</div>
<p> </p>
<p>你这完全是个 C 程序,结果的位数也限死了。</p>
<p> </p>
<p>在网上随便找了一个C++的:</p>
<p> </p>
<pre name="code" class="cpp">std::vector&lt;int&gt; void cal_factorial(int n)
{
  std::vector&lt;int&gt; a;
  a.push_back(1);

  for (int i = 2; i &lt;= n; ++i) {
    int carry = 0;

    for (int j = 0; j &lt; a.size(); ++j) {
      int temp = a[j] * i + carry;
      a[j] = temp % 10;
      carry = temp / 10;
    }

    while (carry) {
      a.push_back(carry % 10);
      carry /= 10;
    }
  }

  return a;
}</pre>
 
<p> </p>
</div>
<p> </p>
<p>网上的确有很多这样的例子,我也看到过,请仁兄给出好的解决方案,,算法这个东西后人基本上都是在学习前人吧,有几个是原创的啊,你在网上找到的很多也是从经典制作中摘抄的。。。</p>
9 楼 hardPass 2009-12-17  
这个方法得的结果精确不精确啊?
8 楼 Solstice 2009-12-17  
<div class="quote_title">supersun 写道</div>
<div class="quote_div">
<p> </p>
<p>
C.不使用BigInteger,计算超大数阶乘算法——&gt;用整型数组保存每位数的结果,最后返回字符串,效率最高</p>
<pre name="code" class="java">private static final String ArrayStringFactorial(int n) {
        int a[] = new int[200];// 确保保存最终运算结果的数组位数足够大,200位的数已经够大了
        int carry = 0;// 进位标志位
        int digit = 1;// 位数
        a[0] = 1;// 将结果先初始化为1
        int temp;// 阶乘的任一元素与临时结果的某位的乘积结果
        StringBuffer resultStr = new StringBuffer();

        for (int i = 2; i &lt;= n; ++i)// 开始阶乘,阶乘元素从2开始依次“登场”
        {
            // 按最基本的乘法运算思想来考虑,将临时结果的每位与阶乘元素相乘
            for (int j = 1; j &lt;= digit; ++j) {
                temp = a[j - 1] * i + carry;// 相应阶乘中的一项与当前所得临时结果的某位相乘(加上进位)
                a[j - 1] = temp % 10;// 更新临时结果的位上信息
                carry = temp / 10; // 看是否有进位
            }
            while (carry!=0?true:false)// 如果有进位
            {
                a[(++digit) - 1] = carry % 10;// 新加一位,添加信息。位数增1
                carry /= 10; // 看还能不能进位
            }
        }
        for (int i = digit; i &gt;= 1; --i) {
            resultStr.append(a[i - 1]);
        }
        return resultStr.toString();

}</pre>
 
<p><br><span style="color: #ff0000;">分治策略</span>
请继续关注下文。。。。。。。。。。</p>
</div>
<p> </p>
<p>你这完全是个 C 程序,结果的位数也限死了。</p>
<p> </p>
<p>在网上随便找了一个C++的:</p>
<p> </p>
<pre name="code" class="cpp">std::vector&lt;int&gt; void cal_factorial(int n)
{
  std::vector&lt;int&gt; a;
  a.push_back(1);

  for (int i = 2; i &lt;= n; ++i) {
    int carry = 0;

    for (int j = 0; j &lt; a.size(); ++j) {
      int temp = a[j] * i + carry;
      a[j] = temp % 10;
      carry = temp / 10;
    }

    while (carry) {
      a.push_back(carry % 10);
      carry /= 10;
    }
  }

  return a;
}</pre>
 
<p> </p>
7 楼 robertliudeqiang 2009-12-17  
BigInteger bigInteger=new BigInteger(""+n);

不如改成

BigInteger bigInteger=BigInteger.valueOf(n);

好,多谢楼主分享。
6 楼 supersun 2009-12-16  
liyun_1981 写道
纠正一个地方,把while (carry!=0?true:false)改为while (carry!=0),呵呵。


谢谢,昨晚上肯定真喝多了,居然写出这样的条件,O(∩_∩)O哈哈~
5 楼 supersun 2009-12-16  
lioncin 写道
我记得再华科的算法书上有这么一个实例吧


难道此算法是传说中“华科”的专利?国内外计算机科学的经典教材中都有这么一例吧,我写出来只是督促自己坚持学习下去罢了,O(∩_∩)O哈哈~
我看的是《Data Structures & Algorithms in Java 2nd Edition》
4 楼 supersun 2009-12-16  
Elminster 写道
话说,分治策略在哪?


分治在后面文章中会讨论的!
3 楼 lioncin 2009-12-16  
我记得再华科的算法书上有这么一个实例吧
2 楼 Elminster 2009-12-16  
话说,分治策略在哪?
1 楼 liyun_1981 2009-12-16  
纠正一个地方,把while (carry!=0?true:false)改为while (carry!=0),呵呵。

相关推荐

Global site tag (gtag.js) - Google Analytics