ВНИМАНИЕ: Конкурс для начинающих!!!

AndreyD
Offline
Зарегистрирован: 07.10.2018

ua6em пишет:

у ключа есть ещё и тело, к примеру с одной стороны на 112 а с другой 7 )))

Ну я же перебираю комбинацию ключей, а не размеров.

kolyn
Offline
Зарегистрирован: 18.01.2019

Если порядок вывода будет нарушен по сравнению с исходным массивом, надеюсь, это не будет ошибкой? Например так:

Ключи
2. 10-12: 514 руб. 55 коп.
6. 13-15: 628 руб. 45 коп.
7. 14-17: 702 руб. 76 коп.
9. 16-18: 819 руб. 89 коп.
12. 19-22: 1108 руб. 26 коп.
14. 6-8: 382 руб. 8 коп.
15. 9-11: 495 руб. 97 коп.
16. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 319 миллисекунд

 

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

AndreyD пишет:

ua6em пишет:

у ключа есть ещё и тело, к примеру с одной стороны на 112 а с другой 7 )))

Ну я же перебираю комбинацию ключей, а не размеров.

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

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

Та ладно, клиника это когда механик не умеет закручивать/откручивать гайки; электронщик паять; а программист программировать, врач лечить и так далее.

AndreyD
Offline
Зарегистрирован: 07.10.2018

Ну я всё-таки за идею перебора сочетаний ключей без повторений с последующей проверкой на наличие всех размеров и сравнению стоимости полученных наборов.

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

От перебора так или иначе никуда не деться. Самый интересный вопрос - отсечение бесперспективных вариантов. Т.е. сокращение объема перебора.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

andriano пишет:

Самый интересный вопрос - отсечение бесперспективных вариантов. Т.е. сокращение объема перебора.

Дополню для желающих погуглить такие приёмы: это называется "метод ветвей и границ".

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

Первый фундаментальный вопрос как обозначать наборы и желательно в цифрах, так как все же МК считает в цифрах. Допустим в условии даны 3 гаечных ключа. Сколько наборов из их можно собрать. Правильно 8 наборов. От набора когда ключей нет 000 , до того когда состоят из трех ключей 111. Думаю вам будет понятно. что позиция это номер ключа в задании а 1-испльзуется/0 -нет.  Дальше создается тип данных набор, стоимость набора, на сколько гаек он применим. И две функции определение стоимости по набору и определение количества гаек по набору.  Ну а дальше уже проявляйте навыки эффективного программирования.

ПС: Так как в условии дано 17 ключей, то на описания набора хватит 3-х байтов. всего вариантов набора будет 2^17=131072 включая когда все ключи в наборе отсутсвуют. Так что достаточно их перебрать сохранив тот вариант когда при большем количестве гаек будет меньшая цена.

AndreyD
Offline
Зарегистрирован: 07.10.2018

Методом полного перебора.

Ключи
1. 6-8: 382 руб. 8 коп.
4. 9-11: 495 руб. 97 коп.
5. 10-12: 514 руб. 55 коп.
8. 13-15: 628 руб. 45 коп.
10. 14-17: 702 руб. 76 коп.
12. 16-18: 819 руб. 89 коп.
15. 19-22: 1108 руб. 26 коп.
17. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 38582 миллисекунд

Буду думать как ускорить.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

AndreyD пишет:

Буду думать как ускорить.

Начните с #57

kolyn
Offline
Зарегистрирован: 18.01.2019

kolyn пишет:

Если порядок вывода будет нарушен по сравнению с исходным массивом, надеюсь, это не будет ошибкой? Например так:

Ключи
2. 10-12: 514 руб. 55 коп.
6. 13-15: 628 руб. 45 коп.
7. 14-17: 702 руб. 76 коп.
9. 16-18: 819 руб. 89 коп.
12. 19-22: 1108 руб. 26 коп.
14. 6-8: 382 руб. 8 коп.
15. 9-11: 495 руб. 97 коп.
16. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 319 миллисекунд

 

Евгений Петрович, повторю вопрос. Если порядок вывода не принципиален, готов выложить свою версию.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

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

kolyn
Offline
Зарегистрирован: 18.01.2019

//
//  Тип данных для хранения ключа
//
struct Spanner : public Printable {
  uint32_t price;// цена в копейках
  uint8_t size1;  // размер 1
  uint8_t size2;  // размер 2
  uint8_t included; // если 1, то включается в результирующий набор,0 - возможно будет включен,10 - исключен из перебора

  //ЗДЕСЬ НЕ ТАК,КАК У ВАС. included если 1 (оn), то включается в результирующий набор,0 (off) - возможно будет включен,10 (excluded) - исключен из перебора

  Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const uint8_t ini = 0)
    :  price(p), size1(s1), size2(s2), included(ini) {}

  size_t printTo(Print & p) const {
    size_t res = p.print(size1);
    res += p.print('-');
    res += p.print(size2);
    res += p.print(": ");
    res += printPrice(p, price);
    return res;
  }

  static size_t printPrice(Print & p, const uint32_t priceCop) {
    size_t res = p.print(priceCop / 100);
    res += p.print(" руб. ");
    res += p.print(priceCop % 100);
    res += p.print(" коп.");
    return res;
  }
};



