新手跪求一个数列的超大数

Question

斐波那契数列★★
1,1,2,3,5,8,13,21............
这个数列是不是很熟悉？它就是斐波那契数列,问题是朋友给出的,是说要求第n项然后输出来,要求是求10的9次方项是多少,我的写了如下的代马
  
import java.math.BigInteger;
import java.io.*;
import java.util.*;
public class Fibonacci {   
    public static void main(String[] args) {   
        Scanner scan =new Scanner(System.in);
               int n;
               
            n=scan.nextInt();
                
      BigInteger[] fib = new BigInteger[n];    
          fib[0] = BigInteger.ONE;    
        fib[1] = BigInteger.ONE;    
  
        for(int i = 2; i < fib.length; i++)    
           fib[i] = fib[i-1].add(fib[i-2]);    
  System.out.print(fib[n-1]);    
      System.out.println();   
    }   
}  
但我这个只能搞出第一万项来,接着就溢出了算不了第十万项是多少,跪求方法,请教教

Answer 1

呵呵 这个要用大数加法，所有的数字都用字符串表示，
比如 23329+333
当两个数相加的时候先对其两个字符串，然后在对每个字符相加，比如 ‘9’+‘3’-‘0’=12
然后12/10=1 进位，12%10=2 作为当前为的结果，再往后加就是吧进位和下两位字符相加  比如
‘2’+‘3’+1-‘0’=6 进位为零。再下两位  ‘3’+‘3’-‘0’=6
如果java的字符串也装不下结果的话那就放在文件里
只能给你提供思想了 代码就不写了 
 如果要看代码 就去搜搜 大整数加法 代码

Answer 2

对两个大数进行加法运算，可以考虑用ArrayList数组实现

Answer 3

