想象一辆汽车在一条从 0 开始的数字线上。汽车可以在有约束的情况下向前和向后移动,我们必须发出指令让它向前或向后移动:-
汽车将以 1 步开始移动,每次移动后,汽车加速度将增加 1。 对于例如。
汽车在0点起步
假设我们让汽车向前移动
2. 汽车将向前移动 1 步所以现在汽车在 +1
假设我们让汽车向前移动
3. 汽车将向前移动 2 步,所以现在汽车在 +3 位置
假设我们让汽车向前移动
4. 汽车将向前移动 3 步,所以现在汽车在 +6 处
假设我们让汽车向前移动
5. 汽车将向前移动 4 步,所以现在汽车在 +10
假设我们让汽车向后移动
6. 汽车将向后移动 5 步,所以现在汽车处于 +5
假设我们让汽车向后移动
7. 汽车将向后移动 6 步,所以现在汽车位于 -1
假设我们让汽车向前移动
8. 汽车将向前移动 7 步,所以现在汽车在 +6 处
等等....
所以现在的问题是汽车是否可以以这种方式行驶:-
1. 哪些数字是不可能到达的?
2. 有什么算法可以计算到达数字 X 的最小迭代次数?
我已经尝试了很多自己寻找任何模式和任何算法,也在互联网上找到解决这个问题的任何解决方案,但没有找到比蛮力解决方案更好的方法。请帮忙!!!
最佳答案
- 因为
-n+(n+1)=1
可以得到任何数字,所以要得到任何N
可以使用2N
连续的数字。 - 从
1
开始添加,直到达到N
或超过它。在超调的情况下,有两种可能:- Overshoot 是偶数,那么就把加号改成负号,等于Overshoot 的一半。
- Overshoot 是奇数,通过添加下一个数字并在需要时减去另一个下一个数字来使其变为偶数。如果超调现在不为零,转2.1。
例子:
45:
1+2+3+4+5+6+7+8+9+10=55,所以超调是偶数,按(2.1)。
1+2+3+4-5+6+7+8+9+10=45。46:
1+2+3+4+5+6+7+8+9+10=55,所以超调是奇数。
1+2+3+4+5+6+7+8+9+10+11=66,所以超调是偶数,所以按照(2.1)。
1+2+3+4+5+6+7+8+9-10+11=46。12:
1+2+3+4+5=15,所以超调是奇数。
1+2+3+4+5+6=21,超调还是奇数,减去。
1+2+3+4+5+6-7=14,超调是偶数,所以按(2.1)。
-1+2+3+4+5+6-7=12。5:
1+2+3=6,所以超调是奇数。
1+2+3+4=10,还是奇数,再减去下一个数。
1+2+3+4-5=5,所以过冲偶数和零,不用去(2.1)。
关于algorithm - 在一些约束条件下在数轴上移动汽车。找出汽车无法到达的号码以及到达特定号码的最佳方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57761405/