среда, 1 августа 2012 г.

questions: loop




    Цель данной лекции: рассмотреть циклы for и while, вложенные циклы, алгоритм сортировки "пузырьком", алгоритм сортировки вставкой, алгоритм бинарного поиска, алгоритм слияния сортированных массивов, идиому обмена элементов значениями через дополнительную переменную, идиому обмена элементов значениями без дополнительной переменной

    Также рассмотрим рассмотрим: префиксный и постфиксный инкремент/декремент, преобразование любого Java-типа в String, конкатенацию строк, одномерные массивы, System.arrayCopy(...)

    Темы для самостоятельной проработки: многомерные массивы, switch, тернарный условный оператор.
    В теории программирования доказано, что программу для решения задачи любой сложности можно составить только из трех структур, называемых следованием, ветвлением и циклом. Этот результат установлен Боймом и Якопини еще в 1966 году путем доказательства того, что любую программу можно преобразовать в эквивалентную, состоящую только из этих структур и их комбинаций.
    Следование, ветвление и цикл называют базовыми конструкциями структурного программирования.
Подтемы
    - Array Invertion
    - Sorted Array Merging
    - Bubble Sort
    - Insertion Sort
    - Selection Sort

    Вычисление/алгоритм удобно представлять в виде комбинации нескольких "поведений". К базовым поведениям относятся: ветвление (if, switch), 

----------------------------------------------------------------
В Java есть 4 типа циклов
- "классический" for (for (int k = 0; k < 3; k++) {...})
- while (int k = 0; while(k < 3) {...; k++;})
- do .. while (int k = 0; do {...; k++} while (k < 3))
- foreach (for (Integer i : new ArrayList<Integer>()) {...})

    Сортировка может делаться с различной целью. 
    Типичные: 
    - необходимо вывести все записи в возрастающем/убывающем порядке
    - необходимо взять из массива фиксированное количество максимальных/минимальных элементов (пример 20 самых больших из массива в 100 элементов)
    - поиск всех дубликатов в массиве
    - этап подготовки массива к поиску элементов с помощью алгоритма бинарного поиска 
    - этап подготовки массива к поиску диапазонов с помощью алгоритма бинарного поиска

   Необходимо помнить, что индексация в массиве начинается с 0. Это значит, что в массиве размером 10 элементов
int[] arr = new int[10];
допустимыми индексами будут 0, 1, 2, 3, ..., 8, 9.

     Читаем счетчик цикла

    Цикл весьма гибкая конструкция и позволяет многое. Например:

    Перебрать числа в прямом порядке:
public class TestFor00 {
    public static void main(String[] args) {
        for(int k = 0; k < 10; k++) {
            System.out.print(k + " ");
        }
    }
}
>> 0 1 2 3 4 5 6 7 8 9

     Перебрать числа в прямом порядке через один:
public class TestFor10 {
    public static void main(String[] args) {
        for(int k = 0; k < 10; k+=2) {
            System.out.print(k + " ");
        }
    }
}
>> 0 2 4 6 8

    Перебрать числа в обратном порядке:
public class TestFor20 {
    public static void main(String[] args) {
        for(int k = 9; k >= 0; k--) {
            System.out.print(k + " ");
        }
    }
}
>> 9 8 7 6 5 4 3 2 1 0

    Перебрать числа в обратном порядке через один:
public class TestFor30 {
    public static void main(String[] args) {
        for(int k = 9; k >= 0; k-=2) {
            System.out.print(k + " ");
        }
    }
}
>> 9 7 5 3 1

    Пользуемся счетчиком цикла

    Мы также можем читать счетчик цикла и использовать его как индекс в массиве.

    Перебрать элементы массива в прямом порядке:
public class TestFor01 {
    public static void main(String[] args) {
        int[] arr = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
        for(int k = 0; k < arr.length; k++) {
            System.out.print(arr[k] + " ");
        }
    }
}
>> 0 10 20 30 40 50 60 70 80 90

    Перебрать элементы массива в прямом порядке через один:
public class TestFor11 {
    public static void main(String[] args) {
        int[] arr = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
        for(int k = 0; k < arr.length; k+=2) {
            System.out.print(arr[k] + " ");
        }
    }
}
>> 0 20 40 60 80

    Перебрать элементы массива в обратном порядке:
public class TestFor21 {
    public static void main(String[] args) {
        int[] arr = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
        for(int k = arr.length - 1; k >= 0; k--) {
            System.out.print(arr[k] + " ");
        }
    }
}
>> 90 80 70 60 50 40 30 20 10 0

    Перебрать элементы массива в обратном порядке через один:
public class TestFor31 {
    public static void main(String[] args) {
        int[] arr = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
        for(int k = arr.length - 1; k >= 0; k-=2) {
            System.out.print(arr[k] + " ");
        }
    }
}
>> 90 70 50 30 10

    Меняем счетчик цикла

    Более того, счетчик цикла можно не только читать, но и изменять. Это считается "дурным тоном", но компилятор этому не препятствует.

    Покажем несколько "странных" конструкций.


    Цикл, "стоящий на месте":
public class InfinityFor {
    public static void main(String[] args) {
        for (int k = 0; k < 10; k++) {
            System.out.print(k + " ");
            k--;
        }
    }
}
>> 0 0 0 0 0 0 0 0 0 0 ...
Выводит бесконечную последовательность нолей.

    Цикл, "проскальзывающий назад":
public class BackwardFor {
    public static void main(String[] args) {
        for (int k = 0; k < 10; k++) {
            System.out.print(k + " ");
            k-=2;
        }
    }
}
>> 0 -1 -2 -3 -4 -5 -6 ...

 Вопрос: будет ли этот цикл выводить бесконечную последовательность или остановится?

     Вложенный FOR

    Циклы становятся более интересными, когда мы "вкладываем" один цикл в другой.
    Простое вложение - циклы не зависят друг от друга (декартово произведение множеств значений индексов, т.е. все возможные пары):
public class TestNestedFor {
    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                System.out.print("(" + i + "," + j + ") ");
            }
            System.out.println();
        }
    }
}
>> (0,0) (0,1) (0,2) (0,3) (0,4) 
>> (1,0) (1,1) (1,2) (1,3) (1,4) 
>> (2,0) (2,1) (2,2) (2,3) (2,4) 
>> (3,0) (3,1) (3,2) (3,3) (3,4) 
>> (4,0) (4,1) (4,2) (4,3) (4,4)
Растущая пирамида - второй предел внутреннего индекса зависит от внешнего индекса
public class TestPyramidForAsc {
    public static void main(String[] args) {
        int[] arr = {0, 10, 20, 30, 40};
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.print(arr[j] + " ");
            }
            System.out.println();
        }
    }
}
>> 0 
>> 0 10 
>> 0 10 20 
>> 0 10 20 30 
>> 0 10 20 30 40
    Убывающая пирамида - второй предел внутреннего индекса зависит от внешнего индекса
public class TestPyramidForDesc {
    public static void main(String[] args) {
        int[] arr = {0, 10, 20, 30, 40};
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                System.out.print(arr[j] + " ");
            }
            System.out.println();
        }
    }
}
>> 0 10 20 30 40 
>> 0 10 20 30 
>> 0 10 20 
>> 0 10 
>> 0

     Цикл WHILE
   TBD

    Лабораторные
    Задания лабораторных можно прочитать на этой странице.

Автор: