百度变态规则问题 解法

引用

变态比赛规则

为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛，负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。

由于一些员工（比如同部门或者相邻部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自由分组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。

比如4个人，编号为1~4,如果分为两个组并且1，2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如

果是1，2，3一组，4单独一组，那么一共需要打三场比赛 1 vs 4，2 vs 4，3 vs 4。


很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人，通过上面这种比赛规则，总比赛场数有可能为K场吗？

比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛，如果分为三组则需要3场比赛。但是无论怎么分都不可能恰需要1场比赛。


相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。

思路：原帖讨论很多，但个人觉得不是基于JAVA的思考方式，这里无非就是N所有可能的拆法产生的比赛数目能和K吻合而已。恰好拆数字之前写过，只要在最里层加个判断把K值放进去比较一下就可以了。代码不细改了，以下做参考。

package algorithm;

import java.util.Stack;

public class NumberDivide {

  /**
   * @param args
   */
  private Stack<Integer> stack = new Stack<Integer>();
  private int divide(int m,int n){
    if(n==0) return 1;
    int m1=n;
    while(m1>0){
      if(m1<=m){
        stack.push(m1);
        if(divide(m1,n-m1)>0){
          System.out.println(stack);
          int pi=stack.size()*(stack.size()-1)/2;
          for(int i:stack){
            pi*=i;
          }
          System.out.println(pi);
        }
        stack.pop();
      }
      m1--;
    }   
    return 0;
  }
  public void divide(int n){
    divide(n-1,n);
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    new NumberDivide().divide(6);
  }

}