DRAKON.SU

Текущее время: Четверг, 24 Май, 2018 09:14

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 82 ]  На страницу 1, 2, 3, 4, 5  След.
Автор Сообщение
 Заголовок сообщения: Базовые компьютерные алгоритмы
СообщениеДобавлено: Понедельник, 16 Октябрь, 2017 17:20 

Зарегистрирован: Понедельник, 14 Декабрь, 2015 19:18
Сообщения: 108
Крутой программист это умеет!
Предлагаю открыть раздел, посвященным базовым компьютерным алгоритмам, понимание которых является признаком профессионального программиста.

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships."
Linus Torvalds


Трудность темы
Я сам начинаю изучать дисциплину "алгоритмы и структуры данных".
При изучение я столкнулся с не очень легким пониманием всего этого.
Встретил много словесных объяснений, кода. Интуитивно ощущается что это можно подавать как-то полегче, более понятно.
Представляется, что не обязательно быть крутым дядькой-теоретиком, чтобы познать какое-нибудь слияние или вставку в красно-черное дерево.

Есть выход!
Считаю, что изображение работы алгоритма в виде ДРАКОН-схемы:
-понизит порог вхождения в данную дисциплину
-привлечет внимание начинающих программистов
-увеличит радость от познаваемого
-сделает мир чуточку лучше :)

Алгоритм для старта
Постарался и создал сортировку пузырьком. Я, наконец, понял как это работает :) !
Предлагаю Вашему вниманию два варианта.
Учел опыт Степана с алгоритмом "Луна". Понял, что лучше сделать два варианта:
-программный
-понятный

Ясность алгоритма
Открыт к критике и исправлениям.
Хочу чтобы алгоритм ясно и моментально воспринимался.
Хочу чтобы когнитивное восприятие сработало на все 100%.
Поэтому если заметите не точность в самом алгоритме или есть предложение как улучшить с точки зрения когнитивной эргономике - я открыт к доработкам!

Работа сообща
Также я призываю заинтересовавшихся выкладывать алгоритмы, которые хочется показать.
Т.к. вместе мы наполним этот раздел быстрее и качественнее.
Возможно, введем понятие сложности алгоритма, будем сами алгоритмы сортировать)

P.S. Крутой программист еще и тот, кто знает английский, поэтому не стесняемся его использовать.
Гуру - повод поупражняться.
Новичкам - повод учиться.


--------------------------------------------------------------------------------------------
Итак, встречайте - "Bubble sort"!


Вложение:
Bubble sort.png
Bubble sort.png [ 34.89 КБ | Просмотров: 1856 ]

