powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача: измерить длинну очереди, не используя массивов
60 сообщений из 60, показаны все 3 страниц
Задача: измерить длинну очереди, не используя массивов
    #33989102
Dremmm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Есть конечная очередь, состоящая из элементов типа int. Необходимо узнать длину очереди, используя команды push, pop(сообщает также об отсутствии элементов в очереди), не используя выделение дополнительной памяти, а именно массивов, которые будут дублировать содержимое очереди. при этом очередь должна сохранить первоначальный вид, т.е. элементы должны находится в не в той же последовательности, что и до определения ее длинны.

Единственное решение которое приходит на ум:
"Скачать" все элементы в String, а потом восстановить очередь, но по условию элементы очереди не должны дублироваться, может у нее нет решения?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33989136
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
DremmmЕдинственное решение которое приходит на ум:
Плохо :( Стопроцентная задача на маркер.

Dremmmможет у нее нет решения?
Я практически уверен, что в условиях задачи есть какое-нибудь маленькое дополнительное условие - например, все "элементы очереди различны" или "неотрицательны" или что-нибудь в этом роде. Если нет - надо пошевелить мозгами.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33989151
Dremmm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Условие задачи "слово в слово".
Самое первое что пришло на ум, добавить "свой int", брать первый элемент, увеличивать счетчик на 1, и возвращать этот элемент в очередь, пока не дойду до моего intа, но если в очереди уже есть "мой элемент"?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33989424
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Слово в слово? Любопытно. Хотя формулировка не очень четкая. Я вижу нечестное решение: воспользоваться рекурсивной функцией. При этом явного выделения памяти и массовов не будет. Функцию надо будет вызвать дважды (поскольку она будет переворачивать очередь, второй раз - чтобы вернуть элементы в начальный порядок).

Что же до честных решений, то это должен быть именно маркер, то, что Вы назвали "свой int". Но тут есть ключевой аспект, в решаемости которого я сходу не уверен: как определить, что очередь прокручена до конца.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33989505
Dremmm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
softwarerСлово в слово? Любопытно. Хотя формулировка не очень четкая. Я вижу нечестное решение: воспользоваться рекурсивной функцией. При этом явного выделения памяти и массовов не будет. Функцию надо будет вызвать дважды (поскольку она будет переворачивать очередь, второй раз - чтобы вернуть элементы в начальный порядок).

Что же до честных решений, то это должен быть именно маркер, то, что Вы назвали "свой int". Но тут есть ключевой аспект, в решаемости которого я сходу не уверен: как определить, что очередь прокручена до конца.
а как узнать что ты перевернул всю очередь? без ее дублирования
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33989558
Dremmm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решение

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);
}
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33989578
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dremmmstatic Stack stack = new Stack();
Дык в условии очередь или стек?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33989581
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dremmmа как узнать что ты перевернул всю очередь?
В рекурсивной функции-то? По признаку пустоты очереди.

Dremmmбез ее дублирования
Говорю же, в формулировке задачи дырка, допускающая нечестное решение. По сути дублирование есть, но оно неявное, без массивов и подобных структур данных.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33990532
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
softwarer Dremmmstatic Stack stack = new Stack();
Дык в условии очередь или стек?
это зависит только от типа входа.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33990644
Den_di
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
что-то не очень понятно.
у нас есть класс 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

теперь осталось как-то понять, что очередь пройдена полностью. для этого можно использовать маркер. (хотя и не всегда работает). или отправить в плавание помеченный элемент и ждать, пока он не всплывёт.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33991526
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklinэто зависит только от типа входа.
Это принципиальное условие в силу требования неизменности данных. Если для очереди решение может и существовать, то для стека честное решение (то есть использующее O(1) памяти кроме собственно данных стека) явно невозможно.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33991787
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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 буфер.

если использовать "стандартный" класс то надо копаться в классе, но вручную будет все-равно проще.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33991808
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklinвроде как:
Нет. Очередь - это черный ящик с методами enqueue/dequeue и соблюдающимся принципом FIFO. Стек - это черный ящик с методами push/pop и соблюдающимся принципом LIFO. Не более того.

