整数列{x(n)}满足x(0)=2,|x(k)|=|x(k-1)+1| (k≥1). 求|x(1)+...+x(2019)|的最小值

elim

题: 整数列{x(n)}满足x(0)=2,|x(k)|=|x(k-1)+1| (k≥1). 求|x(1)+x(2)+...+x(2019)|的最小值

elim

据此编写python 程序:

1. def mmp(l):
   
2.     s,t=l[0],l[1]
   
3.     v = t+1
   
4.     if v == 0:
   
5.         return [[s,0]]
   
6.     if v < 0: v = -v
   
7.     return [[s-v,-v],[s+v,v]]
   
8. 
   
9. 
   
10. def iv(l):
    
11.     u,v=l[0],l[1]
    
12.     if v == 0:
    
13.         return [l]
    
14.     vv=v
    
15.     if vv < 0: vv=-v
    
16.     return [[u-v,-vv-1],[u-v,vv-1]]
    
17. 
    
18. 
    
19. def fd(n=5):
    
20.     a=[[0,2]]
    
21.     k=0
    
22.     while k < n:
    
23.         N=len(a)
    
24.         for i in range(N):
    
25.             j = N-1-i
    
26.             u=mmp(a[j])
    
27.             NN=len(u)
    
28.             for ii in range(NN):
    
29.                 jj=NN-1-ii
    
30.                 ll=u[jj]
    
31.                 if (ll in a[:j]) or (ll in a[j+1:]):
    
32.                     u.remove(ll)
    
33.             a = a[:j]+u+a[j+1:]
    
34.         k += 1
    
35.     return a

复制代码

对不同的 n 运行代码发现了一些规律. 下帖继续......

elim

沿用上贴的记号, 将 f^n({0,2)}) 的元素按字典排列法列出在第 n 行, 得以下列表.
由此可知 |x(1)+...+x(7)| 的最小值是 0 等等. 现在的问题是如何找出第 n(>2) 行元素的通项公式?

