有一长度为N(1<=Ｎ<=10)的地板，给定三种不同瓷砖：一种长度为1，一种长度为2，另一种长度为3，数目不限。要将这个长度为N的地板铺满，并且要求长度为1的瓷砖不能相邻，一共有多少种不同的铺法？在所有的铺设方法中，一共用了长度为1的瓷砖多少块？
　　例如，长度为4的地面一共有如下4种铺法，并且，一共用了长度为1的瓷砖4块：
　　4=1+2+1
　　4=1+3
　　4=2+2
　　4=3+1
　　编程求解上述问题。用户输入N，输出不同铺法数和长度为一的瓷砖数。
鉴于论坛最近比较冷清，和大家分享这道题，希望大家给出自己的算法或思路，谢谢各位。

没想出啥好算法，穷举的凑个热闹

#include <stdio.h>
#include <stdlib.h>

#define LENGTH_MAX     10
#define TILE_SIZE       3

const int tile_value[TILE_SIZE] = { 1, 2, 3 };

int count = 0;

void print(int ans[], int ip)
{
    int sum = 0;
    printf("[%03d]:\n", ++count);
    for ( int i = 0; i < ip; ++i )
    {
        sum += ans[i] == tile_value[0];
        printf( "%3d", ans[i] );
    }
    printf( "\nCOUNT is %d\n\n", sum );
}

void fun(int ans[], int ip, int sum, int pre_floor)
{
    if ( sum >= LENGTH_MAX )
    {
        if ( sum == LENGTH_MAX )
        {
            print( ans, ip );
        }
        return;
    }

    for ( int i = !pre_floor; i < TILE_SIZE; ++i )
    {
        ans[ip] = tile_value[i];
        fun( ans, ip + 1, sum + ans[ip], i );
    }
}

int main(void)
{
    int ans[LENGTH_MAX] = { 0 };

    fun( ans, 0, 0, 1 );
    return EXIT_SUCCESS;
}

[ 本帖最后由 azzbcc 于 2014-12-31 09:52 编辑 ]

sum += ans[i] == tile_value[0];
这句是什么意思

return EXIT_SUCCESS;
这又是什么意思？

动态规划。

解释一下cal中数组c的意义：
c[i][0]表示铺满长度为i的地板的所有方法使用长度为1的瓷砖的数量；
c[i][1]表示铺满长度为i的地板且最后一块瓷砖长度为1的方法数；
c[i][2]表示铺满长度为i的地板且最后一块瓷砖长度为2的方法数；
c[i][3]表示铺满长度为i的地板且最后一块瓷砖长度为3的方法数；

cal函数通过返回值返回总的方法数，通过c1返回长度为1的瓷砖使用数量。

这是个基本算法示例。还可以优化。

#include <stdio.h>

#define MAX_N    42

int cal(int n, int * c1)
{
    int c[MAX_N + 1][4] = {{1}, {1, 1}, {0, 0, 1}, {2, 1, 1, 1}};
    int i;
    
    for(i = 4; i <= n; i++)
    {
        c[i][0] = c[i - 2][0] + c[i - 3][0] +
            c[i - 3][0] + c[i - 3][1] + c[i - 3][2] + c[i - 3][3] +
            c[i - 4][0] + c[i - 4][1] + c[i - 4][2] + c[i - 4][3];
        c[i][1] = c[i - 1][2] + c[i - 1][3];
        c[i][2] = c[i - 2][1] + c[i - 2][2] + c[i - 2][3];
        c[i][3] = c[i - 3][1] + c[i - 3][2] + c[i - 3][3];
    }
    *c1 = c[n][0];
    return c[n][1] + c[n][2] + c[n][3];
}

int main()
{
    int n, c, c1;
    
    scanf("%d", &n);
    c = cal(n, &c1);
    printf("%d %d\n", c, c1);
    
    return 0;
}

我来个数学解
设有 a个"长度为3的地板"，b个"长度为2的地板"，c个"长度为1的地板"
只考虑 "长度为3的地板"和"长度为2的地板"，则其排列组合数为 C(a,a+b)
"长度为1的地板"不能相邻，也就是只能插入到上述两种地板的间隙中，其排列组合数为C(c,a+b+1)

#include <stdio.h>

// 排列组合 n! / r! / (n-r)!
unsigned C( unsigned r, unsigned n )
{
    unsigned a=1, b=1;
    for( r=(r<n-r?r:n-r); r!=0; --n, --r )
        a*=n, b*=r;
    return a/b;
}

unsigned foo( unsigned n )
{
    unsigned sum = 0;

    // a*3 + b*2 + c*1 = n
    for( unsigned a=0; a*3<=n; ++a )
    for( unsigned b=0; a*3+b*2<=n; ++b )
    {
        unsigned c = (n-a*3-b*2)/1;
        if( c > a+b+1 ) continue; // 此时e为0

        // a个'3' 放置到 (a+b)个位置 上
        unsigned d = C(a,a+b);

        // c个'1' 放置到 (a+b+1)个位置 上
        unsigned e = C(c,a+b+1);

        sum += d*e;
    }

    return sum;
}

int main( void )
{
    unsigned n;
    scanf( "%u", &n );
    printf( "%u\n", foo(n) );

    return 0;
}

获益良多

看来数学确实是解决算法问题的有力工具

给个回溯法的解

#include<stdio.h>
#include<malloc.h>
#include<math.h>

#define MAX 3

int Tile[MAX] = {1, 2, 3};
int count = 0;
int sum = 0;

void NumTile_1(int *S, int n, int top, int len);//回溯法 


int main()
{
    int n;
    int *S;
    scanf("%d", &n);
    while (n != 0)
    {
        S = (int *)malloc(sizeof(int)*n);
        sum = count = 0;
        NumTile_1(S, n, 0, 0); 
        printf("\ns = %d\n", sum);
        free(S);
        
        scanf("%d", &n);
    }
    
    return 0;
}

void NumTile_1(int *S, int n, int top, int len)//回溯法 
{
    int i;
    
    if (n == len)
    {
        count++;
        printf("\n%d = ", n);
        for (i=0; i<top; i++)
        {
            printf(" %d +", S[i]);
            if (S[i] == Tile[0])
            {
                sum++;
            }
        }
    }
    if (n <= len)
        return ;
    
    i = 0;
    if (top > 0 && S[top-1] == Tile[0]) 
        i = 1;
        
    for ( ; i<MAX; i++)
    {
        S[top] = Tile[i];
        NumTile_1(S, n, top+1, len+Tile[i]); 
    }
}

6楼答案有问题
我错了，他6楼答案没有问题，只是没有写出1个个数

[ 本帖最后由 巧若拙 于 2014-12-31 20:48 编辑 ]