Forums.Avtograd.Ru: Алгоритмы - Forums.Avtograd.Ru

Перейти к содержимому

  • (3 Страниц)
  • +
  • 1
  • 2
  • 3
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

Алгоритмы

#1 Пользователь офлайн   parovozik

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 700
  • Регистрация: 01 Ноябрь 07

Отправлено 16 Март 2008 - 11:59

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

Локомотив

0


  • (3 Страниц)
  • +
  • 1
  • 2
  • 3
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

Другие ответы в этой теме

#21 Пользователь офлайн   Macro-Z

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 397
  • Регистрация: 02 Ноябрь 07

Отправлено 09 Апрель 2008 - 21:43

Я тебя понял ! Можешь ответить где это применяется практический ?
0

#22 Пользователь офлайн   KORENHACK

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 464
  • Регистрация: 01 Ноябрь 07

Отправлено 10 Апрель 2008 - 07:08

Мы тут алгоритмы обсуждаем. Не обязательно применять это на практике. И не надо писать что-то вроде "Я не собираюсь напрягать свой мозг ради этого...".
0

#23 Пользователь офлайн   Saray

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 2 388
  • Регистрация: 31 Январь 08

Отправлено 10 Апрель 2008 - 09:05

Просмотр сообщенияKORENHACK (10.4.2008, 8:08):

Мы тут алгоритмы обсуждаем. Не обязательно применять это на практике. И не надо писать что-то вроде "Я не собираюсь напрягать свой мозг ради этого...".

Типа я такой крутой, всех озадачил никому не нужным геммороем :blink:
это вам, батенька, в раздел "искусственный интеллект" надо :lol:
Если женщина не права, нужно извиниться и замолчать.
0

#24 Пользователь офлайн   Administr

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 328
  • Регистрация: 08 Ноябрь 07

Отправлено 10 Апрель 2008 - 09:07

Подскажите алгоритм пирамидального метода сортировки элементов в массиве плз.
Вебмастер: продвижение, разработка, дизайн, верстка и др. контакты в профиле. Люблю советские электрогитары, куплю или приму в дар электрогитары или запчасти от них. Интересуют все модели с этого сайта: http://oecc.ru/
0

#25 Пользователь офлайн   Macro-Z

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 397
  • Регистрация: 02 Ноябрь 07

Отправлено 10 Апрель 2008 - 10:02

Просмотр сообщенияKORENHACK (10.4.2008, 7:08):

Мы тут алгоритмы обсуждаем. Не обязательно применять это на практике. И не надо писать что-то вроде "Я не собираюсь напрягать свой мозг ради этого...".

Напишите алгоритм сортировки чисел в массиве что бы они поочерёдно распологались друг от друга.
Ты чего либо понял ? Скорее всего нет ! И применить это нельзя на практике ! Смысл создания такого алгоритма?
0

#26 Пользователь офлайн   Saray

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 2 388
  • Регистрация: 31 Январь 08

Отправлено 10 Апрель 2008 - 10:59

Просмотр сообщенияMacro-Z (10.4.2008, 11:02):

Напишите алгоритм сортировки чисел в массиве что бы они поочерёдно распологались друг от друга.
Ты чего либо понял ? Скорее всего нет ! И применить это нельзя на практике ! Смысл создания такого алгоритма?

даже если целю задачи является обучение, то бишь голимая теория,
все равно задачи надо конкретнее ставить:
1. Какая нужна реализация алгоритм сортировки (пузырьковая, и т.д.)
2. Каким образом сопоставлять N-мерные пространства для операции сравнивания (мультисортировка или сопоставление по одному параметру)

N-мерное пространство байт можно проще представить по аналогии:
I измерение - символ
II измерение - строка
III измерение - набор строк (файл)
IV измерение - набор файлов (каталог)
и т.д.

если автор уточнит эти вопросы, думаю всем будет понятно что и как реализовывать,
а так задача неконкретная
Если женщина не права, нужно извиниться и замолчать.
0

#27 Пользователь офлайн   Saray

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 2 388
  • Регистрация: 31 Январь 08

Отправлено 10 Апрель 2008 - 11:45

Просмотр сообщенияAdministr (10.4.2008, 10:07):

Подскажите алгоритм пирамидального метода сортировки элементов в массиве плз.

Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево — это такое двоичное дерево, у которого выполнены условия:

1. Каждый лист имеет глубину либо d либо d − 1, d — максимальная глубина дерева.
2. Значение в любой вершине больше, чем значения ее потомков.

Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] — Array[2i] и Array[2i+1].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева:

Array[i]\geq Array[2i]

Array[i]\geq Array[2i+1]

при 1\leq i<n/2.

Этот шаг требует O(n) операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], … , Array[n] — упорядоченная последовательность.

