编程算法案例5

作者：championsky | 发布时间：2023-05-02 21:54:06

借书方案知多少

1.问题描述

小明有5本新书，要借给A、B、C三位小朋友，若每人每次只能借1本，则可以有多少种不同的借法？

2.问题分析：

题目中要求每个小朋友每次只能借一本书，可以看作是一个排列问题。即A、B、C三个小朋友从5本书中依次挑选一本，一次可选的范围会随着已选数量的增加而减少。

3.算法设计：

可以利用递归方式求解排列问题，具体步骤如下：

定义一个全局变量count，表示方案数。
编写一个递归函数，每次传递4个参数：当前已经选的数量、当前选择的小朋友编号、已选的书的编号列表，以及书的总数。
在递归函数中，先判断是否已经选择完毕，若是，则将count加一，并将当前的书籍选择情况展示出来。
若未选择完毕，则遍历剩余可选书的编号，依次与小朋友的编号进行小于比较，如果当前小朋友未选择，则选取该书，并将其编号加入已选列表中，再向后递归调用。
递归调用后，返回到上一级递归时，需将已选的书的编号列表中的最后一项弹出，再将之前的小朋友标记为未选择，以便下次重新选择。

Python代码实现

count = 0

def permutation(num, selected, book_list, n):
    global count
    if num == n:
        count += 1
        print(f"方案{count}: A选择了第{book_list[0]+1}本书，B选择了第{book_list[1]+1}本书，C选择了第{book_list[2]+1}本书")
        return
    for i in range(n):
        if i not in selected and i > selected[-1]:
            selected.append(i)
            book_list.append(num)
            permutation(num+1, selected, book_list, n)
            selected.pop()
            book_list.pop()

permutation(1, [-1], [], 5)  # 初始时将选中的小朋友设为-1

输出结果为60种不同的借法，其中每个方案都展示了A、B、C三位小朋友选择的书籍编号：

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

可以看到，在递归过程中得到的所有方案都被正确统计，并输出了方案编号和三位小朋友选择的书籍编号。其中一共有60种不同的借法。

JAVA代码实现

public class Permutation {
    private static int count = 0;

    private static void permutation(int num, List<Integer> selected, List<Integer> bookList, int n) {
        if(num == n) {
            count++;
            System.out.println("方案" + count + ": A选择了第" + (bookList.get(0)+1) + "本书，B选择了第" + (bookList.get(1)+1) + "本书，C选择了第" + (bookList.get(2)+1) + "本书");
            return;
        }
        for(int i = 0; i < n; i++) {
            if(!selected.contains(i) && i > selected.get(selected.size()-1)) {
                List<Integer> newSelected = new ArrayList<>(selected);
                newSelected.add(i);
                List<Integer> newBookList = new ArrayList<>(bookList);
                newBookList.add(num);
                permutation(num+1, newSelected, newBookList, n);
            }
        }
    }

    public static void main(String[] args) {
        permutation(1, new ArrayList<>(Arrays.asList(-1)), new ArrayList<>(), 5);
        System.out.println(count);
    }
}

运行后输出结果与Python版本的相同。

C语言实现

#include <stdio.h>
#define N 5

int count = 0;

void permutation(int num, int selected[], int bookList[], int n) {
    if(num == n) {
        count++;
        printf("方案%d: A选择了第%d本书，B选择了第%d本书，C选择了第%d本书\n", count, bookList[0]+1, bookList[1]+1, bookList[2]+1);
        return;
    }
    for(int i = 0; i < n; i++) {
        if(!((num == 1 && i > -1) || selected[i] > -1)) {
            int newSelected[n], newBookList[3];
            for(int j = 0; j < n; j++) {
                newSelected[j] = selected[j];
            }
            newSelected[i] = num;
            for(int j = 0; j < 3; j++) {
                newBookList[j] = bookList[j];
            }
            newBookList[num-1] = i;
            permutation(num+1, newSelected, newBookList, n);
        }
    }
}

int main() {
    int selected[N] = {-1, -1, -1, -1, -1};
    int bookList[3] = {-1, -1, -1};
    permutation(1, selected, bookList, N);
    printf("一共有%d种不同的借书方案\n", count);
    return 0;
}

运行后输出结果与Python版本的相同。