首页 > 专题系列 > Java解POJ > POJ 3472 Holey Square Tiling [解题报告] Java
2013
11-12

POJ 3472 Holey Square Tiling [解题报告] Java

Holey Square Tiling

问题描述 :

Given a square of size n + 2 with a square hole of size n − 2 in the middle (see the figure below), calculate the number of different ways to tile it with dominoes of size 1 × 2.

输入:

The input consists of multiple test cases. Each test case contains only one integer n (3 ≤ n ≤ 104). Process util EOF is met.

输出:

For each test case, output the desired number in decimal using the comma as the thousand separator.

样例输入:

3
50

样例输出:

196
401,520,777,816,387,690,468,975,409,805,843,797,460,004

解题代码:

//* @author 
import java.util.*;
import java.io.*;
import java.math.*;

public class Main {

    /**
     * @param args the command line arguments
     */
    static BigInteger []a=new BigInteger[10005];
    public static void main(String[] args) {
       // TODO code application logic here
        int n;
        a[0]=BigInteger.ONE;
        a[1]=BigInteger.ONE;
        for(int i=2;i<=10000;i++) a[i]=a[i-1].add(a[i-2]);
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            n=cin.nextInt();
            BigInteger ans=a[n-1].pow(4);
            ans=ans.add(a[n].pow(2).multiply(a[n-2].pow(2)));
            ans=ans.add(BigInteger.valueOf(6).multiply(a[n].multiply(a[n-2].multiply(a[n-1].pow(2)))));
            ans=ans.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(2));
            String s=ans.toString();
            StringBuffer sbf=new StringBuffer();
            int p=0;
            for(int i=s.length()-1;i>=0;i--){
                p++;
            sbf.append(s.charAt(i));
                if(p==3&&i>0){
                    sbf.append(",");
                    p=0;
                }
            }
            sbf.reverse();
            System.out.println(sbf.toString());
        }

    }

}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

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

  3. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?