Решение Загадки ленивого хобо

Я бы хотел помочь в оптимизации этого вычисления, который находится из Lazy Hobo Riddle :

  

Там когда-то было 4 hoboes, путешествующих по всей стране. Во время   они бежали по средствам, поэтому они остановились на ферме, чтобы посмотреть   для некоторой работы. Фермер сказал, что было 200 часов работы, которые   может быть сделано в течение следующих нескольких недель. Фермер сказал:   что то, как они разделили работу, соответствовало им. Соглашались   для запуска следующего дня.

     

На следующее утро один из hoboes - который был заметно умнее   и более ленивый, чем другие 3, - сказал, что для них не было причин   делать то же самое количество работы. Этот hobo продолжал предлагать   следующая схема:

     
  • Все бродяги будут рисовать соломинку.
  •   
  • Солома будет отмечена цифрой.
  •   
  • Число будет указывать как количество дней, в которые должен работать ящик, так и количество часов, которые будут обрабатываться в каждый из этих дней. Для   Например, если солома была отмечена цифрой 3, то hobo, кто ее рисовал,   работайте 3 часа в день в течение 3 дней.
  •   

Само собой разумеется, что ленивый хобо убедил других   согласитесь с этой схемой, и что благодаря ловкости руки ленивый хобо   нарисовал лучшую соломинку.

     

Загадка заключается в том, чтобы определить возможные способы разделить работу   согласно предыдущей схеме.

В основном это связано с нахождением всех возможных решений \ $ a, b, c, d \ $ таких, что \ $ a ^ {2} + b ^ {2} + c ^ {2} + d ^ {2} = 200 \ $

for(int a = 1;a<=100; a++)
    for(int b = 1; b<=100; b++)
        for(int c = 1; c<=100; c++)
            for(int d = 1; d<=100; d++){
                ++counter;
                if(a*a + b*b + c*c + d*d == 200)
                    cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
            }
34 голоса | спросил user54410 9 +04002014-10-09T10:06:58+04:00312014bEurope/MoscowThu, 09 Oct 2014 10:06:58 +0400 2014, 10:06:58

9 ответов


41

Обратите внимание, как квадрат числа 15 или больше превышает 200? Что вы можете сделать, устанавливается интервал от 1 до 14. Нет никакого преимущества в оценке одной и той же комбинации снова и снова. Поймите, что наиболее эффективным способом является структурирование ваших циклов, таких как

$$ a \ leq b \ leq c \ leq d $$

В вашей попытке вы выполняете итерацию 38416 раз!

Ограничив интервал, вы повторяете только 2380 раз!

Еще одна вещь, которую вы можете сделать: проверить и разбить, когда \ $ a ^ {2} + b ^ {2} + c ^ {2} + d ^ {2}> 200 \ $

for(int a = 1; a<=14; a++)
    for(int b = a; b<=14; b++)
        for(int c = b; c<=14; c++)
            for(int d = c; d<=14; d++){
                if(a*a + b*b + c*c + d*d == 200)
                    cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
                else if(a*a + b*b + c*c + d*d > 200)
                    break;
            }

Теперь вы повторяете только 1214 раз! Это более эффективно.

ответил Quaxton Hale 9 +04002014-10-09T10:16:37+04:00312014bEurope/MoscowThu, 09 Oct 2014 10:16:37 +0400 2014, 10:16:37
40

Следует отметить, что четвертая итерация бесполезна. После того, как вы зафиксировали первые 3 переменные, вам нужно найти значение для четвертого, что равно 200 минус сумма квадратов первого. 3. Вам не нужно проходить все возможные числа, чтобы проверить, является ли один из них квадрат равен N, вы можете просто взять квадратный корень из N и проверить, является ли оно целым числом или нет.

Еще одно замечание заключается в том, что вы получаете одно и то же решение несколько раз в другом порядке. Это можно легко избежать (и избежать много итераций из-за этого), упорядочив переменные.

Наконец, вы можете уменьшить количество итераций, если вы потерпите неудачу раньше. Как только вы проверите a = 15 и увидите, что в квадрате больше 200, вам больше не нужно проверять более высокие значения для.