10的9次方？我懒得等了而且也不知道最终会不会OutOfMemery2万是可以的而且最后似乎一行都太长，我的println根本打不出来package test;import java.math.BigDecimal;public class Test1 {
public static void main(String[] args) {
try {
BigDecimal[] fib = new BigDecimal[2];
fib[0] = new BigDecimal("1");
fib[1] = new BigDecimal("1");
System.out.println(fib[0]+"\n"+fib[1]);
for (int i = 0; i < 100000; i++) {
BigDecimal temp = fib[1];
fib[1] = fib[0].add(fib[1]);
fib[0] = temp;
System.out.println(fib[1]);
if(i==20000){
System.out.println("ok");
break;
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
}

Answer 4

....呃楼上的,我写的那个代马也可以运行两万的,只是再高位就不得了,BigDecimal和我用的BigInteger 
是一样的...郁闷,有人能用数组把那个大数写出来吗想看下算法.

Answer 5

嗯，不晓得BigDecimal或BigInteger能支持到多长，如果足够长的话，等待足够长的时间，应该是可以出来的。
ps：
10的9次方啊！假设不会错。
一天＝86400秒
一秒一次需要时间：11574.074074074074074074074074074天。
一秒1万次需要:1.1574天，我的机器似乎没这么好性能，我也等不了哇。

Answer 6

但问题是我连第十万位都不得啊,十万位我同学都能搞出来他用别的编的,而我写的那代马说outofmemary

Answer 7

   1. package test;  
   2.   
   3. public class VeryBigNumAdd {  
   4.   
   5.     public static void main(String[] args) {  
   6.         VeryBigNumAdd vbn = new VeryBigNumAdd();  
   7.         String a = "123453243455535634535252345234677576252241234123523453664563634";  
   8.         String b = "123453243455535634535252345234677576252241234123523453664563634";  
   9.         String result = vbn.doAdd(a, b);  
  10.         System.out.println("result:" + result);  
  11.     }  
  12.   
  13.     String doAdd(String a, String b) {  
  14.         String str = "";  
  15.         int lenA = a.length();  
  16.         int lenB = b.length();  
  17.         int maxLen = (lenA > lenB) ? lenA : lenB;  
  18.         int minLen = (lenA < lenB) ? lenA : lenB;  
  19.         String strTmp = "";  
  20.         for (int i = maxLen - minLen; i > 0; i--) {  
  21.             strTmp += "0";  
  22.         }  
  23.         // 把长度调整到相同  
  24.         if (maxLen == lenA) {  
  25.             b = strTmp + b;  
  26.         } else  
  27.             a = strTmp + a;  
  28.         int JW = 0;// 进位  
  29.         for (int i = maxLen - 1; i >= 0; i--) {  
  30.             int tempA = Integer.parseInt(String.valueOf(a.charAt(i)));  
  31.             int tempB = Integer.parseInt(String.valueOf(b.charAt(i)));  
  32.             int temp;  
  33.             if (tempA + tempB + JW >= 10 && i != 0) {  
  34.                 temp = tempA + tempB + JW - 10;  
  35.                 JW = 1;  
  36.             } else {  
  37.                 temp = tempA + tempB + JW;  
  38.                 JW = 0;  
  39.             }  
  40.             str = String.valueOf(temp) + str;  
  41.         }  
  42.         return str;  
  43.     }  
  44. }  
按照这个改吧，只需要稍微改动一下主函数的一个字符串就可以了，自己动动脑吧

Answer 8

public static void main(String[] args)
{

String s1 = "1";
String s2 = "1";
System.out.println(s1 + "\n" + s2);
for(int i = 0; i <= 5000; i++)
{
String result = addPartition(s2,s1);
System.out.println(result);
System.out.println("长度：" + result.length());
s1 = s2;
s2 = result;
}
}

/**
 * 将分划好的字符串集合循环相加
 * @param val1
 * @param val2
 * @return
 */
public static String addPartition(String val1,String val2)
{
Vector<String> vec1 = new Vector<String>();
Vector<String> vec2 = new Vector<String>();
vec1 = partition(val1);//分划字符串
vec2 = partition(val2); //遍历第二个数的集合
for(int i = 0; i < vec2.size(); i++)
{ String strResult = addition(vec1.get(i),vec2.get(i));//将两个数的段相加 //判断是否有进位，50位为一段，超过50位证明相加有进位
if(strResult.length() > 50)
{
strResult = strResult.substring(1, strResult.length());// 去掉进位值
vec1.set(i, strResult);
try
{

String prevNum = vec1.get(i + 1);// 获取前一段数

prevNum = addition(prevNum,"1");// 加上进位值 vec1.set(i + 1, prevNum);
}
catch(Exception e)
{
//如果有异常，证明该段的前一个位置没有段了
//在前面添加一个段
vec1.add("1");
}
}
else
{
vec1.set(i, strResult);
}
}
String result = "";
for(int j = vec1.size() - 1; j >= 0; j--)
{
result += vec1.get(j);
} return result;
}

/**
 * 对两个集合的段相加
 * @param val1
 * @param val2
 * @return
 */
public static String addition(String val1,String val2)
{
boolean isZero = false;//判断第一个数的第一位是否为0
if(val1.charAt(0) == '0')
{
val1 = "1" + val1;//如果为0的话在前面加上1，否则new BigInteger的时候会丢失位数
isZero = true;
}

BigInteger num1 = new BigInteger(val1);
BigInteger num2 = new BigInteger(val2);
String result = (num1.add(num2)).toString();

if(isZero)
{
if(result.charAt(0) == '1')//如果第一个数还是等于1，代表前面相加后没有进位值
{
result = result.substring(1,result.length());//去掉刚开始在前面添加的那个1
}
else//有进位值
{
//把第一个数变成1，因为有进位值的话一开始的那个1会变成2，所以要改回1
result = result.substring(1,result.length());
result = "1" + result;
}
}
return result;
}

/**
 * 以50位为一段字符串作为一个数
 * @param str
 * @return
 */
public static Vector<String> partition(String str)
{
int segments = str.length() / 50;//获取段数
int lastSegment = str.length() % 50;//不够一段剩下的个数
Vector<String> val = new Vector<String>();
int n = 50;
int m = 0;
for(int i = 0; i < segments; i++)
{
String pStr = str.substring(str.length() - n, str.length() - m);//每50位截取一段
val.add(pStr);//添加到集合

n += 50;
m += 50;
}
if (lastSegment != 0)//如果不够一段的个数不为0
{
val.add(str.substring(0, lastSegment));//把这小段添加到集合
}
return val;
}

Answer 9

这位大哥，你还在闭门造成，写效率低下的代码。虽然探索精神不错，但不值得褒奖，特别是人家LZ已经会用BigInteger的情况下

Answer 10

main函数里的循环改成while(true)去
- -！忘记改了

Answer 11

用BigInteger或其它BigXXX是不够的，空间会溢出。
要自己写。
10的9次方是一个亿。第一个亿的项的数值大约不超过2千万位。目前程序中MAX_BITS=2千万;这样，程序运行时需要40M字节的空间（两个MAX_BITS个数的字节数组进行FIBONACCI数列计算），若MAX_BITS=2亿;（结果是2亿个位数，大约可能是10的10次方的项），则空间需要800M字节。/**
 *
 * 计算到2千万位的fibonaci数
 *
 */
public class Fib1 {    private static final  int MAX_BITS=20000000;//2千万位
    private static byte[] b1=new byte[MAX_BITS],
                             b2=new byte[MAX_BITS];//放2千万位的fibonaci数
    private static int rpos=0;//当前进位的位置。
   
    private static void addToB1()
    {//b1=b1+b2;
       
       byte r=0,r1=0;
       for(int i=0;i<=rpos;i++)
       {
          r1=(byte)((b1[i]+b2[i]+r)/10);//计算进位
          b1[i]=(byte)((b1[i]+b2[i]+r)%10);//计算值
          r=r1;
         
       }
      
       if(r!=0)
       {
           if(rpos>=MAX_BITS)
           {
               System.out.println("结果已超出2千万位了！");
               System.exit(-1);
           }
           rpos++;
           b1[rpos]=r;
       }
     
    }
    private static void addToB2()
    {//b2=b1+b2;
       
       
        byte r=0,r1=0;
           for(int i=0;i<=rpos;i++)
           {
               r1=(byte)((b1[i]+b2[i]+r)/10);//计算进位
              b2[i]=(byte)((b1[i]+b2[i]+r)%10);//计算值
              r=r1;
             
           }
         
           if(r!=0)
           {
               if(rpos>=MAX_BITS)
               {
                   System.out.println("结果已超出2千万位了！");
                   System.exit(-1);
               }
               rpos++;
               b2[rpos]=r;
           }
          
       
    }
   
    /**
     * 打印出最终运算结果
     * @param b 放2千万位的fibonaci数
     */
    private static void print(byte[] b)
    {
       
        int cc=0;
        if(b[rpos]==0) rpos--;
        System.out.println("本次结果一共有："+(rpos+1)+" 位。");
        for(int i=rpos;i>=0;i--)
        {
            System.out.print(b[i]);
            cc++;
            if(cc>=50){System.out.println();cc=0;}
        }
       
       
    }
   
   
    /**
     * n==1,表示第1项0，n==2表示第2项1，真正计算是从第3项开始的。
     * @param n  计算第几项
     * 注：n>=1
     */
    private static byte[] fib(long n)
    {
       
        b2[0]=1;//b1默认从0开始，b2默认从1开始。
       
        for(long i=3;i<=n;i+=2)
        {
        addToB1();
        addToB2();
        }
        if(n%2==1) return b1;
        else       return b2;
    }
   
    /**
     * @param args
     */
    public static void main(String[] args)
    {
        // 先计算第20万项。
        print(fib(200000));
    }}

Answer 12

换了个代码，这次代码比我之前写的那个快太多了- -！
不过之前那个确实很慢啊大家看下不知道这个效率怎么样，5W次用了7秒public class Fibonacci
{
/*
 * 思路是两个数组代表两个数
 * 为了不必要的循环用-1作为一个结束标识
 * 如果计算结果为153483,在数组里存的顺序实际上是384315
 * 也就是倒着放的，这是因为加法右对齐，如果有进位则直接在后面放1即可
 * 
 */
private static final int MAX_LENGTH = 100000;//数组的长度
private static int end = 1;//终点符
public static void main(String[] args)
{
byte[] num1 = new byte[MAX_LENGTH];
byte[] num2 = new byte[MAX_LENGTH];
    num1[0] = 1;//一开始是1
    num1[1] = -1;//第二位结束循环
    num2[0] = 1;
    num2[1] = -1;
    System.out.println(num1[0] + "\n" + num2[0]);
    
    byte[] result = null;
    for(int i = 0; i < 50000; i++)
    {
     result = add(num1.clone(),num2.clone());
     num2 = num1;
     num1 = result;
     //display(result);
    }
    display(result);
    System.out.println(end);
}

public static byte[] add(byte[] num1, byte[] num2)
{
int carry = 0;
int i = 0;
while(true)
{
if(num2[i] == -1)//终止标识
{
break;
}
carry = num1[i] + num2[i];
if(carry >= 10)//有进位
{
if (num1[i + 1] != -1)// 前一个不是终点
{
num1[i + 1] += 1;//加上进位1
}
else//前一个是终点
{
num1[i+1] = 1;//设置进位1
num1[i+2] = -1;//设置终点标识
end++;//结束标识往后移一个位置
}
num1[i] = (byte)(carry % 10);//设置余数
}
else//无进位
{
num1[i] = (byte)carry;
}
i++;
}
return num1;

}

public static void display(byte[] result)
{
for(int i = end - 1; i >= 0; i--)
{
System.out.print(result[i]);
}
System.out.println("\n");
}
}

Answer 13

郁闷啊  重新测了一次
   同样的程序在Eclipse里做5W次用16秒
   在DOS里跑1000次用了10秒- -！
      无语了

Answer 14

不想和你争，acm上这是最基本的题目，还有大数乘法、除法都比加法复杂多了

Answer 15

我之前那代马用BigInteger写的那个跑一万次都不用一秒哦....唉郁闷好像都说要用数组来做,但我是初学不太懂,同学用数学软件来搞不用一秒就能出....哈哈

Answer 16

不想和你争，acm上这是最基本的题目，还有大数乘法、除法都比加法复杂多了

Answer 17

求 Fibonacci 数列第 n 项的公式：

Answer 18

计算想法是常用的Fibonacci的迭代计算法：
a=1,b=1;
a+b=>a   //a=2
b+a=>b   //b=3
重复做上述两步即：
a+b=>a   
b+a=>b   
就行了。
因此：
1）只要两个数组：一个表示数a,另一个表示数b
2)由于每一个数组都有2千万位，因而做 数组a+数组b=>数组a时，不是每次都计算2千万位，而是只算已有的进位数（这就是变量rpos的作用--可大幅度减少循环次数）
3）由于每次做两次加法，因而若求第10亿项，循环其实只要一半5亿次就行了。当然若有数学系的学生，可从数学上对Fibonaci计算规则进行大幅度的优化，如：著名的Mathmatics数学包。由于其中含有大量数学知识，就不述了。

Answer 19

这题正是在一个在线acm之类测试题里出来的...唉初学java我还是不太懂,继续埋头看书去,希望等知识多了回过头来能做出这题了吧