//
//  Массив всех ключей
//
static Spanner spanners[] = {
  {6, 8 , 38208},
  //{22, 24, 145560},
  {8, 9 , 41520},
  {8, 10, 43054},
  {9, 11, 49597},
  {14, 15, 61714},
  //{13, 12 , 30000},
 // {15, 17, 31000},
  {14, 17, 70276},
  {16, 17, 76496},
  {16, 18, 81989},
  {17, 19, 82312},
  {10, 12, 51455},
  {12, 13, 56544},
  {12, 14, 57675},
  {13, 15, 62845},
  {18, 19, 82877},
  {19, 22, 110826},
  {22, 24, 161570},
  {24, 27, 171570}

  /*{6, 8 , 38208},
    {9, 11, 49597},
    {8, 9 , 41520},
    {6, 8 , 39208},
    {24, 27, 171570},
    {8, 24, 1570},
    {24, 27, 201570}*/

};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);
const uint8_t on = 1, off = 0, excluded = 10;// если 1, то включается в результирующий набор,0 - возможно будет включен,10 - исключен из перебора

//
//  Эта функция вычисляет оптимальный набор ключей
//  и устанваливает поле included в on для ключей,
//  которые попадают в решение, и off или excluded для ключей,
//  которые не попадают в решение.
//
void doCalculations(void) {
  spanSort(spanners);              //отсортировали
  uint8_t quantityOff;            //ввели переменную кол-ва ключей, которые могут быть включены "off" в набор
  uint8_t quantityOn;            //ввели переменную кол-ва ключей, которые могут быть включены "off" в набор
  uint8_t quantitySize = totalSize();//кол-во уникальных размеров и заодно удалили (excluded) дубли
  uint8_t minQuantSpann;            //ввели переменную миним. кол-во ключей, из которых может состоять набор
  if (quantitySize % 2 == 0)
    minQuantSpann = quantitySize / 2;
  else minQuantSpann = quantitySize / 2 + 1; //Вычислили мин. возможное кол-во ключей
  //Serial.println(minQuantSpann);
  quantityOn = unique();                        //включили уникальные 6*8; 9*11; 24*27.
  exclud();                        //Тут исключать 8*9
  quantityOff = offSpanners();     //
  if (quantityOff == 0)return;
  sortOff(spanners); //Сортировка невклученных офф вперед
  //перебор вариантов.Почти все, что выше исключительно для умеьшения возм. сочетаний и времени.
  bruteForce(minQuantSpann, quantityOff, quantityOn, quantitySize);
}

//
//  Функция печатает результирующий
//  набор ключей и его стоимость
//
void printResults(void) {
  Serial.println("Ключи");
  uint32_t total = 0;
  for (uint8_t i = 0; i < totalSpanners; i++) {
    if (spanners[i].included == on) {
      Serial.print(i + 1);
      Serial.print(". ");
      Serial.println(spanners[i]);
      total += spanners[i].price;
    }
  }
  Serial.print("Стоимость набора: ");
  Spanner::printPrice(Serial, total);
  Serial.println();
}
//--------------------------------------------------


//
// Функция пнребора вариантов сочетаний ключей
//
void  bruteForce(uint8_t minQ, uint8_t qOff, uint8_t qOn, uint8_t qSize)
{
  uint8_t tempArr[qOff];
  uint32_t tempTotal = 0;
  //тут цикл, и не забывать про дин массивы память освобождать ретюрн выход из цикла
  for ( minQ; minQ <= qOff; minQ++)
  {                                                             //Serial.print(minQ);  Serial.print(' ');
    bool flagComplect = false;
    uint8_t *currArr;
    currArr = new uint8_t[minQ - qOn];
    uint32_t currTotal = 0;

    for (uint8_t i = 0; i < minQ - qOn; i++)                     //первое сочетание ключей
      currArr[i] = i + 1;
    for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
      spanners[currArr[i] - 1].included = on;
    if ( totalSizeOn(qOff, qOn, qSize) == true)                  //если собрался правильный набор набор
    {
      for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
      {
        if (spanners[i].included == on)
          currTotal += spanners[i].price;
      }
      if ( currTotal <= tempTotal || tempTotal == 0  )            //если цена  меньше записанной или это первый набор
      {
        tempTotal = currTotal;                                    //записываем цену
        for (uint8_t i = 0; i < qOff; i++)                        //темп аррей делаем пустым
          tempArr[i] = 0;
        for (uint8_t i = 0; i < minQ - qOn; i++)
        {
          tempArr[currArr[i] - 1] = 1;                            //записываем в темп аррей
          //Serial.print(currArr[i]);  Serial.print(' ');
        }
        flagComplect = true;                                      //поднимаем флаг "собран комплект"

      }
    }
    for (uint8_t i = 0; i < minQ - qOn; i++)                      //сбросили ключи в "off"
      spanners[currArr[i] - 1].included = off;

    while (NextSet(currArr, qOff, minQ - qOn))                     //новое сочетание ключей
    {

      for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
      {
        spanners[currArr[i] - 1].included = on;
      }
      if ( totalSizeOn(qOff, qOn, qSize))                          //если собрался правильный набор набор
      {
        for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
        {
          if (spanners[i].included == on)
            currTotal += spanners[i].price;
        }
        if ( currTotal <= tempTotal || tempTotal == 0  )            //если цена  меньше записанной или это первый набор
        {
          tempTotal = currTotal;                                   //записываем цену
          for (uint8_t i = 0; i < qOff; i++)                       //темп аррей делаем пустым
            tempArr[i] = 0;
          for (uint8_t i = 0; i < minQ - qOn; i++)
          {
            tempArr[currArr[i] - 1] = 1;                           //записываем в темп аррей
            //Serial.print(currArr[i]);  Serial.print(' ');
          }
          flagComplect = true;                                     //поднимаем флаг "собран комплект"
        }
      }

      for (uint8_t i = 0; i < minQ - qOn; i++)                     //сбросили ключи в "off"
        spanners[currArr[i] - 1].included = off;
      if ( flagComplect == true )                                  // Если комплект собрался
        break;                                                     //выходим из переборa (четное кол - во ключей - без вриантов;
                                                                   // нечетное - первым нйдет дешевый.
    }

    delete[] currArr;                                              // динамич. массив удаляем

    if (flagComplect == false)
    {
      for (uint8_t i = 0; i < qOff; i++)                           //если в иттерации не нашли комплект дешевле выходим
        spanners[i].included = tempArr[i];
      break;
    }

    if ( qOff == minQ )                                            //Последняя иттер.
    {
      for (uint8_t i = 0; i < qOff; i++)
        spanners[i].included = tempArr[i];
    }

  }
}
//-------------------------------------------------



