Look-and-Say数列
Look-and-See (边看边说) 数列具有好玩儿而神秘的特性，本文简要介绍它和它衍生出来的康威常数。
绿春ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为成都创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：18982081108（备注：SSL证书合作）期待与您的合作！
沿革
1977年7月1-13日，国际奥林匹克数学竞赛在前南斯拉夫首都贝尔格莱德举行，赛间，荷兰队非正式地给英国队出了个难题(其实类似脑筋急转弯),大致是这样的：
1, 11, 21, 1211, 111221
上述数列的下一项是什么呢？
英国队未予答复...
故事并没有结束，后来，在剑桥大学执教的著名数学家约翰·霍顿·康威( John·Horton·Conway)从他的学生那儿拿到了这道题，他发现了其中的奥秘，并对它进行了分析和传播。
康威在1986年去普林斯顿大学接任了著名的约翰·冯·诺依曼（John von Neumann）教授的位子，继续教书。
特征
给定种子数 d (种子数在0到9之间，非1), 那么，该数列就可以具体化为：
d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …
如果种子数是1, 具体化后的数列就是本文开头的那个数列了。
如果种子数是22，那么，具体化后的数列的每一项的每个数字，都是2，并且每一项都是22。
当种子数不是22 时， 具体化后的数列的各项是依次增长的。
增长率
种子数不为22时，此数列的后项与前项比有极限，这个极限被称为康威常数，常用 λ 表示。
λ ≈ 1.303577269034296391257099112152551890730702504659404875754861390628550...
我想知道：这里应该有图片，可是为什么51CTO的图片上传的“确认”按钮点了没效果呢？
由于无法上传，请查看我创建的百度词条“Look-and-say 数列” 中的配图.
(上图截取自维基百科： Look-and-say sequence , 我在百度百科为这个词建立了词条，感兴趣的可以去看下)
上图中的四条曲线各自是一个 Look-and-say 数列的图示： 红色的种子数是23，蓝色的是1，紫色的是13，绿色的是312。
随着 x 轴方向的变量不断变大，各个曲线的斜率趋向统一，极限值就是康威常数( Conway Constant )。
用途
看起来是无用之用的一个脑筋急转弯性质的数列，但康威却给出了不同的回答。
康威基于这个数列建立了 Cosmological theorem，解释了宇宙衰变(Cosmological decay)，用这个数列解释了化学元素衰变和相对原子质量之间的关系。
实现
多种编程语言均可实现这个数列，现在我给出该数列在几种编程语言中的实现：
JavaScript 实现1
/*
node las.js
*/
function lookAndSay(str) {
return str.replace(/(.)\1*/g, function(seq, p1){return seq.length.toString() + p1})
}
var num = "1";
for (var i = 10; i > 0; i--) {
console.log(num);
num = lookAndSay(num);
}JavaScript 实现2：
/*
* @Author: suifengtec
* @Date: 2017-08-22 03:45:05
* @Last Modified by: suifengtec
* @Last Modified time: 2017-08-22 03:51:02
*/
/*
node las1.js
*/
function lookAndSay(digits) {
var result = '',
chars = (digits + ' ').split(''),
lastChar = chars[0],
times = 0;
chars.forEach(function(nextChar) {
if (nextChar === lastChar) {
times++;
}
else {
result += (times + '') + lastChar;
lastChar = nextChar;
times = 1;
}
});
return result;
}
(function output(seed, iterations) {
for (var i = 0; i < iterations; i++) {
console.log(seed);
seed = lookAndSay(seed);
}
})("1", 10);Lua语言的实现：
-- @Author: suifengtec
-- @Date: 2017-08-22 03:51:07
-- @Last Modified by: 'suifengtec'
-- @Last Modified time: 2017-08-22 03:56:18
--a lua implement of the look-and-say sequence
-- lua las.lua
function lookAndSay(n)
local t = {1}
return function()
local ret = {}
for i, v in ipairs(t) do
if t[i-1] and v == t[i-1] then
ret[#ret - 1] = ret[#ret - 1] + 1
else
ret[#ret + 1] = 1
ret[#ret + 1] = v
end
end
t = ret
n = n - 1
if n > 0 then return table.concat(ret) end
end
end
for i in lookAndSay(10) do print(i) endPHP 实现：
'; $num = lookAndSay($num); }
Python 实现：
# -*- coding: utf-8 -*- # @Author: suifengtec # @Date: 2017-08-22 04:00:59 # @Last Modified by: 'suifengtec' # @Last Modified time: 2017-08-22 04:02:27 # # Look and Say 数列的 Python 实现 # python las.py # def lookAndSay(number): result = "" repeat = number[0] number = number[1:]+" " times = 1 for actual in number: if actual != repeat: result += str(times)+repeat times = 1 repeat = actual else: times += 1 return result num = "1" for i in range(10): print(num) num = lookAndSay(num)
Rust 中的实现：
/* rustc -o rs.exe las.rs && rs */ fn las(in_seq: &[i8]) -> Vec{ assert!(!in_seq.is_empty()); let mut result = Vec::new(); let mut current_number = in_seq[0]; let mut current_runlength = 1; for i in &in_seq[1..] { if current_number == *i { current_runlength += 1; } else { result.push(current_runlength); result.push(current_number); current_runlength = 1; current_number = *i; } } result.push(current_runlength); result.push(current_number); result } fn main() { let mut seq = vec![1]; for i in 0..10 { println!("{}=>{:?}", i, seq); seq = las(&seq); } }
Go 语言的实现:
/*
* @Author: coolwp.com
* @Date: 2017-08-22 01:55:09
* @Last Modified by: suifengtec
* @Last Modified time: 2017-08-22 02:37:27
**/
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)
fmt.Println(a)
fmt.Println(b)
}PS: 由于这个 js 不支持 Go 语言代码高亮，并且缩进也显示有问题， 所以请在粘贴后执行 go fmt。
结论
有一种声音认为：宇宙是一个程序，这个数列和康威常数用数字支持了这种说法。
本文首发酷威普和51CTO,转载需注明。
文章名称：Look-and-Say数列
转载源于：http://cdiso.cn/article/ggdjjh.html
