斐波那契字符串数组修改
也许我上次的作业理解错了。实际问题描述应该如下所示：
我有一个数组：AB AB BAB ABBAB BABABBAB 数组
每一项的数量都是基于斐波那契数的。
将第 n 个字符串和第 n+1 个字符串放在一起，然后生成第 n+2 个字符串：
BABABBAB = BAB + ABBAB
然后是第 x 个字符串（例如 10^16 -th) 从最后一个字母算起的第n项的字母是A还是B？例如。第 6 个字母是 B，不仅在第 6 个术语 BABABBAB 中，而且在后面的术语中 ABBABBABABBAB
第 7 个字母在第 6 个术语 BABABBAB 中是 A code> 以及后面的术语 - ABBABBABABBAB
最鼓舞人心的消息是有人有 θ(1) 解决方案。
如果 [x / g] * g >= x - 1 则为 B 否则就是A。 g 是中庸之道。
但他或她没有解释为什么它有效。
Maybe I misunderstand my assignment last time.The actually problem description should be like the following:
I have an array: A B AB BAB ABBAB BABABBAB
The number of each term of the array is base on the Fibonacci number.
Put the n-th string and the n+1-th string together, then producing the n+2-th string:
BABABBAB = BAB + ABBAB
Then is the x-th (eg.10^16-th) letter of the n-th term which count from the last letter is A or B? Eg. the 6th letter was B, not only in the 6th term BABABBAB but also in the later terms ABBABBABABBAB
The 7th letter is A in the the 6th term BABABBAB and also in the later terms - ABBABBABABBAB
The most inspiring news is that someone has a Θ(1) solution.
if [x / g] * g >= x - 1 then it's B
else it's A.
g is the golden mean.
but he or she didn't explain why it works.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
查看有关斐波那契字的维基百科文章。其中给出了第 n 位数字的公式以及参考文献。
Have a look at the Wikipedia article on Fibonacci Word. A formula for the n'th digit is given there along with references.