//Функция вычисляет  количество существующих размеров среди включенных "On"ключей и сравнивает с зна
bool totalSizeOn(uint8_t qOff, uint8_t qOn, uint8_t qSize)
{
  uint8_t inSize = 0;
  for (uint8_t i = 0; i < qOn + qOff; i++)
  { bool flag1 = false;
    bool flag2 = false;
    if (spanners[i].included == on)

    {
      for (int k = i - 1; k >= 0; k--)
      { if (spanners[k].included != on)
        {
          continue;
        }
        if (spanners[i].size1 == spanners[k].size1 ||
            spanners[i].size1 == spanners[k].size2)
        {
          flag1 = true;
        }
        if (spanners[i].size2 == spanners[k].size1 ||
            spanners[i].size2 == spanners[k].size2)
        {
          flag2 = true;
        }
      }
      if (flag1 == false) inSize++;
      if (flag2 == false) inSize++;
    }
  }

  if (inSize != qSize)
    return false;
  else return true;
}
//---------------------------------------------------------



//
//Функция всех сочетаний для чисел 1…n по m.
//Честно содрана на <a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a>
//
bool NextSet(uint8_t *a, uint8_t  n, uint8_t  m)
{
  uint8_t k = m;
  for (int i = k - 1; i >= 0; --i)
    if (a[i] < n - k + i + 1)
    {
      ++a[i];
      for (uint8_t j = i + 1; j < k; ++j)
        a[j] = a[j - 1] + 1;
      return true;
    }
  return false;
}
//-----------------------------------------------------

//
//Функция подсчета невключенных(off)ключей
//
uint8_t offSpanners()
{
  uint8_t j = 0;
  for (uint8_t i = 0; i < (totalSpanners ); i++)
  {
    if (spanners[i].included == off)
      j++;
  }
  return j;
}
//----------------------------------------

//
// функция сортировки ключей по "off"; ключи со значением included == off станут первыми
//
void sortOff(Spanner * spanarray)
{
  Spanner tmp[] = {};
  for (uint8_t i = 0; i < (totalSpanners ); i++)
  {
    for (int j = 0; j < totalSpanners - 1; j++)
    {
      if ((spanarray[j].included) > (spanarray[j + 1].included))
      {
        tmp[0] = spanarray[j];
        spanarray[j] = spanarray[j + 1];
        spanarray[j + 1] = tmp[0];
      }
    }
  }
}
//------------------------------------------------------

//
//Функция исключает из анализа (excluded) ключи, размеры которых дублируют обязательно включенные функцией unique()
//
//
void exclud()
{
  uint8_t inSp = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on) inSp++;
  }
  inSp = inSp * 2;
  uint8_t *arrayTemp = new uint8_t[inSp];
  uint8_t j = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on)
    {
      arrayTemp[j] = spanners[i].size1;
      j++;
      arrayTemp[j] = spanners[i].size2;
      j++;
    }
  }
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    bool flag1 = false;
    bool flag2 = false;
    if (spanners[i].included == off)
    {
      for (uint8_t k = 0; k < j; k++)
      {
        if (spanners[i].size1 == arrayTemp[k] )
        {
          flag1 = true;
        }
        if (spanners[i].size2 == arrayTemp[k])
        {
          flag2 = true;
        }
      }

    }
    if (flag1 == true && flag2 == true )
    {
      spanners[i].included = excluded;
    }
  }
  delete[] arrayTemp;
}
//-----------------------------------------------------------

//
// Функция определяет неповторяющиеся размеры и ключи, которым они принадлежат, "делаем" "on"
//
uint8_t unique()
{
  uint8_t uniqueSpanner = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    bool flag1 = false;
    bool flag2 = false;
    for (uint8_t k = 0; k < totalSpanners; k++)
    {
      if (i == k) continue;                              //сам на себя
      if (spanners[k].included == excluded) continue;     //на удаленный
      if (spanners[i].size1 == spanners[k].size1 ||
          spanners[i].size1 == spanners[k].size2)
      {
        flag1 = true;
      }
      if (spanners[i].size2 == spanners[k].size1 ||
          spanners[i].size2 == spanners[k].size2)
      {
        flag2 = true;
      }
    }
    if (flag1 == false || flag2 == false)
    {
      spanners[i].included = on;
      uniqueSpanner++;
    }
  }
  return uniqueSpanner;
}
//------------------------------------------

