}
// сконструировать очередь из массива исходных значений Queue(char а[]) { putloc = 0; getloc = 0; q = new char[a.length+1]; for(int i = 0; i < a.length; i++) put(a[i]);
}
// поместить символ в очередь void put(char ch) { if(putloc==q.length-1) { System.out.println(" - Queue is full."); return; } putloc++; q[putloc] = ch;
}
// извлечь символ из очереди char get() { if(getloc == putloc) { System.out.println(" - Queue is empty."); return (char) 0; } getloc++; return q[getloc];
} }
// продемонстрировать класс Queue в действии class QDemo2 { public static void main(String args[]) { // построить пустую очередь для хранения 10 элементов Queue ql = new Queue(10); char name[] = {'Т', 'o', 'm'}; // построить очередь из массива Queue q2 = new Queue(name); char ch; int i; // поместить ряд символов в очередь ql for(i=0; i < 10; i++) ql.put((char) ('A1 + i)); // построить одну очередь из другой очереди Queue q3 = new Queue(ql); // показать очереди System.out.print("Contents of qclass="underline" "); for(i=0; i < 10; i++) { ch = ql.get(); System.out.print(ch); } System.out.println("\n"); System.out.print("Contents of q2: "); for(i=0; i < 3; i++) { ch = q2.get(); System.out.print(ch); } System.out.println("\n"); System.out.print("Contents of q3: "); for(i=0; i < 10; i++) { ch = q3.get(); System.out.print(ch); } }
} ``` Результат выполнения данной программы выглядит следующим образом: ``` Contents of qclass="underline" ABCDEFGHIJ Contents of q2: Tom Contents of q3: ABCDEFGHIJ ``` Рекурсия
В Java допускается, чтобы метод вызывал самого себя. Этот процесс называется рекурсией, а метод, вызывающий самого себя, — рекурсивным. Вообще говоря, рекурсия представляет собой процесс, в ходе которого нечто определяет самое себя. В этом отношении она чем-то напоминает циклическое определение. Рекурсивный метод отличается в основном тем, что он содержит оператор, в котором этот метод вызывает самого себя. Рекурсия является эффективным механизмом управления программой.
Классическим примером рекурсии служит вычисление факториала числа. Факториал числа N представляет собой произведение всех целых чисел от 1 до N. Например, факториал числа 3 равен 1x2x3, или 6. В приведенном ниже примере программы демонстрируется рекурсивный способ вычисления факториала числа. Для сравнения в эту программу включен также нерекурсивный вариант вычисления факториала числа. // Простой пример рекурсии, class Factorial { // Рекурсивный метод, int factR(int n) { int result; if(n==l) return 1; // Рекурсивный вызов метода factRO . result = factR(n-l) * n; return result; } // Вариант программы, вычисляющий факториал итеративным способом, int factl(int n) { int t, result; result = 1; for(t=l; t <= n; t++) result *= t; return result; } } class Recursion { public static void main(String args[]) { Factorial f = new Factorial(); System.out.println("Factorials using recursive method."); System.out.println("Factorial of 3 is " + f.factR(3)); System.out.println("Factorial of 4 is " + f.factR(4)); System.out.println("Factorial of 5 is " + f.factR(5)); System.out.println(); System.out.println("Factorials using iterative method."); System.out.println("Factorial of 3 is " + f.factl(3)); System.out.println("Factorial of 4 is " + f.factl(4)); System.out.println("Factorial of 5 is " + f.factl(5)); } }
Ниже приведен результат выполнения данной программы. Factorials using recursive method. Factorial of 3 is 6 Factorial of 4 is 24 Factorial of 5 is 120 Factorials using iterative method. Factorial of 3 is 6 Factorial of 4 is 24 Factorial of 5 is 120
Действия нерекурсивного метода fact I () не требуют особых пояснений. В нем используется цикл, в котором числа, начиная с 1, последовательно умножаются друг на друга, постепенно образуя произведение, дающее факториал.
Рекурсивный метод f actR () действует несколько сложнее. Когда метод factR() вызывается с аргументом, равным 1, он возвращает 1, а иначе —произведение, определяемое из выражения factR(n-l)*n. Для вычисления этого выражения вызывается метод factR () с аргументом п-1. Этот процесс повторяется до тех пор, пока значение переменной п не окажется равным 1, после чего из предыдущих вызовов данного метода начнут возвращаться полученные значения. Например, при вычислении факториала 2 первый вызов метода factR () повлечет за собой второй вызов того же самого метода, но с аргументом 1. В результате метод возвратит значение 1, которое затем умножается на 2 (т.е. исходное значение переменной п). В результате всех этих вычислений будет получен факториал, равный 2. По желанию в тело метода factR () можно ввести операторы println (), чтобы сообщать, на каком именно уровне осуществляется очередной вызов, а также отображать промежуточные результаты вычислений.
Когда метод вызывает самого себя, в системном стеке распределяется память для новых локальных переменных и параметров, и код метода выполняется с этими новыми переменными и параметрами с самого начала. При рекурсивном вызове метода не создается его новая копия, но лишь используются его новые аргументы. А при возврате из каждого рекурсивного вызова старые локальные переменные и параметры извлекаются из стека, и выполнение возобновляется с точки вызова в методе. Рекурсивные методы можно сравнить по принципу действия с постепенно сжимающейся и затем распрямляющейся пружиной.
Рекурсивные варианты многих процедур могут выполняться немного медленнее, чем их итерационные эквиваленты, из-за дополнительных затрат системных ресурсов на неоднократные вызовы метода. Если же таких вызовов окажется слишком много, то в конечном итоге может быть переполнен системный стек. А поскольку параметры и локальные переменные рекурсивного метода хранятся в системном стеке и при каждом новом вызове этого метода создается их новая копия, то в какой-то момент стек может оказаться исчерпанным. Если возникнет подобная ситуация, исполняющая система Java сгенерирует исключение. Но в большинстве случаев об этом не стоит особенно беспокоиться. Как правило, переполнение системного стека происходит тогда, когда рекурсивный метод выходит из под контроля.
Главное преимущество рекурсии заключается в том, что она позволяет реализовать некоторые алгоритмы яснее и проще, чем итерационным способом. Например, алгоритм быстрой сортировки довольно трудно реализовать итерационным способом. А некоторые задачи, например искусственного интеллекта, очевидно, требуют именно рекурсивного решения. При написании рекурсивных методов следует непременно указать в соответствующем месте условный оператор, например if, чтобы организовать возврат из метода без рекурсии. В противном случае возврат из вызванного однажды рекурсивного метода может вообще не произойти. Подобного рода ошибка весьма характерна для реализации рекурсии в практике программирования. Поэтому рекомендуется пользоваться операторами, содержащими вызовы метода println (), чтобы следить за происходящим в рекурсивном методе и прервать его выполнение, если в нем обнаружится ошибка. Применение ключевого слова static
Иногда требуется определить такой член класса, который будет использоваться независимо от всех остальных объектов этого класса. Как правило, доступ к члену класса организуется посредством объекта этого класса, но в то же время можно создать член класса для самостоятельного применения без ссылки на конкретный экземпляр объекта. Для того чтобы создать такой член класса, достаточно указать в самом начале его объявления ключевое слово static. Если член класса объявляется как static, он становится доступным до создания любых объектов своего класса и без ссылки на какой-нибудь объект. С помощью ключевого слова static можно объявлять как переменные, так и методы. Наиболее характерным примером члена типа static служит метод main (), который объявляется таковым потому, что он должен вызываться виртуальной машиной Java в самом начале выполняемой программы.
Для того чтобы воспользоваться членом типа static за пределами класса, достаточно указать имя этого класса с оператором-точкой. Но создавать объект для этого не нужно. В действительности член типа static оказывается доступным не по ссылке на объект, а по имени своего класса. Так, если требуется присвоить значение 10 переменной count типа static, являющейся членом класса Timer, то для этой цели можно воспользоваться следующей строкой кода: Timer.count = 10;