Вложение:
Bubble sort Readable.png
Bubble sort Readable.png [ 34.28 КБ | Просмотров: 1856 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 17 Октябрь, 2017 13:00 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 208
Откуда: Казань
Алгоритм в общем случае неправильный!
Ошибка будет в месте array[j] > array[j+1].
Если массив состоит из 1 элемента, то
array[0] > выход за границу массива ?
А если в массиве 0 элементов (такое тоже бывает), то
выход за границу массива > выход за границу массива ?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 17 Октябрь, 2017 14:28 

Зарегистрирован: Понедельник, 14 Декабрь, 2015 19:18
Сообщения: 108
Цитата:
Алгоритм в общем случае неправильный!
Ошибка будет в месте array[j] > array[j+1].
Если массив состоит из 1 элемента, то
array[0] > выход за границу массива ?
А если в массиве 0 элементов (такое тоже бывает), то
выход за границу массива > выход за границу массива ?


Верно. Возможен такой вариант:

Вложение:
Bubble sort2.png
Bubble sort2.png [ 34.71 КБ | Просмотров: 1815 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 18 Октябрь, 2017 09:44 

Зарегистрирован: Понедельник, 14 Декабрь, 2015 19:18
Сообщения: 108
Представляю для сравнения исходную схему, и полученную из неё ДРАКОН схему.

Вложение:
Bubble sort compare.png
Bubble sort compare.png [ 88.85 КБ | Просмотров: 1794 ]

Как Вы считаете что получилось лучше? Какие есть "+" и "-" у каждой из представленных схем?
В ДРАКОН-схеме один цикл показан иконкой "ДЛЯ", другой иконкой "Вопрос". Хорошо ли это для визуального восприятия?

Представляю также код и поясняющую схему алгоритма пузырьковой сортировки:
Вложение:
Bubble sort code and descr.png
Bubble sort code and descr.png [ 94.77 КБ | Просмотров: 1794 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 18 Октябрь, 2017 10:18 

Зарегистрирован: Среда, 03 Май, 2017 09:55
Сообщения: 127
Владимир Невзоров писал(а):
Представляю также код и поясняющую схему алгоритма пузырьковой сортировки:

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

"Цикл for" в духе "swapped==true?" выглядит странно.
Логично, же, что проверка "а были ли перестановки" должна произойти в конце пробежки.
Т.е. "start: hasSwaps=false;", "for each index", ... , "if (hasSwaps) goto start;"

Ну и по-моему, рокировка "array[j]>array[j+1]" будет полезной.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 23 Октябрь, 2017 15:58 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 458
Владимир Невзоров писал(а):
Представляю для сравнения исходную схему, и полученную из неё ДРАКОН схему.

1. Цикл while (swapped) надо переделать в цикл со стрелкой. Проверка в первый прогон не нужна.
2. Сравнение и перестановку и вытащил в отдельную функцию:
- Так основная функция будет понятней.
- Кроме того, новую функцию можно применять для других алгоритмов сортировки.

Вложение:
bubble.png
bubble.png [ 24.54 КБ | Просмотров: 1746 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 23 Октябрь, 2017 16:05 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3656
Откуда: Москва
1. Две иконы "Цикл for" должен быть шире по горизонтали, чем другие иконы.

2. Пустая икона в конце цикла for заставляет читателя морщить лоб и думать. Это плохо.
В нее желательно поместить поясняющую надпись.
Например, "Конец цикла" (Loop end)

==========================================

Степан Митькин писал(а):
надо переделать в цикл со стрелкой.

Степан, хороший термин: "цикл со стрелкой" (Arrow loop).

Он гораздо лучше, чем мой старый термин "обычный цикл".


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 23 Октябрь, 2017 16:48 

Зарегистрирован: Среда, 07 Январь, 2015 14:53
Сообщения: 715
Владимир Паронджанов писал(а):
Степан, хороший термин: "цикл со стрелкой" (Arrow loop).

Он гораздо лучше, чем мой старый термин "обычный цикл".

Лучше термин "Цикл с вопросом" - отображается смысл и структура цикла.

Лучше термин "Цикл ДЛЯ" заменить на термин "Цикл". Такой термин соответствует конструкциям цикла в языках программирования, имеет явно выраженные границы цикла. При программировании, наличие явно выраженных границ цикла, позволяет использовать операторы Continue и Break.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 24 Октябрь, 2017 17:40 

Зарегистрирован: Вторник, 27 Май, 2008 13:24
Сообщения: 153
В данном случае ДРАКОН не проясняет сущность алгоритма. Её проясняет картинка выше с клеточками. Или хотя бы просто фраза: "По завершении внутреннего цикла максимальный элемент оказывается на крайнем правом месте". Пожалуй здесь понятнее (в том числе визуально понятнее) псевдокод. И вылезает недостаток ДРАКОНа: цикл "FOR" визуально почти не отличим от "ДЕЙСТВИЕ" и потому вложенность циклов не бросается в глаза. А она существенна для понимания алгоритма. Должна "бросаться".

Псевдокод:
Дано:
----массив
Надо:
отсортировать элементы массива по возрастанию
Переменные:
----количествоЯчеек, номерЯчейки: целое
----обменяно: логическое
количествоЯчеек := длинна массива
обменяно := да
ПОКА обменяно == да
---|номерЯчейки := 1
---|ПОКА номерЯчейки < количествоЯчеек
---|---|обменяно := нет
---|---|ЕСЛИ элемент > следующего
---|---|---|поменять элементы местами
---|---|---|обменяно := да
---|---|номерЯчейки := номерЯчейки + 1
---|---|# максимальный для данного подмассива элемент на крайнем правом месте
---|количествоЯчеек := количествоЯчеек - 1 # укоротили массив на 1

Код:
Код:
var
  i, col, buf: int
  exchanged: bool
  x: array[1..10, int]
 
x = [10, 9, 1, 3, 2, 5, 4, 7, 6, 8]
col= 10

exchanged=true
while exchanged:
    i= 1
    while i < col:
        exchanged= false
        if x[i] > x[i+1]:
            buf= x[i]
            x[i]= x[i+1]
            x[i+1]= buf
            exchanged= true
        i= i+1
    col= col-1

# вывод результата
for j in 1..10:
    echo x[j]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 24 Октябрь, 2017 20:49 

Зарегистрирован: Среда, 03 Май, 2017 09:55
Сообщения: 127
dvuugl писал(а):
Пожалуй здесь понятнее (в том числе визуально понятнее) псевдокод. И вылезает недостаток ДРАКОНа: цикл "FOR" визуально почти не отличим от "ДЕЙСТВИЕ" и потому вложенность циклов не бросается в глаза. А она существенна для понимания алгоритма. Должна "бросаться".

Поддерживаю.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 25 Октябрь, 2017 12:08 

Зарегистрирован: Понедельник, 14 Декабрь, 2015 19:18
Сообщения: 108
Цитата:
По-моему, кодом понятнее: в коде есть отступы и видно где границы блоков. Видно: вот он цикл, вот мы перебираем все элементы, вот мы переставляем.
Вы же в Дракон-схеме вытянули всё в одну линию, и глазом не за что зацепиться. В итоге получилась колбаса из которой ничего непонятно.

Цитата:
В данном случае ДРАКОН не проясняет сущность алгоритма.

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

Цитата:
Ну и по-моему, рокировка "array[j]>array[j+1]" будет полезной.

Имеется ввиду сделать так - "array[j+1] < array[j]" ?
Если так, то что это даст?

Цитата:
2. Сравнение и перестановку и вытащил в отдельную функцию:

Круто получилось! А это в редакторе, который устанавливается на рабочий стол, сделано?
Цитата:
1. Цикл while (swapped) надо переделать в цикл со стрелкой. Проверка в первый прогон не нужна.

Цитата:
Степан, хороший термин: "цикл со стрелкой" (Arrow loop).
Он гораздо лучше, чем мой старый термин "обычный цикл".

Цитата:
Лучше термин "Цикл с вопросом" - отображается смысл и структура цикла.


Тогда вот так:

Вложение:
Bubble sort Readable2.png
Bubble sort Readable2.png [ 34.31 КБ | Просмотров: 1691 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 25 Октябрь, 2017 13:27 

Зарегистрирован: Среда, 07 Январь, 2015 14:53
Сообщения: 715
Дракон русский язык, так и надо писать на русском языке.
Не нужен иностранный язык!


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 25 Октябрь, 2017 13:45 

Зарегистрирован: Среда, 03 Май, 2017 09:55
Сообщения: 127
Владимир Невзоров писал(а):
Цитата:
Ну и по-моему, рокировка "array[j]>array[j+1]" будет полезной.

Имеется ввиду сделать так - "array[j+1] < array[j]" ?
Если так, то что это даст?


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

Если же сделать Yes направо ("нужен обмен?" -- направо да), тогда у схемы появится визуальная структура. Это можно сравнить с "отступом" в текстовом варианте.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 25 Октябрь, 2017 13:49 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3656
Откуда: Москва
Владимир Невзоров писал(а):
Тогда вот так:

Вложение:
Bubble sort Readable2.png

Владимир, попробуйте —
1) уберите заливку икон и
2) сделайте заливку фона, как в примерах Степана Митькина


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 25 Октябрь, 2017 15:09 

Зарегистрирован: Среда, 03 Май, 2017 09:55
Сообщения: 127
Владимир Паронджанов писал(а):
Владимир Невзоров писал(а):
Тогда вот так:
Вложение:
Bubble sort Readable2.png

Владимир, попробуйте —
1) уберите заливку икон и
2) сделайте заливку фона, как в примерах Степана Митькина

Лучше вообще всю заливку убирать. Зачем она?
Если бы она как-нибудь помогала пониманию, тогда да.
Но просто так -- лучше вообще без заливки.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 25 Октябрь, 2017 16:45 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 458
Владимир Невзоров писал(а):
Изображение

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

Вместо "Take array with elements" надо записать:
Current element is the first array element
(Поместить это между стрелочками)

То есть показываем, откуда начинаем.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 25 Октябрь, 2017 16:53 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 458
Вложение:
20171025155250.png
20171025155250.png [ 31.2 КБ | Просмотров: 1670 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 26 Октябрь, 2017 09:25 

Зарегистрирован: Понедельник, 14 Декабрь, 2015 19:18
Сообщения: 108
Владимир Паронджанов писал(а):
Владимир, попробуйте —
1) уберите заливку икон и
2) сделайте заливку фона, как в примерах Степана Митькина