//
//Функция вычисляет общее количество существующих размеров и удаляет (excluded) дубли ключей
uint8_t totalSize()
{
  uint8_t inSize = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    bool flag1 = false;
    bool flag2 = false;
    for (int k = i - 1; k >= 0; k--)
    {
      if (spanners[i].size1 == spanners[k].size1 ||
          spanners[i].size1 == spanners[k].size2)
      {
        flag1 = true;
      }
      if (spanners[i].size2 == spanners[k].size1 ||
          spanners[i].size2 == spanners[k].size2)
      {
        flag2 = true;
      }
      if ((spanners[i].size1 == spanners[k].size1 ||
           spanners[i].size1 == spanners[k].size2) &&
          (spanners[i].size2 == spanners[k].size1 ||
           spanners[i].size2 == spanners[k].size2))

      {
        spanners[i].included = excluded;
      }
    }
    if (flag1 == false) inSize++;
    if (flag2 == false) inSize++;
  }
  return inSize;
}
//-------------------------------------------------------

//
// функция сортировки ключей от дешевых к дорогим
//
void spanSort(Spanner * spanarray)
{
  Spanner tmp[] = {};
  for (uint8_t i = 0; i < (totalSpanners ); i++)
  {
    for (int j = 0; j < totalSpanners - 1; j++)
    {
      if ((spanarray[j].price) > (spanarray[j + 1].price))
      {
        tmp[0] = spanarray[j];
        spanarray[j] = spanarray[j + 1];
        spanarray[j + 1] = tmp[0];
      }
    }
  }
}
//------------------------------------------------------
void setup(void) {
  Serial.begin(9600);
  const uint32_t start = millis();
  doCalculations();
  //uint8_t nota;
  //nota = totalSize();
  //Serial.print("notUnique "); Serial.print(nota); Serial.print('\n');
  const uint32_t duration = millis() - start;
  printResults();
  Serial.print("Время расчёта: ");
  Serial.print(duration);
  Serial.println(" миллисекунд");
}

void loop(void) {}

Стиль "Ма-ма мы-ла ра- му". Ну как умею.

P.S. Код изменил. 1-й раз залил неверную версию.

 

b707
Offline
Зарегистрирован: 26.05.2017

kolyn пишет:

Стиль "Ма-ма мы-ла ра- му". Ну как умею.

P.S. Код изменил. 1-й раз залил неверную версию.

 

Набор и время еще укажите

kolyn
Offline
Зарегистрирован: 18.01.2019

Исходный набор:

    {6, 8 , 38208},
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 49597},
    {10, 12, 51455},
    {12, 13, 56544},
    {12, 14, 57675},
    {13, 15, 62845},
    {14, 15, 61714},
    {14, 17, 70276},
    {16, 17, 76496},
    {16, 18, 81989},
    {17, 19, 82312},
    {18, 19, 82877},
    {19, 22, 110826},
    {22, 24, 145560},
    {24, 27, 171570}

Ключи
2. 10-12: 514 руб. 55 коп.
6. 13-15: 628 руб. 45 коп.
7. 14-17: 702 руб. 76 коп.
9. 16-18: 819 руб. 89 коп.
12. 19-22: 1108 руб. 26 коп.
14. 6-8: 382 руб. 8 коп.
15. 9-11: 495 руб. 97 коп.
16. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 430 миллисекунд

Тот же набор, но ключ 13*15 можно заменить двумя дешевыми 13*12 и 15*17:

  {6, 8 , 38208},
  {8, 9 , 41520},
  {8, 10, 43054},
  {9, 11, 49597},
  {14, 15, 61714},
  {13, 12 , 30000},
  {15, 17, 31000},
  {14, 17, 70276},
  {16, 17, 76496},
  {16, 18, 81989},
  {17, 19, 82312},
  {10, 12, 51455},
  {12, 13, 56544},
  {12, 14, 57675},
  {13, 15, 62845},
  {18, 19, 82877},
  {19, 22, 110826},
  {22, 24, 161570},
  {24, 27, 171570}

Ключи
1. 13-12: 300 руб. 0 коп.
2. 15-17: 310 руб. 0 коп.
3. 8-10: 430 руб. 54 коп.
5. 12-14: 576 руб. 75 коп.
10. 16-18: 819 руб. 89 коп.
13. 19-22: 1108 руб. 26 коп.
15. 6-8: 382 руб. 8 коп.
16. 9-11: 495 руб. 97 коп.
17. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6139 руб. 19 коп.
Время расчёта: 1015 миллисекунд

И еще один странный набор ключей с уникальными размерами и  более дорогими дубликатами:

    {6, 8 , 38208},
    {9, 11, 49597},
    {8, 9 , 41520},
    {6, 8 , 49200},
    {14, 15, 61714},
    {24, 27, 171570},
    {8, 24, 1570},
    {24, 27, 201570}

Ключи
2. 6-8: 382 руб. 8 коп.
5. 9-11: 495 руб. 97 коп.
6. 14-15: 617 руб. 14 коп.
7. 24-27: 1715 руб. 70 коп.
Стоимость набора: 3210 руб. 89 коп.
Время расчёта: 0 миллисекунд

 

b707
Offline
Зарегистрирован: 26.05.2017

kolyn - исходный набор ключей, если я понял - дан в условии Конкурса.

Откуда вы другие наборы взяли? Если придумали сами - зачем их публиковать в этой ветке?

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

b707 пишет:

kolyn - исходный набор ключей, если я понял - дан в условии Конкурса.

