一道有趣的编程题

[rwdy2008]

最近遇到这样一个题，觉得挺有意思，V 友们一起讨论下撒

题目如下： N 个面包，分两种吃法，一次吃 1 个或者一次吃 2 个，求所有吃法的序列组合并打印。

PS：是所有的序列组合，不是总数。不限语言

[GAMEKON]

export default class EatingBread
{
a:Array<number> = [];
n:number = 0;

constructor(arg)
{
this.n = parseInt(arg);
this.eat(this.n);
}

eat(i:number):void
{
if (i==0 && this.sum()==this.n)
console.log(this.a);
else if (i==1)
{
this.a.push(1);
this.eat(i - 1);
this.a.pop();
}
else
{
this.a.push(1);
this.eat(i - 1);
this.a.pop();
this.a.push(2);
this.eat(i - 2);
this.a.pop();
}
}

sum():number
{
let s = 0;
for (let i in this.a)
s+=this.a[i];
return s;
}
}

new EatingBread(8);

[GAMEKON]

```

export default class EatingBread
{
a:Array<number> = [];
n:number = 0;

constructor(arg)
{
this.n = parseInt(arg);
this.eat(this.n);
}

eat(i:number):void
{
if (i==0 && this.sum()==this.n)
console.log(this.a);
else if (i==1)
{
this.a.push(1);
this.eat(i - 1);
this.a.pop();
}
else
{
this.a.push(1);
this.eat(i - 1);
this.a.pop();
this.a.push(2);
this.eat(i - 2);
this.a.pop();
}
}

sum():number
{
let s = 0;
for (let i in this.a)
s+=this.a[i];
return s;
}
}

new EatingBread(8);

```

[kualalumpur]

``` javascript
bread(5)
function bread(remain = 0, result = '') {
if (remain <= 0)
return console.log(result) // 没有面包了, 打印结果

if(remain >= 2) // 条件允许一次吃两个
bread(remain - 2, result + '2');

bread(remain - 1, result + '1'); // 一次吃一个
}

```

格式化显示(以及非递归版):
https://paste.ubuntu.com/p/TWDPBBwhgp/

[caixiangyu17]

@bolide2005 动态规划的核心就是找一个通项公式，你这就是动态规划

[chinvo]

爬楼梯一次上两阶还能理解

面包一口吃两个是要噎死么

[jerry033]

就是除以 2，能整除就是一种排列；不能整除，加上 1，这就是第二种排列；之后替换将吃 2 个的情况替换成吃 1 个两次，遍历、迭代……

[bolide2005]

@caixiangyu17 #24 被你这么一说好像还真是……递推公式都有了

[coderluan]

改了初值的斐波那契数列而已，至于求总数还是组合，并没有什么影响吧。

[jadeity]

'''python
def how2eat(n):
if n <= 0:
#先不考虑数入非数字的人了
return '先给钱买面包'
#先看看一次吃一个的情况，转成字符串了。
only1 = str(10 ** n // 9)
#做个是不是要循环的记号
carry_on = True
#做个列表先存上只吃一个的
countlist = [only1]
#要开始循环啦
while carry_on:
#不知道从哪看的把 False 情况放前面好，但是貌似不好解释顺序
#就是如果这个字符串里没有两个或以上的 1 了，那么就不循环了
#为什么不循环了看 else
if only1.count('1') < 2:
carry_on = False
else:
#到了 else 说明有两个或以上的 1，就是吃了两次
#一次吃 1 个，然后把最前边的两次吃 1 个的删掉
only1 = only1[2:]
#从后边补上一个一次吃两个的 2
only1 = only1+'2'
#把这种情况追加到列表里
#然后回去看看还有没有两次吃 1 个的，有继续把
#两个次吃 1 个的换成一次吃 2 个的
#直到没有这种情况
#按组合而不是排列来说是不考虑位置的吧？
#反正我是这么想的，新手不知道怎么换成递归。
countlist.append(only1)
return countlist



n = input('你有多少个面包:\n')
print('你可以这样吃：\n')
print(how2eat(int(n)))
'''

[crazyzzm]

这道题不是算法入门题目么。。没有空间要求，学递归的基本题目啊，简单动态规划

[jadeity]

@crazyzzm 空间要求是指的内存占用吗？如果内存不够的话应该怎么改？我自己的方法试了一下到 N=一万的时候要 15 秒，N=十万 python 直接提示内存错误了。

[waltyyy]

```java
public class EatBreadQuestion {

private static final String STR_1 = "1 ";
private static final String STR_2 = "2 ";

public static void printAllCombination(int breadSize) {
print("", breadSize);
}

private static void print(String beforeInfo, int breadSize) {
if (breadSize > 1) {
print(beforeInfo + STR_1, breadSize - 1);
print(beforeInfo + STR_2, breadSize - 2);
} else if (breadSize == 1) {
print(beforeInfo + STR_1, breadSize - 1);
} else {
System.out.println(beforeInfo);
}
}

public static void main(String[] args) {
printAllCombination(1);
}

}
```

[necomancer]

有意思。我的解决方案是先算不定方程，求出来所有可能组合，然后对每个组合算全排列(distin with duplicate)……也就是 112 的排列只有 112,121,211 这样。这个排列很耗时……

[af463419014]

@caixiangyu17
('1' + x, f(n - 1))和('11' + x, f(n - 2))重复了

在 f(n - 1) 里包含 ('1' + x, f(n - 2))
也就是 ('1' + x, f(n - 1)) 里包含 ('1' + x, '1' + f(n - 2)) == ('11' + x, f(n - 2))

[Zeahoo]

@chinvo 老哥你说的对啊

[projectzoo]

典型的走阶梯啊。。

f(n) = f(n-1) + f(n-2)

[siyemiaokube]

最优算法大概就是矩阵快速幂了吧？还有更强的吗

[congeec]

@siyemiaokube fibonacci 求和有 O1 解法。这个我就不清楚了

[20015jjw]

这题学过 cs 的都会吧..

[akio]

@necomancer 全排列用队列不停的进出遍历一遍所有的应该时间应该还好吧