试用Le Chat解决圆周相邻和平方问题‐2 - l1t1/note GitHub Wiki

这是注册Le Chat后几轮优化后的程序，默认语言没有汉语，选的英语

# 用二进制数bitand运算不为0代替in square_set和in path判断来改写

import time

def generate_square_bitmap(max_num):
    """Generate a bitmap where each bit represents whether a number is a perfect square."""
    max_sum = 2 * max_num
    square_bitmap = 0
    i = 1
    while i * i <= max_sum:
        square_bitmap |= (1 << i * i)
        i += 1
    return square_bitmap

def place_numbers(n):
    """Place numbers from 1 to n in a circle such that the sum of each adjacent pair is a perfect square."""
    square_bitmap = generate_square_bitmap(n)

    def is_square(num):
        """Check if a number is a perfect square using the bitmap."""
        return (square_bitmap & (1 << num)) != 0

    def backtrack(path, used):
        if len(path) == n:
            # Check if the sum of the first and last number in the path is a perfect square
            if is_square(path[0] + path[-1]):
                return path
            return None

        for num in range(1, n + 1):
            if (used & (1 << num)) == 0 and (len(path) == 0 or is_square(path[-1] + num)):
                path.append(num)
                used |= (1 << num)
                result = backtrack(path, used)
                if result:
                    return result
                path.pop()
                used &= ~(1 << num)
        return None

    return backtrack([], 0)

def main():
    while True:
        try:
            n = int(input("Enter a value for n (0 to exit): "))
            if n == 0:
                print("Exiting the program.")
                break
            start_time = time.time()
            result = place_numbers(n)
            end_time = time.time()
            if result:
                print("Sequence found:", result)
            else:
                print("No valid sequence found.")
            print(f"Time taken: {end_time - start_time:.4f} seconds")
        except ValueError:
            print("Please enter a valid integer.")

if __name__ == "__main__":
    main()