2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Хорошие решения.
Сообщение02.02.2006, 08:32 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
В противоположность темы об ошибках, хочется завести тему об удачных решениях в программировании :) Просьба всех, кому по каким-то непонятным причинам удалось написать удачный (с Вашей точки зрения) код, или удачно решить какую-то проблему, размещать Ваши решения здесь :) С комментариями, ессно :)

 Профиль  
                  
 
 
Сообщение03.02.2006, 19:52 


13/09/05
153
Москва
Смотрю я этот топик и возникает мысль, что последнее время с хорошими идеями не очень:))

 Профиль  
                  
 
 
Сообщение03.02.2006, 20:07 


13/09/05
153
Москва
А так, ознакомившись с патернами, могу сказать, что мой код, касаемый интерфейса, стал проще и лучше, и уже на автомате можно спроектировать новую задачу.
Особенно я бы отметил патерны "Fasade", "Command", "Factory method".

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

 Профиль  
                  
 
 
Сообщение03.02.2006, 20:12 


13/09/05
153
Москва
Еще отметил бы совместное использование Command и Memento - в итоге получаем бесконечный Undo/Redo с простотой реализации. Каждый объект сам знает, как ему восстановиться/сохраниться, это защито внутри его и никому извне не видно.
Причем сам объект знает, что в нем именно изменилось, и отпадает потребность в сохранении ненужных данных.

 Профиль  
                  
 
 Сортировка списка
Сообщение17.02.2006, 11:17 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
При сортировке списка (методом простого обмена) надо первый раз доходить до конца списка, потом до предпоследнего эл-та, потом до пред-предпоследнего, и т.д. При этом не совсем ясно (кроме как на первом проходе), на каком месте надо останавливаться. Можно, конечно на первом проходе списка его длину посчитать, и т.д. Вот, как мне кажется, удачное решение для сортировки списка - без всякого подсчета длины списка и счетчиков :) (на Паскале, поскольку хотел ее сначала поместить в эту тему):

Код:
Procedure Sorting(l: List);
Var
p, LL, pstop: List;
k: Integer;
begin
  LL:= l;
  pstop := nil;
  while pstop <> LL do
  begin
    l:= LL;
    p:= l^.next;
    while p <> pstop do
    begin
      if p^.info > l^.info then
      begin
        k:= p^.info;
        p^.info:= l^.info;
        l^.info:= k;
      end;
      l:= l^.next;
      p:= p^.next;
    end;
    pstop := l;
  end;
end;


Структура List выглядит так:
Код:
Type
  List= ^Node;
  Node = record
    info: Integer;
    next: List
  end;

 Профиль  
                  
 
 Re: Сортировка списка
Сообщение17.02.2006, 12:57 
Аватара пользователя


20/01/06
64
оттуда
Sanyok, скажите, что Вы пошутили :)
Если указатели сравнивать с nil, будет немного покороче.[/b]

 Профиль  
                  
 
 
Сообщение17.02.2006, 13:09 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Нет, не скажу (что пошутил) Шутить я не шутил, а сесть в лужу - это запросто :). Мне казалось, что так существенно сокатится число проходов (в 2 раза), по сравнению с вариантом, когда надо сравнивать с nil. Приведите Ваше решение (которое будет короче).

 Профиль  
                  
 
 
Сообщение17.02.2006, 13:11 
Аватара пользователя


20/01/06
64
оттуда
Код:
procedure sorting (l: List);
var t1, t2: List;
    k: integer;
begin
    t1 := l;
    while t1^. next <> NIL do begin
        t2 := t1^. next;
        while t2 <> NIL do begin
            if t1^. info > t2^. info then begin
                k := t1^. info;
                t1^. info := t2^. info;
                t2^. info := k;
            end;
            t2 := t2^. next;
        end;
        t1 := t1^. next;
    end;
end;

 Профиль  
                  
 
 
