|
|
« Предыдущая тема | Следующая тема » |
Опции темы | Опции просмотра |
|
|
|||||
блогер
Регистрация: Oct 2005
Адрес: Днепродзержинск - город Брежнева и других логопедов
Сообщений: 1,421
Записей в блоге: 4
|
Ну смотрите, что вам по минимуму нужно:
на первом проходе: загнать в стек, достать след. элемент (не лучше 2-х присваиваний) на втором проходе: достать из стека (и присвоить текущий элемент тому, что достали), присвоить след. элемент (не лучше 2-х присваиваний). Т.е. по сути то же + работа со стеком и два прохода зачем-то.
__________________
Бобры отвечают на вопросы не потому, что знают на них ответы; они отвечают потому, что их спрашивают. |
|
|||||
Реализация и тесты двунаправленного списка
http://jacksondunstan.com/articles/1288
__________________
משיח לא בא משיח גם לא מטלפן |
|
|||||
Регистрация: Apr 2010
Сообщений: 219
|
alatar, означает ли это, что в некоторых случаях есть смысл преобразовать Vector в Array (в зависимости от предполагаемого действия)? Или я не уловил мысль?
Понятно что вряд ли кто будет этим заниматься в реальном проекте, вопрос скорее академический. Хотя... |
|
|||||
Modus ponens
|
-De- Да ну блин, смысл в том, что ответ на вопрос предполагал более абстрактное мышление (моя реализация только попытка показать, что имелось в виду, я же сразу же написал, что во флеше она не будет наверняка самой оптимальной). Смысл в том, что у задачи есть универсальное решение не привязаное к конкретному языку. Т.е. переносимое между языками - вот уже подробности реализации экзаменирующийся / экзаменатор мог бы даже и не знать. Наверное лучше было изначально задать вопрос типа "объясните без того, чтобы писать код"...
Там тест не отражает реальное положение вещей. Главная разница между вектором и массивом заключается в том, что вектор, это "настоящий" массив. Т.е. если вы создали его длины 100, то он и выделил под 100 элементов 100 * sizeof ( тип массива ). А массив во флеше, это очень такой загадочный зверь, т.е. если вы, например будете заполнять индексы массива не с 0 а с 1, то вы по факту будете делать то же самое, что и . Соответственно, в зависимости от ситуации выделение памяти может сильно отличаться для обоих типов при в принципе похожих исходных значениях. Кроме того, естественно что скорость доступа / чтения / записи будет отличаться ну и т.п.
__________________
Hell is the possibility of sanity |
|
|||||
блогер
Регистрация: Oct 2005
Адрес: Днепродзержинск - город Брежнева и других логопедов
Сообщений: 1,421
Записей в блоге: 4
|
Я писал про максимально абстрактный вариант в #25
Какого из действий не будет в максимально абстрактном варианте? 1) пуш в стэк 2) поп из стэка 3) шаг по "старому" списку 4) установка следующего элемента в новом списке Или какое-то из них не будет вызывать присваивание? Или какие-то можно обьединить, не добавив при этом ещё одного присваивания? Или моё решение не переносится на какой-то язык?
__________________
Бобры отвечают на вопросы не потому, что знают на них ответы; они отвечают потому, что их спрашивают. |
|
|||||
Modus ponens
|
Да, не переносится, например функциональные языки без побочных эффектов не разрешают разрушающее присваивание (Scheme / ML / Erlang). Но не в этом же суть... абстракция - это когда вы множество разнообразных явлений объединяете по какому-то сходному для всех принципу, и этот же принцип можно назвать абстракцией. Тоесть, ответ заключался в том, что нужно список положить в стек, а потом оттуда забрать. Как именно вы это будете делать - это конкретика (т.е. противоположность абстракции). Кроме того, любое конкретное оптимальное решение будет реализацией единственного абстрактного решения.
__________________
Hell is the possibility of sanity |
|
|||||
блогер
Регистрация: Oct 2005
Адрес: Днепродзержинск - город Брежнева и других логопедов
Сообщений: 1,421
Записей в блоге: 4
|
А сделать новый список, цепляя в его начало элементы старого по порядку (такая вот абстракция) - можно на функциональщине?
Ну блин, не нужен стэк. О(1) оно должно памяти жрать. Иначе как-то стыдно про оптимальность говорить.
__________________
Бобры отвечают на вопросы не потому, что знают на них ответы; они отвечают потому, что их спрашивают. |
|
|||||
Modus ponens
|
так это и будет использованием стека... Т.е. к чему я это говорю: в разных языках самая оптимальная реализация может быть разной (т.как реализация самих языков разная), но есть общее правило, которое абстрактно описывает оптимальный случай решения рассматриваемой задачи.
__________________
Hell is the possibility of sanity |
|
|||||
Регистрация: Jul 2008
Сообщений: 912
|
Вот есть несколько задач с АСМ ICPC 2011. Как можно такое решать, ещё и за короткое время.
Последний раз редактировалось Sintesis; 16.07.2011 в 16:11. |
Часовой пояс GMT +4, время: 21:39. |
|
« Предыдущая тема | Следующая тема » |
|
|