Как оптимизировать цикл for?

Question

У меня проблема, скажем так: Найдите все две пары чисел (x, y) и (z, t) , такие что x³ + y³ = z³ + t³ , где ( x, y)! = (z, t) и x³ + y³ <10000 </strong>.

Взяв кубический корень из 10 000 гильдий 21.544 -> округлите до 21, и я получил:

#include <iostream>

using namespace std;

int main() {
    for( int x = 1; x <= 20; ++x ) {
        for( int y = x + 1; y <= 21; ++y ) {
            for( int z = x + 1; z <= y - 1; ++z ) {
                for( int t = z; t <= y - 1; ++t ) {
                    if( x*x*x + y*y*y == z*z*z + t*t*t ) {
                        cout << x << ", " << y << ", " << z << ", " << t << endl; 
                    }
                }
            } 
        }
    }
    return 0;
}

Я знаю, что этот код можно оптимизировать больше, и это то, что я ищу. Кроме того, один из моих друзей сказал мне, что y может быть x + 2 вместо x + 1 , и я сомневаюсь в этом, так как если
x = 1 , тогда у нас никогда не будет y = 2 , который в этом случае пропустил одно возможное решение.

Есть мысли?

Answer 1

Что ж, есть одна очевидная алгоритмическая оптимизация, которая может быть сделана с учетом текущей структуры цикла, вы оптимизируете совершенно правильно, ограничивая свои диапазоны до кубического корня 10000.Однако вы можете пойти дальше и ограничить свой диапазон по y, исходя из корня куба 10000-x.Это одна вещь, которую вы можете сделать.

Другая оптимизация заключается в том, что на земле нет причин, чтобы это было 4 цикла.Просто сделайте 2 цикла и вычислите значения x ^ 3 + y ^ 3 и проверьте наличие дубликатов.(Это так же хорошо, как вы собираетесь получить, не углубляясь в особенности корней куба.) На самом деле это не правильно использует API, но вы поняли:Мультикарта и искать повторы.

Answer 2

Типичный компромисс: память на скорость.

Сначала ограничение на x довольно большое: если предположить, что (x,y) упорядочено с x <= y, то

    x^3 + y^3 < N and x^3 < y^3 (for positive numbers)
=>  x^3 + x^3 < N (by transitivity)
<=> x^3 < N/2
<=> x <= floor((N/2)^(1/3))

Таким образом x <= 17 здесь.

Теперь запомним результат x^3 + y^3 и построим ассоциативную таблицу (сумма -> пары). Кстати, есть ли причина выбрасывать (x,x) как пару?

int main(int argc, char* argv[])
{
  typedef std::pair<unsigned short, unsigned short> Pair;
  typedef std::vector<Pair> PairsList;
  typedef std::unordered_map<unsigned short, PairsList> SumMap;

  // Note: arbitrary limitation, N cannot exceed 2^16 on most architectures
  // because of the choice of using an `unsigned short`
  unsigned short N = 10000;
  if (argc > 1) { N = boost::lexical_cast<unsigned short>(argv[1]);  }

  SumMap sumMap;

  for (unsigned short x = 1; x*x*x <= N/2; ++x)
  {
    for (unsigned short y = x; x*x*x + y*y*y <= N; ++y)
    {
      sumMap[x*x*x + y*y*y].push_back(Pair(x,y));
    }
  }

  for (SumMap::const_reference ref: sumMap)
  {
    if (ref.second.size() > 1)
    {
      std::cout << "Sum: " << ref.first
                << " can be achieved with " << ref.second << "\n";
      // I'll let you overload the print operator for a vector of pairs
    }
  }

  return 0;
}

Мы здесь O (N ^ 2).

Answer 3

Я бы предложил рассчитать мощности во внешних циклах (РЕДАКТИРОВАТЬ: Вычеркнуты вычисления из циклов for):

int x3, y3, z3;
for( int x = 1; x <= 20; ++x ) {
    x3 = x * x * x;
    for( int y = x + 1; y <= 21; ++y ) {
        y3 = y * y * y;
        for( int z = x + 1; z <= y - 1; ++z ) {
            z3 = z * z * z;
            for( int t = z; t <= y - 1; ++t ) {
                if( x3 + y3 == z3 + t*t*t ) {
                    cout << x << ", " << y << ", " << z << ", " << t << endl; 
                }
            }
        } 
    }
}

В любом случае, почему вы хотите оптимизировать (по крайней мере, для этого примера)? Это работает за 20 мс на моем ПК ... Так что, я думаю, у вас есть похожие проблемы в более широком масштабе.

Answer 4

Используйте таблицу от сумм до набора пар чисел, генерирующих эту сумму.

Вы можете сгенерировать эту таблицу двумя вложенными циклами for, а затем прогонять таблицу, собирая суммы с несколькими решениями.

Answer 5

Составьте список всех номеров и их операционный результат. Сортировать список по результатам. Результаты проверки соответствия на наличие разных операндов.

Answer 6

Как общее резюме:

• Рассчитайте кубы по мере того, как вы делаете цикл, а не в конце, таким образом int xcubed = x*x*x; сразу после цикла x (аналогично y и z).Это спасет вас от расчета одних и тех же значений несколько раз.Поместите их в таблицу, чтобы вычислить их только один раз.
• Создайте таблицу с суммами кубов, используя хеш-таблицу некоторой степени, и пусть она содержит дубликаты (не путать с хеш-коллизиями).
• Любой, у кого есть дубликат, является решением.

1729, кстати, должно стать одним из ваших решений.1 куб плюс 12 кубов, а также 9 кубов + 10 кубов.

Для проверки производительности можно, конечно, выбрать более высокое значение maxsum (а также запустить его несколько раз).

алгоритм строго O (N ^ 2/3).(2/3, потому что вы идете только к кубическому корню из N, а затем это O (m ^ 2) в этом меньшем диапазоне).