• 解题:铺瓷砖

    2016/12/08 Vinny Hu 17 评论

题目:

小明想给自己家里铺瓷砖,他们家的瓷砖比较独特,瓷砖只有长度为 1  2   3 三种类型,它们的宽都为1,而且小明家要铺的地面也很独特,地面的宽度为1,长度为n。并且小明这个人有强迫症,他铺瓷砖时有一条规定就是,任意两个相邻的瓷砖的长度不能相同!

请你帮帮小明。

输入:n

输出:满足铺设要求的总数。

样例如下:

输入:

输出:

当n = 4时,可有如下方案:

4 = 1 + 2 + 1;

4 = 3 + 1;

4 = 1 + 3;

【解题提示】:

  • 请在评论中先给出你的实现思路;
  • 然后贴出实现的代码;
  • 编程语言不限;
  • 评论支持代码高亮,请点击评论框菜单栏上的 <> 按钮;

 

1 收藏


直接登录
最新评论
  • 匿名了 JAVA 2016/12/11

     

    • 匿名了 JAVA 2016/12/11

      暴力计算

    • 王念一 高一学生 2016/12/11

      思路捏??

      • 匿名了 JAVA 2016/12/13

        一块一块的铺,遍历循环,上面代码有问题, 改成 缓存 + 递归

         

  • 王念一 高一学生 2016/12/11

    思路:深度优先,若走到某点发现走不通(比如从4开始走2-1-后面没有了)就回溯。

    代码:

     

  • 砍死小明!

  • 思路是采用动态规划,地面长度为n,声明一个n*3的数组state,然后state[i][1]表示当铺到第i个长度时最后一块是1的个数,state[i][2]表示最后一块是2的个数,state[i][3]表示最后一块是3的个数,然后每次往后算算到第k个的时候,去看state[k-1]中最后一块为2和3的个数,一次类推。

    个人观点,不敢保证正确性。

  • lrscy 学生 2016/12/16

     

  • 可可 程序员 2016/12/17

    代码写的并不好,可能还有精简的方式

    算法方面应该还有其他的方式,但是这是我能想到的方式

    • 可可 程序员 2016/12/17

      修订一个版本

  • /**
    * @param n 剩余铺设长度
    * @param i 瓷砖长度i后接长度n
    * @return
    */
    public int puCiZhuan(int n,int i){
    if(n<=0)
    return 0;
    if(n==1)
    return i==1?0:1;
    if(n==2)
    return i==2?0:1;
    if(n==3)
    return i==0?3:2;
    if(i==0)
    return puCiZhuan(n-1,1)+puCiZhuan(n-2,2)+puCiZhuan(n-3,3);
    if(i==1)
    return puCiZhuan(n-2,2)+puCiZhuan(n-3,3);
    if(i==2)
    return puCiZhuan(n-1,1)+puCiZhuan(n-3,3);
    if(i==3)
    return puCiZhuan(n-1,1)+puCiZhuan(n-2,2);
    return 0;
    }
    @Test
    /**
    * 宽1,长n的地面铺设 宽1长分别为1,2,3的瓷砖,
    * 相邻两块不能相同,有多少种铺设方式
    * n=4,输出3:
    * 1,2,1
    * 1,3
    * 3,1
    */
    public void testPuCiZhuan(){
    int num=puCiZhuan(5,0);
    System.out.println(num);
    }

  • 含章   03/24

    我用php做了一个程序,主要功能时输出所有的排列组合,水平有限,仅供参考

     

  • wx_LGG2sSin   05/23