|
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
|
|||||||||||
Кратчайший путь до какой-то координаты. Ошибка std::bad_alloc08.02.2017, 22:34. Показов 3024. Ответов 33
Метки нет (Все метки)
Задача
Примеры : Моё решение :
1. При некоторых значениях(например, входной файл: 20 20 20 1 5), после нескольких секунд (от 4 до 40) программа вылетает с такой ошибкой: 2. Сайт почему-то не может её запустить, пишет "Ошибка при выполнении программы", я подозреваю, что это связано с предыдущей проблемой. Хотя тест из условия работает и пара моих тестов тоже. Если какие-то непонятки с кодом, задавайте вопросы, я всё объясню. Не по теме: Что-то мне подсказывает, что всем будет просто
1
|
|||||||||||
| 08.02.2017, 22:34 | |
|
Ответы с готовыми решениями:
33
Ошибка terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc Ошибка terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc |
|
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
|
||
| 10.02.2017, 19:32 [ТС] | ||
|
likehood,
size()
0
|
||
|
70 / 70 / 35
Регистрация: 06.07.2016
Сообщений: 415
|
|
| 10.02.2017, 19:35 | |
|
Ну сделайте вы очередь ручками , это 10 минут занимает. И отлаживайте по-нормальному.
0
|
|
|
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
|
|
| 10.02.2017, 19:40 | |
|
Я бы обернул 34 и 35 строки в блок try-catch, поймал исключение bad_alloc и посмотрел размеры очередей в момент прихода исключения.
0
|
|
|
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
|
||||||||
| 10.02.2017, 20:07 [ТС] | ||||||||
|
likehood, к сожалению, я новичок и не смог разобраться, как в try-catch-throw засунуть проверку на bad_alloc. Так что, я просто засунул в цикл это:
Кликните здесь для просмотра всего текста
0 0
1 1 2 2 3 3 4 4 5 5 6 6 7 7 7 7 8 8 9 9 10 10 11 11 12 12 13 13 13 13 14 14 15 15 16 16 17 17 18 18 18 18 19 19 20 20 21 21 22 22 23 23 23 23 24 24 25 25 26 26 27 27 27 27 28 28 29 29 29 29 30 30 30 30 31 31 31 31 31 31 32 32 33 33 34 34 35 35 36 36 37 37 37 37 38 38 39 39 40 40 41 41 41 41 42 42 43 43 44 44 45 45 45 45 46 46 47 47 47 47 48 48 48 48 49 49 49 49 49 49 50 50 51 51 51 51 52 52 53 53 53 53 54 54 54 54 55 55 55 55 56 56 56 56 56 56 57 57 58 58 59 59 60 60 61 61 61 61 62 62 63 63 64 64 65 65 65 65 65 65 66 66 66 66 65 65 66 66 67 67 66 66 67 67 67 67 68 68 67 67 68 68 68 68 67 67 63 63 64 64 65 65 65 65 66 66 66 66 67 67 67 67 68 68 69 69 69 69 70 70 70 70 70 70 70 70 70 70 71 71 70 70 70 70 70 70 71 71 72 72 72 72 72 72 73 73 73 73 72 72 73 73 73 73 72 72 71 71 72 72 72 72 72 72 69 69 70 70 61 61 62 62 63 63 64 64 65 65 66 66 66 66 67 67 68 68 69 69 70 70 70 70 70 70 71 71 71 71 70 70 71 71 72 72 71 71 72 72 72 72 71 71 71 71 70 70 70 70 71 71 65 65 66 66 66 66 66 66 66 66 66 66 67 67 67 67 68 68 65 65 65 65 65 65 65 65 64 64 61 61 57 57 58 58 58 58 58 58 58 58 58 58 56 56 57 57 57 57 57 57 57 57 53 53 52 52 53 53 54 54 55 55 56 56 57 57 57 57 58 58 59 59 60 60 61 61 61 61 61 61 62 62 62 62 61 61 62 62 63 63 62 62 63 63 63 63 62 62 62 62 61 61 61 61 62 62 62 62 58 58 58 58 57 57 56 56 57 57 57 57 57 57 57 57 57 57 56 56 56 56 56 56 56 56 56 56 56 56 57 57 57 57 57 57 56 56 57 57 57 57 Notoriously,
0
|
||||||||
|
70 / 70 / 35
Регистрация: 06.07.2016
Сообщений: 415
|
||
| 10.02.2017, 20:11 | ||
|
1
|
||
|
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
|
|
| 10.02.2017, 20:30 [ТС] | |
|
Notoriously, ради интереса сделал руками. Проблема решилась, ура. Но настроение у меня упало, т.к. я всё ещё не понял, почему при использовании очередей она вылетает? STL контейнеры, их удобство - одна из главных причин, из-за которой я учусь кодить на плюсах. Неужели никто на этом сайте не сталкивался подобной ошибкой?
0
|
|
|
Вездепух
13241 / 6873 / 1827
Регистрация: 18.10.2014
Сообщений: 17,422
|
||||||||||||
| 10.02.2017, 21:08 | ||||||||||||
|
Добавлено через 14 минут
<= n?Добавлено через 8 минут Но входе 20, 2, 8, 15, 1 программа вылетает в pathRestore
x сравнивается cо start_y, а y со start_x. Что это за мешанина?
1
|
||||||||||||
|
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
|
||||||||
| 10.02.2017, 21:09 [ТС] | ||||||||
|
TheCalligrapher, читайте внимательнее главный пост.
Вот последняя версия кода со встроенными очередями. Пример данных, с которыми она вылетает : 20 15 14 7 8
0
|
||||||||
|
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
|
|||||||
| 10.02.2017, 21:18 [ТС] | |||||||
|
TheCalligrapher,
Не понимаю, зачем вам сдалась эта функция, если проблема не в ней, ну да ладно. Изменил строчки 23, 24 и чуток переделал pathRestore. Теперь функция pathRestore здесь точно такая же, как и в рабочей программе, без встроенных очередей.
0
|
|||||||
|
Вездепух
13241 / 6873 / 1827
Регистрация: 18.10.2014
Сообщений: 17,422
|
||||||||||||||||||||||||
| 10.02.2017, 21:46 | ||||||||||||||||||||||||
Сообщение было отмечено SaynorPRO как решение
РешениеpathRestore из-за явной ошибки в pathRestore. О каком "проблема не в ней" может идти речь?Проблем разного рода в вашем коде много. ---- В horseStep к чему вот это вот
pathY. На работоспособность это "не влияет", ибо pathRestore проверяет только x, но все же дичь налицо.---- В horseStep что вот это за странная проверка
Роль этой проверки уже взял на себя массив used. Либо продолжайте пользоваться used, тогда эта проверка ни нафиг не нужна, ибо условие будет всегда истинно. Либо выкиньте нафиг совершенно ненужный массив used и используйте вместо него pathX и/или pathY.---- В pathRestore за циклом
x == -2?Добавлено через 6 минут А n-то зачем было уменьшать? n - это размер. Его нет никаких причин вдруг уменьшать. Разве что только запутать читателя кода (меня - успешно запутали).
2
|
||||||||||||||||||||||||
|
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
|
||||||||||||
| 10.02.2017, 22:06 [ТС] | ||||||||||||
|
TheCalligrapher, сейчас всё объясню.
pathRestore я иду с конечной вершины, до начальной. Поэтому я просто пометил начальную вершину в массиве предков как -2. То есть, как только функция pathRestore, дойдёт до начальной вершины, переменные x и y получат значения -2(-2, потому что он изначально заполнен у меня как -1, -1 означает, что к клетке нету пути, я это проверяю в функции horseStep. Предрекаю вопрос "почему не ноль?". Ответ: ноль может быть координатой), выполнится проверка условия и произойдёт выход из цикла.
x, потому что у y будет такое же значение, так что разницы нету. Можете приписать && y != -2, разницы не будет. А можете вообще поменять проверку на y != -2, всё будет так же.Надеюсь всё понятно объяснил. На данный момент у меня появились новые проблемы. Вылетов с bad_alloc больше нет, но ответ программа выдаёт все равно неправильный. И тут у меня даже мыслей нету, как это можно исправить, потому что в версии программы с ручными очередями, всё то же самое, просто заменены очереди. Там всё работает идеально. Как я сказал ранее, по факту я заменил только очереди. Неужели я как-то криво обрабатываю встроенные очереди? Если хотите, я могу скинуть код рабочей версии программы, чтобы вы убедились в моих словах. Кстати, условие в строке 76 можно убрать, оно не нужно, я проверил. Добавлено через 8 минут TheCalligrapher,
0
|
||||||||||||
|
Вездепух
13241 / 6873 / 1827
Регистрация: 18.10.2014
Сообщений: 17,422
|
|||||||||
| 10.02.2017, 22:46 | |||||||||
Сообщение было отмечено SaynorPRO как решение
РешениеpathX и pathY играют в вашем алгоритме. Речь идет лишь о том, что в ваше коде содержится бессмысленное двойное присваивание
Если проследить эволюцию этого места в вашем коде, то очевидно, что вы уже обращали на это место внимание. Но разглядеть ляп все равно не смогли. Это, кстати, лишний повод упомянуть, что вместо того, чтобы плодить независимые массивы pathX и pathY для X и Y надо было не полениться, а завести структуру - пару { x, y } - и хранить ее уже в одном-единственном массиве path.used проверка pathX и pathY на -1 в функции horseStep - совершенно бессмысленна. Эта проверка всегда истинна, ибо проверку на "уже посещенность" клетки у вас возложена на массив used. До тех пор, пока эта задача возложена на массив used, никакого смысла в инициализации ваших массивов pathX и pathY значением -1 нет и никакого смысла в проверке на -1 тоже нет. Вы можете вообще изначально не инициализировать pathX и pathY - оставить там мусор - и убрать из кода ненужную проверку на -1. На работоспособность программы это не повлияет.Либо выкиньте массив used вообще, а проверку посещенности клетки делайте через pathX и pathY. Тогда изначальная инициализация -1, разумеется, нужна. (Я так понимаю, что вы уже так и сделали.)0. То есть при размере массива N допустимыми являются индексы от 0 до N-1. То есть размер всегда на 1 больше, чем максимально допустимый индекс. И проверка на попадание в диапазон допустимых индексов выглядит как 0 <= i && i < N. Обратите внимание на строгое сравнение во втором случае. Это то, к чему мы привыкли в С++. Так было всегда. Поэтому при переходе от индексации с 1 к индексации с 0 из индексов вычитается 1, но из размера ничего никогда вычитать не надо. Вы же вычли из размера 1, и проверка на правильность индекса у вас приобрела вид 0 <= i && i <= N. Это вызывает справедливое недоумение: зачем из размера вычли 1? Если размер доски 8, то он и в Африке 8, независимо от выбранного способа индексации. Почему вдруг в N оказалось 7?Кому-то, возможно, в такой ситуации больше нравится работать не с размером, а с максимальным индексом. Тогда все становится на свои места - действительно из максимального индекса надо вычесть 1, и действительно проверка на попадание в диапазон будет выглядеть как 0 <= i && i <= max. Но тогда лучше не называть его n, а назвать его, например, max_i или еще что-то в этом роде. А n - скорее имя для размера, а не для индекса.
1
|
|||||||||
|
11 / 11 / 5
Регистрация: 05.10.2016
Сообщений: 122
|
||||||||
| 10.02.2017, 23:43 [ТС] | ||||||||
|
TheCalligrapher,
pathX, а pathY.Что же в итоге. Я случайно переделал очередь не в очередь, а в стек. Самое интересное, что он вроде как выдаёт адвекватный ответ(как оказалось - не совсем, до клетки он доходит, но путь - не кратчайший). Я допускаю ужасные ошибки - я знаю. Но я программирую чуть больше полугода, а на плюсах - хорошо если месяц будет, хотя то что я не заметил в упор, что сделал это бессмысленное присваивание - это не зависит от опыта программирования, тут моя рассеянность сыграла роль. Однако, в конце концов, я исправил все недочёты и теперь могу с уверенностью сказать, что программа на 100% работоспособная(чекер полностью засчитал). Корень проблемы оказался не в функции horseStep, а в pathRestore. Скорее всего, из-за своей уверенности в том, что ошибка в horseStep(уже не помню, на основе чего я вынес это решение), я даже и мысли не допускал, что может быть по другому. Огромное спасибо всем, кто ковырялся в моём коде и пытался помочь. В частности спасибо TheCalligrapher и likehood, за проявленное внимание к чужой проблеме. Полностью работоспособный код
0
|
||||||||
|
Вездепух
13241 / 6873 / 1827
Регистрация: 18.10.2014
Сообщений: 17,422
|
||
| 11.02.2017, 00:07 | ||
|
И чтобы этот принцип работал правильно, т.е. чтобы волна расходилась от стартовой точки равномерно во все стороны, нам необходимо придерживаться следующего правила: чем раньше волна достигла некоей точки, тем раньше она должна пройти через эту точку дальше. Именно это обуславливает необходимость использования именно очереди (FIFO), а не стека (LIFO) и именно это дает нам "поиск в ширину". Если заменить очередь стеком, то мы получим алгоритм псевдо-"поиска в глубину". Этот алгоритм будет находить какой-то путь от старта к финишу, но совершенно не обязательно кратчайший.
1
|
||
| 11.02.2017, 00:07 | |
|
Ошибка std::bad_alloc Ошибка std::bad_alloc Ошибка: terminate called after throwing an instance of 'std::bad_alloc' Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|