本帖最后由 王守恩 于 2019-11-13 11:13 编辑
谢谢 elim!谢谢 wintex! 确实是一道不错的题目!还有比这更好的答案吗?!
题: 数列满足 a(0)=2,|a(k)|=|a(k-1)+1|,k≥1,求|a(1)+a(2)+…+a(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,.........
特别地,S(2019)=44
我是这样想的:
1,记 a(1)=0 的解为基本解
基本解=0, 1, 1, 0, 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 项都只会出现 1 次,不会重复(前面不会有,后面也不会有),
也就是说:只要知道 3 项,后面的答案就改不了了。
3,不管a(0)是什么,只要算出a(1),a(2),a(3),后面的答案是唯一的;
4,不管a(0)是什么,只要算出a(1),a(2),a(3),在基本解里可以找到唯一的位置;
5,不管a(0)是什么,只要算出a(1),a(2),a(3),后面的算法可以归到爬楼梯问题上去。 |