V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
rwdy2008
V2EX  ›  程序员

一道有趣的编程题

  •  
  •   rwdy2008 · 2018-04-27 11:03:01 +08:00 · 6070 次点击
    这是一个创建于 2162 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    41 条回复    2018-04-28 14:36:39 +08:00
    troycheng
        1
    troycheng  
       2018-04-27 11:13:58 +08:00
    吃到第 N 个面包时的状态,前驱状态可以是从第 N-2 个吃两个,也可以从 N-1 个吃一个
    N=1 的时候,只有一种吃法
    N=2 的时候,有两种吃法
    序列的话,加个变量记一下结果即可
    bolide2005
        2
    bolide2005  
       2018-04-27 11:16:16 +08:00
    有啥意思啊……这不就是爬楼梯问题吗,换个马甲
    vegito2002
        3
    vegito2002  
       2018-04-27 11:17:29 +08:00
    如果一次可以吃 1..N-1 个, 打印所有序列; 就是一个拆分加法求和的问题
    oceanTu
        4
    oceanTu  
       2018-04-27 11:31:58 +08:00
    问题基因是兔子数列
    如果要列举可以做子问题拆分 question(N)状态下吃一个和吃两个,得到两个子问题 question(N-1), question(N-2)。
    子问题状态会重复,可以保存状态优化。
    脑子里 YY 了一下,解的结构像是巨大的二叉树,节点是子问题,两个枝是吃一个,吃两个。任意从根到叶子的路径是一种吃法。
    ai277014717
        5
    ai277014717  
       2018-04-27 11:32:33 +08:00
    这不是动态规划么。
    ballshapesdsd
        6
    ballshapesdsd  
       2018-04-27 11:45:37 +08:00
    毫无难度
    cdlixucd
        7
    cdlixucd  
       2018-04-27 11:51:38 +08:00
    @ballshapesdsd talk is cheap,show me the code
    qiuyk
        8
    qiuyk  
       2018-04-27 11:51:59 +08:00
    呃 不就是多记录个状态么 动态规划完了还原解法不就好了....
    LenonZeng
        9
    LenonZeng  
       2018-04-27 11:55:36 +08:00
    把第 n 步和第 n-1 步的情况搞清楚 得到一个递推式子外加 0 个面包 1 个面包 2 个面包的初始情况 递归下
    daxingzhesun
        10
    daxingzhesun  
       2018-04-27 11:56:14 +08:00
    好像有个题叫走台阶,一次走一步或者两步,好像是 2 的 n 次方-1
    rwdy2008
        11
    rwdy2008  
    OP
       2018-04-27 11:58:26 +08:00
    V 友们,觉得 so easy 的,展示出你们如大屌般强悍的最优代码啊
    Youen
        12
    Youen  
       2018-04-27 12:01:37 +08:00
    backtracking 吗
    daxingzhesun
        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);
    }

    }
    rwdy2008
        14
    rwdy2008  
    OP
       2018-04-27 12:04:38 +08:00
    @daxingzhesun 题目是打印所有的序列,不是序列总数
    caixiangyu17
        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))))))
    动态规划了解一下
    lhx2008
        16
    lhx2008  
       2018-04-27 12:06:30 +08:00 via Android
    楼上说动态规划的,真的有用到吗?
    hourann
        17
    hourann  
       2018-04-27 12:12:34 +08:00 via iPhone
    @lhx2008 哈哈哈,加个 lru_cache 就是了
    shilyx
        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
    请按任意键继续. . .
    xuc
        19
    xuc  
       2018-04-27 12:26:53 +08:00
    bolide2005
        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)
    联立可解
    GAMEKON
        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);
    GAMEKON
        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);

    ```
    kualalumpur
        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/
    caixiangyu17
        24
    caixiangyu17  
       2018-04-27 13:43:10 +08:00
    @bolide2005 动态规划的核心就是找一个通项公式,你这就是动态规划
    chinvo
        25
    chinvo  
       2018-04-27 13:53:22 +08:00
    爬楼梯一次上两阶还能理解

    面包一口吃两个是要噎死么
    jerry033
        26
    jerry033  
       2018-04-27 13:59:21 +08:00
    就是除以 2,能整除就是一种排列;不能整除,加上 1,这就是第二种排列;之后替换将吃 2 个的情况替换成吃 1 个两次,遍历、迭代……
    bolide2005
        27
    bolide2005  
       2018-04-27 14:00:52 +08:00
    @caixiangyu17 #24 被你这么一说好像还真是……递推公式都有了
    coderluan
        28
    coderluan  
       2018-04-27 14:35:25 +08:00   ❤️ 1
    改了初值的斐波那契数列而已,至于求总数还是组合,并没有什么影响吧。
    jadeity
        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)))
    '''
    crazyzzm
        30
    crazyzzm  
       2018-04-27 14:59:58 +08:00
    这道题不是算法入门题目么。。没有空间要求,学递归的基本题目啊,简单动态规划
    jadeity
        31
    jadeity  
       2018-04-27 15:13:06 +08:00
    @crazyzzm 空间要求是指的内存占用吗?如果内存不够的话应该怎么改?我自己的方法试了一下到 N=一万的时候要 15 秒,N=十万 python 直接提示内存错误了。
    waltyyy
        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);
    }

    }
    ```
    necomancer
        33
    necomancer  
       2018-04-27 17:06:56 +08:00
    有意思。我的解决方案是先算不定方程,求出来所有可能组合,然后对每个组合算全排列(distin with duplicate)……也就是 112 的排列只有 112,121,211 这样。这个排列很耗时……
    af463419014
        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))
    Zeahoo
        35
    Zeahoo  
       2018-04-27 17:20:31 +08:00
    @chinvo 老哥你说的对啊
    projectzoo
        36
    projectzoo  
       2018-04-27 17:26:59 +08:00   ❤️ 1
    典型的走阶梯啊。。

    f(n) = f(n-1) + f(n-2)
    siyemiaokube
        37
    siyemiaokube  
       2018-04-27 22:53:22 +08:00 via iPhone
    最优算法大概就是矩阵快速幂了吧?还有更强的吗
    congeec
        38
    congeec  
       2018-04-27 23:21:10 +08:00 via iPhone
    @siyemiaokube fibonacci 求和有 O1 解法。这个我就不清楚了
    20015jjw
        39
    20015jjw  
       2018-04-28 07:09:23 +08:00 via Android
    这题学过 cs 的都会吧..
    akio
        40
    akio  
       2018-04-28 10:40:10 +08:00
    @necomancer 全排列用队列不停的进出遍历一遍所有的应该时间应该还好吧
    allen3921
        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");
    }
    }
    ```
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1171 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 18:28 · PVG 02:28 · LAX 11:28 · JFK 14:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.