Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Есть конечная очередь, состоящая из элементов типа int. Необходимо узнать длину очереди, используя команды push, pop(сообщает также об отсутствии элементов в очереди), не используя выделение дополнительной памяти, а именно массивов, которые будут дублировать содержимое очереди. при этом очередь должна сохранить первоначальный вид, т.е. элементы должны находится в не в той же последовательности, что и до определения ее длинны. Единственное решение которое приходит на ум: "Скачать" все элементы в String, а потом восстановить очередь, но по условию элементы очереди не должны дублироваться, может у нее нет решения? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 09:08 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
DremmmЕдинственное решение которое приходит на ум: Плохо :( Стопроцентная задача на маркер. Dremmmможет у нее нет решения? Я практически уверен, что в условиях задачи есть какое-нибудь маленькое дополнительное условие - например, все "элементы очереди различны" или "неотрицательны" или что-нибудь в этом роде. Если нет - надо пошевелить мозгами. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 09:18 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Условие задачи "слово в слово". Самое первое что пришло на ум, добавить "свой int", брать первый элемент, увеличивать счетчик на 1, и возвращать этот элемент в очередь, пока не дойду до моего intа, но если в очереди уже есть "мой элемент"? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 09:25 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Слово в слово? Любопытно. Хотя формулировка не очень четкая. Я вижу нечестное решение: воспользоваться рекурсивной функцией. При этом явного выделения памяти и массовов не будет. Функцию надо будет вызвать дважды (поскольку она будет переворачивать очередь, второй раз - чтобы вернуть элементы в начальный порядок). Что же до честных решений, то это должен быть именно маркер, то, что Вы назвали "свой int". Но тут есть ключевой аспект, в решаемости которого я сходу не уверен: как определить, что очередь прокручена до конца. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 10:59 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarerСлово в слово? Любопытно. Хотя формулировка не очень четкая. Я вижу нечестное решение: воспользоваться рекурсивной функцией. При этом явного выделения памяти и массовов не будет. Функцию надо будет вызвать дважды (поскольку она будет переворачивать очередь, второй раз - чтобы вернуть элементы в начальный порядок). Что же до честных решений, то это должен быть именно маркер, то, что Вы назвали "свой int". Но тут есть ключевой аспект, в решаемости которого я сходу не уверен: как определить, что очередь прокручена до конца. а как узнать что ты перевернул всю очередь? без ее дублирования ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 11:21 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Решение static Stack stack = new Stack(); public static int Task1(Stack stack) { if (!(stack.empty())) { Integer i = (Integer) stack.pop(); int j = Task1(stack); stack.push(i); return ++j; } else { return 0; } }; public static void main(String[] args) { stack.push(5); stack.push(3); stack.push(10); int count = Task1(stack); } ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 11:32 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Dremmmstatic Stack stack = new Stack(); Дык в условии очередь или стек? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 11:35 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Dremmmа как узнать что ты перевернул всю очередь? В рекурсивной функции-то? По признаку пустоты очереди. Dremmmбез ее дублирования Говорю же, в формулировке задачи дырка, допускающая нечестное решение. По сути дублирование есть, но оно неявное, без массивов и подобных структур данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 11:36 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarer Dremmmstatic Stack stack = new Stack(); Дык в условии очередь или стек? это зависит только от типа входа. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 15:01 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
что-то не очень понятно. у нас есть класс List (пусть это очередь), мы не знаем его структуры и имеем доступ только к ф-циям push(type) и pop(type).И пусть ф-ция вернёт zero, если всё выбрано. догда для очереди 2-3-5-3-4 после выборки и записи будет: 4-2-3-5-3 3-4-2-3-5 ... 2-3-5-3-4 теперь осталось как-то понять, что очередь пройдена полностью. для этого можно использовать маркер. (хотя и не всегда работает). или отправить в плавание помеченный элемент и ждать, пока он не всплывёт. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 15:23 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Aklinэто зависит только от типа входа. Это принципиальное условие в силу требования неизменности данных. Если для очереди решение может и существовать, то для стека честное решение (то есть использующее O(1) памяти кроме собственно данных стека) явно невозможно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.09.2006, 21:30 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarer Aklinэто зависит только от типа входа. Это принципиальное условие в силу требования неизменности данных. Если для очереди решение может и существовать, то для стека честное решение (то есть использующее O(1) памяти кроме собственно данных стека) явно невозможно. вроде как: стек: A<-B<-C<-...<-Last(==Head) новый эл-т добавляется перед Head и перенос послденей вправо A<-B<-C<-...<-Last<-NEW(==Head) pop берет Head + переносит ее влево A<-B<-C<-...LastChild<-Last(==Head) A<-B<-C<-...<-LastChild(==Head) очередь: нужно еще не потерять Tail A(==Head)<-B<-C<-...Last(==Tail) новый эл-т добавляется после Head и перенос послденего влево NEW(==Head)<-A<-B<-C<-...Last(==Tail) pop берет из Tail+ перенос хвоста влево A(==Head)<-B<-C<-...LastChild<-Last(==Tail) A(==Head)<-B<-C<-...LastChild(==Tail) если использовать "ручную" очередь + убрать удаление эл-та, то реально сделать, используя только 1 буфер. если использовать "стандартный" класс то надо копаться в классе, но вручную будет все-равно проще. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.09.2006, 11:23 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Aklinвроде как: Нет. Очередь - это черный ящик с методами enqueue/dequeue и соблюдающимся принципом FIFO. Стек - это черный ящик с методами push/pop и соблюдающимся принципом LIFO. Не более того. Если "делать ручную очередь" или "копаться в классе", задача не имеет смысла, потому что тогда длина очереди известна (например, в Вашей терминологии - tail - head + 1). Алгоритмические задачи такого рода ставятся только на использование интерфейса объекта (при этом, зная производительность операций, мы можем рассуждать о производительности алгоритма). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.09.2006, 12:19 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarer Aklinвроде как: Нет. Очередь - это черный ящик с методами enqueue/dequeue и соблюдающимся принципом FIFO. Стек - это черный ящик с методами push/pop и соблюдающимся принципом LIFO. Не более того. вы вручную хоть раз очередь строили? это не черный ящик, если знать начало очереди, а вполне нормальный элемент. и работать с ним просто.(можно написать класс для простоты) softwarer Если "делать ручную очередь" или "копаться в классе", задача не имеет смысла, это почему? если у вас динамическая очередь (т.е. сразу не знаешь, сколько добавлено, удалено, и т.д.) то вполне нормально softwarer потому что тогда длина очереди известна (например, в Вашей терминологии - tail - head + 1). Нет. и Head и Tail - лишь указатели на динамически выделяемые структуры, и между выделениями 2х такихструктур может выделятся сколько угодно другой памяти, не имеющей отношения к очереди softwarer Алгоритмические задачи такого рода ставятся только на использование интерфейса объекта (при этом, зная производительность операций, мы можем рассуждать о производительности алгоритма). какого объекта? стандартного класса? так можно свой написать, там мало строк будет. и не только интерфейс, еще и эффективность сами определите. очень многие пишут свои менеджеры памяти для уменьшения количества занимаемой памяти, но при этом о фактическом сборе мусора речи не идет. также приходится все вручную удалять. не вижу ничего тяжелого написать свою очередь ручками и узнать ее размер используя лиш 1 указатель + 1 long например FIFO и LIFO полностью работают на моей схеме выше. и все жы: почему черный ящик-то? или кроме стандартов вы не делали ничего? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.09.2006, 13:29 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
special for you: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.09.2006, 14:00 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
аналогично пишется очередь + перегрузкой операторов дибиваемся -слиянием стеков -проверка на равенство(> или < или <= и др) -доступ к элементу по [] -и т.д. -добавление элементов: MyStackVar += 150; -или + = либо слияние, либо добавление, -или - = вычитание (удаление последнего эл-та) такой же класс (без перегузки операторов) я проводил даже в VB! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.09.2006, 14:04 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Дык ясно же написано что есть две веревки за которые можно дергать push, pop куда вы лезете с реализацией очереди!!!! Повторю softwarer: Очередь - это черный ящик при доступе внутрь класса узнать длину очереди не было бы вообще проблемой а с рекурсией действительно нечестно, память выделится в стеке... хотя и без явного выделения а хотя.... автор"Скачать" все элементы в String, а потом восстановить очередь, но по условию элементы очереди не должны дублироваться , может у нее нет решения? написано же ЭЛЕМЕНТЫ не должны дублироваться)) все честно с маркером тода, если элементы уникальные, прокрутить один раз в цикле, задача то учебная ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.09.2006, 23:28 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Aklin вы вручную хоть раз очередь строили? это не черный ящик, если знать начало очереди, а вполне нормальный элемент. и работать с ним просто.(можно написать класс для простоты) А вы хоть раз слышали про черный ящик и интерфейс? Нормально реализованная очередь - это классический черный ящик ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.09.2006, 23:31 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Mike_za Aklin вы вручную хоть раз очередь строили? это не черный ящик, если знать начало очереди, а вполне нормальный элемент. и работать с ним просто.(можно написать класс для простоты) А вы хоть раз слышали про черный ящик и интерфейс? Нормально реализованная очередь - это классический черный ящик черный ящик для вас, или черный ящик как хорошо организованный и не дающий сбоев механизм? я вообще не люблю черных ящиков, за исколючением: нормально сделанный и открываеюмый в любой момент. про рекурсию: а с чего вы взяли, что при pop память в очереди не уменьшается. вы ведь забераете эл-т? нормально реализованный "ящик" по рекурсии даст вполне нормальный результат. также можно удаять из 1го, а добавлять во 2ой. память - только на 1 буфер. Special 4u: черный ящик + использование не более O(sizeof(vartype)) доп. места. (добавьте к тому, что я раньше написал, и используйте вышеописанный класс как "черный" ящик) Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2006, 11:20 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Aklinчерный ящик для вас, или черный ящик как хорошо организованный и не дающий сбоев механизм? Черный ящик - вполне однозначное понятие, "или" здесь неуместно. Подробности - в словаре. Aklinя вообще не люблю черных ящиков, Понимаю. А получая двойку по матану, не говорили, что не любите матана? Aklinпро рекурсию: а с чего вы взяли, что при pop память в очереди не уменьшается. Мы не "взяли". Это "неизвестно". Aklin вы ведь забераете эл-т? нормально реализованный "ящик" по рекурсии даст вполне нормальный результат. Чушь. Нормально реализованный ящик может как экономить время за счет памяти, так и наоборот. В определение очереди не входят условия на логику управления памятью. Aklinтакже можно удаять из 1го, а добавлять во 2ой. Что явно противоречит условию задачи. Такое впечатление, что Вы совсем не думаете, что пишете, лишь бы возразить. Да и по приведенному Вами коду видна.. поспешность. AklinSpecial 4u: черный ящик + использование не более O(sizeof(vartype)) доп. места. Хм. Контрольный вопрос: чем написанное Вами отличается от O(1)? Aklin (добавьте к тому, что я раньше написал, и используйте вышеописанный класс как "черный" ящик) unsigned int Lenn(MyStack<T> &m) { T l; unsigned int len=0; l = m.Pop(); if( l==0 )return 0; len = Lenn( m )+1; m.Push( l ); return len; } Замечательно. Угадайте с трех раз, у кого из участников темы Вы позаимствовали это решение? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2006, 12:35 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarer Aklinчерный ящик для вас, или черный ящик как хорошо организованный и не дающий сбоев механизм? Черный ящик - вполне однозначное понятие, "или" здесь неуместно. Подробности - в словаре. черный ящик бывает разным. либо это неизвестный вам объект лишь с глобальными действиями, либо это ваш же объект, прикрытый для простоты последующей работы. softwarer Aklinя вообще не люблю черных ящиков, Понимаю. А получая двойку по матану, не говорили, что не любите матана? нет. черных ящиков я не люблю потому, что неизвестно что там + нельзя ничего дописать, а учитывая что переписать не так тяжело, то я переписал бы. softwarer Aklinпро рекурсию: а с чего вы взяли, что при pop память в очереди не уменьшается. Мы не "взяли". Это "неизвестно". вот установите, а потом говорите. мне все известно в моем коде. softwarer Aklin вы ведь забераете эл-т? нормально реализованный "ящик" по рекурсии даст вполне нормальный результат. Чушь. чушь == недопонимание? softwarer Нормально реализованный ящик может как экономить время за счет памяти, так и наоборот. поправка: если ящик не тривиальный. тогда никакой экономии. softwarer В определение очереди не входят условия на логику управления памятью. здесь речь не об определении softwarer Aklinтакже можно удаять из 1го, а добавлять во 2ой. Что явно противоречит условию задачи. Такое впечатление, что Вы совсем не думаете, что пишете, лишь бы возразить. Да и по приведенному Вами коду видна.. поспешность. поспешность - лишь от того, что это эде не первый раз делаю, и почти наизусть могу подобные классы писать. очень помогает. softwarer AklinSpecial 4u: черный ящик + использование не более O(sizeof(vartype)) доп. места. Хм. Контрольный вопрос: чем написанное Вами отличается от O(1)? если нечем - так получается, что я выполнил условие задачи? softwarer Aklin Замечательно. Угадайте с трех раз, у кого из участников темы Вы позаимствовали это решение? я не заимствовал, а показал, что даже из черного ящика такое возможно вытянуть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2006, 13:42 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Aklin Как вам удаётся не различать реализацию (односвязный список) и интерфейс (push/pop/empty) объекта (stack'a)? Aklin я не заимствовал, а показал, что даже из черного ящика такое возможно вытянуть. Чёрным ящиком было решение опубликованное Dremmm в пятом сверху сообщении? %) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2006, 16:20 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
NotGonnaGetUs Aklin Как вам удаётся не различать реализацию (односвязный список) и интерфейс (push/pop/empty) объекта (stack'a)? Push - добавление к очереди (стека) Pop - получение из очереди (стека) структура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением. да и односвязный список бывает либо очередь либо стек, а дальше только деревья... NotGonnaGetUs Aklin я не заимствовал, а показал, что даже из черного ящика такое возможно вытянуть. Чёрным ящиком было решение опубликованное Dremmm в пятом сверху сообщении? %) нашел, но: -использование статического стека? зачем? -стек был создан, зачем его еще раз пересоздавать? - в общем у меня то же но для моего класса. вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2006, 17:47 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Aklin -использование статического стека? зачем? "статического стека" не существует. автор сделал переменную содержащую сслыку на стек статической, чтобы к ней можно было обращаться из статического метода main... Aklin -стек был создан, зачем его еще раз пересоздавать? Где там пересоздаётся стек? Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением. вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели. Это не шутка? :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2006, 18:14 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
NotGonnaGetUs Aklin -использование статического стека? зачем? "статического стека" не существует. автор сделал переменную содержащую сслыку на стек статической, чтобы к ней можно было обращаться из статического метода main... существует статический класс, который позже расширяется динамически. NotGonnaGetUs Aklin -стек был создан, зачем его еще раз пересоздавать? Где там пересоздаётся стек? = new Stack(); NotGonnaGetUs Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением. вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели. Это не шутка? :) что именно? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2006, 18:27 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=33991526&tid=1346569]: |
0ms |
get settings: |
8ms |
get forum list: |
12ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
62ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
72ms |
get tp. blocked users: |
2ms |
| others: | 264ms |
| total: | 435ms |

| 0 / 0 |
