Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 9 ] |
|
||
Автор | Сообщение | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Elia |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Наткнулся на такую задачу. Оказалась очень занимательной, Дана таблица 10х10, заполненная повторяющимися числами от 1 до 33. Требуется найти путь от 1 до 33, проходящий через все 33 числа ровно по 1му разу. По диагонали двигаться не разрешается.
Путь я нашел, но не без перебора. Автором такого класса задач по всей видимости является Л.П. Мочалов, но в его книге алгоритм только на тривиальные задачи. Вопрос: Как максимально математизировать эту задачу, чтобы минимизировать перебор? Думал про теорию графов и линейную алгебру. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Вернуться к началу | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Emphatic18 |
|
|
Elia писал(а): Требуется найти путь от 1 до 33, проходящий через все 33 числа ровно по 1му разу. А путь должен быть по числам следующим в порядке возрастания 1-2-3...33 или в любом порядке, лишь бы по разу на каждом из чисел? |
||
Вернуться к началу | ||
Booker48 |
|
|
Emphatic18 писал(а): А путь должен быть по числам следующим в порядке возрастания 1-2-3...33? Это невозможно при заданных значениях и было бы тривиально, если бы было возможно. |
||
Вернуться к началу | ||
За это сообщение пользователю Booker48 "Спасибо" сказали: Elia |
||
Emphatic18 |
|
|
Алгоритм Дейкстры здесь нельзя применить?
|
||
Вернуться к началу | ||
Booker48 |
|
|
Elia
В голову лезет волновой алгоритм, очень ресурсожоркий. Но ничего лучшего не могу предложить. И он, вроде бы, должен закончиться за 33 шага. |
||
Вернуться к началу | ||
Elia |
|
|
Emphatic18 писал(а): Алгоритм Дейкстры здесь нельзя применить? Я не додумал как сформулировать задачу, в особенности - ограничения, в графах. Вершин брать 100 или 33, если 33 - то как ребра занумеровать и как отметить, что в зависимости от того, из какой вершины попал в текущую, доступна только часть маршрутов. А если брать 100 вершин как применять алгоритм, чтобы определять ненужные вершины? |
||
Вернуться к началу | ||
Elia |
|
|
Booker48 писал(а): Elia В голову лезет волновой алгоритм, очень ресурсожоркий. Но ничего лучшего не могу предложить. И он, вроде бы, должен закончиться за 33 шага. Спасибо, про волновой алгоритм кстати не подумал. Но он по сути как полный перебор будет? |
||
Вернуться к началу | ||
Booker48 |
|
|
Elia писал(а): ...про волновой алгоритм кстати не подумал. Но он по сути как полный перебор будет? Не совсем. Мне кажется, что на такой структуре, как таблица, будут эффективно отсекаться "лишние" трассы, как только волна дойдёт до числа, которое уже содержится в трассе (как при пересечении существующей трассы, так и при обработке новой клетки). Но количество трасс растёт, конечно, быстро. Надо бы помоделировать, да мне долго это писать, хотя он и не сложен в реализации. ))) |
||
Вернуться к началу | ||
Booker48 |
|
|
Подумал немного: волновой алгоритм идеально применим к этой задаче. Полного перебора не будет, волну надо запускать от двойки (2), поскольку она ровно один раз встречается в таблице и точно войдёт в решение, если оно вообще существует.
Но даже если бы все числа входили в таблицу более одного раза (допустим, 3, чаще не получится по причинам общего количества клеток и чисел), то решение было бы получено максимум после запуска третьей волны. |
||
Вернуться к началу | ||
[ Сообщений: 9 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Занимательная задачка
в форуме Начала анализа и Другие разделы школьной математики |
7 |
317 |
18 фев 2023, 12:53 |
|
Занимательная математика
в форуме Алгебра |
13 |
714 |
04 май 2015, 02:25 |
|
Занимательная чушь
в форуме Палата №6 |
18 |
1045 |
16 июл 2019, 18:06 |
|
Занимательная стереометрических задача
в форуме Геометрия |
9 |
288 |
23 окт 2022, 11:34 |
|
Занимательная задача по геометрии | 30 |
1040 |
26 фев 2022, 23:43 |
|
Занимательная задача про переустановку колес | 3 |
305 |
20 фев 2022, 10:34 |
|
Занимательная задача про взвешивание монет
в форуме Начала анализа и Другие разделы школьной математики |
55 |
1242 |
17 фев 2023, 18:39 |
|
Занимательная задача на объём цилиндра
в форуме Геометрия |
2 |
110 |
16 май 2023, 17:11 |
|
Во сколько раз дороже? Занимательная арифметика | 9 |
516 |
16 мар 2018, 17:31 |
|
Определитель над полем или занимательная агрономия.
в форуме Линейная и Абстрактная алгебра |
1 |
423 |
10 ноя 2016, 16:40 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |