一道有趣的编程题

吃法

序列

组合

编程

41 条回复 • 2018-04-28 14:36:39 +08:00

1

troycheng

2018-04-27 11:13:58 +08:00

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

2

bolide2005

2018-04-27 11:16:16 +08:00

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

3

vegito2002

2018-04-27 11:17:29 +08:00

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

4

oceanTu

2018-04-27 11:31:58 +08:00

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

5

ai277014717

2018-04-27 11:32:33 +08:00

这不是动态规划么。

6

ballshapesdsd

2018-04-27 11:45:37 +08:00

毫无难度

7

cdlixucd

2018-04-27 11:51:38 +08:00

@ballshapesdsd talk is cheap,show me the code

8

qiuyk

2018-04-27 11:51:59 +08:00

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

9

LenonZeng

2018-04-27 11:55:36 +08:00

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

10

daxingzhesun

2018-04-27 11:56:14 +08:00

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

11

rwdy2008

OP

2018-04-27 11:58:26 +08:00

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

12

Youen

2018-04-27 12:01:37 +08:00

backtracking 吗

13

daxingzhesun

2018-04-27 12:02:42 +08:00

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);
}

}

14

rwdy2008

OP

2018-04-27 12:04:38 +08:00

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

15

caixiangyu17

2018-04-27 12:04:47 +08:00

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))))))
动态规划了解一下

16

lhx2008

2018-04-27 12:06:30 +08:00 via Android

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

17

hourann

2018-04-27 12:12:34 +08:00 via iPhone

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

18

shilyx

2018-04-27 12:25:26 +08:00

递归嘛，最简单，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
请按任意键继续. . .

19

xuc

2018-04-27 12:26:53 +08:00

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

20

bolide2005

2018-04-27 12:29:07 +08:00 via Android

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

21

GAMEKON

2018-04-27 12:47:49 +08:00

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);

22

GAMEKON

2018-04-27 12:56:33 +08:00

```

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);

```

23

kualalumpur

2018-04-27 13:40:45 +08:00

``` 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/

24

caixiangyu17

2018-04-27 13:43:10 +08:00

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

25

chinvo

2018-04-27 13:53:22 +08:00

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

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

26

jerry033

2018-04-27 13:59:21 +08:00

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

27

bolide2005

2018-04-27 14:00:52 +08:00

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

28

coderluan

2018-04-27 14:35:25 +08:00

1

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

29

jadeity

2018-04-27 14:55:23 +08:00

'''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)))
'''

30

crazyzzm

2018-04-27 14:59:58 +08:00

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

31

jadeity

2018-04-27 15:13:06 +08:00

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

32

waltyyy

2018-04-27 16:04:45 +08:00

```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);
}

}
```

33

necomancer

2018-04-27 17:06:56 +08:00

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

34

af463419014

2018-04-27 17:10:50 +08:00

@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))

35

Zeahoo

2018-04-27 17:20:31 +08:00

@chinvo 老哥你说的对啊

36

projectzoo

2018-04-27 17:26:59 +08:00

1

典型的走阶梯啊。。

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

37

siyemiaokube

2018-04-27 22:53:22 +08:00 via iPhone

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

38

congeec

2018-04-27 23:21:10 +08:00 via iPhone

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

39

20015jjw

2018-04-28 07:09:23 +08:00 via Android

这题学过 cs 的都会吧..

40

akio

2018-04-28 10:40:10 +08:00

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

41

allen3921

2018-04-28 14:36:39 +08:00

```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");
}
}
```