python coding test course, finding the number of friends

Hello! In this lecture, we will cover an algorithm problem to calculate Ichin numbers. An Ichin number is a number made up of 0s and 1s that does not have two consecutive 1s. For example, 3-digit Ichin numbers are 000, 001, 010, 100, 101, 110, which totals to 6.

Problem Description

Given an integer N, we will solve the problem of finding all N-digit Ichin numbers and outputting their count.

Problem

Input N and output the count of all N-digit Ichin numbers.

Example Input

N = 3

Example Output

6

Approach to the Problem

There are two approaches to solve this problem. The first method uses recursion with DFS (Depth-First Search), and the second method uses Dynamic Programming. Let’s take a detailed look at each method.

1. Method Using Recursive DFS

The recursive method follows these two rules to generate Ichin numbers:

  • If the current digit is 0, we can place either 0 or 1 in the next position.
  • If the current digit is 1, we can only place 0 in the next position.

According to these rules, we can write a recursive function to generate Ichin numbers. Here is the implementation:

def count_ichin(N, current_sequence, last_digit):
    if len(current_sequence) == N:
        return 1

    count = 0
    if last_digit == 0:
        count += count_ichin(N, current_sequence + '0', 0)
        count += count_ichin(N, current_sequence + '1', 1)
    else:
        count += count_ichin(N, current_sequence + '0', 0)

    return count

N = 3
result = count_ichin(N, '', 0)
print(result)

The above code defines a recursive function count_ichin() to generate Ichin numbers, passing N and an empty string as initial values. The last digit starts as 0.

2. Method Using Dynamic Programming

When calculating Ichin numbers, using dynamic programming allows for a more efficient solution through memorization. The count of Ichin numbers I(n) can be defined with the following recurrence relation:

I(n) = I(n-1) + I(n-2)

The meaning of this equation is as follows:

  • If you place 0 in the n-1 position: The count of Ichin numbers is I(n-1).
  • If you place 10 in the n-2 position: The count of Ichin numbers is I(n-2).

Now we will implement dynamic programming based on this recurrence relation:

def find_ichin_count(N):
    if N == 1:
        return 1
    elif N == 2:
        return 1

    dp = [0] * (N + 1)
    dp[1] = 1
    dp[2] = 1

    for i in range(3, N + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[N]

N = 3
result = find_ichin_count(N)
print(result)

With the above code, the dynamic programming approach to finding Ichin numbers has been efficiently implemented.

Comparison and Selection

The recursive method is easy to understand but may be inefficient for large N values. In contrast, the dynamic programming method uses memory to reuse previous computation results, making it more performant. Generally, it is advisable to use dynamic programming for larger N values.

Conclusion

In this lecture, we discussed the problem of finding Ichin numbers. We learned to calculate Ichin numbers using both recursive and dynamic programming methods. I hope this problem helps you enhance your algorithmic problem-solving skills.

Thank you!