0

我是一名初学者程序员，正在尝试 Codility 青蛙跳问题。这是我的代码解决方案：

int solution(int, int, int, unsigned long int&);

int main(){

    unsigned long int stepsTaken = 1;

    int x = 10;
    int y = 85;
    int d = 30;

    solution(x, y, d, stepsTaken);

    cout << "Total Steps Taken: " << stepsTaken << endl;
}

int solution( int X, int Y, int D, unsigned long int &stepsTaken) {

    int currentPosition = X;
    int positionToGetTo = Y;
    int stepsJumpedEachTime = D;

    currentPosition += stepsJumpedEachTime;

    if(currentPosition < positionToGetTo){

        stepsTaken++;
        solution(currentPosition, positionToGetTo, stepsJumpedEachTime, stepsTaken);
    }

    return stepsTaken;
}

现在我遇到的问题是，当我尝试满足处理 1-1000000000 范围内的数字的要求时。如果我将上面的 int y 更改为 2000000，我会得到一个否定的返回值。unsigned long int 应该返回一个正数，但是当我使用 2000000 时它返回负数。

4

8 回答 8

2

迭代时间太长。

int destination = Y - X;
int steps = destination / D;
int remainder = destination % D;
if (remainder != 0){
    steps++;
}
return steps;
于 2013-10-12T06:49:03.910 回答
2

发生这种情况是因为 C++ 中的 int 数字有限制 - 请参阅http://www.cplusplus.com/reference/climits/。在大多数情况下，标准类型应该可以满足您的需求。

如果没有标准类型足够大，请参阅C++ 的最佳（速度）任意精度库是什么？

这是您的代码的更简单版本，您怎么看？

unsigned long int solution( int currentPosition, int positionToGetTo , int stepsJumpedEachTime) {

    if (currentPosition >= positionToGetTo)
        return 0; 

    return 1 + solution(currentPosition + stepsJumpedEachTime, positionToGetTo, stepsJumpedEachTime);

}

int main(){

    int x = 10;
    int y = 85;
    int d = 30;

    unsigned long int stepsTaken = solution(x, y, d);

    cout << "Total Steps Taken: " << stepsTaken << endl;
}
于 2013-09-19T15:23:47.673 回答
1

在不使用递归的情况下使其工作，如下所示：

#include <iostream>
#include <iostream>

using namespace std;

unsigned long int solution( int currentPosition,int positionToGetTo ,int       stepsJumpedEachTime);

int main(){

int x = 10;
int y = 1000000000;
int d = 30;

unsigned long int stepsTaken = solution(x, y, d);

cout << "Total Steps Taken: " << stepsTaken << endl;
}

unsigned long int solution(int currentPosition, int positionToGetTo ,int   stepsJumpedEachTime){

unsigned long int stepsTaken = 1;

currentPosition += stepsJumpedEachTime;

while (currentPosition < positionToGetTo){

    currentPosition += stepsJumpedEachTime;
    stepsTaken++;

}

return stepsTaken;

}
于 2013-09-20T08:53:04.937 回答
0

C 解决方案。Codility 100 分中的 100 分

int FrogJmp(int X, int Y, int D) {

    int result = 0;
    int dest = Y - X;
    result = dest / D;

    if (dest % D != 0) {
        result++;
    }
    return result;
}
于 2014-05-18T22:33:35.767 回答
0

使用 ceil 的解决方案：

#include <cmath>
#include <climits>

int solution(int X, int Y, int D) 
{
    if (X >= Y)
        return 0;

    if (D == 0)
        return INT_MAX;

    return std::ceil((double)(Y - X) / D);
}
于 2014-07-13T17:33:01.073 回答
0

在我的 x64 CPU 上，100% 的“float”版本比“int”版本快三倍：

#include <cmath>

int solution(int X, int Y, int D)
{
    return std::floor( (double)( Y - 1 - X ) / D + 1 );
}
于 2014-02-22T16:21:12.380 回答
0

100% 得分 - C 代码 :Codility: FrogJmp

int solution(int X, int Y, int D) {
    // write your code in C90
    if (Y == X) 
      return 0;
    else
      return (((Y - X) / D) + (((Y - X) % D) > 0 ? 1 : 0));     
}

预期的最坏情况时间复杂度为 O(1) 意味着没有迭代......

于 2014-08-08T02:55:39.680 回答
0

我希望这会奏效：

class Solution {
    public int solution(int X, int Y, int D) {
    if(X>=Y)
    return 0;
    if((Y-X)%D!=0) return (Y-X)/D+1;
    else
    return (Y-X)/D;
   }
}
于 2014-02-08T18:26:38.813 回答