In this tutorial, we will be understanding a very interesting problem known as The Friends-Travel Problem. Let us first understand what do we want to achieve in this problem.
Friends-Travel Problem Explaination
Let us suppose n friends want to go to a party, they can travel either individually or along with a friend as a couple. We assume that for n friends, n motorbikes are available.
We need to compute the number of ways the n friends can travel to the party, either individually or in pair of two as a couple.
Solution to the Friends-Travel Problem
One can either manually code the naive approach using loops and if-else conditions or can go for the faster approach which is the Recursion approach. If you want to know more about recursion read the tutorial mentioned below.
Read more about Recursion: Recursion in Python
In order to solve a bigger problem, one needs to break a bigger problem into smaller problems. But before that, let’s look at the lower values of n ( 1, 2, and 3).
For n = 1 and n = 2, there are only one and two possible ways respectively. And for n = 3, we have four possible cases. How?
For every value of n, a friend has two choices, either the friend can travel alone and we can check for n-1 friends.
Or the friend can choose a friend from the n-1 friends to travel with and then we check for n-2 friends.
Code Implementation of the Friends-Bike Problem
The code implementation is very simple through recursion. Just make sure you have understood the solution explained earlier.
def count_no_ways(n): if(n<3): return n return (count_no_ways(n-1)) + ((n-1) * count_no_ways(n-2)) n = int(input("Enter the number of friends: ")) print(count_no_ways(n))
I hope the problem, solution, and code implementation are clear to you. Thank you for reading the tutorial!
Happy learning! 😇