算法解題：在一串無限的數字序列中，找到特定位置上的數字？

By徐培鈞
LinkedIn

更新日期： 2025 年 3 月 8 日

在程式設計與數學問題中，數字序列相關的題目經常出現。

本篇文章將針對一個特定的數字序列謎題，進行詳細解說並提供完整的解題思路與程式實現，適合初學者理解與學習。

希望透過這篇文章，讓讀者能夠掌握這類問題的解法，並舉一反三，應用於類似的演算法問題中。

題目說明

給定一個無限延伸的數字序列，如下所示：

123456789101112131415161718192021……

這個序列是將自然數 (1, 2, 3, 4, …) 依序連接在一起形成的一個長串數字。

我們的任務是在這個序列中，找到特定位置 (索引) 上所對應的數字。例如：

  • 序列中的第 9 位是數字 9。
  • 序列中的第 10 位是數字 1（數字 10 的第一位）。
  • 序列中的第 11 位是數字 0（數字 10 的第二位）。

目標

我們需要找出以下位置上的數字：

  1. 第 1,000,000 位的數字。
  2. 第 1,000,000,000 位的數字。
  3. 第 1,000,000,000,000 位的數字。

性能要求

演算法的執行時間應保持在 2 秒以內，即使是面對超大數字的位置查詢。

概念轉換：難民與土地的比喻

理解題目的方式

為了更直觀地理解這個問題，我們可以將題目想像成有一群「難民」（數字）需要入住某個地區（序列中的土地位置）。

這些難民根據他們「體型」（數字位數）的不同，會被分配到不同大小的居住區域。

城市中的不同社區：

  1. 瘦子人種（1 位數，1 間臥室）：
    • 住在第一個社區，接收號碼牌 1 ~ 9 的人。
    • 共有 9 個人，每個人只需要 1 間臥室。
    • 因此，第一社區區總共需要 9 * 1 = 9 間臥室（土地 1 ~ 9 號）。
  2. 普通人種（2 位數，2 間臥室）：
    • 住在第二個社區，接收號碼牌 10 ~ 99 的人。
    • 共有 90 個人，每個人需要 2 間臥室。
    • 因此，第二社區總共需要 90 * 2 = 180 間臥室（土地 10 ~ 189 號）。
  3. 胖子人種（3 位數，3 間臥室）：
    • 住在第三個社區，接收號碼牌 100 ~ 999 的人。
    • 共有 900 個人，每個人需要 3 間臥室。
    • 因此，第三社區總共需要 900 * 3 = 2700 間臥室（土地 190 ~ 2889 號）。
  4. 更多空間的社區：
    • 4 位數需要 4 * 9000 = 36000 間臥室。
    • 5 位數需要 5 * 90000 = 450000 間臥室。
    • 依此類推，每個社區根據人種的「體型」需要的空間成倍增長。

數字的小房子與房間分配

我們將不同位數的數字比喻成不同大小的小房子，每個房間對應數字中的一位數字：

  • 1 位數 (瘦子人種)：小房子只有 1 間房間，例如：[5] 代表數字 5。
  • 2 位數 (普通人種)：小房子有 2 間房間，例如：[4][2] 代表數字 42。
  • 3 位數 (胖子人種)：小房子有 3 間房間，例如：[7][0][3] 代表數字 703。

從 0 開始數的房間編號

在程式語言和數學中，編號經常從 0 開始，而不是從 1 開始，這與我們日常生活中的計數方式有所不同。例如：

  • 第一個房間編號是 0，第二個房間編號是 1，第三個房間編號是 2。
  • 如數字 703，房間編號與數字對應關係如下：
[7][0][3]
  0  1  2

用餘數 (Modulo) 來計算房間編號

計算房間編號時，經常使用餘數 (%) 運算。例如：

(位置 - 1) % 數字位數 = 房間編號
  • 示例：計算 1811 號位置在數字 703 中的房間位置：
(1811 - 1) % 3 = 1810 % 3 = 2
  • 這表示 1811 號位置對應到數字 703 的「第 2 號房間」，數字是 3。

範例解析：從理論到實際

