2013
11-10

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

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)，为什么要这样拆分，原则是什么？