Нет, там, наоборот, сказано:

ЕвгенийП пишет:
Разумеется, программа не должна зависеть ни от количества ключей (в разумных пределах), ни от цен на них - она должна работать для любого набора. В случае, если размеры ни разу не повторяются, она должна выдать изначальный набор. В случае, если набор состоит из одинаковых ключей, она должна выдать поднабор из одного ключа (самого дешёвого). Ну, и так далее.

kolyn
Offline
Зарегистрирован: 18.01.2019

b707 пишет:

kolyn - исходный набор ключей, если я понял - дан в условии Конкурса.

Откуда вы другие наборы взяли? Если придумали сами - зачем их публиковать в этой ветке?

Если бы Вы конкретнее изложили свою просьбу, а именно показать результат выполнения программы с набором ключей, заданных в условиях конкурса, я бы так и сделал;)

b707
Offline
Зарегистрирован: 26.05.2017

ЕвгенийП пишет:

Нет, там, наоборот, сказано:

ЕвгенийП пишет:
Разумеется, программа не должна зависеть ни от количества ключей (в разумных пределах), ни от цен на них - она должна работать для любого набора. В случае, если размеры ни разу не повторяются, она должна выдать изначальный набор. В случае, если набор состоит из одинаковых ключей, она должна выдать поднабор из одного ключа (самого дешёвого). Ну, и так далее.

прошу прощения, значит недочитал :)

Тем не менее, для упрощения сравнения эффективности решений участников, лучше указывать время разбора одного единственного набора - приведенного в условиях

kolyn
Offline
Зарегистрирован: 18.01.2019

b707 пишет:

прошу прощения, значит недочитал :)

b707 пишет:

ошибаетесь.

С вашей внимательностью вам трудно в программировании придется :)

b707
Offline
Зарегистрирован: 26.05.2017

kolyn пишет:

b707 пишет:

ошибаетесь.

С вашей внимательностью вам трудно в программировании придется :)

Упс, крыть нечем :)

kolyn
Offline
Зарегистрирован: 18.01.2019

kolyn пишет:

Стиль "Ма-ма мы-ла ра- му". Ну как умею.

Евгений Петрович, хотелось бы Вашей реакции. Зачтено? Нет?

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

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

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

b707 пишет:

Тем не менее, для упрощения сравнения эффективности решений участников, лучше указывать время разбора одного единственного набора - приведенного в условиях

Не согласен.

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

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

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

b707
Offline
Зарегистрирован: 26.05.2017

andriano пишет:

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

то что вы описываете - это читерство :) и оно легко видно в исходном коде.

но такое поведение может обьясняться не только "заточкой" программы под конкретные данные. Очевидно, что практически любой набор может быть предварительно упрощен путем отбрасывания очевидных вариантов. Некоторые наборы, например, по мере последовательного упрощения могут решены и чисто аналитически, вообще без перебора. Тогда та программа, алгоритм которой в состоянии разпознать эти закономерности - найдет решение на порядок быстрее, чем та что всегда работает перебором.

Чем больше подобных правил реализовано в программе, тем меньше остается вариантов для перебора и быстрее работает алгоритм в целом. При этом вполне может сложится ситуация, что на одних наборах программа обгоняет всех, а на других отстает... и при этом никакого "читерства" нет.

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

 ИМХО, без какого-то тестового набора или нескольких наборов нет четкого критерия первенства.

kolyn
Offline
Зарегистрирован: 18.01.2019

b707 пишет:

 ИМХО, без какого-то тестового набора или нескольких наборов нет четкого критерия первенства.

Например, среднее от Время/Ключ для N различных тестовых наборов.

Но это решать не мне;)

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

b707 пишет:

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

Согласаен.

Цитата:

 ИМХО, без какого-то тестового набора или нескольких наборов нет четкого критерия первенства.

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

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

kolyn пишет:

Например, среднее от Время/Ключ для N различных тестовых наборов.

В математике есть три разных вида среднего. Не говоря даже о медиане, которая также претендует на это звание.

И, если Время/Ключ - это формула, то вряд ли она имеет верную размерность. Объем перебора - отнюдь не линейная функция от числа ключей.

kolyn
Offline
Зарегистрирован: 18.01.2019

andriano пишет:

В математике есть три разных вида среднего. 

А Вам какое больше нравится?;)

andriano пишет:

И, если Время/Ключ - это формула, то вряд ли она имеет верную размерность.

Да. Это формула. И она имеет правильную размерность. мс / шт = мс.

AndreyD
Offline
Зарегистрирован: 07.10.2018

Главное не победа, а участие. :)

В своих ранее сделанных поделках я структуры и указатели не использовал. Плохо в них разбираюсь.

И максимальное "разумное" количество ключей для этого кода равно 64.

Результат для набора из задания:

Ключи
2. 19-22: 1108 руб. 26 коп.
5. 16-18: 819 руб. 89 коп.
7. 14-17: 702 руб. 76 коп.
8. 13-15: 628 руб. 45 коп.
12. 10-12: 514 руб. 55 коп.
15. 6-8: 382 руб. 8 коп.
16. 9-11: 495 руб. 97 коп.
17. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 3529 миллисекунд

Код:

