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|bababea| = 42

d|abacad|abacad| = 42

示例2:Message1: |acabbaaa message2: |dcbabaaaa.

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

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

我是用c写的，除了算法本身，我基本上已经完成了所有的工作。

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

Answer 1

我已经回答了一个不同的问题，我认为这个问题的解决方案是完全相同的。您需要求解方程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, m2Timen");
    }
}
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[1] n2[2] m1Time[42] m2Time[42]