Собственно, чтобы не плодить множество тем, хотелось бы создать одну, где люди могут выкидывать удавшиеся и не очень решения, дабы мудрые Анонимусы их исправляли, указывали на ошибки, на неточности и попросту на быдлокод…
Итак, начну.
Задача звучит так: в матрице NxN найти наименее весомый путь из точки 1;1 до точки N;N. дополнение(автор снубил): ходить можно только направо и вниз. Вывести путь…
//dumpz.org/16541/
Задача решена, но что-то мне подсказывает, что не наилучшим способом. Кому делать нечего – покурите…
5 февраля 2010 в 17:02
спасибо за ответы.)
5 февраля 2010 в 13:01
Вообще, я что-то слабо себе представляю участок кода, который "работает быстро, но нифига не ясно как".
И, да. Экономить на спичках никогда (или почти никогда) не надо.
5 февраля 2010 в 12:04
Для этого еще существуют такие замечательные вещи, как комментарии.
Вообще код должен быть прозрачным. Не помню точно кто (но кто-то из гуру) писал, что код надо создавать так, будто его потом будет поддерживать неуравновешанный маньяк, который чуть что готов порезать и съесть (ну это в вольной интерпретации, конечно).
5 февраля 2010 в 12:04
Это место критично с точки зрения быстродействия? Если нет, то однозначно пониманию. Если да – то тоже пониманию, но можно сразу написать и альтернативную "быструю" версию.
Оптимизация необходима не всегда и, как правило, уже после написания программы.
А вы запишите ход решения в комментариях. Они для того и нужны.
5 февраля 2010 в 8:03
возник вопрос: если стоит выбор между быстродействием и пониманием, чему отдавать предпочтение?
всякие Павловские пишут, что однозначно второму…
в самом деле, я знаю, как написать так, чтобы это было красиво, но не знаю, как это объяснить даже самому себе после того, как забуду ход решения…
31 января 2010 в 20:03
а есть же дефолтная "sizeof(xxx)"…
я всегда писал макросами)
спасибо)
31 января 2010 в 20:02
Если не ошибаюсь, да, в файле limits.h живет.
31 января 2010 в 20:01
С учетом же дополнения, на мой взгляд, ваш алгоритм вполне удачен. Единственное – раз уж вы выделяете массив на N+1, можете заполнить нулевую строчку и нулевой столбец INT_MAX-ами, что позволит вам избавиться от большинства специальных случаев с проверками на первый столбец или первую строку.
31 января 2010 в 20:01
не додумался. он есть как константа? так и называется "INT_MAX"?
31 января 2010 в 20:00
#19, к сожалению, это не гарантируется. К примеру, MS Visual Studio 2010 Beta 2, по отзывам судя, это еще не поддерживает, не знаю про более поздние версии.
Официально это называется variable-length array, чтобы вам удобнее искать было.
31 января 2010 в 20:00
я под g++ собираю, даже не знаю, какие там в мягком компиляторы(
спасибо.)
31 января 2010 в 19:05
да, забыл, в условии:
можно ходить только вниз и направо
31 января 2010 в 19:05
#17, спасибо за ответ. думаю, на большинстве современных машин он реализован.
31 января 2010 в 19:05
хотя туплю, что "думать", покурю гугл
31 января 2010 в 19:04
#9. Ответ №1: эта возможность появилась только в стандарте C99, который до сих пор реализован далеко не везде. Если требуется совместимость с более старым C89 или с компиляторами, не поддерживающими массивы переменной длины, их использовать не следует.
31 января 2010 в 19:02
#13, ну это не то, ты меня не совсем понял.)
#14, спасибо, хорошый ссыль.
#9 намекает какбе, что код у меня плохой, а алгоритм неверный. правда почему, так и не объяснил)
31 января 2010 в 19:02
Потому что я задам матрицу вида
1 100 1 11
1 100 1 100 1
1 100 1 100 1
1 100 1 100 1
1 11 100 1
Здесь самый дешевый путь – змейкой, но ваша программа его не найдет – она не умеет ходить вверх и влево.
31 января 2010 в 19:00
№9 хороший код комментирует сам себя
31 января 2010 в 17:02
//algolist.manual.ru/
31 января 2010 в 17:01
P.S.: называние себя быдлокодером, так же как и называние себя мего програмистом – две крайности одной сущности
P.P.S.: собрал для тебя немного ссылок для начала:
//www.wasm.ru
//www.rsdn.ru
//www.gamedev.ru
//www.uninformed.org (немного узкоспециализированно)
fprog.ru
31 января 2010 в 17:00
2 Александр Лищенер
Хочешь стать програмистом? Перестань сидеть фконтакте.
Иди на форумы где сидят люди с большим опытом.
Учись у НИХ, а не ЗДЕСЬ
31 января 2010 в 14:03
> чтобы указывали на МОИ ошибки
Ну алгоритм уже изначально неверный, и это первая и последняя ошибка.
> в коде очень не хочется ковыряться
+1
Особенно в котором ни одного коммента нет даже.
31 января 2010 в 14:03
2МужикНеВКраснойКуртке
я знаю, про нуль. так удобнее, пока, по крайней мере.)
нет, структура менее удобна
ммм. задача у меня получилась. я просто выкинул код, чтобы всякий, кто хочет, мог на него полюбоваться, а кому совсем делать нечего – сказать мне, где можно было лучше)
так яснее?
кстати, вопрос №1.
вроде размеры массива должны быть константные, нет?
почему можно
int N;
int array[N];
?
31 января 2010 в 14:03
Денис, почему это алгоритм неверый О_о?
31 января 2010 в 14:02
#6 Да граф хранится как матрица смежности, просто я не совсем верно выразился))
31 января 2010 в 14:02
2МужикВКраснойКуртке.
В C массивы нумеруются с нуля.
И ещё, может результат хранить в struct {int x; int y;} result[N] ?
Ты скажи словами как ты делаешь, в коде очень не хочется ковыряться.
31 января 2010 в 14:00
#2
Интересно узнать.
А вы каким образом в программе граф храните, нежели не в матрице смежности?
Александр, код действительно лажовенький, точнее, велосипедный.
Сам когда-то писал такое, используя алгоритм Дейкстры, как справедливо и верно заметил Максим.
На всякий случай, вот код (на чистых сях, правда):
//www.sadreamer.net/sources/show/9
31 января 2010 в 13:05
прошу администрацию забанить Антона, или Антона не дурить. это, конечно, смешно, но у всего есть свои пределы.
Максим, мне очень стыдно, но я не изучал делфи и о графах знаю только то, что они есть).
Дейстру покурю, спасибо…
31 января 2010 в 13:05
а вообще хотелось бы, чтобы указывали на МОИ ошибки, а не на возможные способы решения задачи
31 января 2010 в 13:04
Решал подобную задачу, толко у меня в задании был дан граф и нужно было найти минимальный путь к одной заданой вешины графа из всех остальных( в принципе матрицу можна представить в виде графа, так что задание оч похоже). Использовал алгоритм Дейкстры.Если будет нужно могу выложить и исходники (Delphi)