问题描述

java算法题，公司的笔试题

suppose you have N cakes, N is an interger>0
// at each time, you can either eat 1 cake, or 2 cakes or 3 cakes
// PROBLEM: How many ways can you eat all N cakes
// for example, N = 4, (1,2,1) and (1,1,2) are considered to be different ways
// but (1,1,1,1) and (1,1,1,1) are considered to be the same way
求大神解答！！！！

解决方案

参考
http://bbs.csdn.net/topics/390360329
一样的问题，C#实现。
需要Java实现，请先采纳我的答案。

解决方案二：

我可以给你个思路,我没有时间要不然试试看能不能计算出来:
题目中假设只能吃1或2或3块也就是说只能在这三个里面选；
假设n是奇数,那么要保证是奇数，则必须是n个1或者n-2个1 +2或者n-3个1 +3或者n个3相加就没有了，
然后你将里面能排列的排一下就行了；
假设n是偶数的话也是一样的，不会很多的因为它们几个不会超过1或2或3的
这种分析你应付考试应该可以了

我花了不少时间帮你解决的,可感觉你没给高悬赏真没动力啊
如果回答对您有帮助,请采纳

解决方案三：

奇数还少了个:n-1个2 +1+1或n-2个2+3或n-2个2+1+2

解决方案四：

奇数部分还还少了2的运算你自己想吧；
第二个回答有欠缺的,请勿参考；

解决方案五：

用树解决吧。

package csdnA.EatCake;

public class Solution {

private int count = 0 ;

public int countCakeEat(int N){

    if(N==1){
        count = 1 ;
    }else{
        TreeNode root = new TreeNode(0,0);
        generateTree(N,root) ;
    }

    return count ;
}

private void generateTree(int N , TreeNode parent){
    TreeNode child1 = new TreeNode(1 , parent.sum+1) ;
    TreeNode child2 = new TreeNode(2 , parent.sum+2) ;
    TreeNode child3 = new TreeNode(3 , parent.sum+3) ;
    parent.child1 = child1  ;
    parent.child2 = child2 ;
    parent.child3 =child3;

    if(child1.sum<N){
        generateTree(N , child1) ;
    }else if(child1.sum==N){
        count++;
    }else{
        //do nothing
    }

    if(child2.sum<N){
        generateTree(N , child2) ;
    }else if(child2.sum==N){
        count++;
    }else{
        //do nothing
    }

    if(child3.sum<N){
        generateTree(N , child3) ;
    }else if(child3.sum==N){
        count++;
    }else{
        //do nothing
    }

}

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Solution s = new Solution() ;
    System.out.println(s.countCakeEat(4));
}

}

package csdnA.EatCake;

public class TreeNode {
int val;
int sum ;
TreeNode child1;
TreeNode child2;
TreeNode child3;

TreeNode(int x) {
    this.val = x;
}

TreeNode(int x , int sum) {
    this.val = x;
    this.sum = sum ;
}
/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

}

}