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
求大神解答！！！！
我可以给你个思路,我没有时间要不然试试看能不能计算出来:
题目中假设只能吃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的运算你自己想吧；
第二个回答有欠缺的,请勿参考；
参考
http://bbs.csdn.net/topics/390360329
一样的问题，C#实现。
需要Java实现，请先采纳我的答案。
用树解决吧。
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
}
}
可以用最大堆来做，比如N=5，则把它分成2+3，3=2+1，2=1+1，然后层层构造最大堆。
第一轮，输出叶子，也就是五个1，然后把来自同一个节点的两个叶子移除。比如说移除2下面的两个为1的叶子。
第二轮，继续输出叶子，也就是三个1和一个2，然后继续删除来自同一个节点的两个叶子。
依次类推，最终只剩根结点5为止。
描述可能不太好理解，画个图会好一点