Умная вещь - упорядочить переменные в порядке убывания, начиная с самого большого числа, которое может по-прежнему приводить к решению.

Решение:

int N = 200;
for (int a = (int) sqrt(N); a >= 0; a--) {
  for (int b = min(a, (int) sqrt(N - a*a)); b >= 0; b--) {
    for (int c = min(b, (int) sqrt(N - a*a - b*b)); c >= 0; c--) {
      double remaining = sqrt(N - a*a - b*b - c*c);
      int d = (int) remaining;
      if ((d == remaining) && (d <= c)) {
        cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
      }
    }
  }
}

Извиняюсь за возможные ошибки, связанные с типом, я не писал C в возрасте.

Вывод:

a: 14 b: 2 c: 0 d: 0
a: 12 b: 6 c: 4 d: 2
a: 10 b: 10 c: 0 d: 0
a: 10 b: 8 c: 6 d: 0
a: 8 b: 8 c: 6 d: 6
iterations: 353
ответил Tibos 9 +04002014-10-09T14:28:53+04:00312014bEurope/MoscowThu, 09 Oct 2014 14:28:53 +0400 2014, 14:28:53
16

Некоторые незначительные вещи, но все равно можно упомянуть:

Когда используется std::endl, буфер очищается, что может немного увеличить производительность , особенно если это сделано несколько раз.

Чтобы получить новую строку без этого добавленного флеша, используйте "\n" в выводе:

std::cout << "\n";

Кроме того, рассмотрите возможность добавления немного большего количества пробелов в операторы множественного цикла для дополнительной читаемости:

for (int a = 1; a <= 100; a++)
ответил Jamal 9 +04002014-10-09T10:26:03+04:00312014bEurope/MoscowThu, 09 Oct 2014 10:26:03 +0400 2014, 10:26:03
14

Стиль

Vogel612 вызывает интересный момент в его комментарий : using namespace std; обычно считается плохой практикой .

Кроме того, вы должны стараться избегать того, чтобы один и тот же номер был жестко закодирован в разных местах: вы могли бы просто использовать const int lim = 200;. Это упрощает чтение /понимание и упрощает обслуживание: win-win!

Оптимизация

Вершись на EngieOP (и немного на rolinger ): вы можете ограничить себя:

$$ a \ leq b \ leq c \ leq d $$

Это приводит к интересным выводам:

$$ 4 * a ^ {2} \ leq a ^ {2} + b ^ {2} + c ^ {2} + d ^ {2} = 200 $$ так $$ a ^ {2} \ leq 50 $$ поэтому $$ a \ leq 7 $$

Мы можем воспользоваться этим преимуществом в коде, остановившись, когда узнаем, что нет надежды найти больше.

Давайте забудем о математике и напишем эту вещь в простом C ++ (сохраняя различные вычисленные значения в переменной для повторного использования):

int main(int argc, char* argv[])
{
    const int lim = 200;
    std::cout << "Hello, world!" << std::endl;
    for(int a = 1; 4*a*a <= lim; a++)
    {
        int tmp1 = a*a;
        for(int b = a; tmp1 + 3*b*b <= lim; b++)
        {
            int tmp2 = tmp1 + b*b;
            for(int c = b; tmp2 + 2*c*c <= lim; c++)
            {
                int tmp3 = tmp2 + c*c;
                for(int d = c; tmp3 + d*d <= lim; d++){
                    if (tmp3 + d*d == lim)
                        std::cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << std::endl;
                }
            }
        }
    }
    return 0;
}

Больше оптимизаций для вас

Когда исправлены a, b и c, поиск d может быть оптимизирован еще больше: мы хотите решить

$$ d ^ {2} = lim - (a ^ {2} + b ^ {2} + c ^ {2}) $$

Вы можете просто вычислить корень и посмотреть, соответствует ли оно целому числу, превышающему c.

ответил Josay 9 +04002014-10-09T14:37:59+04:00312014bEurope/MoscowThu, 09 Oct 2014 14:37:59 +0400 2014, 14:37:59
14