Если "делать ручную очередь" или "копаться в классе", задача не имеет смысла, потому что тогда длина очереди известна (например, в Вашей терминологии - tail - head + 1). Алгоритмические задачи такого рода ставятся только на использование интерфейса объекта (при этом, зная производительность операций, мы можем рассуждать о производительности алгоритма).
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33991854
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
softwarer Aklinвроде как:
Нет. Очередь - это черный ящик с методами enqueue/dequeue и соблюдающимся принципом FIFO. Стек - это черный ящик с методами push/pop и соблюдающимся принципом LIFO. Не более того.


вы вручную хоть раз очередь строили?
это не черный ящик, если знать начало очереди, а вполне нормальный элемент. и работать с ним просто.(можно написать класс для простоты)
softwarer
Если "делать ручную очередь" или "копаться в классе", задача не имеет смысла,


это почему? если у вас динамическая очередь (т.е. сразу не знаешь, сколько добавлено, удалено, и т.д.) то вполне нормально
softwarer
потому что тогда длина очереди известна (например, в Вашей терминологии - tail - head + 1).

Нет. и Head и Tail - лишь указатели на динамически выделяемые структуры, и между выделениями 2х такихструктур может выделятся сколько угодно другой памяти, не имеющей отношения к очереди

softwarer
Алгоритмические задачи такого рода ставятся только на использование интерфейса объекта (при этом, зная производительность операций, мы можем рассуждать о производительности алгоритма).

какого объекта? стандартного класса?
так можно свой написать, там мало строк будет. и не только интерфейс, еще и эффективность сами определите.
очень многие пишут свои менеджеры памяти для уменьшения количества занимаемой памяти, но при этом о фактическом сборе мусора речи не идет.
также приходится все вручную удалять.

не вижу ничего тяжелого написать свою очередь ручками и узнать ее размер используя лиш 1 указатель + 1 long например

FIFO и LIFO полностью работают на моей схеме выше.

и все жы: почему черный ящик-то? или кроме стандартов вы не делали ничего?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33991866
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
#include <iostream.h>

/*
Written by Aklin [aklin20@mail.ru], 2006(c).
*/

template <class T>
class MyStack
{
protected:
	struct cell
	{
		T val;
		cell* n;
	};
	cell *head, *b;

public:
	MyStack<T>();
	~MyStack<T>();

public:
	int Push(T);
	T Pop();
	unsigned int Len();
};

template <class T>
MyStack<T>::MyStack<T>()
{
	head = NULL;
	b = NULL;
}

template <class T>
MyStack<T>::~MyStack<T>()
{
	if( head== 0  )return;

	b = head->n;
	while( b!= 0  )
	{
		delete head;
		head = b;
		b = head->n;
	}
	delete head;
}

template <class T>
int MyStack<T>::Push(T val)
{
	if( head==NULL )
	{
		b = new cell;
		if( !b ) return  1 ;
		b->n = NULL;
		b->val = val;

		head = b;
	}
	else
	{
		b = new cell;
		if( !b ) return  1 ;
		b->n = head;
		b->val = val;

		head = b;
	}

	return  0 ;
}

template <class T>
T MyStack<T>::Pop()
{
	if( head==NULL )
	{
		return  0 ;
	}
	else
	{
		b = head;
		head = head->n;
		T buf = b->val;
		delete b;
		return buf;
	}
}

template <class T>
unsigned int MyStack<T>::Len()
{
	unsigned int i =  0 ;
	b = head;
	while( b!= 0  ){
		i++;
		b = b->n;
	}
	return i;
}

void main(){
	MyStack<long> m1;


	m1.Push(  10  );
	m1.Push(  11  );
	m1.Push(  12  );
	m1.Push(  13  );

	cout << m1.Len() << "\n";

	cout << m1.Pop() << "\n";
	cout << m1.Pop() << "\n";
	cout << m1.Pop() << "\n";
	cout << m1.Pop() << "\n";
	cout << m1.Pop() << "\n";
	cout << m1.Pop() << "\n";
	cout.flush();
}
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33991869
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
аналогично пишется очередь
+ перегрузкой операторов дибиваемся
-слиянием стеков
-проверка на равенство(> или < или <= и др)
-доступ к элементу по []
-и т.д.
-добавление элементов: MyStackVar += 150;
-или + = либо слияние, либо добавление,
-или - = вычитание (удаление последнего эл-та)

