问题
有一个有序数列,序列中所有元素都是2或3或5的倍数,第一个元素是1,那么第n个是什么?(n 从1开始计)
暴力计算
最简单最直接的方法就是暴力计算,计算出第n个值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//获取第 position 位的序列值,position 从1开始计数
func getNum(position int) int {
if position < 1 {
return -1
}
if position == 1 {
return 1
}
cnt := 1
for i := 2; ; i++ {
if i%2 == 0 || i%3 == 0 || i%5 == 0 {
cnt++
}
if cnt == position {
return i
}
}
}
func main() {
fmt.Printf("第-1个数为:%d\n", getNum(-1))
fmt.Printf("第0个数为:%d\n", getNum(0))
fmt.Printf("第1个数为:%d\n", getNum(1))
fmt.Printf("第5个数为:%d\n", getNum(5))
fmt.Printf("第25个数为:%d\n", getNum(25))
fmt.Printf("第1000个数为:%d\n", getNum(1000))
fmt.Printf("第1500个数为:%d\n", getNum(1500))
}
输出:
1
2
3
4
5
6
7
第-1个数为:-1
第0个数为:-1
第1个数为:1
第5个数为:5
第25个数为:33
第1000个数为:1362
第1500个数为:2044
找规律
2、3、5的最小公倍数为30,那么数列是否是周期性的?我们列两个周期看看
1~30:
1
2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30
共 22 个。
31~60:
1
32,33,34,35,36,38,39,40,42,44,45,46,48,50,51,52,54,55,56,57,58,60
也共 22 个。
我们可以发现 31~60 与 1~30 是相似的,相同位置的元素的差是相同的,即 31~60 之间的序列可以表示为
1
30+2,30+3,30+4,30+5,30+6...30+28,30+30
那么找到第 n 个数可以这样实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//获取第 position 位的序列值,position 从1开始计数
func getNum(position int) (result int) {
if position < 1 {
// 不存在
result = -1
return
}
if position == 1 {
// 首位
result = 1
return
}
tmp := []int{2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30}
// position 从1开始
// 除去首元素1的周期数
cycles := (position - 1) / len(tmp)
// 最近一个周期,用的规律序列的第几位
var compliment int
if cycles > 0 {
compliment = (position - 1) % len(tmp)
} else {
compliment = position - 1
}
if compliment > 0 {
result = cycles*30 + tmp[compliment-1]
} else {
result = cycles * 30
}
return result
}
func main() {
fmt.Printf("第-1个数为:%d\n", getNum(-1))
fmt.Printf("第0个数为:%d\n", getNum(0))
fmt.Printf("第1个数为:%d\n", getNum(1))
fmt.Printf("第5个数为:%d\n", getNum(5))
fmt.Printf("第25个数为:%d\n", getNum(25))
fmt.Printf("第1000个数为:%d\n", getNum(1000))
fmt.Printf("第1500个数为:%d\n", getNum(1500))
}
输出:
1
2
3
4
5
6
7
第-1个数为:-1
第0个数为:-1
第1个数为:1
第5个数为:5
第25个数为:33
第1000个数为:1362
第1500个数为:2044