+ 2

[Solved] Solution of code coach [Hofstadter's Q-Sequence]

What's wrong with this code: It passed only 2 cases def q_sequence(n): if n == 1 or n == 2: return 1 else: return q_sequence(n - q_sequence(n - 1)) + q_sequence(n - q_sequence(n - 2)) How can I fix this ? Thanks in advance. def main(): n = int(input(" ")) if n <= 0: print("Please enter a positive integer.") else: result = q_sequence(n) print( result) if __name__ == "__main__": main()

22nd Apr 2024, 2:27 PM
Suhani Kewat
10 odpowiedzi
+ 5
I would say your code runs only for n <= 35 (more or less) after that you run into a stackoverflow. https://en.m.wikipedia.org/wiki/Stack_overflow#:~:text=The%20most%2Dcommon%20cause%20of,can%20fit%20on%20the%20stack. You can try an iterative solution (using for or while loops) or you can try recursion with memoization. https://wellsr.com/JUMP_LINK__&&__python__&&__JUMP_LINK/optimizing-recursive-functions-with-python-memoization/
22nd Apr 2024, 3:22 PM
Denise Roßberg
Denise Roßberg - avatar
+ 3
piano T thanks for your efforts It has passed 5 caese but not passing 6 case def q_sequence(n, cache={1: 1, 2: 1}): if n not in cache: cache[n] = q_sequence(n - q_sequence(n - 1, cache), cache) + q_sequence(n - q_sequence(n - 2, cache), cache) return cache[n] def main(): n = int(input(" ")) if n <= 0: print("Please enter a positive integer.") else: result = q_sequence(n) print(result) if __name__ == "__main__": main()
22nd Apr 2024, 3:54 PM
Suhani Kewat
+ 2
This code has only passed two cases, the 1st and the 2nd. The remaining four cases are failing.
22nd Apr 2024, 2:57 PM
Suhani Kewat
+ 2
I know where the case test 6 problem comes from The programme starts with the first two known values in the sequence. It then uses a loop to build each subsequent value sequentially. This method only works with results that have already been calculated, which greatly simplifies the understanding and maintenance of the code. It completely eliminates any risk of stack overflow due to deep recursion. By calculating the values linearly programme execution time is considerably reduced as the same information does not have to be recalculated several times. thanks for your help Denise Roßberg Here's the method in the code: def q_sequence(n): cache = {1: 1, 2: 1} for i in range(3, n+1): q_n_minus_1 = cache[i-1] q_n_minus_2 = cache[i-2] index_1 = i - q_n_minus_1 index_2 = i - q_n_minus_2 if index_1 <= 0 or index_2 <= 0: continue if index_1 in cache and index_2 in cache: cache[i] = cache[index_1] + cache[index_2] else: continue return cache.get(n, "No valid value for this n")
22nd Apr 2024, 5:23 PM
piano T
+ 1
You can implement memoization a technique that stores the results of recursive function calls in a cache so they do not have to be recalculated every time. It might work but I'm not sure def q_sequence(n, cache={1: 1, 2: 1}): if n not in cache: cache[n] = q_sequence(n - q_sequence(n - 1, cache), cache) + q_sequence(n - q_sequence(n - 2, cache), cache) return cache[n]
22nd Apr 2024, 3:07 PM
piano T
+ 1
Another method is to set the recursion limit. import sys sys.setrecursionlimit(2000) # 2000 for example, you can set it higher or lower However, memoization runs much faster since it doesn't need to re-calculate again.
23rd Apr 2024, 3:50 AM
Wong Hei Ming
Wong Hei Ming - avatar
+ 1
I have solved it, here is the updated version from sys import setrecursionlimit setrecursionlimit(100000) results = [0] * 10000 def Q(n): if n < 1: return if n <=2: return 1 if results[n] != 0: return results[n] results[n] = Q(n - Q(n - 1)) + Q(n - Q(n -2)) return results[n] x = int(input()) print(Q(x)) And thank you all for your efforts
24th Apr 2024, 1:49 AM
Suhani Kewat
0
I’ll have to look up what a Q sequence is, but right off the bat, it’s extremely risky having a function call itself like you do here. You should always avoid that if possible.
22nd Apr 2024, 2:40 PM
Wilbur Jaywright
Wilbur Jaywright - avatar
0
I have looked up the Q sequence. It looks like function recursion is the easiest way to do it, and it also looks like you’ve done it correctly. The first 20 terms of the function you wrote match the 20 terms listed on Wikipedia, and as far as I can tell, the formula is correct. What cases did it fail? Did the code coach give a reason why?
22nd Apr 2024, 2:44 PM
Wilbur Jaywright
Wilbur Jaywright - avatar
0
I don’t know what the other two cases are.
22nd Apr 2024, 3:43 PM
Wilbur Jaywright
Wilbur Jaywright - avatar