такой же класс (без перегузки операторов) я проводил даже в VB!
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992175
Mike_za
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дык ясно же написано что есть
две веревки за которые можно дергать
push, pop
куда вы лезете с реализацией очереди!!!!
Повторю softwarer: Очередь - это черный ящик
при доступе внутрь класса узнать длину очереди не было бы вообще проблемой

а с рекурсией действительно нечестно, память выделится в стеке... хотя и без явного выделения

а хотя....

автор"Скачать" все элементы в String, а потом восстановить очередь, но по условию элементы очереди не должны дублироваться , может у нее нет решения?

написано же ЭЛЕМЕНТЫ не должны дублироваться))
все честно с маркером тода, если элементы уникальные, прокрутить один раз в цикле, задача то учебная
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992178
Mike_za
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklin вы вручную хоть раз очередь строили?
это не черный ящик, если знать начало очереди, а вполне нормальный элемент. и работать с ним просто.(можно написать класс для простоты)

А вы хоть раз слышали про черный ящик и интерфейс?

Нормально реализованная очередь - это классический черный ящик
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992323
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
template <class T>
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;
}

void main()
{
	MyStack<long> m1;


	m1.Push(  10  );
	m1.Push(  11  );
	m1.Push(  12  );
	m1.Push(  13  );


	cout << Lenn<long>( m1 ) << "\n";
	cout.flush();

	cout << m1.Len() << "\n";
	cout.flush();
}
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992396
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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;
}
Замечательно. Угадайте с трех раз, у кого из участников темы Вы позаимствовали это решение?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992455
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Замечательно. Угадайте с трех раз, у кого из участников темы Вы позаимствовали это решение?
я не заимствовал, а показал, что даже из черного ящика такое возможно вытянуть.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992594
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklin
Как вам удаётся не различать реализацию (односвязный список) и интерфейс (push/pop/empty) объекта (stack'a)?

Aklin я не заимствовал, а показал, что даже из черного ящика такое возможно вытянуть.
Чёрным ящиком было решение опубликованное Dremmm в пятом сверху сообщении? %)
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992658
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
NotGonnaGetUs Aklin
Как вам удаётся не различать реализацию (односвязный список) и интерфейс (push/pop/empty) объекта (stack'a)?

Push - добавление к очереди (стека)
Pop - получение из очереди (стека)
структура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением.

да и односвязный список бывает либо очередь либо стек, а дальше только деревья...

NotGonnaGetUs
Aklin я не заимствовал, а показал, что даже из черного ящика такое возможно вытянуть.
Чёрным ящиком было решение опубликованное Dremmm в пятом сверху сообщении? %)
нашел, но:
-использование статического стека? зачем?
-стек был создан, зачем его еще раз пересоздавать?
- в общем у меня то же но для моего класса.

вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992683
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklin
-использование статического стека? зачем?

"статического стека" не существует. автор сделал переменную содержащую сслыку на стек статической, чтобы к ней можно было обращаться из статического метода main...

Aklin
-стек был создан, зачем его еще раз пересоздавать?

Где там пересоздаётся стек?


Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением.

вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели.

Это не шутка? :)
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992695
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
NotGonnaGetUs Aklin
-использование статического стека? зачем?

"статического стека" не существует. автор сделал переменную содержащую сслыку на стек статической, чтобы к ней можно было обращаться из статического метода main...

существует статический класс, который позже расширяется динамически.
NotGonnaGetUs

Aklin
-стек был создан, зачем его еще раз пересоздавать?

Где там пересоздаётся стек?

= new Stack();
NotGonnaGetUs


Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением.

вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели.

Это не шутка? :)
что именно?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992726
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklinсуществует статический класс, который позже расширяется динамически.

Код написанный Dremmm - это код на java.
Там не существует никаких статических классов.

Aklin
= new Stack();

Это единственно место в коде, где происходит создание объекта класса "Stack".

Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением.

вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели.

Aklin
NotGonnaGetUs
Это не шутка? :)
что именно?

