我在确定是否存在 int N 时的缺陷在哪里 x1 + v1 * N = x2 + v2 * N

Question

所以我试图解决一个问题，你确定两只袋鼠是否最终会同时降落在同一点，因为一只袋鼠从位置 x1 开始并且每次移动距离 v1跳，另一个 x2 和 v2 用于测量相同。

示例：

输入0 3 4 2表示x1=0、v1=3、x2=4、v2=2。他们最终会降落在同一个点上，因为他们从起点到每一跳之后的距离都是

0 -> 3 -> 6 -> 9  -> 12
4 -> 6 -> 8 -> 10 -> 12

我的解决方案未能通过一些测试用例，我想知道我的 O(1) 解决方案的逻辑缺陷在哪里：

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    static void Main(String[] args) {
        string[] tokens_x1 = Console.ReadLine().Split(' ');
        int x1 = Convert.ToInt32(tokens_x1[0]);
        int v1 = Convert.ToInt32(tokens_x1[1]);
        int x2 = Convert.ToInt32(tokens_x1[2]);
        int v2 = Convert.ToInt32(tokens_x1[3]);
        // What needs to be determined is whether there exists an N such that
        // x1 + v1 * N = x2 + v2 * N
        // or, equivalenly, 
        // (x1 - x2) = (v2 - v1) * N 
        double ndouble = ((double)x1 - (double)x2) / ((double)v2 - (double)v1); 
        Console.WriteLine(ndouble == (int)ndouble ? "YES" : "NO");
    }
}

Answer 1

有两个问题：

floating point numbers 导致舍入错误
除以零（如@samgak 所述）

所以你的方法变成了这样：

return (x1 == x2) || 
  (((x1 < x2 && v1 > v2) || (x2 < x1 && v2 > v1)) && (x1 - x2) % (v1 - v2) == 0);

如果 x1 与 x2 相同，则我们无需进一步查找。这是 v1 == v2 和袋鼠相遇的唯一情况。检查第一个数字是否可以被第二个数字整除是用模数和整数完成的，这样就不会出现舍入错误。在应用模数之前，我们确保袋鼠彼此靠近而不是远离彼此（1 % -1 == 0 但正如@zerkms 指出的那样不是解决方案）。

Answer 2

这是一个 C 解决方案

int main(){
    int x1; 
    int v1; 
    int x2; 
    int v2; 
    scanf("%d %d %d %d",&x1,&v1,&x2,&v2);
    int x = x1-x2,v = v2-v1;
    if((v==0 && x==0)||(x!=0 && v!=0 && x%v==0 && (x*v>=0)))
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

我在确定是否存在 int N 时的缺陷在哪里 x1 + v1 * N = x2 + v2 * N

Where is my flaw in determining whether there exists an int N such that x1 + v1 * N = x2 + v2 * N

c#

algorithm

precision

casting