如何找到一个有效的算法来识别每个x最小的n,k,f ^(n)f(x)= ^(n + k)(x)

时间:2021-01-09 07:18:38

The titular question is associated to the following problem: https://i.gyazo.com/07b7dde7efe1df0b7ae9550317851fda.png

标题问题与以下问题有关:https://i.gyazo.com/07b7efe1df0b7ae9550317851fda.png。

And a more detailed explanation of the titular problem can be provided but I can't post more than two links so if someone replies and asks for it I can provide it to you!

并且可以提供一个更详细的标题问题的解释,但我不能张贴超过两个链接,所以如果有人回复和要求,我可以提供给你!

To start, I understand that the whole question is based upon the idea of the tortoise and hare algorithm for cycle detection (I would link the Wikipedia page, but I don't have enough reputation). I also understand that the existence of a loop is proven by the tortoise and hare 'meeting up' with each other after leaving the first node. I also know that where they meet up for the second time in the second phase of the algorithm is indicative of exactly where the loop begins.

首先,我理解整个问题是基于乌龟和兔子算法的循环检测思想(我会链接*的页面,但我没有足够的声誉)。我也明白,在离开第一个节点后,乌龟和兔子“相遇”证明了循环的存在。我还知道,在算法的第二阶段,它们第二次相遇的地方表明了循环的确切起点。

Unfortunately, I simply can't wrap my head around relating this/these facts to the question given and how to create an algorithm for it.

不幸的是,我不能把这些事实和所给的问题以及如何创建算法联系起来。

Any help is greatly appreciated!

非常感谢您的帮助!

1 个解决方案

#1


0  

No idea how you're supposed to make an algorithm for it, but it seems like simple modulo math. T(x) = x mod 5 and H(x) = 2x mod 5. You're asked to solve for when T(x) = H(x). Since both expression are modulo 5, you know they're equal when 2x - x = 5k where k is some integer.

不知道如何为它建立一个算法,但它看起来很简单。T(x) = x mod 5和H(x) = 2x mod 5。要求解T(x) = H(x)因为这两个表达式都是模5,所以当2x - x = 5k时它们是相等的,k是一个整数。

#1


0  

No idea how you're supposed to make an algorithm for it, but it seems like simple modulo math. T(x) = x mod 5 and H(x) = 2x mod 5. You're asked to solve for when T(x) = H(x). Since both expression are modulo 5, you know they're equal when 2x - x = 5k where k is some integer.

不知道如何为它建立一个算法,但它看起来很简单。T(x) = x mod 5和H(x) = 2x mod 5。要求解T(x) = H(x)因为这两个表达式都是模5,所以当2x - x = 5k时它们是相等的,k是一个整数。