Змінюй хід війни! Допомагай ЗСУ!

"А нука, гуру!" второй эпизод

  • Автор теми Автор теми dr_mousefly
  • Дата створення Дата створення
Команда требует так :) Сказали, дебажить проще. Тогда не спорил, а сейчас уже автоматически так пишется.
 
вроде бы суть та же. только у вас, насколько я понял, функция Raise( int ix ) по сути реализует инкремент в двоичной системе счисления (если единице сопоставить true в вашем массиве _data, а нулю - false)? можно немного упростить, если учесть, что в итоге вы переберете все возможные булевские последовательности длины n, то есть, все двоичные числа от 0 до 2^n - 1. а значит, их не нужно как-то специально получать, можно просто брать двоичные представления всех чисел от 0 до 2^n - 1. верну сейчас свое решение, чё уже скрывать ))
 
Да это я сам подумал, спасибо. Просто мне показалось, что считать поднятые биты у двоичного представления числа как-то долго будет. Ну и такой странноватый аргумент, что для двоичного представления упор будет на N=64, а дальше не получится или надо будет что-то придумывать с "очень большим целым числом". Хотя фактически 32 уже выше башни, это миллиард вариантов, и мой атлончик задумчиво хрустит винчестером, не выдавая мне решение в разумное время.

N = 20 - 3 секунды (1.8ГГц процессор). Значит, для N=30 будет уже час, а для N = 64 - 16 миллиардов часов.
 
я же специально написал, что N не более 20.. так что лезет даже в 32-разрядное целое. ;)
и перебирать надо не от нуля до 2^N, а от 3. варианты 0, 1, 2 не имеют смысла по условиям задачи, так как содержат нуль или одно слагаемое. но это мелочи.
 
написал алгоритм, который решает задачу, со сложностью (если не заморачиваться и брать по максимуму) где-то O(n^3). реально гдето O(n^2).
у вас, как я понял, алгоритм как минимум O(2^n), что намного дольше.
выкладывать или подумаете еще?

проверил для 4
и для 9 в промежутках 3-14, 39-45, остальное влом стало проверять
 
Korian, так ведь там в любом случае 2^n - n - 1 комбинаций, и наши алгоритмы просто все эти комбинации распределяют по соответствующим группам с одинаковой суммой. Да, есть лишних n пробегов, но для N = 20 это всего лишь 20 проходов из миллиона, несерьезная избыточность.

Каким же образом Вы считаете возможным при сложности алгоритма пусть даже n^3 сгенерировать миллион комбинаций за счет 8000 действий?

Думать уже некогда, работа, да и сроки выкладывания решений подходят к концу. Но будет очень интересно посмотреть на алгоритм :)
 
Achenar сказав(ла):
Korian, так ведь там в любом случае 2^n - n - 1 комбинаций, и наши алгоритмы просто все эти комбинации распределяют по соответствующим группам с одинаковой суммой. Да, есть лишних n пробегов, но для N = 20 это всего лишь 20 проходов из миллиона, несерьезная избыточность.
Натисніть, щоб розгорнути...

Вот где должен выйти на сцену интеллект Оршански и из экспоненциального брутал форса сделать алгоритм с логарифмической зависимостью . Прошу ведущего добавить ему немного времени на разработку.
 
выкладывайте. мне тоже интересно как у вас получилась O(n^3) когда кол-во результатов 2^n - (n + 1) в любом случае. что-то гениальное должно быть
 
Разбор "полетов"

Комиссия не признала ни один из алгоритмов ,реализующих решение по следующим соображениям :
1. возбуждение вопросов политического характера ,обоснованных схожим условием с первой задачей,выросшими запросами в разы к информационным сетям,наблюдаемых с периода публикации задачи ,подозрительным акцентом по выбору числа Н к раскладываемому числу М в сути его выбора после разрешения и наглядному обману
2.отсутствие математического подхода к составлению алгоритма, кучи которых были известны человечеству до появления ЭВМ
3.анализ результатов дает право утверждать отсутствие некоторых возможных частей (слагаемых)
4.нарушение права Стрензерины ,как участницы ,заявить о некотором сговоре между автором задачи и доном Хеллоу,аргументированном в лишении смысла по времени оптимизировать решение задачи каким либо другим способом.
Ждем алгоритма Корияна.
 
жаль, что комиссия так не предложила свой вариант решения задачи, за что она была расформирована, а все её решения - отменены
 
Тыемураз сказав(ла):
Комиссия не признала ни один из алгоритмов
Натисніть, щоб розгорнути...
рано еще делать выводы, еще часа 2 есть

Код: 
#include <vector>
#include <iostream>
#include <algorithm>

typedef std::vector<unsigned int> UIntVector;
typedef std::vector<UIntVector> UIntVectorVector;
typedef std::vector<UIntVectorVector> UIntVectorVectorVector;

//----------------------------------------------------------------------------------------------------
void FindSummands(const unsigned int number, const unsigned int maxSummand, UIntVectorVectorVector* results)
{
   UIntVectorVector& currentResult = (*results)[number];
   for (unsigned int lastSummand = maxSummand; lastSummand * (lastSummand + 1) / 2 >= number; --lastSummand)
   {
      const unsigned int firstSummand = number - lastSummand;
      const UIntVectorVector& parentResult = (*results)[firstSummand];

      for (UIntVectorVector::const_iterator curResult = parentResult.begin();
         curResult != parentResult.end(); ++curResult)
      {
         if (curResult->back() >= lastSummand)
            continue;

         currentResult.push_back(*curResult);
         currentResult.back().push_back(lastSummand);
      }
   }
}

