`

递归与分治策略（二）：超大阶乘的实现

F#算法编程J#C 
阅读更多

递归与分支策略：
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)，呵呵。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    递归与分治策略 递归与分治策略

    分治与递归的关系密切，递归常常是实现分治策略的工具。在 Ackerman 函数中，虽然函数定义本身是递归的，但也可以转换为非递归形式。然而，递归版本往往更直观，更容易理解问题的本质。 在计算复杂度上，递归和分治...

    递归与分治策略

    ### 递归与分治策略 #### 一、递归与分治策略概述 递归与分治策略是一种广泛应用于计算机科学和算法设计中的方法。这种方法的核心思想是将复杂问题分解为若干个相同类型的子问题，然后递归地解决这些子问题，最后...

    C 语言程序设计：递归与分治策略.ppt

    C语言程序设计：递归与分治策略 递归和分治策略是C语言程序设计中的两个重要概念。递归是一种算法设计技术，通过将问题分解成更小的子问题，并递归地解决这些子问题来解决原问题。分治策略是将问题分解成更小的子...

    NOIP普及讲座1-递归与分治(C++版).pdf

    #### 非递归方式实现阶乘： ```cpp int factorial(int n) { int result = 1; for (int i = 1; i ; ++i) { result *= i; } return result; } ``` #### 分析： - 通过循环而非递归来实现，避免了递归可能导致的...

    c语言分治法求众数重数-五大常见算法策略之——递归与分治策略，算法数据结构

    以下我们将探讨几种基于递归和分治策略的算法，包括Fibonacci数列、阶乘计算和小青蛙跳台阶问题。 首先，Fibonacci数列是递归的一个经典例子。递归定义了一个数列，其中每个数是前两个数的和。在C语言中，我们可以...

    算法递归与分治

    在计算机科学领域，算法是解决问题的关键工具，而“递归与分治”是算法设计中极为重要的策略。本文将深入探讨这两个概念，并结合代码解析，帮助读者理解和掌握它们。 首先，我们来理解“递归”。递归是一种在函数...

    第2章递归与分治策略.pptx

    《第2章 递归与分治策略》 递归与分治策略是计算机科学中重要的算法设计思想，尤其在解决复杂问题时显得尤为重要。本章主要探讨如何理解和运用这两种方法，以解决实际编程问题。 **一、递归** 递归是一种函数或...

    数学ch递归与分治策略PPT学习教案.pptx

    《数学ch递归与分治策略》 在数学和计算机科学中，递归与分治策略是解决问题的重要方法。递归是一种自包含的解决问题的方法，它通过将问题分解成更小的子问题来解决原问题。分治策略则是将一个大问题分解成若干个...

    C++语言程序设计：递归与分治策略.ppt

    **C++语言程序设计：递归与分治策略** 在编程领域，递归和分治策略是解决问题的两种重要方法，特别是在C++这样的高级编程语言中。递归是指一个函数在其定义中调用自身的过程，而分治策略是一种将复杂问题分解为多个...

    递归与分治策略PPT学习教案.pptx

    递归与分治策略是计算机科学中两种重要的算法思想，广泛应用于解决复杂问题。递归是一种函数或过程在定义中直接或间接地调用自身的技术，使得问题的解决方案可以通过更小规模的同类问题的解来构建。递归的两个关键...

    递归与分治策略计算机算法设计与分析第PPT学习教案.pptx

    递归与分治策略是计算机科学中用于解决复杂问题的两种重要方法，它们在算法设计与分析中占有核心地位。递归是一种自相似的解决问题的方法，它通过将问题分解为规模更小但结构相同的子问题来求解。而分治策略则是一种...

    《算法设计与分析》实验报告：实验一（分治策略）

    总结来说，这个实验报告着重于理解和应用分治策略，通过实现二分搜索、合并排序和快速排序等算法，以及探索阶乘计算的不同方法，加深了对分治算法设计和分析的理解。同时，通过实验数据分析，进一步掌握了算法效率的...

    递归与分治策略（从概念原理到多个实例的详细讲解）

    递归与分治策略，其中有用到数学归纳法。阶乘函数，Fibonacci数列，基于递归的插入排序，时间递归方程和复杂性分析，整数划分问题，Hanoi塔问题，分治法的适用条件，二分搜索算法，大整数的乘法，Strassen矩阵乘法，...

    递归与分治策略讲义课件.pptx

    【递归】与【分治策略】是计算机科学中解决问题的两种重要方法。递归是一种在函数或子程序中调用自身的技术，它基于数学和逻辑的自我参照性质。一个递归函数通常包括两个关键部分：边界条件和递归模式。边界条件是...

    算法思想——递归与分治

    算法思想——递归与分治 递归和分治是两种常用的算法思想，它们可以单独使用，也可以结合使用以解决复杂的问题。下面我们将详细探讨这两种算法思想。 递归是一种算法思想，它的基本思想是将一个问题分解成一个或多...

    中科大 算法导论 课件（全套4）递归和分治策略

    《中科大 算法导论 课件（全套4）递归和分治策略》这一课件由庄连生教授于2010年春季在中国科学技术大学教授，旨在深入探讨算法设计中的核心概念——递归与分治策略。递归是一种函数或算法直接或间接调用自身的编程...

Magicbox
Global site tag (gtag.js) - Google Analytics