struct Spanner : public Printable {
  uint32_t price;// цена в копейках
  uint8_t size1;  // размер 1
  uint8_t size2;  // размер 2

  Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p) 
    :  price(p), size1(s1), size2(s2) {}
  
  size_t printTo(Print & p) const {
    size_t res = p.print(size1);
    res += p.print('-');
    res += p.print(size2);
    res += p.print(": ");
    res += printPrice(p, price);
    return res;
  }
  
  static size_t printPrice(Print & p, const uint32_t priceCop) {
    size_t res = p.print(priceCop / 100);
    res += p.print(" руб. ");
    res += p.print(priceCop % 100);
    res += p.print(" коп.");
    return res;
  }
};

//  Массив всех ключей
static Spanner spanners[] = {
    {6, 8 , 38208},
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 49597},
    {10, 12, 51455},
    {12, 13, 56544},
    {12, 14, 57675},
    {13, 15, 62845},
    {14, 15, 61714},
    {14, 17, 70276},
    {16, 17, 76496},
    {16, 18, 81989},
    {17, 19, 82312},
    {18, 19, 82877},
    {19, 22, 110826},
    {22, 24, 145560},
    {24, 27, 171570}
    
    
};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);

bool flag1=0, flag2=0, uSpanners[64];
uint8_t allSizes=0, n=0, sizes[128], cSizes[128], elem=0, noKeys=0, unique = 0; 
uint32_t rezTotal = 0, total0 = 0, total = 0;
uint64_t collection=0, rezCollection=0, p0, p=1;

// Функция которая выполняется первой и один раз.
void first(void) {
    memset(sizes, 0, sizeof(sizes[0])*128); // Обнуление массива размеров.
    memset(cSizes, 0, sizeof(cSizes[0])*128); // Обнуление массива кол-ва одинаковых размеров.
    memset(uSpanners, 1, sizeof(uSpanners[0])*64); // Установка единиц в массиве для вычисления ключей, которые полюбому попадают в набор.
    
    // Поиск всех размеров ключей и кол-ва каждого размера
    for (uint8_t i=0; i < totalSpanners; i++) {
      for (uint8_t j=0; j < allSizes; j++) {
        if (sizes[j] == spanners[i].size1) {flag1=1; cSizes[j]++;}
        if (sizes[j] == spanners[i].size2) {flag2=1; cSizes[j]++;}
      }
        if (!flag1) {sizes[allSizes] = spanners[i].size1; allSizes++;} else flag1=0; 
        if (!flag2) {sizes[allSizes] = spanners[i].size2; allSizes++;} else flag2=0;
    }
    n = round(((float)allSizes/2)); // половина всех размеров, для рассчёта границы по кол-ву ключей в наборе
    
    // Выявление ключей, которые полюбому будут в наборе (ключи у которых хотя бы один размер не повторяется с другими ключами), и вычисление их кол-ва.
    for (uint8_t j=0; j < allSizes; j++) 
      if (cSizes[j] == 0) {
        unique++;
        for (uint8_t i = 0; i < totalSpanners; i++) {
          if (spanners[i].size1 == sizes[j]) uSpanners[i] = 0;
          if (spanners[i].size2 == sizes[j]) uSpanners[i] = 0;
        }
    }

    // Сортировка массива структур, ключи, которые полюбому будут в наборе, перемещаются в конец массива
    Spanner tmp[] = {}; uint8_t temp = 0;
    for (uint8_t i = 0; i < totalSpanners; i++)
      for (uint8_t j = 0; j < totalSpanners - i - 1; j++)
      if ((uSpanners[j]) < (uSpanners[j + 1])) {
        temp = uSpanners[j];
        uSpanners[j] = uSpanners[j + 1];
        uSpanners[j + 1] = temp;
        tmp[0] = spanners[j];
        spanners[j] = spanners[j + 1];
        spanners[j + 1] = tmp[0];
      }
    
    // Сортировка массива структур по цене (от максимальной к минимальной) без ключей, которые полюбому будут в наборе.
    for (uint8_t i = 0; i < totalSpanners - unique; i++)
      for (uint8_t j = 0; j < totalSpanners - i - 1 - unique; j++)
      if ((spanners[j].price) < (spanners[j+1].price)) {
        tmp[0] = spanners[j];
        spanners[j] = spanners[j + 1];
        spanners[j + 1] = tmp[0];
      }    
}

// Функция отсечения неперспективных коомбинаций
bool calc(void) {
   flag1=0; flag2=0;  total=0; elem=0; p=1; noKeys=0;
    for (uint8_t i=0; i < totalSpanners; i++,p=p*2) {
       if (!bool((collection) & (p))){
        for (uint8_t j=0; j < elem; j++) {          
          if (sizes[j] == spanners[i].size1) flag1=1;
          if (sizes[j] == spanners[i].size2) flag2=1;
        }
        if (!flag1) {sizes[elem] = spanners[i].size1; elem++;} flag1=0; 
        if (!flag2) {sizes[elem] = spanners[i].size2; elem++;} flag2=0;      
        total = total + spanners[i].price; 
       } else {
        noKeys++;
        if (noKeys > totalSpanners - n) return 0; // Граница по кол-ву ключей в коомбинации
      }
      if ((total > rezTotal) && (rezTotal != 0)) return 0; // Граница по сумме цен ключей
   }
   if (elem != allSizes) return 0; // Отсечение коомбинаций в которых нет всех размеров
   return 1; 
}

void doCalculations(void) {
   // Вычисление верхней границы перебора.
   for (uint8_t i =0; i < totalSpanners-unique;i++) collection |= (1LL<<i);
   // Основной цикл перебора
   do{  
     collection--;
     if (calc()) if ((total < rezTotal) || (rezTotal == 0)) {rezTotal = total; rezCollection=collection;}
  }while (collection>1); 
}