UIntVectorVectorVector MakeDescision(const unsigned int n)
{
   const unsigned int m = n * (n + 1) / 2;

   UIntVectorVectorVector results(m + 1);
   for (unsigned int i = 0; i != n + 1; ++i)
      results[i].push_back(UIntVector(1, i));

   for (unsigned int i = 3; i <= n; ++i)
      FindSummands(i, i - 1, &results);

   for (unsigned int i = n + 1; i != m + 1; ++i)
      FindSummands(i, n, &results);

   for (unsigned int i = 0; i != n + 1; ++i)
      results[i].erase(results[i].begin());

   return results;
}

//----------------------------------------------------------------------------------------------------
bool CompareVectors(const UIntVector& left, const UIntVector& right)
{
   if (left.size() < right.size())
      return true;
   else if (left.size() > right.size())
      return false;

   for (unsigned int index = 0; index != right.size(); ++index)
   {
      if (left[index] < right[index])
         return true;
      else if (left[index] > right[index])
         return false;
   }
   return false;
}

void PrintVector(const UIntVector& vector)
{
   for (UIntVector::const_iterator number = vector.begin();
      number != vector.end(); ++number)
   {
      std::cout << *number << " ";
   }
   std::cout << std::endl;
}

void PrintResults(UIntVectorVectorVector& results)
{
   for (unsigned int i = 3; i != results.size(); ++i)
   {
      std::cout << "------------------------------------- " << i << std::endl;
      std::sort(results[i].begin(), results[i].end(), CompareVectors);
      std::for_each(results[i].begin(), results[i].end(), PrintVector);
   }
}

//----------------------------------------------------------------------------------------------------
int main(int argc, char* argv[])
{
   unsigned int n = 9;

   PrintResults(MakeDescision(n));
}
 
Останнє редагування:
я не вдавался в подробности вашей реализации, просто взял самый глубокий цикл, который нашел, и изменил вот этот кусок
Код: 
currentResult.push_back(*curResult);
currentResult.back().push_back(lastSummand);
на вот такой
Код: 
currentResult.push_back(*curResult);
currentResult.back().push_back(lastSummand);

counter++;
т.е. счетчик добавил и посчитал, сколько раз это место проходится. для 4 получилось 11, для 9 - 502, что в обоих случаях равно 2^n - (n + 1). я туплю может где-то?
 
HelloWorld, ну где там можно ошибиться, это просто счетчик, который просто насчитал количество проходов. Собственно, суть задачи обойти малореально, поэтому я сразу удивился заявленному n^3.

Да, и было бы неплохо результаты (а вообще отлично - замер времени работы для N=20 и скорость процессора туда же). Результаты, скорее всего, правильные, потому что количество проходов правильное, а вот скорость таки интересует :)
 
HelloWorld, действительно, недооценил я самый вложенный цикл. как-то так получилось, что для меня он был почти константным.

HelloWorld сказав(ла):
я не вдавался в подробности вашей реализации, просто взял самый глубокий цикл, который нашел, и изменил вот этот кусок
Натисніть, щоб розгорнути...
хороший способ проверки, плохо шо я об этом не подумал.
 
Внимательно изучаем код, тренируем мозги методом погадывания написанного(нарушение конституционных прав граждан на самоопределение своего трудового времени ) и ждем результатов.Пока предпосылки хорошие, некак в ранних публикациях "тэбэ половинка-1 и мне половинка +1,а ему куча ".
Страсти разгораются.Желательно исключить возможности свойства Буля -"если не дедушка,то бабушка".
 
насчет скорости..

мое решение для 20 - 2.2 секунды. правда, жрет много памяти. неприлично много..

решение кориана для n=20 - 27 секунд. с отключенным выводом, естественно, и не в дебаггерском режиме. видимо, есть почва для оптимизации. плюсы должны быть быстрее джавы, иначе это подорвет основы мироздания. зато жрет мало памяти..

решение Achenar проверить не смог по причине отсутствия полноценной студии. у меня только бесплатная для плюсов стоит.

процессор 3.0ггц
 
HelloWorld сказав(ла):
насчет скорости..

мое решение для 20 - 2.2 секунды. правда, жрет много памяти. неприлично много..

решение кориана для n=20 - 27 секунд. с отключенным выводом, естественно, и не в дебаггерском режиме. видимо, есть почва для оптимизации. плюсы должны быть быстрее джавы, иначе это подорвет основы мироздания. зато жрет мало памяти..

решение Achenar проверить не смог по причине отсутствия полноценной студии. у меня только бесплатная для плюсов стоит.

процессор 3.0ггц
Натисніть, щоб розгорнути...
для оптимизации графа?
как говорит наш президент: "ввимкны уркаину", скоро почвы для оптимизации станет еще больше :D
 
korian сказав(ла):
странно как-то, там вывод полностью вырезан?
у меня получается 4 секунды.
Core 2 Duo E6550 2.33GHz
Натисніть, щоб розгорнути...

извиняюсь, это я прогнал. думал, что если из студии запустить в режиме Release - это будет то же самое, что экзешник запустить, оказалось нет. в итоге, результат - меньше секунды, всё стало на свои места. Core 2 Duo E8400 3.0GHz

strenzer сказав(ла):
для оптимизации графа?
Натисніть, щоб розгорнути...
для оптимизации процессов. в том числе, мыслительных. но в свете последних событий оказалось, что уже нет такой почвы, она ушла из под ног
 
HelloWorld сказав(ла):
для оптимизации процессов. в том числе, мыслительных. но в свете последних событий оказалось, что уже нет такой почвы, она ушла из под ног
Натисніть, щоб розгорнути...

правильно. чепуха эти мыслительные процессы. оптимизировать надо граф. причем перманентно.
 
Ви повинні увійти або зареєструватися, щоб відповісти.
Назад
Зверху Знизу