Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 03.09.2014, 21:41   #51
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Премного благодарен!
Думал я где-то налажал, а тут оказывается такая хитрость нужна.. Большое спасибо, буду знать!
Poma][a вне форума Ответить с цитированием
Старый 18.09.2014, 15:46   #52
Plague
Забанен
Форумчанин Подтвердите свой е-майл
 
Аватар для Plague
 
Регистрация: 01.11.2006
Сообщений: 420
По умолчанию

В итоге то решил 321 задачу?
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
Plague вне форума Ответить с цитированием
Старый 18.09.2014, 16:24   #53
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Яхуууу! С возвращением Мы скучали
Цитата:
В итоге то решил 321 задачу?
Эт Вы про мой вопрос про системы счисления? Он был по другой задачке.. А вот по какой уже и не вспомню.. Пойду, кстати, 321 решу..
Poma][a вне форума Ответить с цитированием
Старый 18.09.2014, 23:05   #54
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Как-то я косячу..
Задачу 321 я действительно решал.. И в 1-Ом посте это было отображено.. Однако, когда я проверял это сегодня, оказалось, что даже попыток не было.. Сейчас же показывает, что я решил ее 27.05..
Посему прошу прощения, за распространение ложной информации.. Видно плохо смотрел..
Poma][a вне форума Ответить с цитированием
Старый 04.10.2014, 09:48   #55
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Дамы и господа, доброе утречко!

Давай представим, что нам дали такую задачу :
Дан целочисленный массив A, в котором N элементов. Необходимо переставить все отрицательные элементы в начало. Порядок не важен..

Дак вот.. Задача решается очень просто.. За O(N).. Так называемый Partition(один проход QSort)

А теперь сделаем такую подлость, скажем, что порядок очень важен!
И при исходных данных
4 (кол-во элементов)
-1 2 -3 4
Мы должны вывести
-1 -3 2 4

Задача решается снова за O(N) при достаточном кол-ве памяти.. В stl это можно сделать одной строкой.. Для этого нужен stable_partition..

НО! Найти как же его сделать без stl'я, я не смогу..
Поэтому предлагаю такой вариант (увы, я его еще не реализовал.. сейчас займусь этим.. отпишусь о результатах)..
Мы снова будем использовать QSort..
Только теперь нам нужно правильно выбрать j.. Если в QSort'e мы идем с конца, то теперь нам нужно выбрать некий элемент с индексом p, такой что, кол-во отрицательныйх элементов в a[p..n] >= кол-во положительных элементов в a[1..p-1]..


Не могли бы Вы разнести в пух и прах мой алгоритм, а также предложить свой!

Спасибо! Удачи!
Poma][a вне форума Ответить с цитированием
Старый 04.10.2014, 13:10   #56
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
скажем, что порядок очень важен!
Т.е. их нужно еще и сортировать?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 04.10.2014, 13:31   #57
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
Т.е. их нужно еще и сортировать?
Не совсем..

Вот.. Это должно работать за O(N) (или за O(N log N) при недостаточно кол-ве памяти)..

Код:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	vector<int> v;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int t; cin >> t; 
		v.push_back(t);
	}

	stable_partition(v.begin(), v.end(), [](const int& t) {return t < 0;});

	for (vector<int>::const_iterator p = v.begin(); p != v.end(); ++p)
		cout << *p << " ";		
}
И вот это.. Тоже работает за O(N).. (или же за O(NlogN)..

Код:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	vector<int> v;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int t; cin >> t; 
		v.push_back(t);
	}

	partition(v.begin(), v.end(), [](const int& t) {return t < 0;});

	for (vector<int>::const_iterator p = v.begin(); p != v.end(); ++p)
		cout << *p << " ";		
}
Только один код при тесте
Код:
4
4 2 -1 -3
Один код выдаст
Код:
-1 -3 4 2
А другой
Код:
-3 -1 2 4

Последний раз редактировалось Poma][a; 04.10.2014 в 13:33.
Poma][a вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вопросы по БД Rost93 PHP 9 28.06.2011 22:18
Вопросы по С++ Fantazerishka Общие вопросы C/C++ 2 19.05.2010 06:52
Вопросы по if, else? molodoyy Помощь студентам 5 21.03.2010 15:34