ВНИМАНИЕ: Конкурс для начинающих!!!
- Войдите на сайт для отправки комментариев
Вс, 18/10/2020 - 21:04
Давно как-то говорили, вроде все были за, я обещал тему замутить, да как-то "замутилось" всё... В общем, не прошло и полгода, и я таки выполняю обещание ...
Объявляется конкурс для тех, кому нравится программирование и есть желание его изучать. Участвовать может любой, кто не зарабатывает и никогда не зарабатывал программированием, т.е. программисты - любители.
Задачу для первого раза я попытался подобрать так, чтобы она требовала головы, но не требовала никаких специальных знаний и никакого оборудования кроме ардуины (подойдёт даже протеус).
Аппаратная среда: Ардуино UNO или любой её клон (включая Nano и т.п.) на ATMega328 с частотой 16МГц.
Среда программирования: без ограничений.
Идея задачи появилась при просмотре вот этого лота. Как видите, там представлены несимметричные гаечные ключи. При этом, некоторые размеры присутствуют в единственном экземпляре (например, 6 или 11). Некоторые в двух, например, 13 есть в ключах 12-13 и 13-15. А некоторые, так и в трёх (например, 8 есть в 6-8, 8-9 и 8-10). Хочется купить самый дешёвый из возможных наборов ключей в котором были бы представлены ВСЁ размеры хотя бы по разу.
Ну, вот, собственно, такая задача: имеется набор несимметричных ключей с известными размерами (по два на ключ) и ценами. Требуется выбрать самый дешёвый поднабор в котором присутствовали бы все размеры.
Разумеется, программа не должна зависеть ни от количества ключей (в разумных пределах), ни от цен на них - она должна работать для любого набора. В случае, если размеры ни разу не повторяются, она должна выдать изначальный набор. В случае, если набор состоит из одинаковых ключей, она должна выдать поднабор из одного ключа (самого дешёвого). Ну, и так далее.
Программа должна печатать решение и время, затраченное на вычисления. Победителем становится программа, решившая задачу наиболее быстро (и правильно, конечно). При этом программа будет проверяться с другими массивами ключей - она не должна ломаться ни при каких правильно заданных данных. Скорость будет определяться как среднее по всем тестам (тесты у разных программ будут одинаковыми).
Срок представления работ на конкурс до 30 ноября включительно.
Для примера я подготовил "скелет" такой программы. Здесь ключ задаётся структурой Spanner, а набор ключей массивом spanners. В массив введены данные из того лота с али.
//
// Тип данных для хранения ключа
//
struct Spanner : public Printable {
uint32_t price;// цена в копейках
uint8_t size1; // размер 1
uint8_t size2; // размер 2
bool included; // если true, то включается в результирующий набор
//
// Изначально считаем, что все ключи включены в результат, а потом ненужные исключим.
// Можно наоборот - изначально всё исключить (написать "ini = true" в след. строке)
// Или задавать каждому индивидуально в 4-ом параметре конструктора (только нафига?)
//
Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const bool ini = true)
: 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]);
//
// Эта функция вычисляет оптимальный набор ключей
// и устанваливает поле included в true для ключей,
// которые попадают в решение, и false для ключей,
// которые не попадают в решение.
//
void doCalculations(void) {
// здесь производятся все вычисления и устанавливаются
// значеия флагов included для каждого ключа.
// Поскольку мы здесь ничего не делаем,
// все included останутся true, как были изначально
}
//
// Функция печатает результирующий
// набор ключей и его стоимость
//
void printResults(void) {
Serial.println("Ключи");
uint32_t total = 0;
for (uint8_t i = 0; i < totalSpanners; i++) {
if (spanners[i].included) {
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();
doCalculations();
const uint32_t duration = millis() - start;
printResults();
Serial.print("Время расчёта: ");
Serial.print(duration);
Serial.println(" миллисекунд");
}
void loop(void) {}
Можете использовать этот скелет и дописывать самостоятельно только вычисления. По сути тут осталось дописать функцию "doCalculations" вместо которой у меня стоит заглушка.
Призовой фонд: автор правильно работающей программы, показавшей наилучшее время получит приз - вот такую плату. Если при этом он еще и побьёт по времени моё решение (которое я планирую выложить после 30 ноября для разбора теми, кто не смог написать сам), то он получит дополнительный приз от меня лично.
Если конкурс окажется успешным (будут участники), возможно договоримся и сделаем его регулярным
плата достойная, надо попробовать сына заинтересовать, правда он даже светодиодиком никогда не моргал и, не программист )))
А вот если аккаунт участника с одного IP с старым программистом, то это кто будет отслеживать? ;))
Интересно - зачем начинающему такая плата...
Интересно - зачем начинающему такая плата...
вот отвечу, ардуиной сына не заинтересовал, а вот к СТМу он благожелательно относится, ждёт, когда допилят среду, говорит, что скоро, подвижки есть, хотя и на стм ничего еще не написал, даже диодом не помаргал, я хоть генератор Димакса пытался сделать, да и диодом моргал )))
А вот если аккаунт участника с одного IP с старым программистом, то это кто будет отслеживать? ;))
Никто. У нас, например, полгорода практически на одном IP-шнике. Так что, если на это смотреть, то я, покойный Ворота и, если не обознался, то и ещё как минимум один участник - все клоняры друг друга!
Интересно - зачем начинающему такая плата...
Как раз начинающему ... это Вам она не нужна, а ему ... ну, вот придётся блинк на целых три диода написать ... или даже на четыре ... это ж ни в какую мегу не полезет!
Так что, если на это смотреть, то я, покойный Ворота и, если не обознался, то и ещё как минимум один участник - все клоняры друг друга!
Ворота? :( Давно?
понятно, что 9 ключей, человек делает это за один полный проход , у Вирта этот метод есть, но только именно этом метод я не смог реализовать в коде, сейчас даже не вспомню как назывался ...
то я, покойный Ворота и, если не обознался, то и ещё как минимум один участник - все клоняры друг друга!
О_О Как так... :(
понятно, что 9 ключей
Восемь, вроде.
Ворота? :( Давно?
30.09
Это оголтелый расизм и дискриминация! Я буду жаловаться в Спортлото!
(это я подписался на посмотреть чем закончится)
понятно, что 9 ключей
Восемь, вроде.
да не вроде, а точно 8, первое полусовершенное число
точно 8, первое полусовершенное число
Первое полусовершенное - это 6
Интересно - зачем начинающему такая плата...
вот отвечу, ардуиной сына не заинтересовал, а вот к СТМу он благожелательно относится, ждёт, когда допилят среду, говорит, что скоро, подвижки есть, хотя и на стм ничего еще не написал, даже диодом не помаргал, я хоть генератор Димакса пытался сделать, да и диодом моргал )))
30.09
Тоска.(((
...покойный Ворота...
PS. Володя был человеком военным, а у военных принято помнить об ушедших товарищах. Я за то, чтобы разместить некролог в "Отвлеченных темах".
PS. Володя был человеком военным, а у военных принято помнить об ушедших товарищах. Я за то, чтобы разместить некролог в "Отвлеченных темах".
Поддерживаю.
В случае, если набор состоит из одинаковых ключей, она должна выдать поднабор из одного ключа (самого дешёвого).
Удалил вопрос, согласно Вашего условия может.
Да, не любил он этого поминания, andriano, весёлый был парень и ему бы не понравилась "официальная грусть". Погиб как-то нелепо - в стольких передрягах был (Афган, Руанда), столько жутких самоделок делал и испытывал (типа самодельный автожир, какие-то невероятные штуки типа катушек тесла и пр.) и всё нипочём. С автожиром грохнулся с приличной высоты, аппарат - в лом, у самого ни царапины. А погиб в самой прозаической автоаварии, в которой и пострадать-то трудно было - чуток теранулись боками с грузовиком, его закрутило и ... об столб шмякнуло. Не попадись это столб, ... В Руанде, рассказывал, уже на расстрел вели - выжил, а тут ... вот уж действительно, "рождённый для виселицы не утонет".
Ладно, давай примем по маленькой, земля ему пухом.
согласно Вашего условия может.
Да, я как-то невнимателен был, когда отвечал.
Ладно, давай примем по маленькой, земля ему пухом.
"... так лучше, чем от водки и от простуд..."
Это, да.
во блин, О_О, ладно... не чокаясь...
Помяну. Светлый был человек, фулюган Всея Руси.
а можно сперва дам ответ, а потом опишу решение...
по моим прикидкам (из вводных массива) останется 8 ключей на сумму 6.367,66
а можно сперва дам ответ, а потом опишу решение...
внимательнее смотрим условия конкурса - важен не только сам ответ, но и скорость работы программы. Поэтому цифра без кода смысла не имеет.
Я напишу комментарий. Я ж математик, "Не могу молчать!".
Женя в условии нашел способ за утилитарной постановкой скрыть очень важную в теории алгоритмов вообще задачу - задачу обхода графа. Решение по сути является поиском самого дешевого маршрута, содержащего полный набор вершин(ключей). Тех новичков, которые считают задачку тривиальной, отошлю к классике учебников по программированию или теории алгоритмов, ну или теории графов.
;))))))
Я напишу комментарий. Я ж математик, "Не могу молчать!".
Женя в условии нашел способ за утилитарной постановкой скрыть очень важную в теории алгоритмов вообще задачу - задачу обхода графа. Решение по сути является поиском самого дешевого маршрута, содержащего полный набор вершин(ключей). Тех новичков, которые считают задачку тривиальной, отошлю к классике учебников по программированию или теории алгоритмов, ну или теории графов.
;))))))
Я напишу комментарий. Я ж математик, "Не могу молчать!".
Женя в условии нашел способ за утилитарной постановкой скрыть очень важную в теории алгоритмов вообще задачу - задачу обхода графа. Решение по сути является поиском самого дешевого маршрута, содержащего полный набор вершин(ключей). Тех новичков, которые считают задачку тривиальной, отошлю к классике учебников по программированию или теории алгоритмов, ну или теории графов.
;))))))
во во, это точно, у меня пример из Вирта не заработал, точнее я с ним не справился
Женя в условии нашел способ за утилитарной постановкой скрыть очень важную в теории алгоритмов вообще задачу - задачу обхода графа. Решение по сути является поиском самого дешевого маршрута, содержащего полный набор вершин(ключей).
;))))))
Если б не этот пост, никогда не узнал бы, что "изобрел" метод поиска в ширину. 0_0
Если разберусь с читерским кодом Е.П. (так, по простому, как раз для новичков написан), может и решу :| Например в 4-й строке что за Принтабля? Ни где найти не могу(
4publicPrintableЕсли разберусь с читерским кодом Е.П. (так, по простому, как раз для новичков написан), может и решу :| Например в 4-й строке что за Принтабля? Ни где найти не могу(
4publicPrintableна чистом русском языке вроде как печатаемое )))
а можно сперва дам ответ, а потом опишу решение...
по моим прикидкам (из вводных массива) останется 8 ключей на сумму 6.367,66
Про восемь я уже писал выше. Смысл в программе.
Ни где найти не могу(
Это потому, что "ни где" не искал. Если в окне поиска нашего форума (в правом верхнем углу) набрать это слово, то первый же результат ведёт на тему, где всё разжёвано.
Уж, как умею.
Видел фильм "Ржевский против наполеона"? Там ржевскому приказывают выдавать себя за женщину и так, чтобы все поверили, а он спрашивает:"Так это что ж, мне теперь кобылу криво парковать? Я не умею!"
Простие, искал Гугл и Яндекс, я их просил) А вутренний поиск - не додумался.
А от "ни где" вез де прям покраснел.
Сегодня дедлайн, если не ошибаюсь. Пытается кто-нибудь поучаствовать?
Я лично еще трепыхаюсь, но близок к "ниасилил".
Евгений Петрович, не томите, публикуйте ответ.
Я неделю за компьютером провел безвылазно, на все дела забил, жена печень выгрызла, чемодан мне паковать начала;)
Сегодня дедлайн, если не ошибаюсь.
ошибаетесь.
С вашей внимательностью вам трудно в программировании придется :)
С вашей внимательностью вам трудно в программировании придется :)
30.10. 2020 в 23:59:59 последний срок. В чем я ошибся?)
С вашей внимательностью вам трудно в программировании придется :)
30.10. 2020 в 23:59:59 последний срок. В чем я ошибся?)
Ноября!!!!! Вы правы!
Есть мысли, но как реализовать в коде не хватает знаний:
1. Считаем сколько всего размеров, скорее всего их нужно будет занести в отдельный массив для дальнейшей проверки наборов.
2. Минимальное количество ключей в наборе будет равно половине от количества размеров. Ну или +1, если нечётное.
3. Перебираем все комбинации ключей от числа половины размеров до максимального количества ключей.
а) откидываем набор, если у него нет всех размеров.
б) если есть все размеры, сравниваем сумму, если меньше то запоминаем.
Между 2 и 3 пунктом можно "зафиксировать" ключи, которые попадут в набор по любому, это ключи у которых размер встречается только один раз, а перебирать уже оставшиеся.
Метод Британского музея? Ну, что ж, достойно. Можете оценить количество вариантов для перебора?
Для вашего набора 89846 комбинаций. Это без последнего предложения про выбор явных ключей. Точнее для любого набора с 16-ю размерами.
Метод Британского музея?
Я больше про брутфорс подумал, хотя это получается примерно одно и тоже.
Не знаю новомоднего словечка "брутфорс". Медод британского музей - это другое название метода полного перебора.
Для вашего набора 89846 комбинаций. Это без последнего предложения про выбор явных ключей. Точнее для любого набора с 16-ю размерами.
Не знаю новомоднего словечка "брутфорс". Медод британского музей - это другое название метода полного перебора.
Спасибо, что подсказали про название метода, попробую изучить. Но пока вижу только вариант для неизменного количества ключей.
Сомневаюсь, но проверять не буду
Ну может кто-нибудь захочет проверить. ссыль
Количество комбинаций равно сумме всех значений, когда n=17, а k изменяется от 8 до 17.
у ключа есть ещё и тело, к примеру с одной стороны на 112 а с другой 7 )))