Programmiererforum

The algorithm for computing the function F(n), where n is a natural number, is given by the following relations:

F(n) = n if n ≥ 10,000,

F(n) = n/4 + F(n / 4 + 2) if n < 10 000 and n is divisible by 4,

F(n) = 1 + F(n + 2) , if n < 10 000 and n is not divisible by 4.

What is the value of the expression F(174) - F(3)?

import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)

@lru_cache(None)
def F(n):
if n >= 10000:
return n
elif n % 4 == 0:
return n // 4 + F(n // 4 + 2)
else:
return 1 + F(n + 2)

print(F(174) - F(3))

Ich bin Student. Unser Lehrer hat uns gebeten, die folgende Aufgabe zu erledigen (ich habe sie der Einfachheit halber ins Englische übersetzt)
[code]The algorithm for computing the function F(n), where n is a natural number, is given by the following relations:

F(n) = n if n ≥ 10,000,

F(n) = n/4 + F(n / 4 + 2) if n < 10 000 and n is divisible by 4,

F(n) = 1 + F(n + 2) , if n < 10 000 and n is not divisible by 4.

What is the value of the expression F(174) - F(3)?
[/code]
[b]Richtige Antwort: 67[/b]
Er hat uns empfohlen, lru_cache für das Caching und eine schnellere Rekursion zu verwenden, aber dieses Caching funktioniert nicht. Funktioniert nicht auf Desktop-PCs, nur auf Online-Python-Interpretern
Mein Code:
[code]import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)

@lru_cache(None)
def F(n):
if n >= 10000:
return n
elif n % 4 == 0:
return n // 4 + F(n // 4 + 2)
else:
return 1 + F(n + 2)

print(F(174) - F(3))
[/code]
VScode:
Das Programm läuft in VScode, die Ausgabeantwort ist leer
https://i.imgur.com/jZwLZyb.png
OnlineGDB:
Das Programm wird in OnlineGDB ausgeführt, die richtige Antwort wird angezeigt
Wenn ich die Zeilen mit Cache auskommentiere, funktioniert alles auch ohne . Das Problem ist, dass wir ähnliche Aufgaben bereits gelöst haben und es die gleiche Situation gab – auf Caching kann man nicht verzichten, aber es funktioniert nur in Online-Interpretern
Das Lustigste ist, dass diese Aufgaben sind für eine Prüfung gedacht, bei der der Zugriff auf einen Online-Dolmetscher natürlich nicht möglich ist.
Das Programm soll sowohl auf dem PC als auch im Online-Dolmetscher eine 67er-Antwort ausgeben, aber es passiert nur im letzten Fall. Vielleicht macht es keinen Sinn, bei dieser Aufgabe Caching zu verwenden, aber ich kann nicht verstehen, warum es nicht funktioniert