Сообщение17.02.2006, 13:24 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Вы Ваше решение прогоняли? Думать я не люблю :) , поэтому лучше сегодня вечером прогоню Ваш вариант. Но сдается мне, он работать не будет :) .

 Профиль  
                  
 
 
Сообщение17.02.2006, 13:34 
Аватара пользователя


20/01/06
64
оттуда
Sanyok писал(а):
...Но сдается мне, он работать не будет :) .

Только если в списке не будет ни одного элемента (l=NIL)

 Профиль  
                  
 
 
Сообщение17.02.2006, 14:02 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Нет, мне кажется он не будет сортировать. Представьте, список надо отсортировать по возрастанию, а числа в списке стоят наоборот: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.
После первого прохода:
9, 8, 7, 6, 5, 4, 3, 2, 1, 10.
После второго (тут, согласно Вашей логике, начинаем со второго эл-та списка):
9, 7, 6, 5, 4, 3, 2, 1, 8, 10.
После третьего прохода (начинаем с третьего эл-та):
9, 7, 5, 4, 3, 2, 1, 6, 8, 10.
После четвертого прохода (начинаем с четвертого):
9, 7, 5, 3, 2, 1, 4, 6, 8, 10.
После пятого прохода (начинаем с пятого эл-та):
9, 7, 5, 3, 1, 2, 4, 6, 8, 10.
Усе. С этого места уже никакие элементы перемещатся со своих мест не будут. Или я ошибся?

 Профиль  
                  
 
 
Сообщение17.02.2006, 14:35 
Аватара пользователя


20/01/06
64
оттуда
Sanyok писал(а):
...Или я ошибся?

Ошиблись. Вот здесь:
Цитата:
После первого прохода:
9, 8, 7, 6, 5, 4, 3, 2, 1, 10.

После первого прохода будет
1, 10, 9, 8, 7, 6, 5, 4, 3, 2
(во время первого прохода t1 всегда указывает на первый элемент списка)
Вот часть первого прохода
10, 9, 8, 7, 6, 5, 4, 3, 2, 1
9, 10, 8, 7, 6, 5, 4, 3, 2, 1
8, 10, 9, 7, 6, 5, 4, 3, 2, 1
ну и так далее. Это же обычная "пузырьковая" сортировка.

И ещё. Не хочется Вас огорчать, но... Я провел эксперимент. Поместил в начало программы
Код:
var s1, s2: real;

а также Вашу и свою процедуры сортировки. Во внутренний цикл каждой процедуры поместил инкременты переменных - s1 в своей, s2 - в Вашей. После чего посортировал массив [1..10000] случайных чисел обеими процедурами.
У меня получилось s1 = s2.

 Профиль  
                  
 
 
Сообщение17.02.2006, 14:51 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
:) Да, я ошибся. Я-то свою процедуру делал исходя из того, что мне в каждый момент времени будут доступны только 2 соседних элемента списка.

P.S. Все-таки полезно в эту тему что-то помещать :) Даже если это будет не самое хорошее решение. :)

 Профиль  
                  
 
 
Сообщение17.02.2006, 15:43 
Аватара пользователя


20/01/06
64
оттуда
По теме. Как-то понадобилось мне перебрать в случайном порядке целые числа от 0 до 799*599 (что-то рисовал на экране), так, чтобы в последовательности каждое число было в точности по одному разу. Под это дело я "изобрёл велосипед":
Код:
...
int a [480000], i, e = 479999, t, p, n;
for (i = 0; i < 480000; i++) a [i] = i;
for (i = 0; i < 480000; i++)
{
    p = rand (e); // rand (e) даёт случайное целое число из [0..e]
    n = a [p]; // очередное число
    swap (&a [p], &a [e]); // swap меняет местами два элемента массива
    e--;
    ... // работаем с n
}
...

до сих пор, правда, не знаю чей.

 Профиль  
                  
 
 
Сообщение17.02.2006, 15:50 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Велосипед - скорее, всего, Ваш (то есть, я имел в виду - Вашего изобретения :) )

Это было что-то типа screen saver-a?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group