1: len= 2 (-3,-3),(3,3)
2: len= 4 (-5,-2),(-1,-4),(-1,2),(7,4)
3: len= 6 (-6,-1),(-4,-3),(-4,1),(2,-5),(2,3),(12,5)
4: len= 7 (-6,-2),(-6,0),(-2,-4),(-2,2),(6,-6),(6,4),(18,6)
5: len= 8 (-7,-1),(-5,-3),(-5,1),(1,-5),(1,3),(11,-7),(11,5),(25,7)
6: len= 9 (-7,-2),(-7,0),(-3,-4),(-3,2),(5,-6),(5,4),(17,-8),(17,6),(33,8)
7: len=10 (-8,-1),(-6,-3),(-6,1),(0,-5),(0,3),(10,-7),(10,5),(24,-9),(24,7),(42,9)
8: len=11 (-8,-2),(-8,0),(-4,-4),(-4,2) ... (32,-10),(32,8),(52,10)
9: len=12 (-9,-1),(-7,-3),(-7,1),(-1,-5) ... (41,-11),(41,9),(63,11)
10: len=13 (-9,-2),(-9,0),(-5,-4),(-5,2) ... (51,-12),(51,10),(75,12)
11: len=14 (-10,-1),(-8,-3),(-8,1),(-2,-5) ... (62,-13),(62,11),(88,13)
12: len=15 (-10,-2),(-10,0),(-6,-4),(-6,2) ... (74,-14),(74,12),(102,14)
13: len=16 (-11,-1),(-9,-3),(-9,1),(-3,-5) ... (87,-15),(87,13),(117,15)
14: len=17 (-11,-2),(-11,0),(-7,-4),(-7,2) ... (101,-16),(101,14),(133,16)
15: len=18 (-12,-1),(-10,-3),(-10,1),(-4,-5) ... (116,-17),(116,15),(150,17)
16: len=19 (-12,-2),(-12,0),(-8,-4),(-8,2) ... (132,-18),(132,16),(168,18)
17: len=20 (-13,-1),(-11,-3),(-11,1),(-5,-5) ... (149,-19),(149,17),(187,19)
18: len=21 (-13,-2),(-13,0),(-9,-4),(-9,2) ... (167,-20),(167,18),(207,20)
19: len=22 (-14,-1),(-12,-3),(-12,1),(-6,-5) ... (186,-21),(186,19),(228,21)
20: len=23 (-14,-2),(-14,0),(-10,-4),(-10,2) ... (206,-22),(206,20),(250,22)
21: len=24 (-15,-1),(-13,-3),(-13,1),(-7,-5) ... (227,-23),(227,21),(273,23)
22: len=25 (-15,-2),(-15,0),(-11,-4),(-11,2) ... (249,-24),(249,22),(297,24)
23: len=26 (-16,-1),(-14,-3),(-14,1),(-8,-5) ... (272,-25),(272,23),(322,25)
24: len=27 (-16,-2),(-16,0),(-12,-4),(-12,2) ... (296,-26),(296,24),(348,26)
25: len=28 (-17,-1),(-15,-3),(-15,1),(-9,-5) ... (321,-27),(321,25),(375,27)
26: len=29 (-17,-2),(-17,0),(-13,-4),(-13,2) ... (347,-28),(347,26),(403,28)
27: len=30 (-18,-1),(-16,-3),(-16,1),(-10,-5) ... (374,-29),(374,27),(432,29)
28: len=31 (-18,-2),(-18,0),(-14,-4),(-14,2) ... (402,-30),(402,28),(462,30)
29: len=32 (-19,-1),(-17,-3),(-17,1),(-11,-5) ... (431,-31),(431,29),(493,31)
30: len=33 (-19,-2),(-19,0),(-15,-4),(-15,2) ... (461,-32),(461,30),(525,32)
31: len=34 (-20,-1),(-18,-3),(-18,1),(-12,-5) ... (492,-33),(492,31),(558,33)
32: len=35 (-20,-2),(-20,0),(-16,-4),(-16,2) ... (524,-34),(524,32),(592,34)
33: len=36 (-21,-1),(-19,-3),(-19,1),(-13,-5) ... (557,-35),(557,33),(627,35)
34: len=37 (-21,-2),(-21,0),(-17,-4),(-17,2) ... (591,-36),(591,34),(663,36)
35: len=38 (-22,-1),(-20,-3),(-20,1),(-14,-5) ... (626,-37),(626,35),(700,37)
36: len=39 (-22,-2),(-22,0),(-18,-4),(-18,2) ... (662,-38),(662,36),(738,38)
37: len=40 (-23,-1),(-21,-3),(-21,1),(-15,-5) ... (699,-39),(699,37),(777,39)
38: len=41 (-23,-2),(-23,0),(-19,-4),(-19,2) ... (737,-40),(737,38),(817,40)
39: len=42 (-24,-1),(-22,-3),(-22,1),(-16,-5) ... (776,-41),(776,39),(858,41)
40: len=43 (-24,-2),(-24,0),(-20,-4),(-20,2) ... (816,-42),(816,40),(900,42)
41: len=44 (-25,-1),(-23,-3),(-23,1),(-17,-5) ... (857,-43),(857,41),(943,43)
42: len=45 (-25,-2),(-25,0),(-21,-4),(-21,2) ... (899,-44),(899,42),(987,44)
43: len=46 (-26,-1),(-24,-3),(-24,1),(-18,-5) ... (942,-45),(942,43),(1032,45)
44: len=47 (-26,-2),(-26,0),(-22,-4),(-22,2) ... (986,-46),(986,44),(1078,46)
45: len=48 (-27,-1),(-25,-3),(-25,1),(-19,-5) ... (1031,-47),(1031,45),(1125,47)
46: len=49 (-27,-2),(-27,0),(-23,-4),(-23,2) ... (1077,-48),(1077,46),(1173,48)
47: len=50 (-28,-1),(-26,-3),(-26,1),(-20,-5) ... (1124,-49),(1124,47),(1222,49)
48: len=51 (-28,-2),(-28,0),(-24,-4),(-24,2) ... (1172,-50),(1172,48),(1272,50)
49: len=52 (-29,-1),(-27,-3),(-27,1),(-21,-5) ... (1221,-51),(1221,49),(1323,51)
50: len=53 (-29,-2),(-29,0),(-25,-4),(-25,2) ... (1271,-52),(1271,50),(1375,52)

王守恩

elim 发表于 2019-10-26 21:34
沿用上贴的记号, 将 f^n({0,2)}) 的元素按字典排列法列出在第 n 行, 得以下列表.
由此可知 |x(1)+...+x(7) ...

题目没看懂，我先试一试下面的题目。
题: 整数列{x(n)}满足x(1)=2,|x(k)|=|x(k-1)+1| (k≥1). 求|x(1)+x(2)+...+x(2019)|的最小值
设S(n)=|x(1)+x(2)+...+x(n)|的最小值，n=1,2,3,4,......
S(n)=2, 1, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5,
0, 6, 1, 5, 2, 4, 3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2,........

王守恩

谢谢elim！看懂了！确实是一道不错的题目！还有比这更好的答案吗？！
题: 整数列{x(n)}满足x(0)=2,|x(k)|=|x(k-1)+1| (k≥1). 求|x(1)+x(2)+...+x(2019)|的最小值
设S(n)=|x(1)+x(2)+...+x(n)|的最小值，n=1,2,3,4,......
S(n)=3, 1, 2, 2, 1, 3, 0, 4, 1, 3, 2, 2, 3, 1, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 1, 5, 2, 4,
        3, 3, 4, 2, 5, 1, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8,.........

elim

王守恩

elim 发表于 2019-10-30 22:45

可以归到 “爬楼梯” 问题。
a(1)=3,a(2)=1,a(3)=2，a(n+1)=a(n) - a(n-1) - a(n-2)

王守恩

elim 发表于 2019-10-30 22:45

可以有一个通项公式吗？

elim

最小值的通项:

elim

王守恩 发表于 2019-10-30 08:29
可以归到 “爬楼梯” 问题。
a(1)=3,a(2)=1,a(3)=2，a(n+1)=a(n) - a(n-1) - a(n-2)

a(n) 是什么?, 递推公式验证到哪里了?