Владимир Ситников писал(а):
Лучше вообще всю заливку убирать. Зачем она?
Если бы она как-нибудь помогала пониманию, тогда да.
Но просто так -- лучше вообще без заливки.

Убрал заливку окон - не будет глаз отвлекаться на цвет.
Решил оставить фон - так считаю лучше визуально алгоритм будет выделяться.

LKom писал(а):
Дракон русский язык, так и надо писать на русском языке.
Не нужен иностранный язык!

Просто хочется захватить весь мир:)

Степан Митькин писал(а):
А вот это лучшее представление пузырьковой сортировки, что я вообще видел.

Вот к этому и стремимся! Спасибо!

Степан Митькин писал(а):
Вместо "Take array with elements" надо записать:
Current element is the first array element
(Поместить это между стрелочками)

То есть показываем, откуда начинаем.

Вот измененная схема:
Вложение:
Bubble sort Readable3.png
Bubble sort Readable3.png [ 34.47 КБ | Просмотров: 1651 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 26 Октябрь, 2017 12:29 

Зарегистрирован: Вторник, 27 Май, 2008 13:24
Сообщения: 153
Код:
Пузырьковая сортировка
ПОВТОРЯТЬ
    ДЛЯ массива с 1-го элемента до предпоследнего
        ЕСЛИ текущий элемент больше следующего
            поменять местами текущий и следующий
ПОКА была хоть одна перестановка
Конец


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 30 Октябрь, 2017 12:23 

Зарегистрирован: Понедельник, 14 Декабрь, 2015 19:18
Сообщения: 108
Selection sort
(сортировка выбором)

Представляю Вашему вниманию схему из интернета и созданную ДРАКОН-схему:

Вложение:
selection sort - compare.png
selection sort - compare.png [ 61.87 КБ | Просмотров: 1566 ]


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

Картина работы алгоритма:
Вложение:
selection sort picture2.png
selection sort picture2.png [ 11.96 КБ | Просмотров: 1557 ]


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

Часовой пояс: UTC + 3 часа


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

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


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

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2018, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB