Студенти от НМА (следи и връзки)
Два начина да се преобразува целочислена променлива в стринг.
int p=23456;
data = String.valueOf(p);
data=p*p+"";
public static void main(String[] args) throws FileNotFoundException {
File file=new File("C:\Java\Name_of_Student\Project2\Project2\danni.txt");
Scanner sc=new Scanner(file);
sc.useDelimiter("\Z");
System.out.println(sc.next());
}
}
Едномерният масив и свързаният списък са две основни абстрактни структури от данни, които се използват за съхранение и управление на колекции от данни, но те имат различни характеристики и приложения.
Едномерен масив:
• Съхранява елементите си в последователни паметови локации.
• Всеки елемент може да бъде достъпен директно чрез индекс, което прави достъпа до произволен елемент много бърз (със сложност O(1)).
• Размерът на масива обикновено е фиксиран и трябва да бъде определен предварително.
• Добавянето или премахването на елементи може да бъде неефективно, тъй като може да изисква пренареждане на останалите елементи.
Свързан списък:
• Съхранява елементите си като поредица от възли, където всеки възел съдържа данни и референция (или указател) към следващия възел в списъка.
• Достъпът до елементите е последователен, което означава, че за да стигнете до определен елемент, трябва да преминете през всички предишни елементи (със сложност O(n) за достъп до n-тия елемент).
• Размерът на свързания списък е динамичен и може да се променя по време на изпълнение на програмата.
• Добавянето и премахването на елементи е много ефективно, тъй като изисква само промяна на референциите, без да се налага пренареждане на останалите елементи.
Изборът между едномерен масив и свързан списък зависи от конкретните изисквания на приложението и операциите, които трябва да се извършват над данните.
import java.util.LinkedList;
public class LinkedSpisuk {
public static void main(String[] args) {
// import java.util.LinkedList;
//public class Main {
// public static void main(String[] args) {
// Създаване на свързан списък
LinkedList animals = new LinkedList();
// Добавяне на елементи
animals.add("Лъв");
animals.add("Тигър");
animals.add("Мечка");
// Обхождане на списъка
for (String animal : animals) {
System.out.println(animal);
}
System.out.println("More actions!");
animals.add("Pile");
for (String animal : animals) {
System.out.println(animal);
}
LinkedList linkedList = new LinkedList();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
for (String parche : linkedList) {
System.out.println("parche= "+parche);
System.out.println(parche);
}
}
}
13. Сортиране на масив
Дефиниция
Да разгледаме отново задача 1 от предния урок. В нея трябваше да се напише програма, която да намира десетте най-високи резултата от НВО в 11. клас. За да я решим, съхранихме всички резултати в масив и извършихме обработка на елементите на масива, като 10 пъти го обходихме и всеки път намирахме и отстранявахме най-големия от останалите за търсене елементи.
Наистина това е едно добро решение. Но да си представим сега, че в задачата се иска да се изведат всички резултати, подредени в намаляващ (низходящ) ред, т.е. от най-високите към най-малките. Процедурата, която извършва такова подреждане, както и обратното подреждане – от най-малките към най големите числа (възходящ) ред, се нарича сортиране на елементите.
Класически алгоритми за сортиране
Съществуват различни алгоритми за сортиране. Едни от най-известните, но не най-ефективни, са алгоритмите на мехурчето и на пряката селекция. Те се пишат лесно, но работят бавно, ако броят на елементите е твърде голям (над 10000).
Алгоритъм на мехурчето (BubbleSort). Идеята на този алгоритъм е следната. Когато в газирана течност мехурче с газ, издигайки се нагоре, се сблъска с по-леки от него, то ги измества и продължава нагоре, а когато срещне по-тежко от него, тогава лекото остава на място, а тежкото тръгва нагоре и стига до края, ако не срещне друго, още по-тежко, разбира се.
Алгоритъмът на мехурчето за сортиране във възходящ ред работи по следния начин: взимаме първия елемент на масива и го сравняваме със следващия (втория) и разменяме стойностите им, ако първият е по-голям от втория. След това сравняваме втория елемент с третия и пак разменяме, ако има нужда. Ако нашият масив е от 10 елемента, след 9 такива сравнения най-вдясно ще „изплува“ най-голямата от десетте стойности. След това започваме отново, като първия елемент сравняваме с втория, и така нататък, но на този етап не извършваме сравняване на предпоследния и последния елемент. Продължаваме по подобен начин, като на всеки следващ етап намаляваме броя на сравненията с едно.
Пример: Нека имаме масив от 7 елемента със стойности: 5, 12, 3, 9, 8, 4, 1. При първото обхождане на елементите получаваме:
5 3 – разменят се, масивът става: 5, 3, 12, 9, 8, 4, 1
12>9 – разменят се, масивът става: 5, 3, 9, 12, 8, 4, 1
12>8 – разменят се, масивът става: 5, 3, 9, 8, 12, 4, 1
12>4 – разменят се, масивът става: 5, 3, 9, 8, 4, 12, 1
12>1 – разменят се, масивът става: 5, 3, 9, 8, 4, 1, 12
Най-големият елемент (12) е заел мястото си. При второ обхождане масивът става:
3, 5, 8, 4, 1, 9, 12, т.е. и предпоследният по големина елемент (9) е заел мястото.
При следващите четири обхождания масивът последователно ще стане:
3, 5, 4, 1, 8, 9, 12
3, 4, 1, 5, 8, 9, 12
3, 1, 4, 5, 8, 9, 12
1, 3, 4, 5, 8, 9, 12
Вижда се, че броят на обхожданията на елементите на масива е с едно по-малък от броя на елементите на масива, тъй като най-накрая първият елемент е заел мястото си, без да извършваме сравняване.
167
Значи, при і = n – 3 тялото на вътрешния цикъл ще се изпълни и n – 2 пъти, и т.н., при і = 0 ще се изпълни 1 път.
Затова сложността на алгоритъма ще бъде Т(n) = c(n-1+n-2+…+2+1) = сп(n-1)/2 = O(n2). За такъв алгоритъм казваме, че е с квадратна сложност.
Реализация на алгоритъма с пряка селекция е функцията SelectionSort:
static void SelectionSort()
{ // метод на пряка селекция
for(int i = 0; i < array.Length - 1; i++)
{ for(int j = i + 1; j array[j])
{ // размяна на елементите
int tmp = array[i]; array[i] array[j]
temp;
array[j];
}
Намерете сложността по време на този алгоритъм.
Какво трябва да се промени в реализацията на алгоритмите, ако искаме те да подреждат елементите на масива array в низходящ ред?
Стандартен алгоритъм за сортиране
Повечето езици за програмиране имат вграден метод, който извършва сортиране по някой известен алгоритъм за подредба на елементи. Езикът Java предлага статичния метод Arrays.sort() на класа Array на пространството от имена System, който извиква с параметър името на масива:
System.Array. Sort();
Алгоритъмът, който Sort използва, е бързото сортиране на Хоор (известно като QuickSort). Макар че сложността му по време в най-лошия случай е (п2), този алгоритъм е много по-бърз в огромно мнозинство от случаите от Алгоритъма на мехурчето и Алгоритъма на пряката селекция заради от- личната си сложност в средния случай – O(n.log, n). В следващ урок ще покажем алгоритъм, чиято сложност в най-лошия случай е 0(n.log, n).
Методът Sort е полиморфен, т.е. има няколко едноименни метода. Един от тях:
Sort(, , )
позволява да се сортира само част от масива в интервала на индексите [, + – 1].
Друга възможност е да се сортира по избран от програмиста критерий:
Sort(, IComparer)
където IComparer е интерфейс, в който трябва да се пренапише критерият за подредба на елементите. По премълчаване методът Sort подрежда елементите във възходящ ред на техните стойности, когато стойностите са от добре подреден тип на езика.
Това може да се промени чрез създаване на нов клас, който е наследник на IComparer и в който се пренаписва методът Compare. Този метод сравнява два обекта от масива и връща 1, ако трябва да се разменят двата елемента по време на сортирането, или -1, ако не трябва да се разменят.
Разгледайте примера по-долу, в който критерият за сортирането на числата е низходящ ред от сбора на цифрите им, а при равни суми по-напред е по-голямото число. Например, ако числата са 23, 18, 115, 46, 7, то след това сортиране те ще бъдат подредени в масива по следния начин: 46, 18, 115, 7, 23. За да използвате класа IComparer, трябва да включите в програмата и пространството от имена System.Collections. class OtherComparer: IComparer
{ public int Compare(object x, object y) { int хсору = (int)х, усору = (int)y;
int s1 = 0, 52 = 0; while (хсору != 0)
169
Сортирането чрез пряка селекция обхожда индексите на масива; за всеки индекс сортирането извиква функциите indexOfMinimum и swap. Ако дължината на масива е
, в масива има
индекса.
Тъй като при всяко изпълнение на цикъла се изпълняват два реда код, може да си помислиш, че сортирането чрез пряка селекция изпълнява
реда код. Това обаче не е вярно! Запомни, че indexOfMinimum и swap са функции: когато някоя от тях се извика, се изпълняват някакви редове код.
Колко реда код се изпълняват при едно извикване на swap? При обикновената имплементация има 3 реда и затова всяко извикване на swap отнема константно време.
Източник: https://bg.khanacademy.org/computing/computer-science/algorithms/sorting-algorithms/a/analysis-of-selection-sort
От сайта на Александър Георгиев: https://www.informatika.bg/lectures/complexity
В Гит: https://github.com/espr1t/action
The Funk Pink Panther – Staykov bass
http://www.facebook.com/video/embed/async/dialog/?url=%2F100000489287250%2Fvideos%2Fvb.100000489287250%2F1299346810091616%2F%3Ftype%3D3
Светлин Стайков
“No entiendo“
Сашо Даниелов – Пиано
Светлин Стайков – Бас
Виктор Викторов – Ударни
Музика и аранжимент – Sandrito Danielov
https://zelenkroki.wordpress.com/wp-admin/post.php?post=8113&action=edit&classic-editor
Блог на Zelenkroki 