首页 > 专题系列 > Java解POJ > POJ 1671 Rhyme Schemes [解题报告] Java
2013
11-10

POJ 1671 Rhyme Schemes [解题报告] Java

Rhyme Schemes

问题描述 :

The rhyme scheme for a poem (or stanza of a longer poem) tells which lines of the poem rhyme with which other lines. For example, a limerick such as If computers that you build are quantum

Then spies of all factions will want ‘em

Our codes will all fail

And they’ll read our email

`Til we’ve crypto that’s quantum and daunt ‘em

Jennifer and Peter Shor (http://www.research.att.com/~shor/notapoet.html)

Has a rhyme scheme of aabba, indicating that the first, second and fifth lines rhyme and the third and fourth lines rhyme.

For a poem or stanza of four lines, there are 15 possible rhyme schemes:

aaaa, aaab, aaba, aabb, aabc, abaa, abab, abac, abba, abbb, abbc, abca, a bcb, abcc, and abcd.

Write a program to compute the number of rhyme schemes for a poem or stanza of N lines where N is an input value.

输入:

Input will consist of a sequence of integers N, one per line, ending with a 0 (zero) to indicate the end of the data. N is the number of lines in a poem.

输出:

For each input integer N, your program should output the value of N, followed by a space, followed by the number of rhyme schemes for a poem with N lines as a decimal integer with at least 12 correct significant digits (use double precision floating point for your computations).

样例输入:

1
2
3
4
20
30
10
0

样例输出:

1 1
2 2
3 5
4 15
20 51724158235372
30 846749014511809120000000
10 115975

解题代码:

//* @author:
import java.util.*;
public class Main{
 
 static double dp[][]=new double[51][51];
 static {
   dp[1][1]=1;
   for (int i=2;i<=50;i++)
     for(int j=1;j<=50;j++)
	dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j;
  }


public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
	while (sc.hasNext()) {
        int n=sc.nextInt();
        if(n==0) break;
	 double ans=0;
	 for (int i=1;i<=n;i++)
          ans+=dp[n][i];
	 System.out.printf("%d %.0f\n",n,ans);
	}
  }
}

  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?