查找两个或更多歌曲的交集的算法 [英] Algorithm to find the intersection of two or more songs

问题描述

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

Lets say we have a bunch of radios and each radio plays the same song on a loop over and over again. Is it possible to synchronize all the songs from all the radios? Can we find a time where we hear all the songs from the beginning?

为简单起见，我们将说我们只有两个收音机.

For the sake of simplicity we will say that we only have two radios.

我有以下公式:

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

c and z represent the length of the song in seconds. a and x represent the current position in the song ( in seconds ) S represents the time when C and Z synchronize. ( When both songs start at the same time )

例如:

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.

Now This first example is the simplest one. For the other cases i would have to multiply z and c by more than two in order to get the appropriate S for them.

我还有其他一些输入，并且我试图提出一种算法，该算法将为我返回S，但是我对此没有运气.

I have some other inputs , and i've tried to come up with an algorithm that will return S for me , but i had no luck with that.

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

Here is what i came up with so far :

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是通过以下方式找到的:

In the first example S was found this way :

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的次数.

I came up with the two formulas below Based on the value of S. But i need to figure out a way to find n without actually using S. Or in other words i need to figure out a way to find how many times i should multiply ( a + b) by n and ( x + y) by n to get S.

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

但是这些公式显然无法使用，因为它们需要S.而且我们不能使用它，因为那应该是我要提出的公式的结果.

But These formulas obviously won't work as they require S. And we can't use that because that should be the result of the formula that i am trying to come up with.

以下是一些计算示例:

a2 = 52
b2 = 4
c2 = 56
s2 = 276

x2 = 60
y2 = 12
z2 = 72
s2 = 276

在这种情况下，它永远不会同步:

Here is a situation where it will never be Synchronized :

A1 = 14
B1 = 4
C1 = 18
S1 = Never synchronizes

A2 = 19
B2 = 5
C2 = 24
S2 = Never synchronizes

在某些情况下，歌曲已经同步:

And Here are some situation where the songs are already Synchronized :

案例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

我当时正在考虑使用最小公倍数，但是我不确定在这种情况下如何实现它，或者对于此问题它是否是正确的解决方案.

I was thinking about using the Least Common Multiple but i am not sure how to implement it in this situation or if its the right solution for this problem.

如果有多于2首歌曲，我想提出的算法也应该起作用. 例如，找到3或4首歌曲的S.

The Algorithm i want to come up with should also work if there are more than 2 songs. For example finding S for 3 or 4 songs.

此算法的主要问题是确定两首歌曲是否同步，计算本身并不那么困难. 你能帮我吗 ?预先感谢

The main problem with this Algorithm is deciding wether the two songs Synchronize or not , The calculation itself is not that hard. Can you help me please ? Thanks in advance

推荐答案

c和z的最小公倍数是歌曲同步的连续时间之间的间隔(如果它们完全同步).这意味着，如果我们可以确定一次，则可以通过添加(或减去)LCM的倍数来找到其余时间.要找到这个时间(实际上是LCM)，请使用扩展的欧几里得算法来查找满足方程式的整数T, U

The least common multiple of c and z is the interval between consecutive times that the songs synchronize (if they synchronize at all). This means that, if we can determine one time, we can find the rest by adding (or subtracting) a multiple of the LCM. To find this time (and indeed, the LCM), use the extended Euclidean algorithm to find integers T, U that satisfy the equation

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

，在替换V = -U时等同于

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

详细地，找到c和z的GCD，检查是否将其除以(c - a) - (z - x)，然后将Bézout系数乘以((c - a) - (z - x))/GCD(c, z).

In detail, find the GCD of c and z, check that it divides (c - a) - (z - x), then multiply the Bézout coefficients through by ((c - a) - (z - x))/GCD(c, z).

这篇关于查找两个或更多歌曲的交集的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！