首页 > 专题系列 > Java解POJ > POJ 1189 钉子和小球 [解题报告] Java
2013
11-09

POJ 1189 钉子和小球 [解题报告] Java

钉子和小球

问题描述 :

有一个三角形木板,竖直立放,上面钉着n(n+1)/2颗钉子,还有(n+1)个格子(当n=5时如图1)。每颗钉子和周围的钉子的距离都等于d,每个格子的宽度也都等于d,且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。

让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落,小球每碰到一个钉子都可能落向左边或右边(概率各1/2),且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。

我们知道小球落在第i个格子中的概率pi=pi=,其中i为格子的编号,从左至右依次为0,1,…,n。

现在的问题是计算拔掉某些钉子后,小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。

输入:

第1行为整数n(2 <= n <= 50)和m(0 <= m <= n)。以下n行依次为木板上从上至下n行钉子的信息,每行中'*'表示钉子还在,'.'表示钉子被拔去,注意在这n行中空格符可能出现在任何位置。

输出:

仅一行,是一个既约分数(0写成0/1),为小球落在编号为m的格子中的概pm。既约分数的定义:A/B是既约分数,当且仅当A、B为正整数且A和B没有大于1的公因子。

样例输入:

5 2
*
   * .
  * * *
 * . * *
* * * * *

样例输出:

7/16

解题代码:

/* @author: */
import java.util.*;
public class Main {
static long gcd(long a,long b)//计算a,b的最大公约数
{
        if(b==0)
           return a;
        else
           return gcd(b,a%b);
}

public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
    
    int m,n;
    long d,tmp;
        n=sc.nextInt();
        m=sc.nextInt();
       char ss[][]=new char[n][];
       long dp[][]=new long[n+1][];

        for(int i=0;i< n;i++){
           ss[i]=new char[i+1];
          for(int j=0;j< i+1;j++)  
           ss[i][j]=sc.next().charAt(0);
         
       }
        for(int i=0;i<=n;i++)
         dp[i]=new long[i+1];

        dp[0][0]=1l<< n;
        for(int i=1;i<=n;i++){
         for(int j=0;j< i;j++)
         {
            if(ss[i-1][j]=='*')
            {
                tmp=dp[i-1][j]>>1;
                dp[i][j]+=tmp;
                dp[i][j+1]+=tmp;
            }
            else                                                                        
                dp[i+1][j+1]+=dp[i-1][j];
         }
     
        }
        
         d=gcd(dp[n][m],dp[0][0]);
         System.out.printf("%d/%d\n",dp[n][m]/d,dp[0][0]/d);

            
   }
}

  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。