Этот шаг требует O(nlogn) операций.
template<class T>
void downHeap( T a[], int k, int n )
{
//  процедура просеивания следующего элемента
//  До процедуры: a[k+1]...a[n]  - пирамида
//  После:  a[k]...a[n]  - пирамида
   T new_elem = a[ k ];
// пока у a[k] есть дети
   while( k <= n / 2 )
   {
	  int child = 2 * k;
  //  выбираем большего сына
	  if( child < n && a[ child ] < a[ child + 1 ] )
		 child++;
	  if( new_elem >= a[ child ] )
		 break;
   // иначе переносим сына наверх
	  a[ k ] = a[ child ];
	  k = child;
   }
   a[ k ] = new_elem;
}
 
template<class T>
void heapSort( T a[], int size )
{
// строим пирамиду
   for( int i = size / 2 - 1; i >= 0; i-- )
   {
	  downHeap( a, i, size - 1 );
   }
// теперь a[0]...a[size-1] пирамида
   for( int i = size - 1; i > 0; i-- )
   {
   // меняем первый с последним
	  T temp = a[ i ];
	  a[ i ] = a[ 0 ];
	  a[ 0 ] = temp;
   // восстанавливаем пирамидальность a[0]...a[i-1]
	  downHeap( a, 0, i - 1 );
   }
}

Если женщина не права, нужно извиниться и замолчать.
0

#28 Пользователь офлайн   Barrabas

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 431
  • Регистрация: 01 Ноябрь 07

Отправлено 10 Апрель 2008 - 12:58

Просмотр сообщенияKORENHACK (8.4.2008, 18:59):

Надо упорядочивать массив, который динамически меняет кол-во свих измерений!
Так тяжело это понять?

Почему все, что Вы не в состоянии сделать называйте ерундой?

Есть массив. Он начинает БЕСКОНЕЧНО расти (растет как кол-во измерений так и размеры уже готовых измерений) и заполняться случайными числами. Его надо сортировать по возрастанию (убыванию) по мере прибавления измерений.

Теперь думаю всем понятно. Алгоритм можно описать на С или Дельфи.

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

каждый столбец - измерение массива
1 8 5
4 9 6
3 7 2

можно отсортировать так
1 2 3
4 5 6
7 8 9
а можно и так
1 4 7
2 5 8
3 6 9
можно и так (сиртируются измерения по сумме значений элементов и элементы в них)
1 2 7
3 5 8
4 6 9

ЗАДАЧА НЕ СФОРМУЛИРОВАНА!!!!
потому и ерунда полная и во второй редакции тоже
0

#29 Пользователь офлайн   KORENHACK

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 464
  • Регистрация: 01 Ноябрь 07

Отправлено 10 Апрель 2008 - 20:12

Просмотр сообщенияMacro-Z (10.4.2008, 10:02):

Напишите алгоритм сортировки чисел в массиве что бы они поочерёдно распологались друг от друга.
Ты чего либо понял ? Скорее всего нет ! И применить это нельзя на практике ! Смысл создания такого алгоритма?

А можно просто сказать, что ты не знаешь как это написать? Так скажи, я вот не знаю, поэтому и спрашиваю у Вас. Если никто не знает, то зачем критиковать? Просто не комментируйте и все.
0

#30 Пользователь офлайн   saDever

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 199
  • Регистрация: 27 Ноябрь 07

Отправлено 11 Апрель 2008 - 02:44

Народ, не ругайтесь если что не так) отдельной темы смысла создавать я думаю нет)
хотелось бы попросить совета, крайне необходима хорошая книжка по алгоритмам, в которой подробно затронута тема Динамического программирования, если кто-нибудь из вас знает такую, не могли бы вы сказать мне авторов ну или в идеале ссылочку)
or no named master B. nice. very nice. nice and cruel ^.^
sadner for ever.
0

#31 Пользователь офлайн   nickla

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 253
  • Регистрация: 16 Ноябрь 07

Отправлено 29 Апрель 2008 - 14:41

С массивами отжог чувак. Разбежись и в стенку - спасешь мир.

Твой алгоритм с твоими динамическими массивами банален и неинтересен. Сортируй массив методом вставки и успокойся.
Тут могла бы быть ваша реклама
0

#32 Пользователь офлайн   [FENIX]

  • Активный пользователь
  • PipPipPip
  • Группа: Пользователи
  • Сообщений: 625
  • Регистрация: 01 Ноябрь 07

Отправлено 11 Май 2008 - 18:23

Народ, помогите кто может. Скажите, где у меня в алгоритме ошибка?
Нужно написать программу на Паскале, которая проверяет массив из 10 целых чисел на знакочередование.
Предпологается, что все элементы массива ненулевые.

Program mass;
uses crt;

var
a:array[1..10] of integer;
i,j:integer;
Ok:Boolean;

Begin
ClrScr;

{Заполняем массив}
For i:=1 to 10 Do
begin
write('a[',i,']=');
Readln(a[i]);
end;

writeln;

i:=1;
j:=2;

Ok:=True;		{Допустим, что знаки чередуются}
While i<=7 Do
While j<=8 Do

