球盒问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

/**************************************************************** 
 * Description: n个一样的球入到m个一样的盒子里，有多少种放法。
 * Author: Alex Li
 * Date: 2024-02-14 10:18:59
 * LastEditTime: 2024-02-14 20:01:41
****************************************************************/
#include <iostream>
#include <vector>

using namespace std;

int n; // 球的总数
int maxBoxes; // 盒子的最大数量
int solution = 0; //方案总数
vector<int> boxes; // 当前分配方案

// 辅助函数，用于打印一种分法
void printSolution() {
    cout<<'{';
    for (int i = 0; i < boxes.size(); ++i) {
        cout << boxes[i];
        if (i < boxes.size() - 1) cout << ",";
    }
    cout<<'}';
    cout <<", ";
}

// 递归函数，用于生成分法
// n: 剩余未分配的球数
// maxBoxes: 最大盒子数量
// boxes: 当前分配方案
// lessValue: 该方案第一个盒子的最小数量，用于保证非递减顺序
void distributeBalls(int n,  int lessValue) {
    // 如果没有剩余球，或者盒子用完，打印当前方案
    //boxs.size<=maxBoxes的情况下是可以有空盒，如果是==的情况就没有空盒
    if (n == 0 && boxes.size() <= maxBoxes) {
        printSolution();
        solution++;
        return;
    }

    // 从lastValue到n遍历，尝试所有可能的球数分配给下一个盒子
    for (int i = lessValue; i <= n; ++i) {
        boxes.push_back(i); // 将球分配给新盒子
        distributeBalls(n - i, i); // 递归分配剩余的球
        boxes.pop_back(); // 回溯，撤销当前盒子的分配
    }
}

