Этот баннер — требование Роскомнадзора для исполнения 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 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Aklinсуществует статический класс, который позже расширяется динамически. Код написанный Dremmm - это код на java. Там не существует никаких статических классов. Aklin = new Stack(); Это единственно место в коде, где происходит создание объекта класса "Stack". Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением. вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели. Aklin NotGonnaGetUs Это не шутка? :) что именно? Вот это: Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс , не понимая, что внутри происходит является огорчением. и это: Aklin вообще не вижу причин для использования стандартного класса , если можно написать самому под свои цели. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2006, 19:01 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Просто трёп. Рассуждаем логически. Если нам нельзя сохранять эл-ты, то мы обязаны вернуть его в очередь. Если очередь содержит произвольные эл-ты, то маркер невозможен. и подсчёты, хеши и т.п. Итого задача не может иметь решения. Как можно узнать конец очереди, если все эл-ты и хранятся в ней, т.е там всегда N-1 эл-т точно есть. А для программистов вроде Aklin: для кого stl писали? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.09.2006, 20:53 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
NotGonnaGetUs Aklinсуществует статический класс, который позже расширяется динамически. Код написанный Dremmm - это код на java. Там не существует никаких статических классов. получается, что все переменные на яве под static? если это оябязательно, то дадно. NotGonnaGetUs Aklin = new Stack(); Это единственно место в коде, где происходит создание объекта класса "Stack". в си это второе создание: первое в Stack st1; и второе st1 = new Stack(); NotGonnaGetUs Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением. вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели. Aklin NotGonnaGetUs Это не шутка? :) что именно? Вот это: Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс , не понимая, что внутри происходит является огорчением. а что вам не нравится в использовании своих классов, оссобенно если их всегда можно переписать? в т.ч. для быстродействия в узких моментах? NotGonnaGetUs Aklin вообще не вижу причин для использования стандартного класса , если можно написать самому под свои цели. еще раз подписался. стандартные классы я разве что в MFC использовал. да и то потому, что там все линки на DLL указывают... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 08:49 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Aklin получается, что все переменные на яве под static? если это оябязательно, то дадно. Неа, получается, что в java поля класса могут быть объявлены как статик, а могут и нет. Aklinа что вам не нравится в использовании своих классов, оссобенно если их всегда можно переписать? в т.ч. для быстродействия в узких моментах? Затем, что всё уже написано и нет никакого смысла (разве что со скуки) переписывать стандартные вещи. Называется это повторным использованием кода и позволяет ускорить процесс разработки и интеграцию кода написанного разными людьми... Aklin еще раз подписался. стандартные классы я разве что в MFC использовал. да и то потому, что там все линки на DLL указывают... Ок. Я понял. С++ это мир, где законы разума действуют по другому, в силу объективного отсутствия стандартов :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 11:29 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
NotGonnaGetUs Aklin получается, что все переменные на яве под static? если это оябязательно, то дадно. Неа, получается, что в java поля класса могут быть объявлены как статик, а могут и нет. тогда не понимаю, зачем там указывал статик, если можно нормально. ведь 1 раз объявляется. и для 1 класса, а не 1 для всех??? NotGonnaGetUs Aklinа что вам не нравится в использовании своих классов, оссобенно если их всегда можно переписать? в т.ч. для быстродействия в узких моментах? Затем, что всё уже написано и нет никакого смысла (разве что со скуки) переписывать стандартные вещи. Называется это повторным использованием кода и позволяет ускорить процесс разработки и интеграцию кода написанного разными людьми... невероятно часто, то что написано не удолетворяет всем условиям. поэтому легче переписать (оссобенно, что всегда есть исходики си++.) NotGonnaGetUs Aklin еще раз подписался. стандартные классы я разве что в MFC использовал. да и то потому, что там все линки на DLL указывают... Ок. Я понял. С++ это мир, где законы разума действуют по другому, в силу объективного отсутствия стандартов :) стандарты - анси си и анси си++ в них есть незаменимые библиотеки, да и все. остатьное не в стандарте и приписывается кем угодно когда угодно. в си программеры почти всегда дают исходники на свои библиотеки, так что и приписать к ним можно все, что угодно. а вот закрытые бибилиотеки (DLL) - другое дело (MFC например) там только интерфейс. и невозможно ничего приписать или переделать под себя. а остальное открыто полностью. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 11:39 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
не читал: флуд. Есть вероятностный метод. Засунуть в очередь длинную случайную последовательность. Прогнать очередь из переда в зад 100 раз, смотря за своим маркером. По ходу прогона первого маркера можно строить второй, которого нет в очереди. Можно повторить прогон со вторым маркером. Вероятность ошибиться будет мала. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 13:16 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
количество маркеров можно увеличивать, уменьшая вероятность ошибки. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 13:18 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
maXmoПрогнать очередь из переда в зад 100 раз Если есть такая возможность, не нужно никаких вероятностей. Весь вопрос в том, как определить, "прогнали мы сто раз" или все еще в середине первого раза, а в очереди сам по себе кучу раз встречается наш маркер. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 13:28 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarer maXmoПрогнать очередь из переда в зад 100 раз Если есть такая возможность, не нужно никаких вероятностей.и как? softwarerВесь вопрос в том, как определить, "прогнали мы сто раз" или все еще в середине первого разапод количеством раз разумеется имеется в виду количество выловленных маркеров (между маркерами одинаковое количество элементов). softwarerа в очереди сам по себе кучу раз встречается наш маркер.чем длиннее маркер, тем меньше вероятность. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 13:56 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
maXmoи как? Если есть возможность "промотать всю очередь", нетрудно выбрать маркер, не встречающийся в очереди. just for example, при "промотке" подсчитать максимальное количество идущих подряд нулей, после чего выбрать маркером N+1 ноль. Но проблема в том, что маркер нужно выбирать изначально, когда про очередь ничего не известно. maXmoчем длиннее маркер, тем меньше вероятность. Чем длиннее очередь, тем больше вероятность :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 14:24 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Aklin тогда не понимаю, зачем там указывал статик, если можно нормально. ведь 1 раз объявляется. и для 1 класса, а не 1 для всех??? Cамое первое предложение в http://sql.ru/forum/actualthread.aspx?tid=338438&pg=1#3147471 ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 14:43 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarerНо проблема в том, что маркер нужно выбирать изначально, когда про очередь ничего не известно.то есть получается, нет детерминированного способа промотать именно всю очередь. Только запихивать маркер и смотреть, когда он вылезет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 15:54 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarerЧем длиннее очередь, тем больше вероятность :)длина очереди / (2^длина маркера в битах) сравнил линейный рост и экспоненциальный :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 15:59 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
или решения нет или задача не верна ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.09.2006, 17:08 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
для полной картины напишу цифирки для своего метода. Для очереди длиной 4ЭБ (2^60 интов) и маркера длиной 16 байт (2^128 значений) имеем вероятность облажаться около 2^(-68) < 10^(- 20 ). Имхо, более чем приемлемо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 11:22 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Да полноте. При этих исходных данных элементарно строится пример ситуации, в которой вероятность не облажаться столь мала, что честно говоря лень считать (а калькуляторы с такой разрядностью не справляются). В практической задаче может быть и можно было бы согласиться с такой вероятностью, но в данном случае задача сугубо теоретическая. А в практическом направлении куда разумнее просто встроить в очередь метод GetLength :) - благо, он легко делается над любым артефактом доопределением методов enqueue/dequeue. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 12:22 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarerПри этих исходных данных элементарно строится пример ситуации, в которой вероятность не облажаться столь малану хотя бы в общих чертах набросай. Подстраивание под алгоритм генерации маркера? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 12:41 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
maXmoну хотя бы в общих чертах набросай. Подстраивание под алгоритм генерации маркера? Маркер - шестнадцать байт, то есть четыре int-а. В очереди используются только эти же четыре значения (означающие, допустим, "влево-вправо-вверх-вниз"). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 13:21 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
я забыл сказать про случайную генерацию маркера? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 13:56 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
оченку вероятности такого совпадения я привёл. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 13:57 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
то есть оценку :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 13:57 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
проще в казино джек-пот сорвать и не надо будет писать дебильную прогу :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 13:59 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
maXmoоченку вероятности такого совпадения я привёл. Давай предположим, что очередь инициализируется тем же генератором :)) P.S. Я понимаю, что спор сугубо беспредметный. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 14:49 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
1) поскольку это не оговорено, то содержание очереди имеет общий вид. А в общем виде содержание очереди не зависит от кода, определяющего её длину. Это не наглое предположение, это правило понимания условий задач (даже сугубо теоретических). Например, если рассмотреть задачу типа "машина едет по шоссе со скоростью 60км/ч, за какое время она проедет 60 км?", то если не оговорено, что водитель пьян и через минуту врежется в столб, то этого не произойдёт. 2) плюс работа генератора может зависеть от многих факторов типа состояния памяти компьютера; это уже вопрос обеспечения качества работы генератора. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 15:07 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
тогда придётся рассчитывать вероятность совпадения алгоритма заполнения очереди с алгоритмом генерации маркера. Тут я не возьмусь даже посчитать число степеней свободы :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 15:11 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
maXmoНапример, если рассмотреть задачу типа "машина едет по шоссе со скоростью 60км/ч, за какое время она проедет 60 км?", то если не оговорено, что водитель пьян и через минуту врежется в столб, то этого не произойдёт. Это неудачный пример, сейчас объясню почему. Если говорится "машина двигается со скоростью 60 км/ч", это означает именно "машина двигается со скоростью 60 км/ч (и это поведение не меняется по ходу дела)". При этом условии невозможно ответить на вопрос "на каком расстоянии от исходной точки окажется водитель машины через 1 час". Потому что, помимо прочего, пьяный водитель мог нечаянно выпасть из машины, и до тех пор, пока машина продолжает двигаться со скоростью 60 км/ч, нарушения условий задачи нет. Я не понимаю, что такое "очередь общего вида" применительно к введению некоторых дополнительных условий задачи. К примеру, каково распределение ее элементов: нормальное? равномерное? другое? величины повторяются? а может последовательность монотонна? итп. Если мы говорим о сугубо теоретических задачах, надо исходить из того, что есть, и не фантазировать. Если мы говорим о задачах на собеседовании, часто предполагается, что соискатель задаст уточняющие вопросы, если сочтет их существенными для решения задачи, либо предложит решение (варианты решения) с дополнительными оговорками, например "в таких-то условиях можно вот так". Но решать задачу, предполагая некий конкретный, не оговоренный условиями вариант, да еще и не выделяя этого - имхо в любом случае ошибка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 19:27 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
есть рабочее решение на основе определения периода маркера и кратных с ним коллизий. 1. пускаем маркер 2. определяем период его гарантированного появления 3. удаляем любой из них 4. проверяем повтор периода от данной позиции 5. если период есть, то подсчитываем кол-во то его нарушения 6. в точке нарушения востанавливаем маркер 7. удаляем маркер на кратной периоду позиции от текущей 8. всё ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 20:58 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
Den_di2. определяем период его гарантированного появления Нельзя ли поподробнее расписать вот этот пункт? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.09.2006, 21:26 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarer(и это поведение не меняется по ходу дела)про это ничего не сказано. softwarerК примеру, каково распределение ее элементов?любое из возможных. Это называется общий случай. softwarerНо решать задачу, предполагая некий конкретный, не оговоренный условиями вариант softwarerДавай предположим, что очередь инициализируется тем же генератором :))это имелось в виду? Проблема только в оговорке? Я уже писал, что детерминированного (работающего во всех случаях) решения с маркером нет (по крайней мере я так думаю). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.09.2006, 14:44 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
softwarerА в практическом направлении куда разумнее просто встроить в очередь метод GetLength :) а если реализация класса очереди закрыта? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.09.2006, 14:46 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
maXmo softwarerА в практическом направлении куда разумнее просто встроить в очередь метод GetLength :) а если реализация класса очереди закрыта? Хм. Вариант 1: доопределить в наследнике методы Enqueue/Dequeue Вариант 2: если они вдруг невиртуальные, сделать прокси-класс, обертку. Хватит? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.09.2006, 21:25 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
обёртки не помогут, если очередь приходит в готовом виде (напр., из другого модуля) (то есть обёртка столкнётся с той же самой проблемой определения длины очереди), а если очередь формируешь сам, то и никакие обёртки не нужны :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.09.2006, 11:23 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
maXmoобёртки не помогут, если очередь приходит в готовом виде (напр., из другого модуля) На этот случай есть третий и четвертый варианты :)) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.09.2006, 12:54 |
|
||
|
Задача: измерить длинну очереди, не используя массивов
|
|||
|---|---|---|---|
|
#18+
пиво с начальником? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.09.2006, 13:25 |
|
||
|
|

start [/forum/topic.php?all=1&fid=16&tid=1346569]: |
0ms |
get settings: |
11ms |
get forum list: |
20ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
64ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
112ms |
get tp. blocked users: |
2ms |
| others: | 258ms |
| total: | 488ms |

| 0 / 0 |
