99 lines
3.4 KiB
Python
99 lines
3.4 KiB
Python
"""
|
|
If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
|
|
|
|
Not all numbers produce palindromes so quickly. For example,
|
|
349 + 943 = 1292
|
|
1292 + 2921 = 4213
|
|
4213 + 3124 = 7337
|
|
That is, 349 took three iterations to arrive at a palindrome.
|
|
|
|
Although no one has proved it yet, it is thought that some numbers, like 196,
|
|
never produce a palindrome. A number that never forms a palindrome through the
|
|
reverse and add process is called a Lychrel number. Due to the theoretical nature
|
|
of these numbers, and for the purpose of this problem, we shall assume that
|
|
a number is Lychrel until proven otherwise. In addition you are given that for
|
|
every number below ten-thousand, it will either (i) become a palindrome
|
|
in less than fifty iterations, or, (ii) no one, with all the computing power that exists,
|
|
has managed so far to map it to a palindrome. In fact, 10677 is the first number to
|
|
be shown to require over fifty iterations before producing a palindrome:
|
|
4668731596684224866951378664 (53 iterations, 28-digits).
|
|
|
|
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers;
|
|
the first example is 4994.
|
|
|
|
How many Lychrel numbers are there below ten-thousand?
|
|
|
|
NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.
|
|
"""
|
|
|
|
import time
|
|
from functools import wraps
|
|
from typing import Any, Callable, TypeVar
|
|
|
|
F = TypeVar("F", bound=Callable[..., Any])
|
|
|
|
|
|
def benchmark(repeat: int = 1) -> Callable[[F], F]:
|
|
"""
|
|
重复运行目标函数并计算平均耗时。
|
|
|
|
平均耗时会被存储在 wrapper.avg_time 和 wrapper.total_time 中，
|
|
同时会打印到控制台。函数的返回值不受影响。
|
|
"""
|
|
if repeat < 1:
|
|
raise ValueError("repeat 必须 >= 1")
|
|
|
|
def decorator(func: F) -> F:
|
|
@wraps(func)
|
|
def wrapper(*args: Any, **kwargs: Any) -> Any:
|
|
total = 0.0
|
|
result = None
|
|
|
|
for _ in range(repeat):
|
|
start = time.perf_counter()
|
|
result = func(*args, **kwargs)
|
|
end = time.perf_counter()
|
|
total += end - start
|
|
|
|
wrapper.avg_time = total / repeat # type: ignore[attr-defined]
|
|
wrapper.total_time = total # type: ignore[attr-defined]
|
|
|
|
print(
|
|
f"[Benchmark] {func.__name__} | 重复 {repeat} 次 | "
|
|
f"平均: {wrapper.avg_time:.6f}s | 总计: {wrapper.total_time:.6f}s" # type: ignore[attr-defined]
|
|
)
|
|
return result
|
|
|
|
# 初始化属性，避免调用前访问报错
|
|
wrapper.avg_time = 0.0 # type: ignore[attr-defined]
|
|
wrapper.total_time = 0.0 # type: ignore[attr-defined]
|
|
return wrapper # type: ignore[return-value]
|
|
|
|
return decorator
|
|
|
|
|
|
def is_palindrome(n):
|
|
return str(n) == str(n)[::-1]
|
|
|
|
|
|
def is_lychrel(n, max_iterations=50):
|
|
for _ in range(max_iterations):
|
|
n += int(str(n)[::-1])
|
|
if is_palindrome(n):
|
|
return False
|
|
return True
|
|
|
|
|
|
@benchmark(repeat=15)
|
|
def count_lychrel_numbers(limit):
|
|
count = 0
|
|
for n in range(1, limit + 1):
|
|
if is_lychrel(n):
|
|
count += 1
|
|
return count
|
|
|
|
|
|
if __name__ == "__main__":
|
|
result = count_lychrel_numbers(10000)
|
|
print(f"Number of Lychrel numbers below 10,000: {result}")
|