int main() {
    cout<<"please input ball number: ";
    cin>>n;
    cout<<"please input box number: ";
    cin>>maxBoxes;
    distributeBalls(n, 1); // 从至少一个球开始分配
    cout<<'\n';
    cout<<"total solution number: "<<solution;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

/**************************************************************** 
 * Description: n个相同的球，m个不同的盒子，共有多少种分法。
 * Author: Alex Li
 * Date: 2024-02-14 21:29:38
 * LastEditTime: 2024-02-18 20:00:49
****************************************************************/
#include <iostream>
#include <vector>

using namespace std;
int n,m;
int wayCount; //记录总的分配方案
vector<int> distribution;
// 打印当前分配方案的函数
void printDistribution(const vector<int>& distribution) {
    cout << "{";
    for (int i = 0; i < distribution.size(); ++i) {
        if (i > 0) cout << ", ";
        cout << distribution[i];
    }
    cout << "} ";
}

// 递归分配球到盒子的函数
// l: 剩余未分配的球数
// m: 盒子的总数
// boxIndex: 当前处理的盒子索引
// distribution: 当前的分配方案，记录每个盒子中球的数量
// wayCount: 引用，用于记录总的分配方式数
void distributeBalls(int l, int boxIndex) {
    // 基础情况：如果所有盒子都考虑完毕
    if (boxIndex == m) {
        if (l == 0) { // 如果没有剩余的球，说明找到了一种有效的分配方式
            printDistribution(distribution);
            wayCount++; // 增加分配方式的计数
        }
        return;
    }

    // 对当前盒子，尝试所有可能的球数
    for (int i = 0; i <= l; ++i) {
        distribution[boxIndex] = i; // 将i个球分配给当前盒子
        distributeBalls(l - i, boxIndex + 1); // 递归处理下一个盒子
    }
}

int main() {
    
    cout << "Enter the number of balls (n): ";
    cin >> n;
    cout << "Enter the number of boxes (m): ";
    cin >> m;
    
    distribution.resize(m, 0); // 初始化，用于追踪每个盒子中球的数量
    
    distributeBalls(n, 0); // 开始递归分配过程

    cout<<"\nTotal ways to distribute " << wayCount << endl;

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

/**************************************************************** 
 * Description: n个不同的球放到m个相同的盒子
 * Author: Alex Li
 * Date: 2024-02-18 17:00:43
 * LastEditTime: 2024-02-18 19:59:08
****************************************************************/
#include <iostream>
#include <cstring> // 用于memset

using namespace std;

int MAX_BALLS;
 int MAX_BOXES;
//int boxes[MAX_BOXES][MAX_BALLS]; // 存储每个盒子中球的编号
vector< vector<int> > boxes;
vector<int> coun; // 存储每个盒子中球的数量
int totalDistributions = 0; // 总分配方案数

void printDistribution() {
    cout << "{ ";
    for (int i = 0; i < MAX_BOXES; ++i) {
        if (coun[i] > 0) { // 如果盒子中有球
            cout << "{";
            for (int j = 0; j < coun[i]; ++j) {
                 if (j >0)cout<<", ";
                cout << boxes[i][j];
               
            }
            cout << "} ";
        }
    }
    cout << "}" <<"; ";
}

void distributeBalls(int ball) {
    if (ball > MAX_BALLS) {
        printDistribution();
        totalDistributions++;
        return;
    }

    for (int i = 0; i < MAX_BOXES; ++i) {
        if (i == 0 || coun[i-1] > 0) { // 保证盒子填充顺序，避免重复
            boxes[i][coun[i]] = ball; // 将球放入盒子
            coun[i]++; // 更新盒子中球的数量
            distributeBalls(ball + 1); // 递归处理下一个球
            coun[i]--; // 回溯
        }
    }
}

int main() {
   cout<<"please input ball number: ";
   cin>>MAX_BALLS;
   cout<<"please input box number: ";
   cin>>MAX_BOXES;
   
   //初始化动态数组 
   boxes.resize(MAX_BOXES);
   for(int i=0;i<boxes.size();i++){
	   boxes[i].resize(MAX_BALLS);          
	   for(int j=0;j<boxes[i].size();j++){
	       boxes[i][j]=0;           //赋值
	}
   }
    coun.resize(MAX_BOXES);

    distributeBalls(1); // 从球编号1开始分配
    
    cout <<'\n'<<"Total ways to distribute " <<totalDistributions << endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

/**************************************************************** 
 * Description: n个不同的球放到m个不同的盒子里
 * Author: Alex Li
 * Date: 2024-02-19 08:50:12
 * LastEditTime: 2024-02-19 09:35:53
****************************************************************/
#include <iostream>
#include <vector>
#include <string>

using namespace std;
  vector<int> distribution; // 记录每个球的分配情况
  int ways = 0; // 分配方案的总数
  int n,m;// n: 总球数  m: 盒子数
// 打印一个分配方案
void printDistribution(const vector<int>& distribution) {
    cout << "{ ";
    for (int i = 1; i <= distribution.size(); ++i) {
        cout << "球" << i << " -> 盒子" << distribution[i];
        if (i <= distribution.size() - 1) cout << ", ";
    }
    cout << " }" << endl;
}

// 递归分配球

// ballIndex: 当前正在分配的球的索引
// distribution: 当前的分配方案
// ways: 分配方案的计数
void distributeBalls(int ballIndex) {
    // 如果所有球都分配完毕，打印当前方案并返回
    if (ballIndex > n) {
        printDistribution(distribution);
        ways++;
        return;
    }

    // 尝试将当前球分配到每一个盒子中
    for (int i = 1; i <= m; ++i) {
        distribution[ballIndex] = i; // 分配球到盒子i
        distributeBalls(ballIndex + 1); // 递归分配下一个球
    }
}

int main() {
  
    cout << "请输入球的数量(n): ";
    cin >> n;
    cout << "请输入盒子的数量(m): ";
    cin >> m;

    distribution.resize(n);
   

    distributeBalls(1); // 开始第1个球开始，递归分配球

    cout << "总的分配方案数为: " << ways << endl;

    return 0;
}