In this article, we’ll look at The Friends-Travel Problem, which is highly interesting.
Friends-Travel Problem:
Assume n friends want to go to a party; they can travel alone or with another friend as a couple. We presume that n motorbikes are offered for n buddies.
We need to figure out how many different ways the n friends can get to the party, either individually or in pairs of two as a couple.
Answer:
One can either manually implement the naive technique using loops and if-else statements or use the quicker Recursion approach.
Before going into the problem just have a glance over the recursion.
To solve a larger problem, it is necessary to divide it into smaller difficulties.
Let us consider the lower values of n like ( 1, 2, and 3).
There are only one and two viable options for n = 1 and n = 2, respectively. And for n = 3, there are four alternative outcomes. How?
For each value of n, a friend has two options: either travel alone or search for n-1 friends.
Alternatively, the friend might choose a friend from the n-1 friends to travel with, and we will then look for n-2 friends.
Examples:
Example1:
Input:
Given number of friends = 3
Output:
Different ways the 3 friends can get to the party = 4
Example2:
Input:
Given number of friends = 5
Output:
Different ways the 5 friends can get to the party = 26
Program for Friends-Travel Problem in Python
Method #1: Using Recursion (Static Input)
Approach:
- Give the number(no of friends) as static input and store it in a variable.
- Create a recursive function say numberof_ways() which accepts the given number as an argument and returns the total number of ways friends can get to the party.
- Inside the function, check if the given number is less than 3 using the if conditional statement.
- If it is true, then return the given number.
- Return the value of {numberof_ways(no_frnds-1)) + ((no_frnds-1) * numberof_ways(no_frnds-2)} (Recursive Logic).
- Pass the given number as an argument to the numberof_ways() function and store it in a variable.
- Print the above result.
- The Exit of the Program.
Below is the implementation:
# Create a recursive function say numberof_ways() which accepts the given number # as an argument and returns the total number of ways friends can get to the party. def numberof_ways(no_frnds): # Inside the function, check if the given number is less than 3 using the if # conditional statement. if(no_frnds < 3): # If it is true, then return the given number. return no_frnds # Return the value of count_no_ways(no_frnds-1)) + ((no_frnds-1) * # count_no_ways(no_frnds-2) (Recursive Logic). return (numberof_ways(no_frnds-1)) + ((no_frnds-1) * numberof_ways(no_frnds-2)) # Give the number(no of friends) as static input and store it in a variable. no_frnds = 3 # Pass the given number as an argument to the numberof_ways() function and # store it in a variable. rslt = numberof_ways(no_frnds) # Print the above result. print("Different ways the", no_frnds, "friends can get to the party = ", rslt)
Output:
Different ways the 3 friends can get to the party = 4
Method #2: Using Recursion (User Input)
Approach:
- Give the number(no of friends) as user input using the int(input()) function and store it in a variable.
- Create a recursive function say numberof_ways() which accepts the given number as an argument and returns the total number of ways friends can get to the party.
- Inside the function, check if the given number is less than 3 using the if conditional statement.
- If it is true, then return the given number.
- Return the value of {numberof_ways(no_frnds-1)) + ((no_frnds-1) * numberof_ways(no_frnds-2)} (Recursive Logic).
- Pass the given number as an argument to the numberof_ways() function and store it in a variable.
- Print the above result.
- The Exit of the Program.
Below is the implementation:
# Create a recursive function say numberof_ways() which accepts the given number # as an argument and returns the total number of ways friends can get to the party. def numberof_ways(no_frnds): # Inside the function, check if the given number is less than 3 using the if # conditional statement. if(no_frnds < 3): # If it is true, then return the given number. return no_frnds # Return the value of count_no_ways(no_frnds-1)) + ((no_frnds-1) * # count_no_ways(no_frnds-2) (Recursive Logic). return (numberof_ways(no_frnds-1)) + ((no_frnds-1) * numberof_ways(no_frnds-2)) # Give the number(no of friends) as user input using the int(input()) function and store it in a variable. no_frnds = int(input("Enter some random number = ")) # Pass the given number as an argument to the numberof_ways() function and # store it in a variable. rslt = numberof_ways(no_frnds) # Print the above result. print("Different ways the", no_frnds, "friends can get to the party = ", rslt)
Output:
Enter some random number = 5 Different ways the 5 friends can get to the party = 26