Вот это:
Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс , не понимая, что внутри происходит является огорчением.
и это:
Aklin
вообще не вижу причин для использования стандартного класса , если можно написать самому под свои цели.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33992790
Den_di
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Просто трёп.
Рассуждаем логически. Если нам нельзя сохранять эл-ты, то мы обязаны вернуть его в очередь. Если очередь содержит произвольные эл-ты, то маркер невозможен. и подсчёты, хеши и т.п. Итого задача не может иметь решения.
Как можно узнать конец очереди, если все эл-ты и хранятся в ней, т.е там всегда N-1 эл-т точно есть. А для программистов вроде Aklin: для кого stl писали?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33993016
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
NotGonnaGetUs Aklinсуществует статический класс, который позже расширяется динамически.

Код написанный Dremmm - это код на java.
Там не существует никаких статических классов.

получается, что все переменные на яве под static? если это оябязательно, то дадно.

NotGonnaGetUs
Aklin
= new Stack();

Это единственно место в коде, где происходит создание объекта класса "Stack".

в си это второе создание: первое в Stack st1;
и второе st1 = new Stack();
NotGonnaGetUs

Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс, не понимая, что внутри происходит является огорчением.

вообще не вижу причин для использования стандартного класса, если можно написать самому под свои цели.

Aklin
NotGonnaGetUs
Это не шутка? :)
что именно?

Вот это:
Aklinструктура простая, организация тоже. и то что нектороые программисты пытаются использовать стандартный класс , не понимая, что внутри происходит является огорчением.


а что вам не нравится в использовании своих классов, оссобенно если их всегда можно переписать? в т.ч. для быстродействия в узких моментах?

NotGonnaGetUs
Aklin
вообще не вижу причин для использования стандартного класса , если можно написать самому под свои цели.
еще раз подписался.
стандартные классы я разве что в MFC использовал. да и то потому, что там все линки на DLL указывают...
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33993370
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklin
получается, что все переменные на яве под static? если это оябязательно, то дадно.

Неа, получается, что в java поля класса могут быть объявлены как статик, а могут и нет.

Aklinа что вам не нравится в использовании своих классов, оссобенно если их всегда можно переписать? в т.ч. для быстродействия в узких моментах?
Затем, что всё уже написано и нет никакого смысла (разве что со скуки) переписывать стандартные вещи.
Называется это повторным использованием кода и позволяет ускорить процесс разработки и интеграцию кода написанного разными людьми...

Aklin
еще раз подписался.
стандартные классы я разве что в MFC использовал. да и то потому, что там все линки на DLL указывают...

Ок. Я понял. С++ это мир, где законы разума действуют по другому, в силу объективного отсутствия стандартов :)
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33993394
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
NotGonnaGetUs Aklin
получается, что все переменные на яве под static? если это оябязательно, то дадно.

Неа, получается, что в java поля класса могут быть объявлены как статик, а могут и нет.

тогда не понимаю, зачем там указывал статик, если можно нормально. ведь 1 раз объявляется. и для 1 класса, а не 1 для всех???

NotGonnaGetUs
Aklinа что вам не нравится в использовании своих классов, оссобенно если их всегда можно переписать? в т.ч. для быстродействия в узких моментах?
Затем, что всё уже написано и нет никакого смысла (разве что со скуки) переписывать стандартные вещи.
Называется это повторным использованием кода и позволяет ускорить процесс разработки и интеграцию кода написанного разными людьми...

невероятно часто, то что написано не удолетворяет всем условиям. поэтому легче переписать (оссобенно, что всегда есть исходики си++.)

NotGonnaGetUs
Aklin
еще раз подписался.
стандартные классы я разве что в MFC использовал. да и то потому, что там все линки на DLL указывают...

Ок. Я понял. С++ это мир, где законы разума действуют по другому, в силу объективного отсутствия стандартов :)
стандарты - анси си и анси си++
в них есть незаменимые библиотеки, да и все.
остатьное не в стандарте и приписывается кем угодно когда угодно.
в си программеры почти всегда дают исходники на свои библиотеки, так что и приписать к ним можно все, что угодно.

а вот закрытые бибилиотеки (DLL) - другое дело (MFC например) там только интерфейс. и невозможно ничего приписать или переделать под себя.