Как и отличная информация от @EngieOP, вы также можете подумать о том, чтобы выполнить несколько повторных вычислений из внутреннего цикла за счет дополнительного int в цикле for. Они могут быть оптимизированы компилятором, но не должны уменьшать ясность.

for(int a = 1; a<=14; a++){
    sum_a = a*a;
    for(int b = a; b<=14; b++){
        sum_b = sum_a + b*b;
        for(int c = b; c<=14; c++){
            sum_c = sum_b + c*c;
/*[... etc ...] */

Он не уменьшит количество итераций, но может уменьшить количество циклов во внутреннем цикле до одного добавления и сравнения (если компилятор еще не поймает оптимизацию и сделает это за вас)

ответил rolinger 9 +04002014-10-09T14:05:47+04:00312014bEurope/MoscowThu, 09 Oct 2014 14:05:47 +0400 2014, 14:05:47
11

Одна вещь, которую следует учитывать, выполнение повторных умножений внутри цикла и /или внутри объявления цикла может быть очень дорогостоящим. Рассмотрим следующее, которое помещает все квадраты в массив, и петли только перебирают через массив. Это устраняет множество дополнительных вычислений. В моих тестах, даже со стоимостью дополнительного цикла, это привело к примерно на 30% увеличению скорости.

int squares[15];
const int limit = 200;
int it_limit = 15;
for (int i = 1; i < it_limit; i++)
    squares[i] = i*i;
int temp = 0;
for (int a = 1; a < it_limit; a++)
{
    temp = squares[a];
    for (int b = a; b < it_limit; b++)
    {
        temp = squares[b] + squares[a];
        if (temp > limit)
            break;
        for (int c = b; c < it_limit; c++)
        {
            temp = squares[c] + squares[b] + squares[a];
            if (temp > limit)
                break;
            for (int d = c; d < it_limit; d++)
            {
                temp = squares[d] + squares[c] + squares[b] + squares[a];
                if (temp > limit)
                    break;
                if (temp == limit)
                    cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << "\n";
            }
        }

    }

}
ответил tinstaafl 9 +04002014-10-09T18:35:45+04:00312014bEurope/MoscowThu, 09 Oct 2014 18:35:45 +0400 2014, 18:35:45
11

Поиск всех решений при небольшом числе итераций:

#include <iostream>
#include <sstream>
#include <map>
#include <vector>

typedef unsigned int T;

int main()
{
    const T LIMIT = 2000000;
    std::map< T,std::vector< std::pair< T,T > > > pairs_of_squares;
    T a, b, c, d, sum_of_squares, remaining;
    unsigned long increment = 0;
    unsigned long num_results = 0;
    unsigned long index;
    std::vector< std::pair< T, T > > array_of_pairs;
    std::stringstream out;

    for ( a = 1; 2 * a * a <= LIMIT - 2; ++a )
    {
        for ( b = a; (sum_of_squares = a*a + b*b) <= LIMIT - 2; ++b )
        {
            remaining = LIMIT - sum_of_squares;
            // Check if it is possible to get another pair (c,d) such that either
            // a <= b <= c <= d or c <= d <= a <= b and, if not, ignore this pair.
            if ( a * a * 2 < remaining && remaining < b * b * 2 )
            {
                ++increment;
                continue;
            }
            pairs_of_squares[sum_of_squares].push_back( std::pair<T,T>(a,b) );

            if ( pairs_of_squares.count( remaining ) != 0 )
            {
                array_of_pairs = pairs_of_squares[ remaining ];
                for ( index = 0; index < array_of_pairs.size(); ++index )
                {
                    c = array_of_pairs[index].first;
                    d = array_of_pairs[index].second;
                    if ( b <= c )
                    {
                        out         << a
                            << ", " << b
                            << ", " << c
                            << ", " << d
                            << '\n';
                        ++num_results;
                    }
                    else if ( d <= a )
                    {
                        out         << c
                            << ", " << d
                            << ", " << a
                            << ", " << b
                            << '\n';
                        ++num_results;
                    }
                    ++increment;
                }
            }
            else
            {
                ++increment;
            }
        }
    }

    std::cout << out.str()
                << num_results << " possibilities found in " << increment << " increments." << std::endl;
    return 0;
}

Вывод:

Для лимита 200:

2, 4, 6, 12
6, 6, 8, 8
2 possibilities found in 75 increments.

real    0m0.005s
user    0m0.003s
sys 0m0.002s

[Примечание: для поиска всех возможных ответов требуется всего 75 итераций, а не более 1000.]

Для лимита в 2 000 000:

...
104, 192, 984, 992
56, 112, 984, 1008
1221 possibilities found in 785771 increments.

real    0m0.890s
user    0m0.873s
sys 0m0.014s

Объяснение:

Не работайте со всеми четырьмя цифрами индивидуально - работайте над двумя парами чисел (низкооцененная пара и высокозначная пара).

Начнем с создания пары чисел \ $ (a, b) \ $ где \ $ a \ leq b \ $ и \ $ a ^ 2 + b ^ 2 \ leq LIMIT - 2 \ $ (примечание: 2 минимальная сумма квадратов для другой пары чисел) и нажимаем эту пару чисел на карту.

Затем он проверяет, содержит ли карта другую пару \ $ (c, d) \ $, где \ $ c \ leq d \ $ и \ $ c ^ 2 + d ^ 2 = LIMIT - a ^ 2 - b ^ 2 \ $ такой, что либо \ $ a \ leq b \ leq c \ leq d \ $, либо \ $ c \ leq d \ leq a \ leq b \ $, и в этом случае он является допустимым ответом и выводит его.

Затем повторяется для других пар \ $ (a, b) \ $.

ответил MT0 10 +04002014-10-10T01:08:40+04:00312014bEurope/MoscowFri, 10 Oct 2014 01:08:40 +0400 2014, 01:08:40
11

Прочитав комментарий Джона , я думал, что мы можем многое сделать лучше ответ EngieOP

for(int a = 1; a<=14; a++)
    for(int b = a; b<=14; b++)
        for(int c = b; c<=14; c++)
            for(int d = c; d<=14; d++){
                if(a*a + b*b + c*c + d*d == 200)
                    cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
                else if(a*a + b*b + c*c + d*d > 200)
                    break;
            }  

Как ускорить это? Уменьшите расчеты!

int resultToReach = 200;
int maxBorder = (int)sqrt(200);
for(int a = 1; a<=maxBorder ; a++)
    for(int b = a; b<=maxBorder ; b++)
        for(int c = b; c<=maxBorder ; c++)
            for(int d = c; d<=maxBorder ; d++){
                int tempResult = a*a + b*b + c*c + d*d;
                if(tempResult == resultToReach)
                    cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
                else if(tempResult > resultToReach)
                    break;
            }  

Но таким образом мы все равно вычисляем a*a + b*b + c*c + d*d для каждой итерации. Поэтому давайте уменьшим их, как ответ rolinger уже показывает

    int resultToReach = 200;
    int maxBorder = (int)sqrt(resultToReach);
    for (int a = 1; a <= maxBorder; a++)
    {
        int firstResult = resultToReach - a * a;
        for (int b = a; b <= maxBorder; b++)
        {
            int secondResult = firstResult - b * b;
            for (int c = b; c <= maxBorder; c++)
            {
                int thirdResult = secondResult - c * c;
                for (int d = c; d <= maxBorder; d++)
                {
                    int tempResult = thirdResult - d * d;
                    if (tempResult == 0)
                    {
                        cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
                        break;
                    }
                    else if (tempResult < 0)
                    {
                        break;
                    }
                }
            }
        }
    }

Если мы теперь изменим петли и добавим некоторые незначительные условия, мы получим это

    int resultToReach = 200;
    int maxBorder = (int)sqrt(resultToReach);

    for (int a = maxBorder; a >= 1; a--)
    {
        int firstResult = resultToReach - a * a;
        if (firstResult >= 3)
        {
            for (int b = a; b >= 1; b--)
            {
                int secondResult = firstResult - b * b;
                if (secondResult >= 2)
                {
                    for (int c = b; c >= 1; c--)
                    {
                        int thirdResult = secondResult - c * c;
                        if (thirdResult >= 1)
                        {
                            for (int d = c; d >= 1; d--)
                            {
                                int tmpResult = thirdResult - d * d;
                                if (tmpResult == 0)
                                {
                                    counter++;
                                    cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
                                    break;
                                }
                                else if (tmpResult > 0)
                                {
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

Поскольку у меня не было C ++ вручную, я сделал выбор времени в C #. Это вычисляет уникальные комбинации 1221 для resultToReach==2000000 примерно 19 секунд .

Взяв комментарий Josay , вы получите это

    int resultToReach = 200;
    int maxBorder = (int)sqrt(resultToReach);

    for (int a = maxBorder; a >= maxBorder/4; a--)
    {
        int firstResult = resultToReach - a * a;
        if (firstResult >= 3)
        {
            int firstBorder = (int)sqrt(firstResult);
            for (int b = min(a, firstBorder); b >= firstBorder/3; b--)
            {
                int secondResult = firstResult - b * b;
                if (secondResult >= 2)
                {
                    int secondBorder = (int)sqrt(secondResult);
                    for (int c = min(b, secondBorder); c >= secondBorder/2; c--)
                    {
                        int thirdResult = secondResult - c * c;
                        if (thirdResult >= 1)
                        {
                            int d = (int)sqrt(thirdResult);
                            if (d <= c && thirdResult == d * d)
                            {
                                cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
                            }
                        }
                    }
                }
            }
        }
    }

Поскольку у меня не было C ++ вручную, я сделал выбор времени в C #. Это вычисляет уникальные комбинации 1221 для resultToReach==2000000 примерно 4,5 секунды .

ответил Heslacher 9 +04002014-10-09T15:51:46+04:00312014bEurope/MoscowThu, 09 Oct 2014 15:51:46 +0400 2014, 15:51:46
7

Я на самом деле не в порядке с предположением, что ответ на вопрос о hobo решает a*a+b*b+c*c+d*d = 200 итеративным способом.

Я думаю, что это квадратный корень и круглый вопрос, который можно решить с помощью жадного алгоритма.

Парень с наивысшей нагрузкой может сделать максимум sqrt(200) = 14,142 часа за 14,142 дня. Закругленное, это будет 14 * 14 = 196, оставляя только 4 часа работы для другого 3. Это не работает.

Попробуйте 13 ... 200- (13 * 13) = 31 для остальных 3, а затем рекурсивно проверьте следующего парня, который дает следующий код:

int find_worst_hours( int workleft, int numguys )
{
    static int num_interations = 0;
    int mine = (int)floor(sqrt((double)workleft));
    TRACE( "Num iterations = %d\n", ++num_interations );
    while( mine > 0 )   {
        int leftover = workleft - mine*mine;
        TRACE( "Guys Left %d:I would do %d, rest would do %d\n", numguys, mine, leftover );
        if ( numguys == 1 ) {
            // last guy
            if ( leftover > 0 ) {
                return -1;      // bad solution, work left over.
            } else {
                // no work left, this is a good solution.
                TRACE( "GOOD END, guy %d, work %d\n", numguys, mine );
                return mine;
            }
        } else {
            // check the rest of guys
            if ( leftover == 0 )    {
                return -1;      // bad solution, the other guys need work
            }
            int next_guys_work = find_worst_hours( leftover, numguys-1 );
            if ( next_guys_work > 0 )   {
                // valid solution
                TRACE( "GOOD PARTIAL, guy %d, work %d\n", numguys, mine );
                return mine;
            } else {
                // couldn't find a solution... try less hours
                mine--;
                // continue while loop
            }
        }

    }
    return -1;      // couldn't find solution
}

Кого вы можете вызвать один раз с помощью:

find_worst_hours( 200, 4 );

И он должен выводиться:

 Num iterations = 1
Guys Left 4:I would do 14, rest would do 4
Num iterations = 2
Guys Left 3:I would do 2, rest would do 0
Guys Left 4:I would do 13, rest would do 31
Num iterations = 3
Guys Left 3:I would do 5, rest would do 6
Num iterations = 4
Guys Left 2:I would do 2, rest would do 2
Num iterations = 5
Guys Left 1:I would do 1, rest would do 1
Guys Left 2:I would do 1, rest would do 5
Num iterations = 6
Guys Left 1:I would do 2, rest would do 1
Guys Left 3:I would do 4, rest would do 15
Num iterations = 7
Guys Left 2:I would do 3, rest would do 6
Num iterations = 8
Guys Left 1:I would do 2, rest would do 2
Guys Left 2:I would do 2, rest would do 11
Num iterations = 9
Guys Left 1:I would do 3, rest would do 2
Guys Left 2:I would do 1, rest would do 14
Num iterations = 10
Guys Left 1:I would do 3, rest would do 5
Guys Left 3:I would do 3, rest would do 22
Num iterations = 11
Guys Left 2:I would do 4, rest would do 6
Num iterations = 12
Guys Left 1:I would do 2, rest would do 2
Guys Left 2:I would do 3, rest would do 13
Num iterations = 13
Guys Left 1:I would do 3, rest would do 4
Guys Left 2:I would do 2, rest would do 18
Num iterations = 14
Guys Left 1:I would do 4, rest would do 2
Guys Left 2:I would do 1, rest would do 21
Num iterations = 15
Guys Left 1:I would do 4, rest would do 5
Guys Left 3:I would do 2, rest would do 27
Num iterations = 16
Guys Left 2:I would do 5, rest would do 2
Num iterations = 17
Guys Left 1:I would do 1, rest would do 1
Guys Left 2:I would do 4, rest would do 11
Num iterations = 18
Guys Left 1:I would do 3, rest would do 2
Guys Left 2:I would do 3, rest would do 18
Num iterations = 19
Guys Left 1:I would do 4, rest would do 2
Guys Left 2:I would do 2, rest would do 23
Num iterations = 20
Guys Left 1:I would do 4, rest would do 7
Guys Left 2:I would do 1, rest would do 26
Num iterations = 21
Guys Left 1:I would do 5, rest would do 1
Guys Left 3:I would do 1, rest would do 30
Num iterations = 22
Guys Left 2:I would do 5, rest would do 5
Num iterations = 23
Guys Left 1:I would do 2, rest would do 1
Guys Left 2:I would do 4, rest would do 14
Num iterations = 24
Guys Left 1:I would do 3, rest would do 5
Guys Left 2:I would do 3, rest would do 21
Num iterations = 25
Guys Left 1:I would do 4, rest would do 5
Guys Left 2:I would do 2, rest would do 26
Num iterations = 26
Guys Left 1:I would do 5, rest would do 1
Guys Left 2:I would do 1, rest would do 29
Num iterations = 27
Guys Left 1:I would do 5, rest would do 4
Guys Left 4:I would do 12, rest would do 56
Num iterations = 28
Guys Left 3:I would do 7, rest would do 7
Num iterations = 29
Guys Left 2:I would do 2, rest would do 3
Num iterations = 30
Guys Left 1:I would do 1, rest would do 2
Guys Left 2:I would do 1, rest would do 6
Num iterations = 31
Guys Left 1:I would do 2, rest would do 2
Guys Left 3:I would do 6, rest would do 20
Num iterations = 32
Guys Left 2:I would do 4, rest would do 4
Num iterations = 33
Guys Left 1:I would do 2, rest would do 0
GOOD END, guy 1, work 2
GOOD PARTIAL, guy 2, work 4
GOOD PARTIAL, guy 3, work 6
GOOD PARTIAL, guy 4, work 12

Итак, потребовалось всего 33 итерации, и мы нашли ответ 2,4,6,12. Это должно быть ОЧЕНЬ быстро вычисляться.

ответил Novicaine 9 +04002014-10-09T18:42:42+04:00312014bEurope/MoscowThu, 09 Oct 2014 18:42:42 +0400 2014, 18:42:42

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132