Python Program for Friends-Travel Problem

/ Python / By

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