В магазине может быть акция, например, ключ 9х12 бесплатно к любому купленному за деньги :) В этом случае, очевидно, покупать такой размер уже не нужно и это обозначается нулевой ценой.
А с точки зрения математики нуль должен работать точно так же, как любая другая цена.
Согласитесь, что алгоритм, который спотыкается на нулевых значениях - вряд ли можно назвать правильным.
kolyn, уточните, на какой плате получены Ваши результаты, приведенные в сообщении #65 ?
Просто у меня на стандартной Уно для Вашего кода тестовый набор из первого поста дает время 567 мс, а у вас написано 430
Только не подумайте, что я Вам не верю - я думаю что дело в том, что у нас с Вами разные условия. Хотелось бы понять в чем, а то сравнивать результаты сложно.
Завтра пойду мини из поделия выковыряю, проверю на ней. Единственное предположение - Нанку ронял, кусочек кварца отбил, частота повысилась. Но это скорее из области фантастики...
У Вас там ограничение на количество ключей - 64. Само по себе не страшно, я же писал, что "в разумных пределах", готов допустить, что это вполне разумный предел - не проблема.
Проблема в другом. Попробуйте, например, 60, ну или хотя бы 33 ключа с одинаковыми размерами. Цены могут быть и разными, но размеры у всех одинаковые. Запустите, посмотрите.
Я согласен с этим аргументом. Но явно в условии прописано не было, написал человек, теперь переписывать ... да, господь с ним, не принципиально.
У его программы, кстати, есть ещё одна проблема явно не прописанная в условии. Программа не любит ключей с одинаковыми размерами на концах (а таких как раз в реальной жизни навалом - типа с одной стороны рожок, а с другой - храповик)! Но я про это помалкиваю - надо было в условии прописывать, а теперь нефиг :-)
Фича, это когда Вам сто рублей переводят, а Вам на счёт тысяча зачисляется. А вот когда Вы кому-то переводите сто рублей, а с вашего счёт тысяча слетает - это баг.
Вы после вот этого выкладывали что-то? Я пропустил? Или пока еще нет?
Нет пока, исправляю и перепроверяю еще раз. Вчера выяснилось, что время исполнения программы у меня и у других участников отличается на 20%. Думаю, что порчу память , и на разных версиях компилятора это по разному вылазит...
Я думаю любая комбинация цен допустима, в том числе и одинаковые цены. И если в условии сказано "минимальная цена" - то не важно, достигается ли она одним ключом 8х10 или двумя другими вполовину дешевле - минимум есть минимум.
Мои вариант с исправлениями. Учел даже ключи с "0-й" ценой. b707, теперь работает и с Вашим хитрым набором)). Но будет находить два дешевых вместо одного при равной цене.
//
// Тип данных для хранения ключа
//
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) - возможно будет включен,
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[] = {
{1, 8 , 4},
{2, 8 , 3},
{4, 6 , 3},
{12, 15 , 3},
{2, 6 , 3},
{4, 8 , 3},
{6, 10 , 3}
};
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();
}
//--------------------------------------------------
//
// Функция пeребора вариантов сочетаний ключей
//
void bruteForce(uint8_t minQ, uint8_t qOff, uint8_t qOn, uint8_t qSize)
{
uint8_t tempArr[qOff];
const uint32_t ooo = 4294967295;
uint32_t tempTotal = ooo;
bool complectYes = false;
for ( minQ; minQ <= qOff + qOn; minQ++)
{ //Serial.println(minQ);
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 != ooo ) || tempTotal == ooo ) //если цена меньше записанной или это первый набор
{
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; //записываем в темп аррей
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 != ooo )|| tempTotal == ooo ) //если цена меньше записанной или это первый набор
{
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; //записываем в темп аррей
}
flagComplect = true; //поднимаем флаг "собран комплект"
}
}
for (uint8_t i = 0; i < minQ - qOn; i++) //сбросили ключи в "off"
spanners[currArr[i] - 1].included = off;
}
delete[] currArr; // динамич. массив удаляем
if (flagComplect == true) // комплект был создан мин.1 раз
complectYes = true;
if (flagComplect == false&&complectYes == true) //если в иттерации не нашли комплект дешевле
{ //и комплект был создан ранее выходим
for (uint8_t i = 0; i < qOff; i++)
spanners[i].included = tempArr[i];
break;
}
if ( qOff == minQ + qOn) //Последняя иттер.
{
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="<a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a>" rel="nofollow"><a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a></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[] = {{0,0,0}};
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++;
}
}
//Serial.print(uniqueSpanner);
return uniqueSpanner;
}
//------------------------------------------
//
//Функция вычисляет общее количество существующих размеров и Функция удаляет (excluded) дубли ключей
//
uint8_t totalSize()
{
int8_t arrSize[totalSpanners * 2] = {};
uint8_t inSize = 0;
uint8_t y = 0;
for (uint8_t i = 0; i < totalSpanners; i++)
{
arrSize[y] = spanners[i].size1;
y++;
arrSize[y] = spanners[i].size2;
y++;
for (int k = i - 1; k >= 0; k--)
{
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;
}
}
}
for (uint8_t i = 0; i < totalSpanners * 2; i++)
{
uint8_t j = 0;
while (j < i && arrSize[j] != arrSize[i])
++j;
if (j == i)
inSize ++;
}
//Serial.print(inSize);
return inSize;
}
//-------------------------------------------------------
//
// функция сортировки ключей от дешевых к дорогим
//
void spanSort(Spanner * spanarray)
{
Spanner tmp[] = {{0, 0, 0}};
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();
const uint32_t duration = millis() - start;
printResults();
Serial.print("Время расчёта: ");
Serial.print(duration);
Serial.println(" миллисекунд");
}
void loop(void) {}
Результат выполнения:
Ключи
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 коп.
Время расчёта: 516 миллисекунд
Просьба, у кого есть возможность - проверьте у себя и сообщите время.
Евгений Петрович, давайте договоримся на берегу. Дано ключ 8*10 - 50руб. и ключи 8*N и 10*N по 25руб.
Там еще куча ключей и в результат могут войти или 8*10 или 8*N и 10*N
Если в ответе 8*N и 10*N - ошибка или нет - цена то одинакова?
А о чём тут договариваться? Ясно сказано, что в решении должны быть все размеры при минимальной цене. Никаких дополнительных условий по которым следует выбирать из двух и более решений с одинаковой ценой нет. Значит, подойдёт любое. Отбраковать решение можно только по одной из двух причин (или обеим сразу): 1) в нём не хватает какого-то размера и 2) существует более дешёвое решение. Других критериев нет.
AndreyD пишет:
Я думаю вероятность того что ключи 8*N и 10*N будут равны по цене с точностью до копейки очень мала.
А это уже не важно. Вероятность того, что ракета пойдёт строго вертикально без малейших, различимых датчиками, отклонений тоже была ничтожной, но это не помешало вылезти делению на ноль и ракете грохнуться. Программирование - оно такое.
А это уже не важно. Вероятность того, что ракета пойдёт строго вертикально без малейших, различимых датчиками, отклонений тоже была ничтожной, но это не помешало вылезти делению на ноль и ракете грохнуться. Программирование - оно такое.
это точно, это если о высоком, а о низком, в параллельной теме по PID... ABS вместо уменьшения тормозного пути...Программирование оно такое...полностью поддерживаю... )))
По оптимизатору, чуток попозжее отпишусь...
Сорри, там глюк был
вот такой набор:
static Spanner spanners[] = { {1, 8 , 0}, {2, 8 , 3}, {1, 2 , 0}, };причем помоему тут ошибка не та же, что в тестах у Евгения
Бесплатных ключей быть не может согласно условия! Об этом думал.
Бесплатных ключей быть не может согласно условия! Об этом думал.
что-то не вижу в головном сообщении таких ограничений. Пусть автор нас рассудит.
что-то не вижу в головном сообщении таких ограничений.
Хочется купить самый дешёвый из возможных наборов ключей в котором были бы представлены ВСЁ размеры хотя бы по разу.
Купить .
AndreyD,
попробуйте с вот таким набором данных
static Spanner spanners[] = { {1, 2 , 1}, {3, 4 , 1}, {5, 6 , 1} };У меня получилось бесконечное исполнение. Может, и конечное, но больше 15 минут я уж не стал ждать.
Исправил. Изменил строку 137.
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[] = { {1, 2 , 1}, {3, 4 , 1}, {5, 6 , 1} //{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{ if (collection != 0) 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) {}Купить .
В магазине может быть акция, например, ключ 9х12 бесплатно к любому купленному за деньги :) В этом случае, очевидно, покупать такой размер уже не нужно и это обозначается нулевой ценой.
А с точки зрения математики нуль должен работать точно так же, как любая другая цена.
Согласитесь, что алгоритм, который спотыкается на нулевых значениях - вряд ли можно назвать правильным.
Тем не менее слово за Евгением
Согласитесь, что алгоритм, который спотыкается на нулевых значениях - вряд ли можно назвать правильным.
Согласен. Но это прикладная задача.
она не должна ломаться ни при каких правильно заданных данных
что-то не вижу в головном сообщении таких ограничений. Пусть автор нас рассудит.
По условию у всех ключей есть цена, а 0 руб. это отсутствие цены. ИМХО.
kolyn, уточните, на какой плате получены Ваши результаты, приведенные в сообщении #65 ?
Просто у меня на стандартной Уно для Вашего кода тестовый набор из первого поста дает время 567 мс, а у вас написано 430
Только не подумайте, что я Вам не верю - я думаю что дело в том, что у нас с Вами разные условия. Хотелось бы понять в чем, а то сравнивать результаты сложно.
Нано 16 МГц Роботдин.
Перепроверил - 430
На моей нанке 534 показывает, но какая разница тесты всех кодов то на одной ардуинке будут тестироваться.
На моей нанке 534 показывает, но какая разница тесты всех кодов то на одной ардуинке будут тестироваться.
на рободине:
LTO -disable, то программа компилируется, загружается, но НЕ РАБОТАЕТ
Пробовал, UNO, NANO, miniCore 328P - везде 534 миллисекунды
Достал лупу, осмотрел плату. Вроде кварц, не керамика. Написано JF16.000. Откуда такой огромный разброс?
Достал лупу, осмотрел плату. Вроде кварц, не керамика. Написано JF16.000. Откуда такой огромный разброс?
какой бутлоадер? старый-новый?
LTO -disable, то программа компилируется, загружается, но НЕ РАБОТАЕТ
Это что? Не нашел(
Optiboot
Попробовал с optiboot загрузчиком такую же модельку нанки (первая была со старым загрузчиком) - 534.
Откуда такой огромный разброс?
разные версии ядра Ардуино по разному компилируют. Пишите номер версии Ардуино ИДЕ
Завтра пойду мини из поделия выковыряю, проверю на ней. Единственное предположение - Нанку ронял, кусочек кварца отбил, частота повысилась. Но это скорее из области фантастики...
ИДЕ 1.8.7
У меня 1.8.13 - windows
1.8.9 - Linux
у оптибута 7 релизов, интересно, какой именно?
Вопрос закрыт. Плата разогнана. Блинк за 811мс! Кварц, сцуко!
Вопрос закрыт. Плата разогнана. Блинк за 811мс! Кварц, сцуко!
Геймер?
остался подвешенным вопрос, почему в режиме компилятора LTO - disable - не работает...
Геймер?
остался подвешенным вопрос, почему в режиме компилятора LTO - disable - не работает...
Я не знаю что это((
Геймер?
остался подвешенным вопрос, почему в режиме компилятора LTO - disable - не работает...
Я не знаю что это((
Это оптимизатор, обычно наоборот, программы валятся при его включении )))
У Вас там ограничение на количество ключей - 64. Само по себе не страшно, я же писал, что "в разумных пределах", готов допустить, что это вполне разумный предел - не проблема.
Проблема в другом. Попробуйте, например, 60, ну или хотя бы 33 ключа с одинаковыми размерами. Цены могут быть и разными, но размеры у всех одинаковые. Запустите, посмотрите.
Евгений, как лрганизатор конкурса - рассудите спор. Могут быть в наборе ключи с нулевой ценой или условия конкурса предполагают только ненулевые цены?
Спор и аргументы сторон - начная с сообщения #103
Да, Вы же понимаете, что это, всё равно. Ну, если человек уже забился на то, что не могут, пусть не могут - дополним задачу таким условием.
Да, Вы же понимаете, что это, всё равно. Ну, если человек уже забился на то, что не могут, пусть не могут - дополним задачу таким условием.
А мой аргумент? http://arduino.ru/forum/pesochnitsa-razdel-dlya-novichkov/vnimanie-konku...
А мой аргумент? http://arduino.ru/forum/pesochnitsa-razdel-dlya-novichkov/vnimanie-konku...
Я согласен с этим аргументом. Но явно в условии прописано не было, написал человек, теперь переписывать ... да, господь с ним, не принципиально.
У его программы, кстати, есть ещё одна проблема явно не прописанная в условии. Программа не любит ключей с одинаковыми размерами на концах (а таких как раз в реальной жизни навалом - типа с одной стороны рожок, а с другой - храповик)! Но я про это помалкиваю - надо было в условии прописывать, а теперь нефиг :-)
У его программы, кстати, есть ещё одна проблема явно не прописанная в условии. Программа не любит ключей с одинаковыми размерами на концах
Это не баг, это фича!
У его программы, кстати, есть ещё одна проблема явно не прописанная в условии. Программа не любит ключей с одинаковыми размерами на концах
Это не баг, это фича!
ага, и с LTO_disable не работает, какой то там еще секрет есть )))
Это не баг, это фича!
Фича, это когда Вам сто рублей переводят, а Вам на счёт тысяча зачисляется. А вот когда Вы кому-то переводите сто рублей, а с вашего счёт тысяча слетает - это баг.
kolyn,
Вы после вот этого выкладывали что-то? Я пропустил? Или пока еще нет?
AndreyD,
Вы попробовали вариант, о котором я писал? Проблема понятна?
kolyn,
Вы после вот этого выкладывали что-то? Я пропустил? Или пока еще нет?
Нет пока, исправляю и перепроверяю еще раз. Вчера выяснилось, что время исполнения программы у меня и у других участников отличается на 20%. Думаю, что порчу память , и на разных версиях компилятора это по разному вылазит...
Еще где-то...
AndreyD,
Вы попробовали вариант, о котором я писал? Проблема понятна?
Да, пробовал, слишком долго перебирает. Попробую перед перебором отсеять одинаковые ключи с большей ценой.
А вот что получилось:
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], dSpanners[64]; uint8_t allSizes=0, n=0, sizes[128], cSizes[128], elem=0, noKeys=0, unique=0, dbl=0; uint32_t rezTotal = 0, total0 = 0, total = 0; uint64_t collection=0, rezCollection=0, 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); // Установка единиц в массиве для вычисления ключей, которые полюбому попадают в набор. memset(dSpanners, 1, sizeof(dSpanners[0])*64); // Установка единиц в массиве для вычисления ключей, которые полюбому попадают в набор. // Поиск более дорогих дублей, всех размеров ключей и кол-ва каждого размера for (uint8_t i=0; i < totalSpanners; i++) { for (uint8_t j=0; j < totalSpanners; j++) if (dSpanners[i] && i != j) if ((((spanners[i].size1 == spanners[j].size1) && (spanners[i].size2 == spanners[j].size2)) || ((spanners[i].size1 == spanners[j].size2) && (spanners[i].size2 == spanners[j].size1))) && (spanners[i].price <= spanners[j].price)) dSpanners[j] = 0; 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)); // половина всех размеров, для рассчёта границы по кол-ву ключей в наборе // Сортировка массива структур, дубли с высокой ценой перемещаются в конец массива Spanner tmp[0]; uint8_t temp = 0; for (uint8_t i = 0; i < totalSpanners; i++) for (uint8_t j = 0; j < totalSpanners - i - 1; j++) if ((dSpanners[j]) < (dSpanners[j + 1])) { temp = dSpanners[j]; dSpanners[j] = dSpanners[j + 1]; dSpanners[j + 1] = temp; tmp[0] = spanners[j]; spanners[j] = spanners[j + 1]; spanners[j + 1] = tmp[0]; } // Вычисление колва дублей с высокой ценой for (uint8_t i=0; i < totalSpanners; i++) if (!dSpanners[i]) {dbl = totalSpanners - i; break;} // Выявление ключей, которые полюбому будут в наборе (ключи у которых хотя бы один размер не повторяется с другими ключами), и вычисление их кол-ва. for (uint8_t j=0; j < allSizes; j++) if (cSizes[j] == 0) { unique++; for (uint8_t i = 0; i < totalSpanners - dbl; i++) { if (spanners[i].size1 == sizes[j]) uSpanners[i] = 0; if (spanners[i].size2 == sizes[j]) uSpanners[i] = 0; } } // Сортировка массива структур, ключи, которые полюбому будут в наборе (без дублей), перемещаются в конец массива for (uint8_t i = 0; i < totalSpanners - dbl; i++) for (uint8_t j = 0; j < totalSpanners - i - 1 - dbl; 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 - dbl; i++) for (uint8_t j = 0; j < totalSpanners - i - 1 - unique - dbl; 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 - dbl; 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 - dbl) 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 - dbl;i++) collection |= (1ULL<<i); // Основной цикл перебора do{ if (collection != 0) 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 - dbl; i++,r=r*2ULL) { 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) {}Евгений Петрович, давайте договоримся на берегу. Дано ключ 8*10 - 50руб. и ключи 8*N и 10*N по 25руб.
Там еще куча ключей и в результат могут войти или 8*10 или 8*N и 10*N
Если в ответе 8*N и 10*N - ошибка или нет - цена то одинакова? В условии про минимальную сумму да, про мин кол-во нет.
И еще одно:
Ну, вот, собственно, такая задача: имеется набор несимметричных ключей
Так что точно не баг)). Там и без этого хватает тараканов.
Евгений Петрович, давайте договоримся на берегу. Дано ключ 8*10 - 50руб. и ключи 8*N и 10*N по 25руб.
Я думаю вероятность того что ключи 8*N и 10*N будут равны по цене с точностью до копейки очень мала.
Я думаю вероятность того что ключи 8*N и 10*N будут равны по цене с точностью до копейки очень мала.
Тестовые комплекты хитрые будут, могут и такой придумать))
Как у тебя, ладится?
Я думаю любая комбинация цен допустима, в том числе и одинаковые цены. И если в условии сказано "минимальная цена" - то не важно, достигается ли она одним ключом 8х10 или двумя другими вполовину дешевле - минимум есть минимум.
Я думаю вероятность того что ключи 8*N и 10*N будут равны по цене с точностью до копейки очень мала.
Тестовые комплекты хитрые будут, могут и такой придумать))
Как у тебя, ладится?
Чуть выше выложил последний вариант.
Есть ещё одна идея для ускорения, на выходных нужно будет попробовать.
Мои вариант с исправлениями. Учел даже ключи с "0-й" ценой. b707, теперь работает и с Вашим хитрым набором)). Но будет находить два дешевых вместо одного при равной цене.
// // Тип данных для хранения ключа // 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) - возможно будет включен, 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[] = { {1, 8 , 4}, {2, 8 , 3}, {4, 6 , 3}, {12, 15 , 3}, {2, 6 , 3}, {4, 8 , 3}, {6, 10 , 3} }; 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(); } //-------------------------------------------------- // // Функция пeребора вариантов сочетаний ключей // void bruteForce(uint8_t minQ, uint8_t qOff, uint8_t qOn, uint8_t qSize) { uint8_t tempArr[qOff]; const uint32_t ooo = 4294967295; uint32_t tempTotal = ooo; bool complectYes = false; for ( minQ; minQ <= qOff + qOn; minQ++) { //Serial.println(minQ); 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 != ooo ) || tempTotal == ooo ) //если цена меньше записанной или это первый набор { 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; //записываем в темп аррей 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 != ooo )|| tempTotal == ooo ) //если цена меньше записанной или это первый набор { 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; //записываем в темп аррей } flagComplect = true; //поднимаем флаг "собран комплект" } } for (uint8_t i = 0; i < minQ - qOn; i++) //сбросили ключи в "off" spanners[currArr[i] - 1].included = off; } delete[] currArr; // динамич. массив удаляем if (flagComplect == true) // комплект был создан мин.1 раз complectYes = true; if (flagComplect == false&&complectYes == true) //если в иттерации не нашли комплект дешевле { //и комплект был создан ранее выходим for (uint8_t i = 0; i < qOff; i++) spanners[i].included = tempArr[i]; break; } if ( qOff == minQ + qOn) //Последняя иттер. { 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="<a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a>" rel="nofollow"><a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a></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[] = {{0,0,0}}; 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++; } } //Serial.print(uniqueSpanner); return uniqueSpanner; } //------------------------------------------ // //Функция вычисляет общее количество существующих размеров и Функция удаляет (excluded) дубли ключей // uint8_t totalSize() { int8_t arrSize[totalSpanners * 2] = {}; uint8_t inSize = 0; uint8_t y = 0; for (uint8_t i = 0; i < totalSpanners; i++) { arrSize[y] = spanners[i].size1; y++; arrSize[y] = spanners[i].size2; y++; for (int k = i - 1; k >= 0; k--) { 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; } } } for (uint8_t i = 0; i < totalSpanners * 2; i++) { uint8_t j = 0; while (j < i && arrSize[j] != arrSize[i]) ++j; if (j == i) inSize ++; } //Serial.print(inSize); return inSize; } //------------------------------------------------------- // // функция сортировки ключей от дешевых к дорогим // void spanSort(Spanner * spanarray) { Spanner tmp[] = {{0, 0, 0}}; 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(); const uint32_t duration = millis() - start; printResults(); Serial.print("Время расчёта: "); Serial.print(duration); Serial.println(" миллисекунд"); } void loop(void) {}Результат выполнения:
Просьба, у кого есть возможность - проверьте у себя и сообщите время.
Отдельно к ua6em: что там с оптимизатором?
Евгений Петрович, давайте договоримся на берегу. Дано ключ 8*10 - 50руб. и ключи 8*N и 10*N по 25руб.
Там еще куча ключей и в результат могут войти или 8*10 или 8*N и 10*N
Если в ответе 8*N и 10*N - ошибка или нет - цена то одинакова?
А о чём тут договариваться? Ясно сказано, что в решении должны быть все размеры при минимальной цене. Никаких дополнительных условий по которым следует выбирать из двух и более решений с одинаковой ценой нет. Значит, подойдёт любое. Отбраковать решение можно только по одной из двух причин (или обеим сразу): 1) в нём не хватает какого-то размера и 2) существует более дешёвое решение. Других критериев нет.
Я думаю вероятность того что ключи 8*N и 10*N будут равны по цене с точностью до копейки очень мала.
А это уже не важно. Вероятность того, что ракета пойдёт строго вертикально без малейших, различимых датчиками, отклонений тоже была ничтожной, но это не помешало вылезти делению на ноль и ракете грохнуться. Программирование - оно такое.
Время расчёта: 641 миллисекунд
Мой очередной вариант.
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], dSpanners[64], stopElem=0, first0=1; uint8_t allSizes=0, n=0, sizes[128], cSizes[128], elem=0, noKeys=0, unique=0, dbl=0; uint32_t rezTotal = 0, total0 = 0, total = 0; uint64_t collection=0, rezCollection=0, p=1, bitsCollection=0; // Функция которая выполняется первой и один раз. void first(void) { memset(sizes, 0, sizeof(sizes[0])*128); // Обнуление массива размеров. memset(cSizes, 0, sizeof(cSizes[0])*128); // Обнуление массива кол-ва одинаковых размеров. memset(uSpanners, 1, sizeof(uSpanners[0])*64); // Установка единиц в массиве для вычисления ключей, которые полюбому попадают в набор. memset(dSpanners, 1, sizeof(dSpanners[0])*64); // Установка единиц в массиве для вычисления ключей, которые полюбому попадают в набор. // Поиск более дорогих дублей, всех размеров ключей и кол-ва каждого размера for (uint8_t i=0; i < totalSpanners; i++) { for (uint8_t j=0; j < totalSpanners; j++) if (dSpanners[i] && i != j) if ((((spanners[i].size1 == spanners[j].size1) && (spanners[i].size2 == spanners[j].size2)) || ((spanners[i].size1 == spanners[j].size2) && (spanners[i].size2 == spanners[j].size1))) && (spanners[i].price <= spanners[j].price)) dSpanners[j] = 0; 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)); // половина всех размеров, для рассчёта границы по кол-ву ключей в наборе // Сортировка массива структур, дубли с высокой ценой перемещаются в конец массива Spanner tmp[0]; uint8_t temp = 0; for (uint8_t i = 0; i < totalSpanners; i++) for (uint8_t j = 0; j < totalSpanners - i - 1; j++) if ((dSpanners[j]) < (dSpanners[j + 1])) { temp = dSpanners[j]; dSpanners[j] = dSpanners[j + 1]; dSpanners[j + 1] = temp; tmp[0] = spanners[j]; spanners[j] = spanners[j + 1]; spanners[j + 1] = tmp[0]; } // Вычисление кол-ва дублей с большей ценой for (uint8_t i=0; i < totalSpanners; i++) if (!dSpanners[i]) {dbl = totalSpanners - i; break;} // Выявление ключей, которые полюбому будут в наборе (ключи у которых хотя бы один размер не повторяется с другими ключами), и вычисление их кол-ва. for (uint8_t j=0; j < allSizes; j++) if (cSizes[j] == 0) { unique++; for (uint8_t i = 0; i < totalSpanners - dbl; i++) { if (spanners[i].size1 == sizes[j]) uSpanners[i] = 0; if (spanners[i].size2 == sizes[j]) uSpanners[i] = 0; } } // Сортировка массива структур, ключи, которые полюбому будут в наборе (без дублей), перемещаются в конец массива for (uint8_t i = 0; i < totalSpanners - dbl; i++) for (uint8_t j = 0; j < totalSpanners - i - 1 - dbl; 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 - dbl; i++) for (uint8_t j = 0; j < totalSpanners - i - 1 - unique - dbl; 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; stopElem=0; first0=1; for (uint8_t i=0; i < totalSpanners - dbl; i++,p=p*2ULL) if (!bool((collection) & (p))){ /* // Граница по кол-ву ключей в коомбинации if (first0) { bitsCollection = collection; do { if (!!(bitsCollection & 1ULL)) noKeys++; bitsCollection = bitsCollection / 2; }while (bitsCollection); if (noKeys > totalSpanners - n - dbl) return 0; first0 = 0; } */ // Граница по сумме цен ключей total = total + spanners[i].price; if ((total > rezTotal) && (rezTotal != 0)) return 0; // Проверка наличия всех размеров if (!stopElem) { 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; if (elem == allSizes) stopElem=1; } } else { // Граница по кол-ву ключей в коомбинации noKeys++; if (noKeys > totalSpanners - n - dbl) return 0; } if (!stopElem) return 0; else return 1; // Проверка что есть все размеры } void doCalculations(void) { // Вычисление верхней границы перебора. for (uint8_t i =0; i < totalSpanners - unique - dbl;i++) collection |= (1ULL<<i); // Основной цикл перебора do{ if (collection != 0) 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 - dbl; i++,r=r*2ULL) { 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) {}А это уже не важно. Вероятность того, что ракета пойдёт строго вертикально без малейших, различимых датчиками, отклонений тоже была ничтожной, но это не помешало вылезти делению на ноль и ракете грохнуться. Программирование - оно такое.
это точно, это если о высоком, а о низком, в параллельной теме по PID... ABS вместо уменьшения тормозного пути...Программирование оно такое...полностью поддерживаю... )))
По оптимизатору, чуток попозжее отпишусь...
Прошу прощения , в 145 сообщении в коде использован один из тестовых наборов ключей. Код с исходным, тем что задан в условии конкурса массивом ключей:
// // Тип данных для хранения ключа // 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) - возможно будет включен, 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}, {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]); 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(); } //-------------------------------------------------- // // Функция пeребора вариантов сочетаний ключей // void bruteForce(uint8_t minQ, uint8_t qOff, uint8_t qOn, uint8_t qSize) { uint8_t tempArr[qOff]; const uint32_t ooo = 4294967295; uint32_t tempTotal = ooo; bool complectYes = false; for ( minQ; minQ <= qOff + qOn; minQ++) { //Serial.println(minQ); 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 != ooo ) || tempTotal == ooo ) //если цена меньше записанной или это первый набор { 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; //записываем в темп аррей 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 != ooo )|| tempTotal == ooo ) //если цена меньше записанной или это первый набор { 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; //записываем в темп аррей } flagComplect = true; //поднимаем флаг "собран комплект" } } for (uint8_t i = 0; i < minQ - qOn; i++) //сбросили ключи в "off" spanners[currArr[i] - 1].included = off; } delete[] currArr; // динамич. массив удаляем if (flagComplect == true) // комплект был создан мин.1 раз complectYes = true; if (flagComplect == false&&complectYes == true) //если в иттерации не нашли комплект дешевле { //и комплект был создан ранее выходим for (uint8_t i = 0; i < qOff; i++) spanners[i].included = tempArr[i]; break; } if ( qOff == minQ + qOn) //Последняя иттер. { 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="<a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a>" rel="nofollow"><a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a></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[] = {{0,0,0}}; 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++; } } //Serial.print(uniqueSpanner); return uniqueSpanner; } //------------------------------------------ // //Функция вычисляет общее количество существующих размеров и Функция удаляет (excluded) дубли ключей // uint8_t totalSize() { int8_t arrSize[totalSpanners * 2] = {}; uint8_t inSize = 0; uint8_t y = 0; for (uint8_t i = 0; i < totalSpanners; i++) { arrSize[y] = spanners[i].size1; y++; arrSize[y] = spanners[i].size2; y++; for (int k = i - 1; k >= 0; k--) { 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; } } } for (uint8_t i = 0; i < totalSpanners * 2; i++) { uint8_t j = 0; while (j < i && arrSize[j] != arrSize[i]) ++j; if (j == i) inSize ++; } //Serial.print(inSize); return inSize; } //------------------------------------------------------- // // функция сортировки ключей от дешевых к дорогим // void spanSort(Spanner * spanarray) { Spanner tmp[] = {{0, 0, 0}}; 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(); const uint32_t duration = millis() - start; printResults(); Serial.print("Время расчёта: "); Serial.print(duration); Serial.println(" миллисекунд"); } void loop(void) {}Время выполнения 516 миллисекунд.