Файл: Алгоритм Выполнения TreeSort.pdf

Обычно, когда ты забываешь написать var перед переменной, как в примере перед counter, JavaScript по-тихому создаёт глобальную переменную и использует её. В строгом режиме выдаётся ошибка. Это очень удобно. Однако, ошибка не выдаётся, когда глобальная переменная уже существует – только тогда, когда присваивание создаёт новую переменную.

Ещё одно изменение – привязка this содержит undefined в тех функциях, которые вызывали не как методы. Когда мы вызываем функцию не в строгом режиме, this ссылается на объект глобальной области видимости. Поэтому если вы случайно неправильно вызовете метод в строгом режиме, JavaScript выдаст ошибку, если попытается прочесть что-то из this, а не будет радостно работать с глобальным объектом.

2.2.3. Выбор языка программирования:

Для Упорядочивание массива я выбрал язык JavaScript.

2.3. Решение задачи:

Программа представляет собой Упорядочивании массива.

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

Для контроля работы пользователей, в программе предусмотрена функция «показать оценки».

Древесная сортировка:

Задача. Упорядочить заданный набор (возможно, с повторениями) некоторых элементов (чисел, слов, т.п.).

Алгоритм Выполнения TreeSort:

Для сортируемого множества элементов построить дерево двоичного поиска:
- первый элемент занести в корень дерева;
- для всех остальных элементов: начать проверку с корня; двигаться влево или вправо (в зависимости от результата сравнения с текущей вершиной дерева) до тех пор, пока не встретится такой же элемент, либо пока не встретится nil. Во втором случае нужно создать новый лист в дереве, куда и будет записано значение нового элемента.
Совершить синтаксический обход построенного дерева, печатая каждую встреченную вершину столько раз, сколько было ее вхождений в сортируемый набор.

Реализация:

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

new(root);

read(f,root^.chislo);

root^.kol:= 1;

root^.left:= nil;

root^.right:= nil;

while not eof(f) do

begin

read(f,x);

p:= root;

while true do

begin

if x = p^.chislo

then begin inc(p^.kol);

break

end;

if x > p^.chislo

then if p^.right <> nil

then p:= p^.right

else begin new(p^.right);

p:= p^.right;

p^.chislo:= x;

p^.kol:= 1;

p^.left:= nil;

p^.right:= nil;

break

end

(* x < p^.chislo *)

else if p^.left <> nil

then p:= p^.left

else begin new(p^.left);

p:= p^.left;

p^.chislo:= x;

p^.kol:= 1;

p^.left:= nil;

p^.right:= nil;

break

end

end;

2.3.1. Блок-схема алгоритма:

Алгоритм Комп Связ-Итер:

Прочитать начало и конец очередного ребра. Далее возможны 4 различные ситуации:

Оба конца ребра еще не относятся ни к одной из ранее встретившихся компонент связности ( mark[u]=0 и mark[v]=0 ). В этом случае количество компонент связности kol увеличивается на единицу, а новая компонента связности получает очередной номер ks+1.
Один конец ребра уже относится к какой-то компоненте связности, а второй - еще нет ( mark[u]=0, а mark[v]<>0 ). В этом случае общее количество компонент связности kol остается прежним, а непомеченный конец ребра получает ту же пометку, что и второй его конец.
Оба конца нового ребра относятся к одной и той же компоненте связности ( mark[u]= mark[v]<>0 ). В этом случае не нужно производить никаких действий.
Концы нового ребра относятся к разным компонентам связности ( ). В этом случае нужно объединить две ранее созданные компоненты связности в одну. Общее количество компонент связности kol уменьшается на 1, а все вершины, принадлежавшие к более новой компоненте связности (больший номер), получают новую пометку. Заметим, что переменная ks, обозначающая очередной свободный номер для следующей компоненты связности, в данном случае изменяться не должна, поскольку нет никакой гарантии, что изменен будет номер именно самой последней компоненты связности.

По окончании работы этого алгоритма в массиве mark будет записано S различных целых чисел, каждое из которых будет означать отдельную компоненту связности. Кроме того, в массиве могут остаться нулевые компоненты: каждая из них будет соответствовать изолированной вершине, которая тоже является отдельной компонентой связности. Следовательно, количество нулей должно быть прибавлено к количеству компонент, найденному в процессе работы основного алгоритма.

Реализация задачи:

kol:=0;

ks:=0;

while not eof(f) do

begin

readln(f,u,v);

if mark[u]=0

then if mark[v]=0

then begin {случай 1}

inc(kol);

inc(ks);

mark[u]:= ks;

mark[v]:= ks;

end

else mark[u]:= mark[v] {случай 2}

else if mark[v]=0

then mark[v]:= mark[u]

{случай 2 - симметричный}

else if mark[u]<>mark[v] {случай 4}

then begin

max:= v;

min:= u;

if u>v then begin

max:= u;

min:= v end;

for i:= 1 to n do

if mark[i]= max

then mark[i]:= min;

dec(kol);

end

end;

for i:=1 to N do

if mark[i]=0 then inc(kol);

2.3.2. Описание переменных: идентификатор, тип:

javascript удалить элемент массива можно при помощи оператора delete:

var myColors = new Array("red", "green", "blue");

delete myColors[1];

alert(myColors); // red,,blue

2.3.3. Листинг программы:

При сравнении 40 и 100 метод sort() вызывает функцию сравнения (40,100).
Функция вычисляет 40-100, и возвращает -60 (отрицательное значение).
Функция сортировки сортирует 40 как значение ниже 100.
Этот фрагмент кода можно использовать для сортировки чисел и сортировки по алфавиту:

<button onclick="myFunction1()">Сортировать по алфавиту</button>
<button onclick="myFunction2()">Сортировать по числам</button>

<p id="demo"></p>

<script>
var points = [40, 100, 1, 5, 25, 10];
document.getElementById("demo").innerHTML = points;

function myFunction1() {
    points.sort();
    document.getElementById("demo").innerHTML = points;
}
function myFunction2() {
    points.sort(function(a, b){return a - b});
    document.getElementById("demo").innerHTML = points;
}
</script>

Листинг программы в текстовом редакторе. Скриншот листинга в окне компилятора

2.3.5. Контрольные примеры:

Найти наибольшее или наименьшее значение массива:

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

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

Сортировка по возрастанию:

Пример

var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return a - b});
// теперь points[0] содержит наименьшее значение
// и points[points.length-1] содержит наибольшее значение

Сортировка по убыванию:

Пример

var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return b - a});
// теперь points[0] содержит наибольшее значение
// и points[points.length-1] содержит наименьшее значение

Три разных варианта входных данных + варианты ошибок пользователя