void printResults(void) {
  Serial.println("Ключи");
  uint32_t total = 0; uint64_t r=1;
  for (uint8_t i = 0; i < totalSpanners; i++,r=2*r) {
    if (!bool((rezCollection) & (r))) {
      Serial.print(i + 1);
      Serial.print(". ");
      Serial.println(spanners[i]);
      total += spanners[i].price;
    }
  }
  Serial.print("Стоимость набора: ");
  Spanner::printPrice(Serial, total);
  Serial.println();
}

void setup(void) {
  Serial.begin(9600);
  const uint32_t start = millis();
  if (totalSpanners > 64) {Serial.println("Колличество ключей больше 64."); return;}
  first();
  doCalculations();
  const uint32_t duration = millis() - start;
  printResults();
  Serial.print("Время расчёта: ");
  Serial.print(duration);
  Serial.println(" миллисекунд");
}

void loop(void) {}  

 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Класс! Мужики, я так боялся, что не будет желающих!

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

kolyn пишет:

Да. Это формула. И она имеет правильную размерность. мс / шт = мс.

Вот так и знал, что к слову "размерность" будут придирки.

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

kolyn
Offline
Зарегистрирован: 18.01.2019

andriano пишет:

Вот так и знал, что к слову "размерность" будут придирки.

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

Я не могу понять, в чем Вы видите ошибку!

Например в тесте 1  находим А ключей за время Т. Тогда на нахождение одного ключа Тср =  Т / А (мс). Проводим n РАЗЛИЧНЫХ тестов. Находим среднее (арифметическое напр.) : (Тср1 + Тср2 + ...+Тсрn)/n. Что не так?

ПС. Возможно в качестве "А" должно быть не кол-во найденных, а исходных ключей.

 

 

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

ЕвгенийП пишет:

Класс! Мужики, я так боялся, что не будет желающих!

и не зря боялись, пришло другое поколение, сверх рационалистическое

kolyn
Offline
Зарегистрирован: 18.01.2019

ua6em пишет:

и не зря боялись, пришло другое поколение, сверх рационалистическое

" Они торчат под рейв и чем-то пудрят носы

они не такие, как мы." 

Бросьте. Это просто старческое брюзжание. Такие же, а может и лучше. Вспомните себя годков эдак в 25. Что бы вы предпочли - решать некую задачу, которая возможно и пощекочет ваш центр удовольствий в будущем или пойти с друзьями потусить прямо сейчас? Если первое - то у вас просто нет друзей. А те, кто ардуинит лет с 10 и не бросил это занятие, в 25 уж никак не "новичок".

В конкурсе примут участие только те, для кого программирование - хобби, кому не жалко на на это времени, у кого "базовые потребности" уже удовлетворены. Ради кайфа в тот момент, когда оно "заработало!!!".

b707
Offline
Зарегистрирован: 26.05.2017

kolyn пишет:

те, кто ардуинит лет с 10 и не бросил это занятие, в 25 уж никак не "новичок".

кстати да, стоило бы четче сформулировать. для кого этот конкурс.  Потому как задачка, прямо скажем, далеко не для начального уровня. Те "новечки", что приходят сюда спрашивать, "как включить светодиод одним нажатием" - не смогут даже сформулировать подходы к решению, не говоря уж о написании работающего кода.

Поэтому актуален вопрос - кто они, участники этого конкурса? :)

kolyn
Offline
Зарегистрирован: 18.01.2019

b707 пишет:

Поэтому актуален вопрос - кто они, участники этого конкурса? :)

Резюме)))

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

kolyn пишет:

Бросьте. Это просто старческое брюзжание. Такие же, а может и лучше. Вспомните себя годков эдак в 25. Что бы вы предпочли - решать некую задачу, которая возможно и пощекочет ваш центр удовольствий в будущем или пойти с друзьями потусить прямо сейчас? Если первое - то у вас просто нет друзей. А те, кто ардуинит лет с 10 и не бросил это занятие, в 25 уж никак не "новичок".

первое!

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

PS ты попутал с приятелями, в русском это жеж просто - ПРИ Я Тело, разницу чувствуешь )))

kolyn
Offline
Зарегистрирован: 18.01.2019

ua6em пишет:

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

Вы к этому осознанию прям со школьной скамьи пришли? Ну значит Вы мудрый человек! До меня это стало доходить после 30. Да и сейчас часто ошибаюсь в людях.  Но эт уже офтоп.

b707
Offline
Зарегистрирован: 26.05.2017

Ребята, не засоряйте тему

AndreyD
Offline
Зарегистрирован: 07.10.2018

b707 пишет:

Поэтому актуален вопрос - кто они, участники этого конкурса? :)

Профессионально программированием не занимался, только базовые курсы в школе (+факультатив) и в институте.

С ардуиной я начал знакомиться лет пять назад, всё началось с того, что я сделал гирлянду на новый год на конденсаторах и стартерах, но стартеры долго не прожили. Поэтому поставил под гирлянду нанку. Затем увлёкся идеей "Умного дома", у меня частный дом. Сейчас у меня действующая система из 3-х нанок, одной Меги и одного одноплатника с установленным на последнем MajorDoMo. В основном управление освещением, так же есть пара сигнализаций, пара гирлянд, цветной прожектор, датчики движения, температуры, влажности, давления, освещённости.

Поэтому программирование меня интересует как инструмент для этого моего увлечения.

