Реализация алгоритмов поиска на языке Java

Размещено на http://www.allbest.ru/

Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет информатики и радиоэлектроники»

Кафедра информационных радиотехнологий

Контрольная работа

По дисциплине «Технология проектирования программного обеспечения информационных систем»

Выполнил:

Манько С.К.

Минск БГУИР 2019



Задание 1

Реализовать три алгоритма поиска на языке Java.

- Линейный поиск.

-Улучшенный линейный поиск.

- Поиск с ограничителем.

Решение

package edu;

import java.io.IOException;

import java.util.Random;

public class Task01 {

int[] A = new int[20];

int request;

Task01() {

fillArray();

System.out.print("Введите число от 0 до 9: ");

try {

request = System.in.read() - 48;

System.out.println(search01());

System.out.println(search02());

System.out.println(search03());

}

catch (Exception Ex) {

}

}

void fillArray() {

for(int i = 0; i < A.length; i++) {

A[i] = Math.abs(new Random().nextInt() % 10);

System.out.print(A[i]);

}

System.out.println();

}

static public void main(String Args[]) {

new Task01();

}

String search01() throws IOException {// находит первое вхождение искомого числа

String answer = "";

System.out.print("Поиск по последнему вхождению. Результат: ");

for (int i = 0; i < A.length; i++) {

if(A[i] == (int) request) {

answer = ((i + 1) + " ");

}

}

return answer;

}

String search02() throws IOException { // находит последнее вхождение искомого числа

String answer = "";

System.out.print("Поиск по первому вхождению. Результат: ");

for (int i = 0; i < A.length; i++) {

if(A[i] == (int) request) {

answer = ((i + 1) + " ");

break;

}

}

return answer;

}

String search03() throws IOException {// находит все вхождения искомого числа

String answer = "";

System.out.print("Поиск по всем вхождениям. Результат: ");

for (int i = 0; i < A.length; i++) {

if(A[i] == (int) request) {

answer += ((i + 1) + " ");

}

}

if(answer == "") return "No matches";

else return answer;

}

}

Задание 2

1 Сделать сортировку выбором;

2 Сделать быструю рекурсивную сортировку.

- Сортировка выбором.

package zadanie2;

import java.util.Scanner;

public class Zadanie21 {

public static void main(String[] args) {

System.out.println("----------------------------");

System.out.println("-- 2.1 Сортировкавыбором --");

System.out.println("----------------------------");

Scanner input = new Scanner(System.in);

System.out.println("Введите длинну массива: ");

int size = input.nextInt();

int A[] = new int[size];

System.out.println("Введитеэлементымассива: ");

for(int i = 0; i < size; i++){

A[i] = input.nextInt();

}

System.out.println("Заданныймассивэлементов: ");

for(int i = 0; i < size; i++){

System.out.print(" " + A[i]);

}

System.out.println();

for(int i=0; i<A.length-1; i++){

int smallest=i;

for(int j=i+1; j<A.length; j++){

if(A[j]<A[smallest]){

smallest=j;

} линейный поиск язык автомат

int temp=A[smallest];

A[smallest]=A[i];

A[i]=temp;

}

}

System.out.println("Массивпослесортировки: ");

for(int i = 0; i < size; i++){

System.out.print(" " + A[i]);

}

System.out.println();

}

}

- Быстрая рекурсивная сортировка.

package zadanie2;

importjava.util.Random;

public class Zadanie22 {

public static int ARRAY_LENGTH=30;

private static int array[]=new int[ARRAY_LENGTH];

private static Random generator=new Random();

public static void initArray(){

for(int i=0; i<ARRAY_LENGTH; i++){

array[i]=generator.nextInt(100);

}

}

public static void printArray(){

for(int i=0; i<ARRAY_LENGTH-1; i++){

System.out.print(array[i]+" ");

}

System.out.println(array[ARRAY_LENGTH-1]);

}

public static void quickSort(){

intstartIndex=0;

intendIndex=ARRAY_LENGTH-1;

doSort(startIndex, endIndex);

}

private static void doSort(int start, int end){

if(start>=end)

return;

int i=start, j=end;

int cur=i-(i-j)/2;

while(i<j){

while(i<cur && (array[i]<=array[cur])){

i++;

}

while(j>cur && (array[cur]<=array[j])){

j--;

}

if(i<j){

int temp=array[i];

array[i]=array[j];

array[j]=temp;

if(i==cur)

cur=j;

elseif(j==cur)

cur=i;

}

}

doSort(start, cur);

doSort(cur+1, end);

}

public static void main(String[] args) {

System.out.println("---------------------------");

System.out.println("-- 2.2 Быстраясортировка --");

System.out.println("---------------------------");

initArray();

printArray();

quickSort();

printArray();

}

}

Задание 3