三大人種 (不同位數的數字)

  1. 瘦子人種（1 位數）：住在一個只有「1 間房間」的小房子裡，例如：[5] 代表數字 5。
  2. 普通人種（2 位數）：住在「2 間房間」的小房子裡，例如：[4][2] 代表數字 42。
  3. 胖子人種（3 位數）：住在「3 間房間」的小房子裡，例如：[7][0][3] 代表數字 703。

社區規劃 (不同位數區域)

  1. 瘦子人種社區：僅有 9 間房子（數字 1 到 9），每間房子只有 1 間房間，共 9 個房間。
  2. 普通人種社區：有 90 間房子（數字 10 到 99），每間房子有 2 間房間，共 180 個房間。
  3. 胖子人種社區：有 900 間房子（數字 100 到 999），每間房子有 3 間房間，共 2700 個房間。

第 13 號房間的推導過程

1️⃣ 確認「第 13 號房間」在哪個社區

  1. 瘦子人種社區：
    • 這個社區有 9 間房子，共 9 個房間。
    • 13 > 9，房間編號超出，需進入下一個社區。
  2. 普通人種社區：
    • 這個社區有 90 間房子，每間房子有 2 個房間，共 180 個房間。
    • 13 – 9 = 4，表示我們要找的「第 13 號房間」在「普通人種社區」的第 4 號房間。

2️⃣ 計算具體的「居民」(數字)

  1. 普通人種社區 的居民 (數字) 從 10 開始。
  2. 每位居民 (數字) 需要 2 個房間 (2 位數)。
  • 哪位居民住在第 4 號房間？
居民編號 = (4 - 1) // 2 = 3 // 2 = 1
  • 對應的居民 (數字)：
起始數字 + 居民編號 = 10 + 1 = 11
  • 數字 11 可以視為一間「有 2 間房間」的小房子：
[1][1]
 0  1

3️⃣ 找到具體「房間」的數字

  • 第 4 號房間 是在數字 11 這間房子中的「第幾間房間」呢？
(4 - 1) % 2 = 3 % 2 = 1
  • 這個結果表示「第 4 號房間」對應到數字 11 中的「第 1 號房間」。
  • 在小房子 [1][1] 裡，第 1 號房間裡住的是數字 1。

4️⃣ 結果：第 13 號房間裡住的是數字 1

第 2000 號房間的推導過程

1️⃣ 確認「第 2000 號房間」在哪個社區

  1. 瘦子人種社區：
    • 9 間房子 (9 個房間)，2000 > 9，超出範圍。
    • 剩下：2000 - 9 = 1991
  2. 普通人種社區：
    • 90 間房子 (180 個房間)，1991 > 180，超出範圍。
    • 剩下：1991 - 180 = 1811
  3. 胖子人種社區：
    • 900 間房子 (2700 個房間)，1811 <= 2700，確定在此社區。

2️⃣ 計算具體的「居民」(數字)

  1. 胖子人種社區 的居民 (數字) 從 100 開始。
  2. 每位居民 (數字) 需要 3 個房間 (3 位數)。
  • 哪位居民住在第 1811 號房間？
居民編號 = (1811 - 1) // 3 = 1810 // 3 = 603
  • 對應的居民 (數字)：
起始數字 + 居民編號 = 100 + 603 = 703
  • 數字 703 可視為一間「有 3 間房間」的小房子：
[7][0][3]
 0  1  2
3️⃣ 找到具體「房間」的數字
  • 第 2000 號房間 在數字 703 中的「第幾號房間」？
(1811 - 1) % 3 = 1810 % 3 = 1
  • 這表示「第 2000 號房間」對應到數字 703 裡的「第 1 號房間」。
  • 在小房子 [7][0][3] 裡，第 1 號房間裡住的是數字 0。

4️⃣ 結果：第 2000 號房間裡住的是數字 0

為什麼要 -1？深入解析位置與房間編號的差異

在解數字序列問題時，我們經常遇到「為什麼要 -1」的疑問。

這個 -1 不僅出現在計算「居民編號 (數字索引)」時，也出現在計算「房間編號 (數字中的具體位數)」時。

接下來，我將通過實際案例和詳細推導，解釋這個 -1 背後的邏輯，並說明「商數」的用途——如何通過商數來確定「實際居民」的數字。

現實世界 VS. 程式世界的編號方式

