c - 消息同步算法

Question

我们有两条无限重复的消息，由字符 a-z 组成。每个字符需要不同的时间单位来传输； a=1, b=2, c=4, d=8,e=16 ..., 字符 |告诉我们消息中的当前位置。我们的工作是说出同步这两条消息需要多少时间单位。同步意味着两条消息同时开始。

示例:

我们有消息 1:ea|babab

和消息 2:d|abaca

因此我们知道消息 1 是 bababea，消息 2 是:abacad。

消息将在 42 个时间单位内同步:

ea|巴巴贝亚| = 42

d|算盘|算盘| = 42

示例 2: 消息 1:|acabbaaa 消息 2:|dcbabaaaa。

解决方案:0，因为他们已经同步了。

我们想提出一种算法来计算第一次同步发生之前的时间。

我正在用 C 语言编写这个。我基本上已经完成了所有的事情，除了算法本身。

我认为这可以使用扩展的欧几里得算法来完成。

Answer 1

我已经回答了不同的question我认为这个问题的解决方案是完全一样的。您需要求解方程 m1Offset+(m1Len * intN1) = m2Offset+(m2Len * intN2)

(m1Len * intN1) - (m2Len * intN2) = (m2Offset - m1Offset)

我们需要找到满足上述等式的 intN1 和 intN2。 当且仅当 m1Len 和 m2Len 的 GCD 相除 (m2Offset - m1Offset) 时才会有解。

在下面的代码中，

• m1Len 和 m2Len:分别是消息 m1 和 m2 的长度。例如:对于“ea|babab”，长度是“bababea”的长度=25，在消息“d|abaca”中，“abacad”的长度=17

• m1Offset 和 m2Offset:初始偏移量。例如:消息“ea|babab”中，“ea”是偏移量，等于17。类似地，在“d|abaca”中，“d”是偏移量，等于8。

• m1Time 和 m2Time 应该相等，这是第一次同步时间。

这是我的代码。

#include <stdio.h>

void findVal(unsigned int m1Offset, unsigned int m1Len, unsigned int m2Offset, unsigned int m2Len) ;
unsigned int getGCD(unsigned int n1, unsigned int n2);

int main()
{
    findVal(17, 25, 8, 17);
    return 0;
}

void findVal(unsigned int m1Offset, unsigned int m1Len, unsigned int m2Offset, unsigned int m2Len) {

    unsigned int  n1       = 0;
    unsigned int  n2       = 0;
    unsigned char foundVal = 1;
    unsigned int  m1Time   = m1Offset;
    unsigned int  m2Time   = m2Offset;

    //No need to find n1 and n2 if msgs are starting from beginning.
    if(((m1Offset == m1Len) && (m2Offset == m2Len)) || ((0 == m1Offset) && (0 == m2Offset)))
    {
        m1Time = 0;
        m2Time = 0;
    }

    //No need to find n1 and n2 if offset times are same.
    else if(m1Offset != m2Offset)
    {
       //Offset times are not same.
       foundVal = 0;

       //Find GCD of m1Len and m2Len.
       unsigned int gcd = getGCD(m1Len, m2Len);

       //There is a solution only if the difference of offsets is divisible by gcd.
       if(0 == (m2Offset-m1Offset) % gcd)
       {
           for(n2=1; n2<(unsigned int)-1; n2++)
           {
               unsigned int temp1 = (m2Len*n2)+(m2Offset-m1Offset);
               if(0 == temp1 % m1Len)
               {
                    n1 = temp1/m1Len;
                    m1Time = m1Offset + n1*m1Len;
                    m2Time = m2Offset + n2*m2Len;

                    foundVal = 1;
                    break;
               }
           }
       }
    }

    if(1 == foundVal)
    {
        printf("Found n1[%u] n2[%u] m1Time[%u] m2Time[%u]\n", n1, n2, m1Time, m2Time);
    }
    else
    {
        printf("Could not find n1, n2, m1Time, m2Time\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[1] n2[2] m1Time[42] m2Time[42]