-
Look-and-say 數列
鎖定
Look-and-say 數列是數學中的一種數列，它的名字就是它的推導方式：給定第一項之後，後一項是前一項的發音。
- 中文名
- 邊看邊説數列
- 外文名
- Look-and-say sequence
- 類 型
- 數學中的一種數列
Look-and-say 數列基本介紹
1983年11月，在英國劍橋大學教書的著名數學家約翰·霍頓·康威(John Horton Conway) 首先發現了Look-and-say的奧秘。
Look-and-say 數列規則
如果我們把 1 作為Look-and-say 數列的第一項，那麼，它的前幾項是這樣的：
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ...
在確定了Look-and-say 數列的第一項之後，就可以根據前一項確定後一項的值了,在上面的示例中，我們把 1 作為此種數列的第一項，那麼，就可以這樣來推導它的其餘項了：
第1個是 1 時,記作 1;
第2個是讀前一個數 "2 個1", 記作 21;
第3個是讀前一個數 "1個2, 1個1", 記作 1211;
第4個是讀前一個數 "1個1,1個2,2個1", 記作 111221;
...
依此類推。
英國數學家約翰·康威(John Conway) 最早介紹和分析了Look-and-say 數列。
Look-and-say 數列和壓縮/解壓縮種的遊標編碼(Run-length encoding)有相似之處。
如果我們從0到9 中的任何數字d開始，那麼d將永遠是序列的最後一個數字。d不同於1，數列的開始幾項如下:
d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …
巴黎綜合理工學院的Ilan Vardi
[1]
率先研究了 d =3 的狀況， 約翰·康威(John Conway) 研究了 d=2 的情況，得出了康威常數。
Look-and-say 數列基本性質
增長性
當 d =22 時，很尷尬的事情發生了，Look-and-say 數列的前幾項是：
22, 22, 22, 22,22, …
d 不等於 22 時，Look-and-say 數列可無限增長,也就是説可有無限個項。
數字出現的侷限性
序列的各個項中，僅包含種子數字(上面提到的 d) 的各個數位上的阿拉伯數字 和 1，2 ，3 這三個阿拉伯數字。
宇宙衰變
化學元素與Look-and-say數列
增長率
在Look-and-say 數列 中，如果
表示數列的第n個成員的位數，那麼存在比值極限
λ ≈ 1.303577269034...
圖1Look-and-say sequence-Conway
康威常數λ 作為斜率換算為角度後，大約為 52.5075度。
康威常數還是一個 71次方多項式的唯一解。
圖1x軸為種子數(22除外)，y軸為10的n次方，
y的變化曲線的顏色代表了不同的種子數：23(紅色)、1(藍色)、13(紫色)、312(綠色)。這些曲線隨着項數的增加趨向於直線，其斜率與康威常數一致。
Look-and-say 數列計算機實現
幾乎每種編程語言都可實現這個數列，這裏給出一個 Go 語言的實現。
/*
* @Author: suifengtec
* @Date: 2017-08-22 01:55:09
* @Last Modified by: suifengtec
* @Last Modified time: 2017-08-22 02:10:25
**/
package main
import (
"fmt"
"math"
"strconv"
"strings"
)
// 獲取以 1 為種子數的Look-and-say 數列任意位置的數字
func getNumberOfLookAndSaySequeceSeed1(position int) int {
if position == 1 {
return 1
}
if position == 2 {
return 11
}
str := "11"
for i := 3; i <= position; i++ {
str += "$"
length := len(str)
tmp := ""
cnt := 1
for j := 1; j < length; j++ {
strSlice := strings.Split(str, "")
if strSlice[j] != strSlice[j-1] {
cntTmp := strconv.Itoa(cnt)
tmp += cntTmp
tmp += strSlice[j-1]
cnt = 1
} else {
cnt++
}
}
str = tmp
}
v, err := strconv.Atoi(str)
//v, err := strconv.ParseInt(str, 10, 64)
if err != nil {
return -1
}
if v > math.MaxInt32 {
return -1
}
return v
}
// 給定任意種子數 seed, 獲取 LookAndSay 數列的 第 position 項
func getNumberOfLookAndSaySequece(seed int, position int) int {
if seed == 22 {
return 22
}
if position == 1 {
return seed
}
seedStr := strconv.Itoa(seed)
str := "2" + seedStr
if position == 2 {
v, err := strconv.Atoi(str)
if err != nil {
return -1
}
if v > math.MaxInt32 {
return -1
}
return v
}
for i := 3; i < position; i++ {
str += "$"
length := len(str)
tmp := ""
cnt := 1
for j := 1; j < length; j++ {
strSlice := strings.Split(str, "")
if strSlice[j] != strSlice[j-1] {
cntTmp := strconv.Itoa(cnt)
tmp += cntTmp
tmp += strSlice[j-1]
cnt = 1
} else {
cnt++
}
}
str = tmp
}
r, err := strconv.Atoi(str)
if err != nil {
return -1
}
if r > math.MaxInt32 {
return -1
}
return r
}
func main() {
position := 5
a := getNumberOfLookAndSaySequeceSeed1(position)
seed := 1
pos := 5
b := getNumberOfLookAndSaySequece(seed, pos)
// 111221
fmt.Println(a)
fmt.Println(b)
}
- 參考資料
-
- 1. Ilan Vardi 論文索引 ．巴黎綜合理工學院．2001-06-08[引用日期2017-08-21]
- 2. Cosmological Theorem/宇宙學原理 ．密歇根州立大學．1997-08-05[引用日期2017-08-21]
