用于查找两首或更多首歌曲的交集的算法

让我们说我们有一堆收音机,每个收音机一遍又一遍地播放同一首歌。 是否可以同步所有收音机中的所有歌曲? 我们能找到一个从一开始就听到所有歌曲的时间吗?

为简单起见,我们会说我们只有两个无线电。

我有以下公式:

c和z表示以秒为单位的歌曲长度。 a和x表示歌曲中的当前位置(以秒为单位)S表示C和Z同步的时间。 (当两首歌同时开始时)

例如 :

Song 1 a = 17 : the time before the song ends. b = 8 : the rest of the song. c = a + b which is the full song in seconds. And Song 2 x = 8 : the time before the song ends. y = 9 : the rest of the song. z = 8 + 9 which is the full song in seconds. Song 1 : a + ( a + b) => S Song 2 : x +(( x + y ) × n) => S Song 1 : 17 + ( 17 + 8) => 42 Song 2 : 8 + ((8 + 9)) = 25 So in order to synchronize song 2 with song 1 we have to multiply (x + y) by two and add x to it. Song 2 : 8 + ((8 + 9) x 2) => 42 So S = 42 and so the two songs will synchronize after 42 seconds. 

现在,第一个例子是最简单的例子。 对于其他情况,我必须将z和c乘以两个以上,以便为它们获得适当的S.

我有一些其他的输入,我试图提出一个算法,将为我返回S,但我没有运气。

这是我到目前为止提出的:

 c = a + b a = 16 b = 4 c = 20 s = 216 

 z = x + y x = 12 y = 5 z = 17 s = 216 S is the LCM of c and z 

在第一个例子中,S就是这样找到的:

 s = x +(z × n) n = ( s − x ) ÷ b 12 + ( 17 × 12) = 216 

 s = a + (c × n) n = ( s − a ) ÷ b 16 + ( 20 × 10 ) = 216 

我想出了下面的两个公式基于S的值。但我需要找出一种方法来找到没有实际使用S的n。换句话说,我需要找出一种方法来找到我应该乘以多少次(a + b)乘n和(x + y)乘n得到S.

 n = ( s − a ) ÷ b S = x + ( y × n) 

但是这些公式显然不会起作用,因为它们需要S.而我们不能使用它,因为这应该是我想要提出的公式的结果。

以下是一些计算的其他示例:

 a2 = 52 b2 = 4 c2 = 56 s2 = 276 x2 = 60 y2 = 12 z2 = 72 s2 = 276 

这是一种永远不会同步的情况:

 A1 = 14 B1 = 4 C1 = 18 S1 = Never synchronizes A2 = 19 B2 = 5 C2 = 24 S2 = Never synchronizes 

以下是歌曲已经同步的情况:

情况1

 A2 = 17 B2 = 0 C2 = 17 S4 = 0 A3 = 25 B3 = 0 C4 = 25 S4 = 0 

案例2

 A4 = 0 B4 = 13 C4 = 13 S4 = 0 A5 = 0 B5 = 21 C5 = 21 S5 = 0 

我在考虑使用最小公倍数,但我不确定如何在这种情况下实现它,或者它是否是解决此问题的正确方法。

如果有超过2首歌曲,我想提出的算法也应该有用。 例如,为3或4首歌曲找到S.

这个算法的主要问题是决定两首歌是否同步,计算本身并不那么难。 你能帮我吗 ? 提前致谢

cz最小公倍数是歌曲同步的连续时间之间的间隔(如果它们完全同步)。 这意味着,如果我们可以确定一次,我们可以通过添加(或减去)LCM的倍数来找到其余的时间。 为了找到这个时间(实际上是LCM),使用扩展的欧几里德算法来找到满足等式的整数T, U

  (c - a) + T*c = (z - x) + U*z 

这取代了V = -U

  T*c + V*z = (c - a) - (z - x). 

详细说,找到cz的GCD,检查它是否除(c - a) - (z - x) ,然后将Bézout系数乘以((c - a) - (z - x))/GCD(c, z)

我用我在评论中提到的逻辑编写了这段代码。 基本思想是找到整数n1和n2,使得(n1 * c) – (n2 * z)=(xa)

关于我如何达到这个等式的简要说明:

s1 = a +(n1 * c)

s2 = x +(n2 * z)

我们需要s1 = s2

=> a +(n1 * c)= x +(n2 * z)

=>(n1 * c) – (n2 * z)=(xa)

我们需要找到满足上述等式的n1和n2。 当且仅当c和z的GCD除以(xa)时,解决方案才存在

请注意:此逻辑适用于两个站。

这是我的代码。

 #include  void findVal(unsigned int a, unsigned int c, unsigned int x, unsigned int z) ; unsigned int getGCD(unsigned int n1, unsigned int n2); int main() { findVal(2, 37, 3, 43); return 0; } void findVal(unsigned int a, unsigned int c, unsigned int x, unsigned int z) { unsigned int n1 = 0; unsigned int n2 = 0; unsigned char foundVal = 1; unsigned int s1 = a; unsigned int s2 = x; //No need to find n1 and n2 if songs are already at the starting point. if((a == c) && (x == z)) { s1 = 0; s2 = 0; } //No need to find n1 and n2 if remaining times are same. else if(a != x) { //Remaining times are not same. foundVal = 0; //Find GCD of c and z. unsigned int gcd = getGCD(c, z); //There is a solution only if the difference of x and a is divisible by the gcd. if(0 == (xa) % gcd) { for(n2=1; n2<(unsigned int)-1; n2++) { unsigned int temp1 = (z*n2)+(xa); if(0 == temp1%c) { n1 = temp1/c; s1 = a + n1*c; s2 = x + n2*z; foundVal = 1; break; } } } } if(1 == foundVal) { printf("Found n1[%u] n2[%u] s1[%u] s2[%u]\n", n1, n2, s1, s2); } else { printf("Could not find n1 and n2\n"); } } unsigned int getGCD(unsigned int n1, unsigned int n2) { while(n1!=n2) { if(n1 > n2) n1 -= n2; else n2 -= n1; } printf("GCD = %u\n",n1); return n1; } 

输出:

 Found n1[21] n2[18] s1[793] s2[793] 

我提出了一种同步超过2首歌曲的解决方法,但这需要花费很多时间!

  1. 如果所有歌曲的当前位置都是0 ,则它们已经同步。
  2. 如果所有歌曲的剩余长度same ,则它们将在剩余长度之后同步。
  3. 如果上述测试(对于普通情况)失败,我们使用启发式方法:

我们可以使用具有以下属性的每首歌曲的对象:

  • 当前位置, x
  • 剩余长度, y
  • 总长度, z = x + y
  • 演奏长度, p

我们为每首歌创建一个这样的对象。 从用户输入xy值,计算z并将p初始化为x

 create a Min-Heap for the objects based on their `p` values. for ( i = 1; i <= some_reasonable_value_like_10000; i++ ) { if (the `p` values of all objects are same) then break from the loop else increase the `p` value of the root of Min-Heap by `z` value of the corresponding object (and heapify, if required) } if ( i <= some_reasonable_value_like_10000) return `p` value of any object! 

在大多数情况下,该算法将采用指数时间,但是,如果有很多歌曲,则该算法很有用。 而且,它不依赖于参数的素数或可分性。

对该算法的评论和建议是最受欢迎的!