Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 08.05.2007, 22:11
незарегистрированный

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
>Я уже все перепробовал
что перепробовал???
Заполни массив большими слкчайными числами и отсортируй.
Или в строке z = z + 1 увеличивай не на 1, а на случайное число
ТОже самое, максимальная размерность которую мне удалось задать это 250000
  #12  
Старый 09.05.2007, 08:52
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>максимальная размерность которую мне удалось задать это 250000
Очевидно, дело не в алгоритме, а в знании языка С. Как там большое случайное число сгенерировать одной командой с помощью встроенных средств и стандартных библиотек, я не знаю. Если random ограничено 16 разрядами, то просто возьми, например random()*65536+random(), или random()*random(). Во втором случае распределение будет неравномерным, но это не слишком существенно.
  #13  
Старый 06.01.2011, 14:36
dzega

 
Сообщений: n/a

Дек сортировкой простых вставок помогите переделать в стек сортировкой бинарных вставок, Заранее спасибо !

____________________________________________

#include <iostream>
#include <stdlib.h>

using namespace std;
#define NOTHING 0
template <class E> struct element{
E mean;
element *prev;
element *next;
};
template <class T> class dek{
element<T> *head;
element<T> *back;
element<T> *tmp;
int count;
public:
dek(){
head=NOTHING;
back=NOTHING;
tmp=NOTHING;
count=0;
}
bool PushFront(T elem){
if(elem==NOTHING)
return false;
tmp = new element<T>;
tmp->mean=elem;
tmp->prev=head;
tmp->next=NOTHING;
if(head==NOTHING){
back=tmp;
}
else{
head->next=tmp;
}
head=tmp;
count++;
return true;
}
bool PushBack(T elem){
if(elem==NOTHING)
return false;
tmp = new element<T>;
tmp->mean=elem;
tmp->prev=NOTHING;
tmp->next=back;
if(back==NOTHING){
head=tmp;
}
else{
back->prev=tmp;
}
back=tmp;
count++;
return true;
}
T PopFront(){
if(head==NOTHING)
return NOTHING;
T res=head->mean;
tmp=head;
head=head->prev;
if(head==back)
head->next=NOTHING;
delete tmp;
count--;
return res;
}
T PopBack(){
if(back==NOTHING)
return NOTHING;
T res=back->mean;
tmp=back;
back=back->next;
if(head==back)
back->prev=NOTHING;
delete tmp;
count--;
return res;
}

bool isEmpty(){
if(count==0)
return true;
else
return false;
}
void print(){
element<T> *t=back;
while(t!=NOTHING){
cout<<t->mean<<" ";
t=t->next;
}
}
};

int main() {
cout << "Сортировка дека методом простых вставок" << endl;
dek<int> *l=new dek<int>();
int gen;
srand(time(NULL));
//генерируем одно и 2х значные случайные числа (~50/50) исключая ноль
for(int i=0;i<15;i++){
gen=(rand()%10>5?rand()%100:rand()%10);
l->PushBack(gen==0?NOTHING:gen);
}
l->print();
cout<<endl;
/* берем из основного дека по кею,
* Вытаскиваем из временного дека по элементу,
* сравниваем с текущим кеем и засовываем в рез
* если текущий кей меньшечем текущий элемент тм,
* то засовываем сначала его, а потом все остальные,
* перекидываем все обратно в тм
* и переходим к следующей итерации (берем следующий элемент кей)
* ВНИМАНИЕ! нельзя чтобы в исходных данных был ноль - он испульзуется
* как ноль! (константа nothing) (АТД возвращает его когда не находит больше элементов)
* можно заменить его на что-то, но я не знаю чем
*/
int key,key2;
dek<int> *tm=new dek<int>();
dek<int> *res=new dek<int>();
do {
key=l->PopFront();
do {
key2=tm->PopFront();
if(key>=key2){
res->PushFront(key);
res->PushFront(key2);
//докидываем оставшиеся
while(!tm->isEmpty()){
key2=tm->PopFront();
res->PushFront(key2);
}
}
else{
res->PushFront(key2);
}
} while(!tm->isEmpty());
//перегоняем обратно в тм
while(tm->PushFront(res->PopFront()));
}while(!l->isEmpty());

while(l->PushFront(tm->PopBack()));
l->print();

return 0;
}
 


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

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите разобраться Мёртвый Анархист Реализация, исходники, языки 13 23.01.2007 08:25