Ну и да, мне ближе к сорока годикам. :)

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kolyn,

попробуйте с вот таким набором данных

static Spanner spanners[] = {
	{1, 8 , 4},
	{2, 8 , 3},
	{4, 6 , 3},
	{12, 15 , 3},
	{2, 6 , 3},
	{4, 8 , 3},
	{6, 10 , 3}
};

У меня получилось

14:22:27.851 -> Ключи
14:22:27.851 -> 5. 12-15: 0 руб. 3 коп.
14:22:27.851 -> 6. 6-10: 0 руб. 3 коп.
14:22:27.851 -> 7. 1-8: 0 руб. 4 коп.
14:22:27.885 -> Стоимость набора: 0 руб. 10 коп.
14:22:27.885 -> Время расчёта: 0 миллисекунд

Здесь явно не хватает размеров 2 и 4.

AndreyD,

попробуйте с вот таким набором данных

static Spanner spanners[] = {
	{1, 2 , 1},
	{3, 4 , 1},
	{5, 6 , 1}
};

У меня получилось бесконечное исполнение. Может, и конечное, но больше 15 минут я уж не стал ждать.

kolyn
Offline
Зарегистрирован: 18.01.2019

ЕвгенийП пишет:

kolyn,

попробуйте с вот таким набором данных

static Spanner spanners[] = {
	{1, 8 , 4},
	{2, 8 , 3},
	{4, 6 , 3},
	{12, 15 , 3},
	{2, 6 , 3},
	{4, 8 , 3},
	{6, 10 , 3}
};

У меня получилось

14:22:27.851 -> Ключи
14:22:27.851 -> 5. 12-15: 0 руб. 3 коп.
14:22:27.851 -> 6. 6-10: 0 руб. 3 коп.
14:22:27.851 -> 7. 1-8: 0 руб. 4 коп.
14:22:27.885 -> Стоимость набора: 0 руб. 10 коп.
14:22:27.885 -> Время расчёта: 0 миллисекунд

Здесь явно не хватает размеров 2 и 4.

 

Упс. Ошибка в логике программы. Она основана на сортировке от дешевых к дорогим,а равенство цен я не учел(

Стоит исправлять или уже все?

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Конечно, стоит.

Про другие ошибки рассказать? Ну, про то, что глаза сразу бросилось?

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

kolyn пишет:

Я не могу понять, в чем Вы видите ошибку!

Например в тесте 1  находим А ключей за время Т. Тогда на нахождение одного ключа Тср =  Т / А (мс). Проводим n РАЗЛИЧНЫХ тестов. Находим среднее (арифметическое напр.) : (Тср1 + Тср2 + ...+Тсрn)/n. Что не так?

Почему Вы решили, что между количеством ключей и временем зависимость линейна?

В этом Вы явно ошибаетесь.

kolyn
Offline
Зарегистрирован: 18.01.2019

ЕвгенийП пишет:

Конечно, стоит.

Про другие ошибки рассказать? Ну, про то, что глаза сразу бросилось?

Конечно!

 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kolyn пишет:
Конечно!

Вы регулярно используете конструкцию

Spanner tmp[] = {};
...
tmp[0] = spanarray[j];

Видимо, Вы считаете, что в строке №1 выделили память и в строке №3 спокойно в неё пишете. Боюсь Вас разочаровать. Напечатайте в сериал sizeof Вашего tmp и посмотрите, сколько там выделилось.

Вы пишете в произвольную память. Если она не под что не распределена, Вам повезло - будет работать, а если она подо что-то выделена, Вы это что-то испортите. Полюбуйтесь, что бывает, когда так пишешь.

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

kolyn
Offline
Зарегистрирован: 18.01.2019

andriano пишет:

Почему Вы решили, что между количеством ключей и временем зависимость линейна?

В этом Вы явно ошибаетесь.

   andriano, разве я упоминал о зависимости времени расчета от количества ключей? Я просто предложил вариант  оценки скорости работы программы. И не утверждал, что он единственно верный. Мне кажется такой формулы не существует в принципе.

Я в свою очередь думаю, что у Вас претензии к  (Тср1 + Тср2 + ...+Тсрn)/n просто к как к абстракной формуле. Вот и беседуем - Вы о круглом, я о красном;)

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

kolyn пишет:

andriano, разве я упоминал о зависимости времени расчета от количества ключей?

Именно. Это утверждение непосредственно следует из предложенной Вами формулы.

Цитата:

Я просто предложил вариант  оценки скорости работы программы. И не утверждал, что он единственно верный. Мне кажется такой формулы не существует в принципе.

А она есть!

Цитата:

Я в свою очередь думаю, что у Вас претензии к  (Тср1 + Тср2 + ...+Тсрn)/n просто к как к абстракной формуле. Вот и беседуем - Вы о круглом, я о красном;)

Видите ли, математика - это не просто набор значков. Каждая строка имеет свой смысл. Вот смысл в приведенной выше формуле есть только в том случае, если зависимость времени и количества линейна. В противном случае эту формулу применять нельзя.

 

PS. Если Вы вправду считаете, что все формулы равнозначны, будете ли Вы считать закон Ома по формуле U=I/R ? Чем она хуже U=I*R ?

Не бывает "абстрактных формул". Каждая из них имеет (либо не имеет) какой-то смысл.

b707
Offline
Зарегистрирован: 26.05.2017

Можно еще попробовать на таком простеньком наборе:

сорри, глюк