1

我目前正在研究https://open.kattis.com/problems/rationalarithmetic以进行自己的练习。我得到 4 位数字和一个操作。输入是：x1 y1 op x2 y2，分数是 x1/y1 和 x2/y2。如果我得到输入：1 3 + 1 2 那么它的 1/3 + 1/2 并且答案应该是最小的分形，所以它的 5/6。我通过了我得到的测试用例，但我不知道我做错了什么。总结一下我的做法：

  1. 读取输入并检查操作是否为 +、-、/ 或 *。我生成一个素数数组来找到最大公约数。
  2. 根据输入的操作将输入发送到函数。
  3. 我用简单的数学计算给定的输入。
  4. 然后我找到最大的公约数并将分子和分母都除以它。
  5. 之后我打印出结果。

这是主要功能以及如果操作是 *. 我以相同的方式处理其他操作，但使用其他数学。

     void mult(int *x1, int *y1, int *x2, int *y2){
      long long top = (*x1) * (*x2);
      long long bottom = (*y2) * (*y1);
      long long frac;
      if(bottom != 0||top != 0){
          frac = commonDiv(top,bottom);
     }else{
         frac = 1;
     }
     string sign = "";
     if(top * bottom < 0){
         sign = "-";
      }else{
         sign = "";
      }
     printf("%s%lld / %lld\n",sign.c_str(),abs(top/frac),abs(bottom/frac) );
    }


     int main()
     {

     int numOp;
     scanf("%d", &numOp);
     getPrime(1,sqrt(100000));
     while(numOp != 0){
      int x1,x2,y1,y2;
      char op[2];
      scanf("%d %d %s %d %d", &x1, &y1, op, &x2, &y2);
      if( op[0] == '+'){
        add(&x1, &y1, &x2,&y2);
      }
      else if(op[0] == '-'){
        sub(&x1,&y1,&x2,&y2);
      }
      else if(op[0] == '/'){
        divi(&x1,&y1,&x2,&y2);
     }
     else{
        mult(&x1,&y1,&x2,&y2);
    }
     numOp--;
    }   
    }

这是给定测试用例的代码，我得到了正确的结果。我需要一些关于不同测试用例或任何建议的提示。 http://ideone.com/jBddSI

4

2 回答 2

1

我会告诉你以下几点：在处理有理数时，忘记用素数列表找到最大公约数。这就是我们在学校都学过的，但是在编程时，使用欧几里德算法可以更容易（和有效地）解决这个任务

于 2015-08-05T09:43:44.010 回答
0

我不明白为什么你只在 [1,10000] 范围内寻找素数，而你分解的数字可以达到 (10^9)^2 = 10^18 但正如 Marom 所说，你应该改用 gdc 算法。

此外，我不明白你为什么在你的函数中传递指向 int 的指针（add，divi ...）。

此外，在这段代码中：

      long long top = (*x1) * (*x2);

我认为如果 x1 和 x2 太大，就会发生溢出，因为转换发生在整数相乘之后（而不是 long long int）。

于 2015-08-05T09:59:43.710 回答