C语言宿舍分配方案计算 - 递归实现及优化

本文将介绍如何使用C语言来解决一个有趣的问题：给n位同学分配宿舍，假设学校充分尊重同学们意见，可以任何x个同学使用一间宿舍(x>0)，问：一共有多少种宿舍分配方案？

例如：n=3时，共有3位同学需要分配宿舍，假设为张三、李四、王五3位同学，则可以有以下5种分配方案：

1. 可以每位同学一个宿舍
2. 可以张三同学单独一间，其余两人共用一间
3. 可以李四同学单独一间，其余两人共用一间
4. 可以王五同学单独一间，其余两人共用一间
5. 可以三位同学共用一间

假设学校宿舍的房间数不小于学生数量。

这个问题可以使用递归来解决。假设有n位同学需要分配宿舍，我们可以将第一个同学的宿舍分配方案分为两种情况：

1. 第一个同学单独一间宿舍，那么剩下的n-1位同学需要分配宿舍的方案数为f(n-1)。
2. 第一个同学与其他同学共用一间宿舍，那么剩下的n位同学需要分配宿舍的方案数为f(n)。

所以总的方案数为f(n) = f(n-1) + f(n)。

基本情况是当只有一个同学时，只有一种分配方案，即f(1) = 1。

下面是用C语言实现的代码：

#include <stdio.h>

int dormitory(int n) {
    if (n == 1)
        return 1;
    else
        return dormitory(n-1) + 1;
}

int main() {
    int n;
    printf("请输入同学的数量：");
    scanf("%d", &n);
    printf("共有%d种宿舍分配方案。\n", dormitory(n));
    return 0;
}

这个代码中，dormitory函数用来计算宿舍分配方案的数量。在main函数中，我们从用户输入获取同学的数量，然后调用dormitory函数计算方案数，并输出结果。

注意：这个方法的时间复杂度为O(2^n)，即随着n的增加，计算量会呈指数级增长，所以当n很大时，计算时间会非常长。如果需要计算较大的n，可以考虑使用动态规划等更高效的方法来解决。