{Случай, когда + - + - ....}
If ((a[i]>0) And (a[i+2]>0)) And ((a[j]<0) And (a[j+2]<0)) then
begin
i:=i+2;
j:=j+2;
end

Else
begin
i:=1;
j:=2;
	 While i<=7 Do
	 While j<=8 Do
	 {Случай, когда - + - + ....}
	 If ((a[i]<0) And (a[i+2]<0)) And ((a[j]>0) And (a[j+2]>0)) then
	 begin
	 i:=i+2;
	 j:=j+2;
	 end
	 Else
	 begin
	 Ok:=False;
	 break;
	 end;


end;

{------------Программа не выдаёт, что будет, если знаки не чередуются-----}


If Ok then
write('Знаки чередуются')
Else
write('Знаки НЕ чередуются');

End.


Когда числа чередуются, тут всё норм. работает, а вот когда они не чередуются, то сообщение об этом не вылазиет. Где у меня ошибка/неточность ?
Верь в себя, и ты чемпион!
0

#33 Пользователь офлайн   corn

  • Новичок
  • Pip
  • Группа: Пользователи
  • Сообщений: 60
  • Регистрация: 09 Май 08

Отправлено 12 Май 2008 - 06:33

Просмотр сообщения[FENIX] (11.5.2008, 19:23):

else
begin
i:=1;
j:=2;
	 While i<=7 Do
	 While j<=8 Do
	 {Случай, когда - + - + ....}
	 If ((a[i]<0) And (a[i+2]<0)) And ((a[j]>0) And (a[j+2]>0)) then
	 begin
	 i:=i+2;
	 j:=j+2;
	 end
	 Else
	 begin
	 Ok:=False;
	 break;
	 end;
end;

Просто у тебя в этом месте возникает бесконечный цикл. Объясняю, если False первое условие, то что происходит:
Заново инициализируются i, j запускается второй цикл While. Дальше едет еще одна проверка и если, и оно равно False
То вызывается остановка ВТОРОГО цикла, a первый начинает заново проверку
0

#34 Пользователь офлайн   Alkanaft777

  • Новичок
  • Pip
  • Группа: Пользователи
  • Сообщений: 21
  • Регистрация: 01 Ноябрь 07

Отправлено 15 Май 2008 - 18:12

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

#35 Пользователь офлайн   Barrabas

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 431
  • Регистрация: 01 Ноябрь 07

Отправлено 15 Май 2008 - 18:29

Просмотр сообщенияAlkanaft777 (15.5.2008, 18:12):

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

чегото не понял нужно проверить массив на чередование знаков и все что ль?
ну например смотришь первый элемент если оно "-"
то все нечетные тоже должны быть "-" а четные "+" ну и проверяешь до первого несовпадения разумеется

или така

			int[] a = {1, -2, 3, 4};
			bool f = (a[0] > 0);
			bool res = true; 
			for (int i = 1; i < a.Length; i++)
			{
				if (a[i] > 0 == f)
				{
					res = false;
					break;
				}
				f = !f;
			}
			MessageBox.Show(res.ToString());

0

#36 Пользователь офлайн   Alkanaft777

  • Новичок
  • Pip
  • Группа: Пользователи
  • Сообщений: 21
  • Регистрация: 01 Ноябрь 07

Отправлено 16 Май 2008 - 16:58

Да, требуется найти чередутся ли элементы массива с противоположными знаками.
Как вариант решения
еще можно привязать знак числа к четности элемента массива. реализуется например так:

....
оk:=truе;
f:=а[1]>0;
fоr i:=1 tо 10 dо

if f=(а[i]>0)хоr оdd(i) thеn оk:=fаlsе;
....
0

#37 Пользователь офлайн   Alkanaft777

  • Новичок
  • Pip
  • Группа: Пользователи
  • Сообщений: 21
  • Регистрация: 01 Ноябрь 07

Отправлено 17 Май 2008 - 16:32

есть еще короче код.
умножать элемент на следующий и проверять знак произведения.
0

#38 Пользователь офлайн   Barrabas

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 431
  • Регистрация: 01 Ноябрь 07

Отправлено 18 Май 2008 - 13:43

Просмотр сообщенияAlkanaft777 (17.5.2008, 16:32):

есть еще короче код.
умножать элемент на следующий и проверять знак произведения.

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

#39 Пользователь офлайн   Saray

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 2 388
  • Регистрация: 31 Январь 08

Отправлено 19 Май 2008 - 07:13

Просмотр сообщенияBarrabas (18.5.2008, 14:43):

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

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

#40 Пользователь офлайн   Barrabas

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 431
  • Регистрация: 01 Ноябрь 07

Отправлено 19 Май 2008 - 10:00

Просмотр сообщенияSaray (19.5.2008, 7:13):

кстати, на современных процессорах одинаково по времени: что проверка знака, что умножение

возможно, но так два действия - умножение и проверка знака

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

  • (3 Страниц)
  • +
  • 1
  • 2
  • 3
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

1 человек читают эту тему
0 пользователей, 1 гостей, 0 скрытых пользователей