找到两首或多首歌曲的交集的算法

假设我们有一堆收音机，每个收音机都在循环播放同一首歌。有可能同步所有收音机里的所有歌曲吗?我们能找个时间从头开始听所有的歌吗?

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

我有以下公式:

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乘以2以上才能得到合适的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的要求，我们不能用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。

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

c和z的最小公倍数是歌曲同步(如果它们完全同步)的连续时间间隔。这意味着，如果我们可以确定一个时间，我们可以通过LCM的一个倍数来找到剩余的时间。要找到这个时间(实际上，LCM)，使用扩展欧几里得算法找到满足方程

的整数T, U

 (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)，然后将bsamzout系数乘以((c - a) - (z - x))/GCD(c, z)。

我用我在注释中提到的逻辑编写了这段代码。基本思想是找到整数n1和n2，使得(n1*c)-(n2*z)=(x-a)

关于我如何得到这个方程的简短解释:

s1 = a+(n1*c)

s2 = x+(n2*z)

我们需要s1=s2

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

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

我们需要找到满足上述方程的n1和n2。解存在当且仅当c和z的GCD除(x-a)。

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

这是我的代码。

#include <stdio.h>
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 == (x-a) % gcd)
       {
           for(n2=1; n2<(unsigned int)-1; n2++)
           {
               unsigned int temp1 = (z*n2)+(x-a);
               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 n2n");
    }
}
unsigned int getGCD(unsigned int n1, unsigned int n2)
{
    while(n1!=n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    printf("GCD = %un",n1);
    return n1;
}

输出:

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

我想出了一个同步2首以上歌曲的解决方案，但这需要很多时间!

如果所有歌曲的当前位置都是0，那么它们已经同步了。
如果所有歌曲的剩余长度为same，则它们将在剩余长度后同步。
如果以上这些测试(对于小情况)失败，我们使用启发式方法:

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

当前位置x
剩余长度y
总长度，z = x + y
播放长度，p

我们为每首歌创建一个这样的对象。用户输入x和y的值，计算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!

这个算法在大多数情况下需要指数级的时间，但是，如果有很多歌曲，它是有用的。而且，它不依赖于参数的素数或可除性。

欢迎对算法的评论和建议!

相关内容

最新更新

热门标签：