а остальное открыто полностью.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33993769
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
не читал: флуд.
Есть вероятностный метод. Засунуть в очередь длинную случайную последовательность. Прогнать очередь из переда в зад 100 раз, смотря за своим маркером. По ходу прогона первого маркера можно строить второй, которого нет в очереди. Можно повторить прогон со вторым маркером. Вероятность ошибиться будет мала.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33993779
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
количество маркеров можно увеличивать, уменьшая вероятность ошибки.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33993827
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maXmoПрогнать очередь из переда в зад 100 раз
Если есть такая возможность, не нужно никаких вероятностей. Весь вопрос в том, как определить, "прогнали мы сто раз" или все еще в середине первого раза, а в очереди сам по себе кучу раз встречается наш маркер.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33993949
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
softwarer maXmoПрогнать очередь из переда в зад 100 раз
Если есть такая возможность, не нужно никаких вероятностей.и как?

softwarerВесь вопрос в том, как определить, "прогнали мы сто раз" или все еще в середине первого разапод количеством раз разумеется имеется в виду количество выловленных маркеров (между маркерами одинаковое количество элементов).

softwarerа в очереди сам по себе кучу раз встречается наш маркер.чем длиннее маркер, тем меньше вероятность.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33994082
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maXmoи как?
Если есть возможность "промотать всю очередь", нетрудно выбрать маркер, не встречающийся в очереди. just for example, при "промотке" подсчитать максимальное количество идущих подряд нулей, после чего выбрать маркером N+1 ноль.

Но проблема в том, что маркер нужно выбирать изначально, когда про очередь ничего не известно.

maXmoчем длиннее маркер, тем меньше вероятность.
Чем длиннее очередь, тем больше вероятность :)
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33994154
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklin
тогда не понимаю, зачем там указывал статик, если можно нормально. ведь 1 раз объявляется. и для 1 класса, а не 1 для всех???


Cамое первое предложение в
http://sql.ru/forum/actualthread.aspx?tid=338438&pg=1#3147471

...
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33994451
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
softwarerНо проблема в том, что маркер нужно выбирать изначально, когда про очередь ничего не известно.то есть получается, нет детерминированного способа промотать именно всю очередь. Только запихивать маркер и смотреть, когда он вылезет.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33994468
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
softwarerЧем длиннее очередь, тем больше вероятность :)длина очереди / (2^длина маркера в битах)
сравнил линейный рост и экспоненциальный :)
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33994744
Den_di
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
или решения нет или задача не верна
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33996057
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
для полной картины напишу цифирки для своего метода.
Для очереди длиной 4ЭБ (2^60 интов) и маркера длиной 16 байт (2^128 значений) имеем вероятность облажаться около 2^(-68) < 10^(- 20 ). Имхо, более чем приемлемо.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33996378
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да полноте. При этих исходных данных элементарно строится пример ситуации, в которой вероятность не облажаться столь мала, что честно говоря лень считать (а калькуляторы с такой разрядностью не справляются).

В практической задаче может быть и можно было бы согласиться с такой вероятностью, но в данном случае задача сугубо теоретическая. А в практическом направлении куда разумнее просто встроить в очередь метод GetLength :) - благо, он легко делается над любым артефактом доопределением методов enqueue/dequeue.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33996443
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
softwarerПри этих исходных данных элементарно строится пример ситуации, в которой вероятность не облажаться столь малану хотя бы в общих чертах набросай. Подстраивание под алгоритм генерации маркера?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33996600
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maXmoну хотя бы в общих чертах набросай. Подстраивание под алгоритм генерации маркера?
Маркер - шестнадцать байт, то есть четыре int-а. В очереди используются только эти же четыре значения (означающие, допустим, "влево-вправо-вверх-вниз").
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33996744
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
я забыл сказать про случайную генерацию маркера?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33996748
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
оченку вероятности такого совпадения я привёл.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33996749
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
то есть оценку :)
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33996756
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
проще в казино джек-пот сорвать и не надо будет писать дебильную прогу :)
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33996964
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maXmoоченку вероятности такого совпадения я привёл.
Давай предположим, что очередь инициализируется тем же генератором :))

P.S. Я понимаю, что спор сугубо беспредметный.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33997015
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
1) поскольку это не оговорено, то содержание очереди имеет общий вид. А в общем виде содержание очереди не зависит от кода, определяющего её длину. Это не наглое предположение, это правило понимания условий задач (даже сугубо теоретических). Например, если рассмотреть задачу типа "машина едет по шоссе со скоростью 60км/ч, за какое время она проедет 60 км?", то если не оговорено, что водитель пьян и через минуту врежется в столб, то этого не произойдёт.

