[笔试题]求乘法结合律的个数

package org.ibatis.helper.test;

import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Associativity {

    public static void main(String[] args)
    {
        int n = 6;
        Set set = extractAssociativity(n);
    }

    private static Set replaceResult4Display(Set set)
    {
        Set result = new HashSet();
        for (Iterator i = set.iterator() ; i.hasNext() ; )
        {
            String str = (String)i.next();
            int strLength = str.length();
            StringBuffer sb = new StringBuffer();
            int count = 0;
            for (int j = 0 ; j < strLength ; j++)
            {
                char c = str.charAt(j);
                sb.append(c == 'X' ? (char)('a' + count++) : c);
            }
            result.add(sb.toString());
        }
        return result;
    }

    public static Set extractAssociativity(int n)
    {
        if (n < 2
        ){
            return Collections.EMPTY_SET;
        }

        Set result = new HashSet();
        result.add("X * X");
        if (n == 2
        ){
            return result;
        }

        for (int i = 3 ; i <= n ; i++)
        {
            result = subExtractAssociativity(result);

            System.out.println("i : " + i + "\tcount : " + result.size());
            System.out.println("-------------------------------------------");
            Set set = replaceResult4Display(result);
            for (Iterator iter = set.iterator() ; iter.hasNext() ; )
            {
                System.out.println(iter.next());
            }
            System.out.println("\n******************************************\n");

        }
        return result;
    }

    private static Set subExtractAssociativity(Set set)
    {
        Set result = new HashSet();
        for (Iterator iter = set.iterator() ; iter.hasNext() ; )
        {
            String str = (String)iter.next();
            int strLength = str.length();
            for (int i = 0 ; i < strLength ; i++)
            {
                char c = str.charAt(i);
                if (c == 'X'
                ){
                    StringBuffer sb = new StringBuffer();
                    for (int j = 0 ; j < strLength ; j++)
                    {
                        if (j == i 
                        ){
                            sb.append("(X * X)");
                        }
                        else sb.append(str.charAt(j));
                    }
                    result.add(sb.toString());
                }
            }
        }
        return result;
    }
}

public class Test2
{
  public long f(int n)
  {
    assert(n>0);
    if(n<=2) return 1;
    long count=0;
    for(int i=1;i<n;++i)
    {
       count=count+c[i]*c[n-i];
    }
    return count;
  }
  long[] c;
  public static void main(String[] args)
  {
    long start=System.currentTimeMillis();
    Test2 test = new Test2();
    int n=36;
    test.c=new long[n+1];
    for(int i=1;i<=n;++i)
    {
      test.c[i]=test.f(i);
      System.out.println("f("+i+")="+test.c[i]);
    }
    System.out.println("use "+(System.currentTimeMillis()-start)+"毫秒");
  }
}

import java.util.ArrayList;
import java.util.List;

public class ParseGroupTest {
	public static void main(String[] args) {
		ParseGroupTest test = new ParseGroupTest();
		test.parseGroup("a", "b", "c", "d", "e");
	}
	
	/**
	 * 存储结果的地方. 注: 代码不严谨, 没有处理相同的情况. 里面可能toString()会有相同的对象.
	 */
	private List<Group> result = new ArrayList<Group>();
	
	public void parseGroup(String... arrays) {
		if (arrays == null || arrays.length < 2) {
			return;
		}
		
		List<Group> groups = new ArrayList<Group>();
		for (int i = 0; i < arrays.length; i ++) {
			Group group = new SingleGroup(arrays[i]);
			groups.add(group);
		}
		
		this.parseGroup(groups);
		
		for (int i = 0; i < result.size(); i ++) {
			System.out.println(result.get(i));
		}
	}
	
	public void parseGroup(List<Group> groups) {
		if (groups == null || groups.size() == 0) {
			return;
		}
		
		if (groups.size() == 1) {
			result.add(groups.get(0));
			return;
		}
		
		if (groups.size() == 2) {
			result.add(new GroupGroup(groups.get(0), groups.get(1)));
			return;
		}
		
		for (int i = 0; i < groups.size() - 1; i ++) {
			List<Group> newGroup = new ArrayList<Group>();
			
			for (int j = 0; j < i; j ++) {
				newGroup.add(groups.get(j));
			}
			
			newGroup.add(new GroupGroup(groups.get(i), groups.get(i + 1)));
			
			for (int k = i+ 2; k < groups.size(); k ++) {
				newGroup.add(groups.get(k));
			}
			
			this.parseGroup(newGroup);
		}
	}
	
	/**
	 * 基类
	 */
	class Group {

	}
	
	/**
	 * 单个String
	 */
	class SingleGroup extends Group {
		String body;
		public SingleGroup(String body) {
			this.body = body;
		}
		
		public String toString() {
			return body;
		}
	}
	
	/**
	 * Group 与Group的组合
	 */
	class GroupGroup extends Group {
		Group leftGroup;
		Group rightGroup;
		public GroupGroup(Group leftGroup, Group rightGroup) {
			this.leftGroup = leftGroup;
			this.rightGroup = rightGroup;
		}
		
		@Override
		public String toString() {
			return "(" + leftGroup.toString() + "*" + rightGroup.toString() + ")";
		}
	}
	
}