How do we optimize the calculation of the route options?



  • There is a function that considers the routing options to be the case if the player can pass no more than n points at a time. Marshrut is linear, is straight from 1.k, right, the player can't pass more than a single scale. For example, up to point 3, if a player can jump three points at a time, there will be 7 options, etc. In fact, linear programming is known as a blacksmith task. I'm not very good at algorithms, but the task has basically been decided, except for optimization. For the entrance of 300x300, the search for a beam takes 1 minute 45 seconds. Maybe you have optimization advice?

    #include <deque>
    #include <stack>
    #include <iostream>
    using namespace std;
    

    class LongNumber {
    private: deque<int> longViewParam;

    public: LongNumber() {

    }
    public: ~LongNumber() {
    longViewParam.~deque();
    }
    public:void parse(long long arg) {
    while (arg > 0) {
    longViewParam.push_front(arg % 10);
    arg = arg / 10;
    }

    }
    public: void representation(stack<int> representValue) {
    longViewParam.clear();
    while (representValue.size() > 0) {
    longViewParam.push_back(representValue.top());
    representValue.pop();
    }
    }

    public: stack<int> SumLongNumber(deque<int> da, deque<int> db) {
    stack<int> result;
    if (da.size() >= db.size()) {
    int shiftFlag = 0;
    while (da.size() > 0) {
    if (db.size() > 0) {
    int operationBuffer = da.back() + db.back() + shiftFlag;
    if ((operationBuffer / 10) > 0) {
    shiftFlag = operationBuffer / 10;
    result.push(operationBuffer % 10);
    }
    else {
    result.push(operationBuffer);
    shiftFlag = 0;
    }
    db.pop_back();
    }
    else {
    result.push(da.back() + shiftFlag);
    shiftFlag = 0;
    }
    da.pop_back();
    }
    if (shiftFlag > 0) {
    result.push(shiftFlag);
    shiftFlag = 0;
    }
    }
    else {
    int shiftFlag = 0;
    while (db.size() > 0) {
    if (da.size() > 0) {
    int operationBuffer = da.back() + db.back() + shiftFlag;
    if ((operationBuffer / 10) > 0) {
    shiftFlag = operationBuffer / 10;
    result.push(operationBuffer % 10);
    }
    else {
    result.push(operationBuffer);
    shiftFlag = 0;
    }
    da.pop_back();
    }
    else {
    result.push(db.back() + shiftFlag);
    shiftFlag = 0;
    }
    db.pop_back();
    }
    if (shiftFlag > 0) {
    result.push(shiftFlag);
    shiftFlag = 0;
    }
    }
    return result;
    }
    public:void Print() {
    deque<int> tempParam = longViewParam;
    while (tempParam.size() > 0) {
    cout << tempParam.front();
    tempParam.pop_front();
    }
    }
    public: deque<int> GetValue() {
    return longViewParam;
    }

    public: LongNumber operator+ (LongNumber arg) {
    LongNumber tempObject;
    tempObject.representation(tempObject.SumLongNumber(arg.longViewParam, this->longViewParam));
    return tempObject;
    }
    };
    LongNumber Jumper(int posCounter, int sizeBlock) {
    LongNumber tempObject;
    tempObject.parse(1);
    LongNumber *buffer;
    if (sizeBlock >= 1) {
    buffer = new LongNumber[sizeBlock + 1];
    int counter = 0;
    buffer[0].parse(1);
    buffer[1].parse(1);

        for (int i = 2; i &lt; sizeBlock + 1; ++i) {
            buffer[i].parse(0);
        }
        if (posCounter == 0 || posCounter == 1) {
            return tempObject;
        }
        while (true) {
            for (int i = 0; i &lt; sizeBlock + 1; ++i) {
                LongNumber temp;
                temp.parse(0);
                for (int j = 0; j &lt; sizeBlock + 1; ++j) {
                    if (j != i) {
                        temp = temp + buffer[j];
                    }
                }
                buffer[i] = temp;
                if (counter == posCounter) {
                    return temp;
                }
                ++counter;
            }
        }
    }
    return tempObject;
    

    }
    int main() {
    Jumper(300, 300).Print();
    system("pause");
    return 0;
    }



  • Several technical councils:

    • hand over complex objects to the reference (e.g., SumLongNumber(deque<int>& da, deque<int>& db)Because it's much faster (this time, everything's irreconcilable to the value, which has to slow down the process appreciably),
    • operator+ It would be possible to make it more rapid if the avoidance of the creation of an intermediate facility (the same is the meaning of the operator),
    • Ten is a slow operation. It is better to keep long whole numbers in structures with a good reason (twice level) and to translate into a decimal place at the last point (for the display),
    • Don't use it. system("pause");because it adds dependence on PPs and it's dangerous at all (why does the system do when calling "pause").



Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2