一道有趣的编程题

[rwdy2008]

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

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

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

[troycheng]

吃到第 N 个面包时的状态，前驱状态可以是从第 N-2 个吃两个，也可以从 N-1 个吃一个
N=1 的时候，只有一种吃法
N=2 的时候，有两种吃法
序列的话，加个变量记一下结果即可

[bolide2005]

有啥意思啊……这不就是爬楼梯问题吗，换个马甲

[vegito2002]

如果一次可以吃 1..N-1 个, 打印所有序列; 就是一个拆分加法求和的问题

[oceanTu]

问题基因是兔子数列
如果要列举可以做子问题拆分 question(N)状态下吃一个和吃两个，得到两个子问题 question(N-1), question(N-2)。
子问题状态会重复，可以保存状态优化。
脑子里 YY 了一下，解的结构像是巨大的二叉树，节点是子问题，两个枝是吃一个，吃两个。任意从根到叶子的路径是一种吃法。

[ai277014717]

这不是动态规划么。

[ballshapesdsd]

毫无难度

[cdlixucd]

@ballshapesdsd talk is cheap,show me the code

[qiuyk]

呃 不就是多记录个状态么 动态规划完了还原解法不就好了....

[LenonZeng]

把第 n 步和第 n-1 步的情况搞清楚 得到一个递推式子外加 0 个面包 1 个面包 2 个面包的初始情况 递归下

[daxingzhesun]

好像有个题叫走台阶,一次走一步或者两步,好像是 2 的 n 次方-1

[rwdy2008]

V 友们，觉得 so easy 的，展示出你们如大屌般强悍的最优代码啊

[Youen]

backtracking 吗

[daxingzhesun]

public int eat(int n) {
if (n == 1 && n == 0) {
return 1;
} else if (n == 2) {
return 2;
}else{
return eat(n-1)+eat(n-2);
}

}

[rwdy2008]

@daxingzhesun 题目是打印所有的序列，不是序列总数

[caixiangyu17]

def f(n):
if n == 1:
return ['1']
if n == 2:
return ['11', '2']
return list(set(list(set(map(lambda x: '1' + x, f(n - 1)))) +
list(set(map(lambda x: '2' + x, f(n - 2)))) +
list(set(map(lambda x: '11' + x, f(n - 2))))))
动态规划了解一下

[lhx2008]

楼上说动态规划的，真的有用到吗？

[hourann]

@lhx2008 哈哈哈，加个 lru_cache 就是了

[shilyx]

递归嘛，最简单，c++：
/*
*　 @file 　: TestNBread.cpp
*　 @author: slx
*　 @date 　: 2018-04-27 12:21:26.865
*　 @note 　: Generated by SlxTemplates
*/

#include <iostream>

using namespace std;

void dojob(int N, char buf[], int sum) {
　　 if (N - sum == 1) {
　　　　 cout << buf << 1 << endl;
　　} else if (N - sum == 2) {
　　　　 cout << buf << 2 << endl;
　　　　 cout << buf << 11 << endl;
　　} else {
　　　　 int len = strlen(buf);
　　　　 buf[len + 1] = 0;
　　　　 buf[len] = '1';
　　　　 dojob(N, buf, sum + 1);
　　　　 buf[len + 1] = 0;
　　　　 buf[len] = '2';
　　　　 dojob(N, buf, sum + 2);
　　}
}

void dojob(int N) {
　　 char *buf = (char *)malloc(N + 1);
　　 memset(buf, 0, N + 1);
　　 dojob(N, buf, 0);
　　 free(buf);
}

int main(int argc, char *argv[])
{
　　 dojob(7);
　　 return 0;
}
结果：
111112
1111111
111121
11122
111211
11212
112111
11221
12112
121111
12121
1222
12211
21112
211111
21121
2122
21211
2212
22111
2221
请按任意键继续. . .

[xuc]

https://leetcode-cn.com/problems/climbing-stairs/

[bolide2005]

用啥动态规划啊
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)
联立可解

[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 全排列用队列不停的进出遍历一遍所有的应该时间应该还好吧

[allen3921]

```go
func fab(n int) {
var s string = "";
myfab(n, s);
}

func myfab(n int, s string) {
if (n == 0) {
fmt.Println(s);
return;
}
if (n > 0) {
myfab(n - 1, s + "1")
}
if (n > 1) {
myfab(n - 2, s + "2");
}
}
```