Реализовать поиск подстрок с помощью конечного автомата.

- Поиск подстрок с помощью конечного автомата.

package zadanie3;

public class Zadanie3 {

private static String T = "FADDADFAADFG";

private static String P = "ADF";

private static int n = T.length();

private static int m = P.length();

public static void main(String[] args) {

int symbol = nextState(T);

System.out.println(symbol - m + 1);

}

public static int nextState(String T){

int state = 0;

int symbol = 0;

while(symbol <T.length()){

char c = T.charAt(symbol);

switch(state){

case 0: if(c == 'A'){

state = 1;

}else{

state = 0;

};

break;

case 1: if(c == 'D'){

state = 2;

}else{

if(c =='A'){

state = 1;

}else{

state = 0;

}

};

break;

case 2: if(c == 'F'){

state = 3;

return symbol;

}else{

if(c =='A'){

state = 1;

}else{

state = 0;

}

};

break;

case 3: if(c == 'A'){

state = 1;

}else{

state = 0;

};

break;

}

symbol++;

}

return -1;

}

}

Задание 4

- Создание объектов

package edu;

import java.util.Random;

public class Task04 { //класс программы

Worker office[] = new Worker[10];

Task04() {

System.out.println("Работа с объектами\n\nпо условию у начальника зарплатa в двое выше чем у обычного сотрудника\nразбежка в зарплатах - 150$\n");

fillOffice(); //метод таска

}

static public void main(String args[]) {

new Task04();

}

void fillOffice() { //заполнение массива

for(int i = 0; i < office.length - 1; i++) {

office[i] = new Worker(getRandomName(), getRandomBirthDay(), getRandomMonthPay());

}

office[office.length - 1] = new Supervisor(getRandomName(), getRandomBirthDay(), getRandomMonthPay());

System.out.println("\nПовышаем зарплату на 50 процентов\n");

for(int i = 0; i < office.length; i++) {

office[i].increaceMonthPay(0.5);

}

}

String getRandomName() {

String firstName[] = {"Bob", "Lusy", "Edd", "Sarah", "Tom", "Jane", "Phill", "Aliss", "John", "Anna"};

String lastName[] = {"Brown", "Shepard", "Williams", "Smith", "Collins", "Stone", "White", "Black", "Cotton", "Shefild"};

return firstName[Math.abs(new Random().nextInt() % 10)] + " " + lastName[Math.abs(new Random().nextInt() % 10)];

}

String getRandomBirthDay() {

return (Math.abs(new Random().nextInt()) % 27 + 1) + "." + (Math.abs(new Random().nextInt()) % 12 + 1) + "." + (Math.abs(new Random().nextInt()) % 20 + 1980);

}

int getRandomMonthPay() {

return Math.abs(new Random().nextInt()) % 150 + 250;

}

}

class Worker {

String name;

String birthday;

int monthPay;

Worker(String name, String birthday, int monthPay) {

this.name = name; //this.**** - обращение к материнскому объекту

this.birthday = birthday;

this.monthPay = monthPay;

System.out.println(message());

}

void increaceMonthPay(double size) {

monthPay *= (1 + size);

System.out.println("Name: " + name + " month pay increace to: " + monthPay + "$");

}

String message() {

return "Name: " + name + " - worker, births at " + birthday + " month pay: " + getMonthPay() + "$";

}

int getMonthPay() { //возращает значение месячной зарплаты

return monthPay;

}

}

class Supervisor extends Worker{ //метод наследования

int monthPayCoeficient = 2;

Supervisor(String name, String birthday, int monthPay) {

super(name, birthday, monthPay);

super.name += " (supervisor)";

super.monthPay = monthPay * monthPayCoeficient;

}

@Override //анотация

String message() {

return "Name: " + name + " - supervisor, births at " + birthday + " month pay: " + getMonthPay() * 2 + "$";

}

}



Литература

1. Берд, Барри Java для чайников / Барри Берд. - М.: Диалектика / Вильямс, 2013. - 521 c.

2. Гарнаев, Андрей WEB-программирование на Java и JavaScript / Андрей Гарнаев , Сергей Гарнаев. - Москва: СПб. [и др.] : Питер, 2017. - 718 c.

3. Гонсалвес, Энтони Изучаем Java EE 7 / Энтони Гонсалвес. - М.: Питер, 2016. - 640 c.

4. Гупта, Арун Java EE 7. Основы / АрунГупта. - М.: Вильямс, 2014. - 336 c.

5. Монахов, В. Язык программирования Java и среда NetBeans (+ CD-ROM) / В. Монахов. - М.: БХВ-Петербург, 2012. - 720 c.

6. Савитч, Уолтер Язык Java. Курс программирования / УолтерСавитч. - М.: Вильямс, 2015. - 928 c.

Размещено на Allbest.ru

...