1️⃣ 真實世界中的編號方式

  • 在日常生活中，房間、座位、樓層的編號通常從 1 開始：
房間 1, 房間 2, 房間 3, ... 房間 10
  • 這種「自然數編號」的方式，直觀且符合我們的日常習慣。

2️⃣ 程式世界中的編號方式

  • 在程式語言中，陣列 (Array)、字串 (String) 等數據結構中的編號 (索引) 是從 0 開始：
房間 0, 房間 1, 房間 2, ...
  • 這被稱為「零基索引 (Zero-based Indexing)」，這種編號方式在程式計算中更方便，因為第一個位置 (索引) 就是 0。

計算居民編號時為什麼要 -1？

在計算「居民編號」時，我們使用的公式是：

居民編號 = (目標位置 - 已用房間數 - 1) // 每位居民佔用的房間數
  • 商數的用途：
    • 計算的「商數」表示目標房間對應的「居民 (數字) 編號」。
    • 再加上起始數字，確定「具體居民 (數字)」是誰。

1️⃣ 示例：計算第 15 號房間的居民編號

  • 普通人種社區 (2 位數)，每位居民佔 2 間房間。
  • 先扣除「瘦子人種社區」的 9 間房間，剩下 15 - 9 = 6 間房間。
  • 計算居民編號：
(15 - 9 - 1) // 2 = 5 // 2 = 2

這個商數 2 代表什麼？

  1. 居民數字計算：
實際居民數字 = 起始數字 + 居民編號
實際居民數字 = 10 + 2 = 10
  1. 解釋邏輯：
  • 「普通人種社區」的數字從 10 開始。
  • 這裡的商數 0 表示我們要找的是「第 2 位居民」，也就是數字 12。

2️⃣ 如果不 -1 會怎樣？

假如不減 1，公式會變成：

(15 - 9) // 2 = 6 // 2 = 3 (錯誤的結果)
  • 計算出「第 3 位居民」，但實際上應該是「第 2 位居民」（從 0 位開始計算）。
  • 如果用這個錯誤的結果去計算：
實際居民數字 = 10 + 3 = 13 (錯誤)
  • 正確的數字應該是 12 而不是 13，這就是不減 1 導致的錯位問題。

📌 總結：計算居民編號時，扣 1 是為了將「從 1 開始數的房間位置」轉換為「從 0 開始數的居民編號」，這樣才能正確計算出實際的數字 (居民)。

計算房間編號時為什麼要 -1？

當找到具體的居民 (數字) 後，我們還需要計算「目標房間」在這間小房子 (數字) 中的具體「房間位置」。這時使用的公式是：

房間編號 = (目標位置 - 1) % 每位居民的房間數

1️⃣ 示例：計算數字 12 中的房間位置

  • 數字 12 可以視為小房子 [1][2]，有 2 間房間，從 0 開始編號：
[1][2]
 0  1
  • 第 15 號房間在這間房子中的「第幾間房間」？
(6 - 1) % 2 = 5 % 2 = 1
  • 為什麼要 -1？

假如不減 1，會變成：

6 % 2 = 0
  • 這將錯誤地指向數字 12 中的「第 0 號房間」(數字 1)，但實際上，我們應該得到「第 1 號房間」的數字 (2)。

📌 總結：扣 1 是因為在計算「第幾間房間」時，需要將自然數位置 (從 1 開始) 轉換成「從 0 開始數」的房間編號，避免錯位。

總結：-1 的兩個核心邏輯

  1. 計算居民編號時 -1：
    • 用來正確計算「第幾位居民」，確保計算出的居民 (數字) 從 0 開始編號，避免計算跳位。
  2. 計算房間編號時 -1：
    • 用來將「從 1 開始數」的目標位置轉換成「從 0 開始數」的房間編號，避免數字位數錯位。

這樣的 -1 邏輯不僅僅是數學中的「小技巧」，更是將「人類語言」轉換為「程式語言」的重要步驟，保證計算結果的準確性。

程式實現

