[Computer Science / Python Algorithm Question]

Fibonacci(tribonacci) sequence

Please fix my code if there is something wrong with the requirements.(Also leave a comment please)

• Problem:
  • find the number of ways to have (where 1) 1 dollars in the jar
  • You may assume that each time you can also put three 1 dollars in the basket
  • for example, there are four ways to have three 1 dollars in the basket:
    • put in one 1 dollar three times
    • first put in one 1 dollar then two 1 dollars
    • first put in two 1 dollars then one 1 dollar
    • put in three 1 dollars altogether
  • the solution must qualify the complexity below,
• Complexity:
  • () time
  • (1) space

==============================================================

# Implementation

""" Find the number of ways to have n (where n >= 1) 1 dollars in the jar You can assume each time you put either one 1 dollar, or two 1 dollars, or three 1 dollars in the jar Parameters ---------- n : an integer >= 1 Returns ---------- the number of ways : an integer """ def prac_1(n): if n <= 2: return n a, b, c = 1, 1, 2 for _ in range(3, n + 1): d = a + b + c a = b b = c c = d

return d

============================================================

# Test <--- the output is given for i in range(1, 20): print(i, prac_1(i))

1 1 2 2 3 4 4 7 5 13 6 24 7 44 8 81 9 149 10 274 11 504 12 927 13 1705 14 3136 15 5768 16 10609 17 19513 18 35890 19 66012