Вы когда-нибудь слышали о стробограмматических числах? Если нет, то вас ждет угощение! Стробограмматические числа — это увлекательное числовое явление, которое проявляет уникальное свойство при повороте на 180 градусов. Проще говоря, в перевернутом виде они выглядят одинаково. Например, число 609 является стробограмматическим, поскольку при его повороте оно по-прежнему отображается как 609.

В этой статье блога мы глубоко погрузимся в мир стробограмматических чисел, изучая различные методы их генерации и идентификации с помощью программирования. Так что пристегните ремни и готовьтесь к увлекательному путешествию!

Метод 1: подход грубой силы

Давайте начнем с простого, но эффективного метода генерации стробограмматических чисел. Мы можем перебрать все возможные числа в заданном диапазоне и проверить, удовлетворяет ли каждое число стробограмматическому свойству. Вот реализация Python:

def is_strobogrammatic(num):
    valid_pairs = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}
    rotated_num = ''.join([valid_pairs.get(digit, '') for digit in reversed(num)])
    return num == rotated_num
def generate_strobogrammatic_numbers(n):
    result = []
    for num in range(10(n-1), 10n):
        if is_strobogrammatic(str(num)):
            result.append(num)
    return result
# Example usage
print(generate_strobogrammatic_numbers(3))

Метод 2: рекурсивный подход

Еще один элегантный способ создания стробограмматических чисел — использование рекурсивного алгоритма. Мы начинаем с базового случая однозначных стробограмматических чисел (0, 1 и 8), а затем рекурсивно строим более крупные стробограмматические числа, добавляя допустимые пары на обоих концах. Вот реализация Python:

def find_strobogrammatic_numbers(n):
    return helper(n, n)
def helper(m, n):
    if m == 0:
        return ['']
    if m == 1:
        return ['0', '1', '8']

    result = []
    sub_numbers = helper(m - 2, n)

    for sub_number in sub_numbers:
        if m != n:
            result.append('0' + sub_number + '0')
        result.append('1' + sub_number + '1')
        result.append('6' + sub_number + '9')
        result.append('8' + sub_number + '8')
        result.append('9' + sub_number + '6')

    return result
# Example usage
print(find_strobogrammatic_numbers(3))

Метод 3: итеративный подход

Если вы предпочитаете итеративное решение, мы можем использовать два указателя для построения стробограмматических чисел от центра наружу. Мы начинаем с однозначных стробограмматических чисел и продолжаем расширять их, пока не достигнем желаемой длины. Вот реализация Python:

def generate_strobogrammatic_numbers(n):
    even_mid = ['11', '69', '88', '96', '00']
    odd_mid = ['0', '1', '8']

    if n == 1:
        return odd_mid

    if n % 2 == 0:
        results = even_mid
        start = 2
    else:
        results = odd_mid
        start = 1

    while start < n:
        new_results = []
        for result in results:
            if start != n - 1:
                new_results.append('1' + result + '1')
            new_results.append('6' + result + '9')
            new_results.append('8' + result + '8')
            new_results.append('9' + result + '6')
            if start != n - 1:
                new_results.append('0' + result + '0')
        results = new_results
        start += 2

    return results
# Example usage
print(generate_strobogrammatic_numbers(3))

Стробограмматические числа – это увлекательная математическая концепция, которая продолжает интриговать и очаровывать как математиков, так и программистов. В этой статье блога мы рассмотрели несколько методов создания и идентификации стробограмматических чисел с использованием грубой силы, рекурсии и итерации.

Независимо от того, являетесь ли вы любопытным энтузиастом или опытным программистом, эти методы предоставят вам инструменты для изучения и экспериментирования со стробограмматическими числами. Так что вперед, погрузитесь в мир стробограмматических чисел и раскройте секреты, скрытые в их числовой симметрии!