def find_digit_at_land(land_position: int) -> int:
    # 初始化變數
    digit_length = 1  # 當前人種的位數 (1 位數, 2 位數, 3 位數 ...)
    start_number = 1   # 當前人種數字的起始 (1, 10, 100, 1000 ...)
    
    # 1. 確認土地所在的位數區間
    while True:
        # 計算當前區間的數字總數和佔據的土地數量
        count_of_numbers = 9 * start_number
        total_digits_in_range = count_of_numbers * digit_length
        
        # 如果土地位置在當前區間內，跳出循環
        if land_position <= total_digits_in_range:
            break
        
        # 扣除當前區間的土地數量，進入下一個區間
        land_position -= total_digits_in_range
        digit_length += 1
        start_number *= 10

    # 2. 計算土地對應的數字
    # 計算是區間內第幾個數字 (從 0 開始)
    number_index = (land_position - 1) // digit_length
    
    # 計算是該數字中的第幾個「房間」(從 0 開始)
    room_index = (land_position - 1) % digit_length
    
    # 計算具體的數字
    actual_number = start_number + number_index
    
    # 3. 根據房間編號，返回對應的數字
    return int(str(actual_number)[room_index])

# 🧪 測試
print(find_digit_at_land(13))   # 預期輸出：1
print(find_digit_at_land(200))  # 預期輸出：1
print(find_digit_at_land(1000)) # 測試更大的位置

# 挑戰題：更大的土地編號
print(find_digit_at_land(1000000))       # 預期可在 2 秒內運行
print(find_digit_at_land(1000000000))    # 更大的挑戰
print(find_digit_at_land(1000000000000)) # 超大土地編號

結語

在這篇文章中，我們運用了數學和邏輯推理，成功解決了這個看似複雜的數字序列謎題。

我們不僅通過比喻解釋了題目的本質，還提供了詳細的程式碼，適合初學者學習。

這個解法能夠快速計算出任何土地編號上的數字，並在大數場景下依然能保持高效，值得作為算法學習中的一個經典案例。

Similar Posts

Django 信號處理：如何在保存前自動處理圖片

By徐培鈞

在 Django 應用中，自動化圖片處理是一項常見需求。

通過信號處理，我們可以在模型的保存操作（save 方法）執行之前，自動執行圖片轉換和上傳等操作。

這篇文章將帶你了解如何實現這一功能，並詳解代碼中的核心邏輯，幫助新手掌握信號的運用。

為什麼要分離圖片處理邏輯？Django 最佳實踐指南

By徐培鈞

在 Django 項目中，將代碼合理分層是保持代碼可讀性、可維護性和可測試性的關鍵之一。

對於圖片處理這類業務邏輯，是否應該單獨抽離成工具函數？

本文將帶你理解分離邏輯的原因和優勢，以及在不同情況下該如何做出選擇。

初學者指南：深入了解 Python 中的 Getter 與 Setter

By徐培鈞

在學習 Python 的物件導向程式設計（Object-Oriented Programming, OOP）時，屬性（Attributes） 的存取和控制是一個重要的課題。

為了保護物件的內部狀態，並提供對屬性值的驗證和控制，程式設計師常常使用 Getter 和 Setter 方法。

在其他編程語言中，如 Java 或 C++，Getter 和 Setter 是以明確的方法形式存在的。

而在 Python 中，我們可以透過 @property 裝飾器，優雅地實現屬性的獲取和設置。

本文將為新手詳細介紹 Python 中的 Getter 與 Setter，解釋其作用、如何定義和使用，以及它們的重要性。

Python 中的 split() 方法詳解：新手指南

By徐培鈞

在 Python 編程中，字串處理 是一項非常常見且重要的任務。

其中，split() 方法是將字串拆分為列表的強大工具。

對於剛開始學習 Python 的新手來說，理解並掌握 split() 方法的用法，將大大提升你在字串處理方面的能力。

本文將深入介紹 Python 中的 split() 方法，並提供豐富的示例，幫助你在實際開發中靈活運用。

深入理解 Python 中的 self 與物件導向原理

By徐培鈞

在 Python 的物件導向編程 (OOP) 中，self 是一個關鍵概念，負責將類別的實例與方法綁定在一起。

初學者經常會對 self 的用途感到疑惑，尤其是為什麼在定義類別方法時，需要將 self 作為第一個參數。

本文將透過範例逐步解析 self 的作用與原理，幫助你掌握 Python 的物件導向設計。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *