首页 > 专题系列 > Java解POJ > POJ 3982 序列 [解题报告] Java
2013
11-13

POJ 3982 序列 [解题报告] Java

序列

问题描述 :

数列A满足An = An-1 + An-2 + An-3, n >= 3

编写程序,给定A0, A1 和 A2, 计算A99

输入:

输入包含多行数据

每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 32767)

数据以EOF结束

输出:

对于输入的每一行输出A99的值

样例输入:

1 1 1

样例输出:

69087442470169316923566147

解题代码:

//* @author: 
import java.util.*;
import java.math.BigInteger; 
public class Main {

 static String doAdd(String a, String b) { //两个大数相加的方法。
        String str = "";   
        int lenA = a.length();   
        int lenB = b.length();   
        int maxLen = (lenA > lenB) ? lenA : lenB;   
        int minLen = (lenA < lenB) ? lenA : lenB;   
        String strTmp = "";   
        for (int i = maxLen - minLen; i > 0; i--) {   
            strTmp += "0";   
        }   
        // 把长度调整到相同   
        if (maxLen == lenA) {   
            b = strTmp + b;   
        } else  
            a = strTmp + a;   
        int JW = 0;// 进位   
        for (int i = maxLen - 1; i >= 0; i--) {   
            int tempA = Integer.parseInt(String.valueOf(a.charAt(i)));   
            int tempB = Integer.parseInt(String.valueOf(b.charAt(i)));   
            
            int temp;   
            if (tempA + tempB + JW >= 10 && i != 0) {   
                temp = tempA + tempB + JW - 10;   
                JW = 1;   
            } else {   
                temp = tempA + tempB + JW;   
                JW = 0;   
            }   
            str = String.valueOf(temp) + str;   
        }   
        return str;   
    }   
  


  public static void main(String[] args) {
  Scanner in=new Scanner(System.in);
 
  String a[]=new String [100];
  while(in.hasNext()){
  a[0]=Integer.toString(in.nextInt());
  a[1]=Integer.toString(in.nextInt());
  a[2]=Integer.toString(in.nextInt());
  for(int i=3;i< 100;i++){
     String temp=doAdd(a[i-1],a[i-2]);
     a[i]=doAdd(temp,a[i-3]);
   }
   
   System.out.println(a[99]);
  }
 }
}

方法二:
import java.math.*;
import java.util.*;

public class Main
{
    public static BigInteger calc(BigInteger a,BigInteger b,BigInteger c)
    {
        BigInteger now = c;
        BigInteger last = b;
        BigInteger llast = a;
        BigInteger answer;
        for(int i=0;i< 97;i++) {
            answer = now.add(last);
            answer = answer.add(llast);
            llast = last;
            last = now;
            now = answer;
        }
        return now;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            int a0 = in.nextInt();
            BigInteger A0 = BigInteger.valueOf(a0);
            int a1 = in.nextInt();
            BigInteger A1 = BigInteger.valueOf(a1);
            int a2 = in.nextInt();
            BigInteger A2 = BigInteger.valueOf(a2);
            System.out.println(calc(A0,A1,A2));
        }
    }
}

  1. “可以发现,树将是满二叉树,”这句话不对吧,构造的树应该是“完全二叉树”,而非“满二叉树”。

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  4. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。