Introduction to Interesting Algorithms in Python - How Much Do You Know About Borrowing Solutions

please call me 2022-11-08 03:33:11 阅读数:446

introductioninterestingalgorithmspythonknow

Problem description

Xiao Ming has 5 new books and wants to lend them to three children A, B and C. If each person can only borrow 1 book at a time, how many different ways can they borrow?

Analysis

This problem is a typical permutation and combination problem, but there are sequential requirements. For example, if the same three people lent books 1, 2, and 3, then A, B, and C borrow 1, 2, 3 and C,B and A borrowing 1, 2, and 3 are two different borrowing methods.Because the amount of data is small enough (5 books, 3 people), exhaustiveness can be used.

It is foreseeable that we need to set up a three-layer loop to simulate different borrowing scenarios.If A borrows first, then A can choose one of the 5 books, that is, there are 5 choices, while B can only choose from the remaining 4 books. After B has selected the book, C can only chooseChoose from the remaining 3 books.Although through simple calculation, it can be calculated that there are a total of 5*4*3=60Different ways of borrowing.But enumerating all the borrowing scenarios through the computer is the embodiment of computer thinking:

books = set(range(1,6))res = []for a in books:for b in books-{a}:for c in books-{a,b}:res.append((a,b,c))print(f"A borrows book {a}, B borrows book {b}, C borrows book {c}")print(f"There are {len(res)} kinds of borrowing methods")

Here we can use numbers 1 to 5 to indicate the number of books, and the books that can be borrowed are a set, so when A borrows a book, the set that B can borrow is the original set minus theA borrowed book, so here you can use the subtraction of the set to generate a new set.Similarly, when C borrows books, the set of available books is the original set minus the books borrowed by A and B.In this way, we can do full traversal.

But as we all know, the advantage of Python lies in its large number of functions and modules. As an interpreted scripting language, it does not require learners to pay too much attention to the underlying C implementation. Therefore, it is often required in C and other languages.The function implemented by the statement can be solved clearly and clearly with one sentence of Python.Therefore, Brother Wen believes that learners who are determined to use Python as the main means to solve problems should pay more attention to the creativity of combining mathematics, implementation methods, and problem solving.In a word, don't reinvent the wheel.

Take this question as an example, for the permutation and combination, Python has done the combinations() and permutations() functions in the built-in module itertools. Using the built-in functions, the result can be obtained in one sentence, so there is no need to consider multiplecycle.

from itertools import permutationsres = list(permutations(range(1,6),3))for i in res:print(f"A borrows the {i[0]}th book, B borrows the {i[1]}th book, C borrows the {i[2]}th book")print(f"There are {len(res)} kinds of borrowing methods")

Output

A borrows book 1, B borrows book 2, and C borrows book 3A borrows the 1st book, B borrows the 2nd book, C borrows the 4th bookA borrows the 1st book, B borrows the 2nd book, C borrows the 5th bookA borrows the 1st book, B borrows the 3rd book, C borrows the 2nd bookA borrows the 1st book, B borrows the 3rd book, C borrows the 4th bookA borrows the 1st book, B borrows the 3rd book, C borrows the 5th bookA borrows the 1st book, B borrows the 4th book, C borrows the 2nd bookA borrows the 1st book, B borrows the 4th book, C borrows the 3rd bookA borrows the 1st book, B borrows the 4th book, C borrows the 5th bookA borrows the 1st book, B borrows the 5th book, C borrows the 2nd bookA borrows the 1st book, B borrows the 5th book, C borrows the 3rd bookA borrows the 1st book, B borrows the 5th book, C borrows the 4th bookA borrows the 2nd book, B borrows the 1st book, C borrows the 3rd bookA borrows the 2nd book, B borrows the 1st book, C borrows the 4th bookA borrows the 2nd book, B borrows the 1st book, C borrows the 5th bookA borrows the 2nd book, B borrows the 3rd book, C borrows the 1st bookA borrows the 2nd book, B borrows the 3rd book, C borrows the 4th bookA borrows the 2nd book, B borrows the 3rd book, C borrows the 5th bookA borrows the 2nd book, B borrows the 4th book, C borrows the 1st bookA borrows the 2nd book, B borrows the 4th book, C borrows the 3rd bookA borrows the 2nd book, B borrows the 4th book, C borrows the 5th bookA borrows the 2nd book, B borrows the 5th book, C borrows the 1st bookA borrows the 2nd book, B borrows the 5th book, C borrows the 3rd bookA borrows the 2nd book, B borrows the 5th book, C borrows the 4th bookA borrows the 3rd book, B borrows the 1st book, C borrows the 2nd bookA borrows the 3rd book, B borrows the 1st book, C borrows the 4th bookA borrows the 3rd book, B borrows the 1st book, C borrows the 5th bookA borrows the 3rd book, B borrows the 2nd book, C borrows the 1st bookA borrows the 3rd book, B borrows the 2nd book, C borrows the 4th bookA borrows the 3rd book, B borrows the 2nd book, C borrows the 5th bookA borrows the 3rd book, B borrows the 4th book, C borrows the 1st bookA borrows the 3rd book, B borrows the 4th book, C borrows the 2nd bookA borrows the 3rd book, B borrows the 4th book, C borrows the 5th bookA borrows the 3rd book, B borrows the 5th book, C borrows the 1st bookA borrows the 3rd book, B borrows the 5th book, C borrows the 2nd bookA borrows the 3rd book, B borrows the 5th book, C borrows the 4th bookA borrows the 4th book, B borrows the 1st book, C borrows the 2nd bookA borrows the 4th book, B borrows the 1st book, C borrows the 3rd bookA borrows the 4th book, B borrows the 1st book, C borrows the 5th bookA borrows the 4th book, B borrows the 2nd book, C borrows the 1st bookA borrows the 4th book, B borrows the 2nd book, C borrows the 3rd bookA borrows the 4th book, B borrows the 2nd book, C borrows the 5th bookA borrows the 4th book, B borrows the 3rd book, C borrows the 1st bookA borrows the 4th book, B borrows the 3rd book, C borrows the 2nd bookA borrows the 4th book, B borrows the 3rd book, C borrows the 5th bookA borrows the 4th book, B borrows the 5th book, C borrows the 1st bookA borrows the 4th book, B borrows the 5th book, C borrows the 2nd bookA borrows the 4th book, B borrows the 5th book, C borrows the 3rd bookA borrows the 5th book, B borrows the 1st book, C borrows the 2nd bookA borrows the 5th book, B borrows the 1st book, C borrows the 3rd bookA borrows the 5th book, B borrows the 1st book, C borrows the 4th bookA borrows the 5th book, B borrows the 2nd book, C borrows the 1st bookA borrows the 5th book, B borrows the 2nd book, C borrows the 3rd bookA borrows the 5th book, B borrows the 2nd book, C borrows the 4th bookA borrows the 5th book, B borrows the 3rd book, C borrows the 1st bookA borrows the 5th book, B borrows the 3rd book, C borrows the 2nd bookA borrows the 5th book, B borrows the 3rd book, C borrows the 4th bookA borrows the 5th book, B borrows the 4th book, C borrows the 1st bookA borrows the 5th book, B borrows the 4th book, C borrows the 2nd bookA borrows the 5th book, B borrows the 4th book, C borrows the 3rd bookA total of 60 borrowing methods

版权声明:本文为[please call me]所创,转载请带上原文链接,感谢。 https://pythonmana.com/2022/312/202211080319247215.html