2) плюс работа генератора может зависеть от многих факторов типа состояния памяти компьютера; это уже вопрос обеспечения качества работы генератора.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33997025
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
тогда придётся рассчитывать вероятность совпадения алгоритма заполнения очереди с алгоритмом генерации маркера. Тут я не возьмусь даже посчитать число степеней свободы :)
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33997968
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maXmoНапример, если рассмотреть задачу типа "машина едет по шоссе со скоростью 60км/ч, за какое время она проедет 60 км?", то если не оговорено, что водитель пьян и через минуту врежется в столб, то этого не произойдёт.
Это неудачный пример, сейчас объясню почему.

Если говорится "машина двигается со скоростью 60 км/ч", это означает именно "машина двигается со скоростью 60 км/ч (и это поведение не меняется по ходу дела)". При этом условии невозможно ответить на вопрос "на каком расстоянии от исходной точки окажется водитель машины через 1 час". Потому что, помимо прочего, пьяный водитель мог нечаянно выпасть из машины, и до тех пор, пока машина продолжает двигаться со скоростью 60 км/ч, нарушения условий задачи нет.

Я не понимаю, что такое "очередь общего вида" применительно к введению некоторых дополнительных условий задачи. К примеру, каково распределение ее элементов: нормальное? равномерное? другое? величины повторяются? а может последовательность монотонна? итп.

Если мы говорим о сугубо теоретических задачах, надо исходить из того, что есть, и не фантазировать. Если мы говорим о задачах на собеседовании, часто предполагается, что соискатель задаст уточняющие вопросы, если сочтет их существенными для решения задачи, либо предложит решение (варианты решения) с дополнительными оговорками, например "в таких-то условиях можно вот так". Но решать задачу, предполагая некий конкретный, не оговоренный условиями вариант, да еще и не выделяя этого - имхо в любом случае ошибка.
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33998113
Den_di
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
есть рабочее решение на основе определения периода маркера и кратных с ним коллизий.
1. пускаем маркер
2. определяем период его гарантированного появления
3. удаляем любой из них
4. проверяем повтор периода от данной позиции
5. если период есть, то подсчитываем кол-во то его нарушения
6. в точке нарушения востанавливаем маркер
7. удаляем маркер на кратной периоду позиции от текущей
8. всё
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33998143
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Den_di2. определяем период его гарантированного появления
Нельзя ли поподробнее расписать вот этот пункт?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33999979
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
softwarer(и это поведение не меняется по ходу дела)про это ничего не сказано.

softwarerК примеру, каково распределение ее элементов?любое из возможных. Это называется общий случай.

softwarerНо решать задачу, предполагая некий конкретный, не оговоренный условиями вариант softwarerДавай предположим, что очередь инициализируется тем же генератором :))это имелось в виду? Проблема только в оговорке? Я уже писал, что детерминированного (работающего во всех случаях) решения с маркером нет (по крайней мере я так думаю).
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #33999993
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
softwarerА в практическом направлении куда разумнее просто встроить в очередь метод GetLength :) а если реализация класса очереди закрыта?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #34001417
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maXmo softwarerА в практическом направлении куда разумнее просто встроить в очередь метод GetLength :) а если реализация класса очереди закрыта?
Хм.

Вариант 1: доопределить в наследнике методы Enqueue/Dequeue

Вариант 2: если они вдруг невиртуальные, сделать прокси-класс, обертку.

Хватит?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #34002308
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
обёртки не помогут, если очередь приходит в готовом виде (напр., из другого модуля) (то есть обёртка столкнётся с той же самой проблемой определения длины очереди), а если очередь формируешь сам, то и никакие обёртки не нужны :)
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #34002756
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maXmoобёртки не помогут, если очередь приходит в готовом виде (напр., из другого модуля)
На этот случай есть третий и четвертый варианты :))
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #34002899
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
пиво с начальником?
...
Рейтинг: 0 / 0
Задача: измерить длинну очереди, не используя массивов
    #34002996
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не.

Вариант 3: Хакнуть нахрен.

Вариант 4: Послать нахрен.
...
Рейтинг: 0 / 0
60 сообщений из 60, показаны все 3 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача: измерить длинну очереди, не используя массивов
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]