Tarkibga o'tish

Excel ustunlari

Excel elektron jadvali ustunlarini harflar bilan belgilaydi: A, B, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA, ...

Ustun nomini songa, sonni ustun nomiga aylantiruvchi ikki masala.

Birinchi masala: ustun nomi → son

"A" → 1, "B" → 2, ..., "Z" → 26, "AA" → 27, "AB" → 28, ..., "ZZ" → 702.

Kirish: "A"     Chiqish: 1
Kirish: "AB"    Chiqish: 28
Kirish: "ZY"    Chiqish: 701
Kirish: "AAA"   Chiqish: 703

Nima uchun oddiy base-26 emas?

Oddiy o'n oltilik yoki o'n ikkilik kabi 0 raqamiga mos harf yo'q. A = 1, Z = 26, AA = 27 — bu 26-lik sanoq, lekin A = 1 bilan boshlanadi, 0 ekvivalenti yo'q. Bu shifted base-26 deyiladi.

G'oya: chapdan o'ngga o'qish

O'nlik sanoqdagi "123" ni 1×100 + 2×10 + 3 deb o'qiganimizdek:

"AB" = A × 26 + B = 1 × 26 + 2 = 28
"ZY" = Z × 26 + Y = 26 × 26 + 25 = 701
"AAA" = A × 26² + A × 26 + A = 1×676 + 1×26 + 1 = 703

FUNCTION COLUMN_TITLE_TO_NUMBER(s)
    result = 0
    FOR har bir c s ichida (chapdan o'ngga)
        digit  = c - 'A' + 1       // 'A'→1, 'B'→2, ..., 'Z'→26
        result = result * 26 + digit
    RETURN result

Dry run: "ZY"

result = 0

c = 'Z': digit = 'Z' - 'A' + 1 = 26,  result = 0 * 26 + 26 = 26
c = 'Y': digit = 'Y' - 'A' + 1 = 25,  result = 26 * 26 + 25 = 701

RETURN 701

Dry run: "AAA"

result = 0

c = 'A': digit = 1,  result = 0 * 26 + 1 = 1
c = 'A': digit = 1,  result = 1 * 26 + 1 = 27
c = 'A': digit = 1,  result = 27 * 26 + 1 = 703

RETURN 703

Murakkablik

  • Vaqt: O(k) — k ustun nomi uzunligi
  • Xotira: O(1)

Ikkinchi masala: son → ustun nomi

1 → "A", 26 → "Z", 27 → "AA", 28 → "AB", 701 → "ZY".

Kirish: 1      Chiqish: "A"
Kirish: 28     Chiqish: "AB"
Kirish: 701    Chiqish: "ZY"
Kirish: 703    Chiqish: "AAA"

Nima uchun oddiy base-26 konversiyasi ishlamaydi?

Oddiy base-26 da: 26 % 26 = 0. Lekin 0 ga mos harf yo'q — A = 1, Z = 26. 0 ekvivalenti bo'lmasligi sababli oddiy % 26 bilan konversiya buziladi.

26 → Z bo'lishi kerak, lekin 26 % 26 = 0 → '\0' (belgi yo'q).

G'oya: har qadamda 1 ayirish

0 raqami yo'qligi muammosini hal qilish uchun har qadamda n = n - 1 qilib, keyin % 26 va / 26 bajariladi. Bu "sanoqni 0-indexed ga o'tkazish" kabi.

FUNCTION COLUMN_NUMBER_TO_TITLE(n)
    result = bo'sh string

    WHILE n > 0
        n     = n - 1                   // 0-indexed ga o'tkazish
        harf  = 'A' + (n % 26)          // 0→'A', 1→'B', ..., 25→'Z'
        result ga harf ni old tomonga qo'sh
        n     = n / 26

    RETURN result

Nima uchun n = n - 1 kerak?

n = 26 ("Z" bo'lishi kerak)
n - 1 = 25
25 % 26 = 25 → 'A' + 25 = 'Z' ✓
25 / 26 = 0 → tsikl tugaydi

n = 27 ("AA" bo'lishi kerak)
n - 1 = 26
26 % 26 = 0 → 'A' + 0 = 'A' ✓
26 / 26 = 1

n = 1
n - 1 = 0
0 % 26 = 0 → 'A' + 0 = 'A' ✓
0 / 26 = 0 → tsikl tugaydi

Natija (teskari): "AA" ✓

Dry run: n = 701 → "ZY"

Qadam 1: n = 701
  n - 1 = 700
  700 % 26 = 24  →  'A' + 24 = 'Y'
  result = "Y"
  n = 700 / 26 = 26

Qadam 2: n = 26
  n - 1 = 25
  25 % 26 = 25  →  'A' + 25 = 'Z'
  result = "ZY"
  n = 25 / 26 = 0

n = 0 → tsikl tugaydi
RETURN "ZY"

Dry run: n = 703 → "AAA"

Qadam 1: n = 703
  n - 1 = 702
  702 % 26 = 0   →  'A' + 0 = 'A'
  result = "A"
  n = 702 / 26 = 27

Qadam 2: n = 27
  n - 1 = 26
  26 % 26 = 0    →  'A' + 0 = 'A'
  result = "AA"
  n = 26 / 26 = 1

Qadam 3: n = 1
  n - 1 = 0
  0 % 26 = 0     →  'A' + 0 = 'A'
  result = "AAA"
  n = 0 / 26 = 0

RETURN "AAA"

Murakkablik

  • Vaqt: O(log₂₆ n) — ustun nomining uzunligi
  • Xotira: O(log₂₆ n) — natija string

Ikkala masala taqqoslanishi

Masala Yo'nalish G'oya Vaqt
Nomi → son "AB" → 28 result = result * 26 + digit O(k)
Son → nom 28 → "AB" n = n - 1, harf = n % 26, n = n / 26 O(log₂₆ n)

Edge case'lar

n = 1: 1-1=0, 0%26=0 → 'A', 0/26=0. Natija: "A".

n = 26: 26-1=25, 25%26=25 → 'Z', 25/26=0. Natija: "Z".

Juda katta son. "FXSHRXW" ~ 2 milliard. 32-bitli son uchun ma'qul. 64-bitli sonda yanada katta ustunlar bilan ishlash mumkin.

Bitta harf. "Z" → 26. 26 % 26 = 0 muammo — shuning uchun n - 1 kerak edi.

Note

'A' + (n % 26) iborasi ishlash uchun 'A' belgisining ASCII raqami ma'lum bo'lishi kerak (65). Ko'p tillarda bu iborasi bevosita ishlaydi, ba'zilarida CHAR('A' + ...) yoki CHR(65 + ...) kabi sinxtatik farqlar bo'lishi mumkin.

Xulosa

Excel ustunlari — shifted base-26 sanoq tizimi. A = 1, Z = 26, nol ekvivalenti yo'q. Shuning uchun oddiy base-26 emas.

Nomdan songa: result = result * 26 + digit — chapdan o'ngga o'qish.

Sondan nomga: har qadam n = n - 1 bilan 0-indexed ga o'tkazilib, n % 26 harf, n / 26 keyingi bosqich. Harflar teskari tartibda yig'iladi.