PrepBro
← Назад к вопросам

Генератор идентификаторов

2.0 Middle🔥 151 комментариев
#ООП и проектирование#Структуры данных и алгоритмы#Язык C++

Условие

Напишите библиотечный класс для генерации уникальных идентификаторов по следующим правилам:

  • Первый идентификатор: "A1"
  • Второй: "A2", ..., девятый: "A9"
  • Десятый: "B1", одиннадцатый: "B2", ...
  • После "Z9" следует "A1-A1", затем "A1-A2", ..., "A1-Z9", "A2-A1", ...

Требования

  • Метод std::string next() возвращает следующий идентификатор
  • Метод void reset() сбрасывает генератор в начальное состояние
  • Класс должен быть потокобезопасным (опционально)

Пример использования

IdGenerator gen;

std::cout << gen.next(); // "A1"
std::cout << gen.next(); // "A2"
// ...
std::cout << gen.next(); // "A9"
std::cout << gen.next(); // "B1"
// ... после 234 вызовов (26*9)
std::cout << gen.next(); // "A1-A1"
std::cout << gen.next(); // "A1-A2"

gen.reset();
std::cout << gen.next(); // "A1"

Подсказки

  • Используйте числовой счётчик и конвертируйте его в нужный формат
  • Рассмотрите задачу как преобразование числа в особую систему счисления

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение: Генератор идентификаторов на C++

Анализ системы счисления

Это система с переменным основанием: каждый уровень состоит из пар (буква, цифра):

  • A1-Z9: 26 букв × 9 цифр = 234 комбинации
  • A1-A1 до Z9-Z9: вложенные пары второго уровня

Реализация

Класс хранит счётчик и конвертирует его в ID:

class IdGenerator {

private:

    long long counter = 0;
    
    std::string convertToId(long long num) {
        const long long BASE = 234;
        std::string result;
        num--;
        
        std::vector<int> indices;
        long long remaining = num;
        
        while (true) {
            indices.push_back(remaining % BASE);
            remaining /= BASE;
            if (remaining == 0) break;
            remaining--;
        }
        
        for (int i = indices.size() - 1; i >= 0; i--) {
            if (i < indices.size() - 1) result += "-";
            
            int pair = indices[i];
            char letter = A + (pair / 9);
            int digit = (pair % 9) + 1;
            
            result += letter;
            result += std::to_string(digit);
        }
        
        return result;
    }

public:

    std::string next() {
        return convertToId(++counter);
    }
    
    void reset() {
        counter = 0;
    }
};

Логика преобразования

  1. Счётчик начинается с 0
  2. При next() счётчик инкрементируется
  3. Число преобразуется в систему счисления с основанием 234
  4. Каждая цифра в новой системе = индекс пары (буква, цифра)
  5. Буква = индекс / 9 (0-25 = A-Z)
  6. Цифра = индекс % 9 (1-9)

Примеры:

  • counter=1 → "A1"
  • counter=9 → "A9"
  • counter=10 → "B1"
  • counter=234 → "Z9"
  • counter=235 → "A1-A1" (первая пара второго уровня)

Потокобезопасность

Для многопоточности добавить: mutable std::mutex mtx;

В методах next() и reset() обернуть код в: std::lock_guardstd::mutex lock(mtx);

Сложность

  • next(): O(log n) время, O(log n) память (n — текущее число)
  • reset(): O(1)

Логарифмическая сложность потому, что глубина преобразования ~ log₂₃₄(n)

Генератор идентификаторов | PrepBro