Рекурсия как способ организации обработки данных

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

1. Рекурсия

Чтобы понять рекурсию, нужно понять рекурсию.

Автор неизвестен

Рекурсия - это такой способ организации обработки данных, при котором программа вызывает сама себя. Рекурсия называется прямой тогда, когда программа вызывает сама себя непосредственно или косвенной - когда программа вызывает саму себя опосредованно, через вызов других программ. Соответственно метод, который внутри своего тела вызывает сам себя, называется рекурсивным методом. Количество вложенных вызовов метода называется глубиной рекурсии.

Существует ряд задач, при решении которых обоснованным является использование именно рекурсивных методов. Например, вычисление различных рекуррентных последовательностей, в которых каждый следующий член, начиная с некоторого, определяется через предыдущие значения.

1.1 Стек вызовов

Чтобы понять, как работает рекурсивный метод, нужно знать, как распределяется память во время исполнения программы. В текущий момент времени может исполняться только один единственный метод из всей программы. Это значит, что, если метод а() вызывает в своем теле метод b(), а сам а() вызывается в main(), то при запуске программы управление сначала будет передано методу main(), затем методу а(), затем методу b(). Метод b() вернёт результат и управление в а(), а()вернет результат и управление в main(), и только потом будут выполняться команды, указанные в методе main()в строках, записанных после строки с вызовом a().

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

1.2 Рекурсия без ветвления

Напишем рекурсивную программу, вычисляющую факториал введенного натурального числа. Напомним, что факториал n! целого неотрицательного числа n задается следующим рекуррентным соотношением:

0! = 1,

n! = n · (n ? 1)! для n > 0.

В задаче будем использовать рекурсивный метод, параметром которого является введенное натуральное число, а результатом - значение его факториала.

import java.util.Scanner;

class FactR {

static long fact(int n) {

return (n == 0)?1:n*fact(n-1);

}

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

System.out.println("Введите n:");

System.out.printf("n!=%d",fact(scan.nextInt()));

}

}

В приведенной программе метод fact() получает на вход целое число n и рекурсивно вычисляет его факториал. Рассмотрим процесс выполнения данной программы дляn=3 более подробно (рис.6.1).

Так как число 3 отлично от нуля, метод попытается умножить число 3 на fact(2), но последняя величина для ее вычисления требует вызова метода fact() с аргументом 2. В результате чего выполнение метода fact() с аргументом 3 приостановится, и программа приступит к выполнению этого же метода с меньшим на единицу значением аргумента. Вычисление fact(2) потребует нахождения fact(1), что вызовет появление еще одного - третьего экземпляра метода fact(). Он, в свою очередь, вызовет fact(0). К этому моменту стек вызовов метода накопит уже четыре вызова экземпляров метода с разными аргументами. При этом вычисления во всех вызванных ранее экземплярах метода приостановлены до завершения работы с последним.

Метод fact(), вызванный с нулевым аргументом, самостоятельно вычислит и вернет с помощью оператора return результат - число 1. Верхний элемент из стека вызовов методов после этого удалится, и возобновятся вычисления величины fact(1). Этот процесс продолжится до тех пор, пока стек вызовов не станет пустым, что произойдет по завершению вычисления значения fact(3). В итоге в метод main()будет возвращено значение 6. Описанный процесс хорошо иллюстрирует диаграмма, представленная на рис. 5.1. На ней наглядно видно, что при выполнении рекурсивного метода сначала происходит так называемое «рекурсивное погружение», а затем «возврат вычисленных результатов».



Рис.6.1 - Диаграмма стека вызовов рекурсивного метода fact(3)

Каждый рекурсивный метод должен иметь условие завершения рекурсии, в противном случае, он будет вызывать себя до тех пор, пока не переполнится стек вызовов. По условию завершения осуществляется возвратиз рекурсивного метода без выполнения рекурсивного вызова. В методе fact() для этого была использована тернарная условная операция, но можно было использовать и операторif.

Отметим, что алгоритм, реализованный в рекурсивной форме, всегда можно представить в итерационном виде, и наоборот. Так, в разделе 3 нами уже была решена задача вычисления факториала натурального числа с использованием цикла.

В большинстве случаев рекурсивные версии программ выполняются несколько медленнее, чем их итерационные варианты. Это связано с дополнительными вызовами методов. Кроме того, поскольку параметры и локальные переменныесохраняютсявстеке,акаждыйновыйвызовсоздаетновыекопии этих значений, то на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Но, несмотря на это, существуют алгоритмы, реализация которых с помощью рекурсивных методов все же намного проще и понятнее, чем с помощью итераций.

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

Задача 1.1 Напишите метод, который читает с клавиатуры положительные целые числа до ввода первого отрицательного числа, и печатает их в обратном порядке. Количество чисел заранее неизвестно.

Объяснение: напишем рекурсивный метод. Условием завершения рекурсивного метода будет условие ввода отрицательного числа. Диаграмма вызовов рекурсивного метода revers() при вводе последовательности из трех положительных чисел приведена на рис. 6.2. При рекурсивном вызове переменные вызывающего метода остаются в памяти и их значения становятся доступными после завершения рекурсивного вызова. Поэтому если в теле метода после строки с рекурсивным вызовом записать строку с оператором вывода на экран, то введенные значения будут выведены в обратном порядке.

Рис.6.2 - Диаграмма вызовов рекурсивного метода revers()

import java.util.Scanner;

class Ex_6_1

{

static void revers(){

int a = new Scanner(System.in).nextInt();

if (a<0) return;

revers();

System.out.printf("%d ",a);

}

public static void main (String[] args)

{revers();}

}

Результат:

4

6

8

9

12

-5

12 9 8 6 4

Среди рекурсивных методов можно выделить методы, построенные по схеме хвостовой рекурсии. Такие методы вызывают себя только перед самым выходом из метода, т.е. оператор return в теле такого метода является самой последней инструкцией. К хвостовой рекурсии можно отнести рассмотренный ранее рекурсивный метод вычисления факториала. Его последняя инструкция выглядит так:

return (n==0)?1:n*fact(n-1);

В задаче 6.1 после рекурсивного вызова функции revers() добавлена еще одна инструкция - печать на экран. Тот факт, что после рекурсивного вызова управление возвращается обратно в экземпляр метода, из которого вызов был сделан, позволил организовать вывод числовой последовательности в обратном порядке. Однако такой вид рекурсии уже нельзя отнести к хвостовой. Если хвостовую рекурсию можно реализовать итеративно, используя лишь фиксированное количество дополнительных переменных (не зависящее от глубины рекурсии), то метод revers() уже невозможно преобразовать в цикл без использования дополнительной памяти (например, массива).

1.3 Рекурсия с ветвлением

До сих пор мы рассматривали примеры рекурсивных методов, в которых каждый экземпляр метода делал не более одного рекурсивного вызова. Однако вызовов может быть и больше. Рекурсия, при которой метод может вызвать себя несколько раз, называется ветвящейся (или рекурсией с ветвлением). Примером ветвящейся рекурсии является рекурсивный метод вычисления чисел Фибоначчи. Рассмотрим его подробнее.

Задача 6.2 Напишите рекурсивный метод, который вычисляет n-ый член последовательности чисел Фибоначчи.

Объяснение: математически последовательность Фибоначчи можно определить, как:

В методе будет два условия завершения рекурсии: при и и два рекурсивных вызова и .

import java.util.Scanner;

public class FibR

{

static long fib(int n) {

return (n>1)?fib(n-1)+fib(n-2):(n==1)?1:0;

}

public static void main(String[] args)

{

Scanner scan=new Scanner(System.in);

System.out.printf("Введите n:");

int n = scan.nextInt();

System.out.printf("fib(%d)= %d",n,fib(n));

}

}

Результат:

Введите n:5

fib(5)= 5

Обратите внимание, что при вычислении fib(5) в соответствии с этой программой понадобится найти fib(4) и fib(3). Определение fib(4), в свою очередь, потребует вычисления fib(3) и fib(2), и так далее. Дерево вызовов метода fib(5) приведено на рис.6.3. Внимательно изучение содержимого стека вызовов для этой задачи показывает, что для нахождения каждого следующего числа Фибоначчи требуется примерно вдвое большее время, чем для определения предыдущего. Поэтому для практического применения такая программа не пригодна.

1.4 Косвенная рекурсия

Косвеннойиливзаимной рекурсиейназывается организация вызовов нескольких методов по кругу (первый метод вызывает второй, второй - третий, …, n-ый метод вызывает первый). Самым простым вариантом косвенной рекурсии можно считать случай, когда метод а() вызывает метод b(), который вызывает метод a(). Рассмотрим рекурсивный способ вычисления значений функций синуса и косинуса в соответствии со следующими тождествами:

Здесь функции синуса и косинуса вызывают одна другую и поэтому являются взаимно рекурсивными.

рекурсия массив сортировка ветвление

Рис.6.3 - Дерево стека вызовов рекурсивного метода fib(5)

Задача 6.3 Напишите рекурсивные методы вычисления синуса и косинуса.

Объяснение: условием завершения рекурсии будем считать равенство аргумента х нулю с точностью до величины eps=0.001. При возврате из самого глубокого рекурсивного вызова нужно будет вычислить нерекурсивносинус и косинус малого числа. Используем для этого первые два члена разложения тригонометрических функций в степенной ряд.

import java.util.Scanner;

public class Ex_6_3

{

static double cos(double x){

if (Math.abs(x)<10e-4)

return x*(1-x*x/6);

else

return 2*sin(x/2)*cos(x/2);

}

static double sin(double x) {

if (Math.abs(x)<10e-4)

return (1-x*x/2);

else

return Math.pow(cos(x/2),2)-Math.pow(sin(x/2),2);

}

public static void main(String[] args)

{

Scanner scan=new Scanner(System.in);

System.out.printf("Введите x:");

double x = scan.nextDouble();

System.out.printf("sin(x)= %5.5f%n",sin(x));

System.out.printf("cos(x)= %5.5f",cos(x));

}

}

Результат:

Введите x:1

sin(x)= -0,54030

cos(x)= -0,84147

1.5 Рекурсивный поиск в массивах

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

Многие рекурсивные алгоритмы строятся по схеме «разделяй и властвуй», предполагающей наличие двух рекурсивных вызовов, каждый из которых работает приблизительно на половине входных данных. Это позволяет разделить задачу на независимые подзадачи того же типа. Часто использование подхода «разделяй и властвуй» обеспечивает более быстрые решения, чем итерационные алгоритмы.

В качестве примера рассмотрим задачу поиска максимального элемента в одномерном массиве. Итеративный вариант решения задачи был рассмотрен в главе 4.Рекурсивное решение типа «разделяй и властвуй» - еще один простой способ решения той же задачи.

Задача 6.4 Напишите рекурсивный метод поиска максимального элемента в целочисленном массиве.

Объяснение: рекурсивный метод будет проводить поиск максимального элемента в массиве a[] от индекса left (левая граница подмассива) до right (правая граница подмассива)включительно. В методе два рекурсивных вызовов, каждый из которых работает на половине заданного участка массива. Задача сводится к нахождению максимального из двух элементов, и решается путем их сравнения. Если в подмассиве один элемент, то он возвращается методом как максимальный. Дерево вызовов рекурсивного метода max() для массива a={5, 10, 12, 8} представлено на рис. 6.4.

В программе используется новый способ вывода массива на экран. В методе println() применен методtoString() класса java.util.Arrays, который преобразует массив в строку.

Алгоритм работы рекурсивного метода:

1. Если индекс left равен индексу right, то завершить поиск и вернуть значение максимального элемента a[left], иначе выполнить действия п.2-3.

2. Поделить анализируемый участок массива пополам. Вызвать метод поиска максимального значения для левого подмассива с границами left и (left+right)/2 и для правого подмассива с границами (left+right)/2+1 и right. Возвращаемыеметодами максимальные элементы для левого и правого участков исследуемого подмассива сохранить в дополнительных переменных temp1 и temp2 соответственно.

3. Вернуть максимальный из двух элементов temp1 и temp2.

public class Ex_6_4

{

static int max(int[] a)

{

return max(a,0, a.length-1); }

static int max (int[] a, int left, int right)

{

if (left==right) return a[left];

else {

int temp1= max(a,left,(left+right)/2);

int temp2= max(a,(left+right)/2+1,right);

returnMath.max(temp1,temp2);}

}

public static void main(String[] args)

{

int[] a = {5,0,-10,9,15,100,-12,3};

System.out.println(java.util.Arrays.toString(a));

System.out.println("Max="+max(a));

}}

Результат:

[5, 0, -10, 9, 15, 100, -12, 3]

Max=100

Еще один алгоритм, построенный по принципу «разделяй и властвуй» - это бинарный поиск в упорядоченном массиве, который также называется методом половинного деления. Идея алгоритма заключается в следующем: если массив упорядоченный, то половину его элементов после сравнения ключа (искомого значения) со средним элементом можно отбросить. Если значение ключа меньше среднего элемента массива, то искомый элемент может находиться только в левой части массива, к которой применяется этот же метод бинарного поиска, если - больше, метод вызывается для правой части массива. Таким образом, в методе будет два рекурсивных вызова.

Рис. 6.4 - Дерево вызовов рекурсивного метода max()

Метод бинарного поиска работает значительно быстрее метода линейного поиска, рассмотренного в главе 4. Так, поиск в неотсортированных массивах занимает время, пропорциональное n, где n-количество элементов массива. При использовании метода бинарного поиска по отсортированным данным среднее время поиска будет пропорционально .

Задача 6.5 Напишите рекурсивный метод поиска в отсортированном целочисленном массиве

Объяснение: в программе используются следующие переменные: массив a[], left - индекс первого элемента (левая граница), right - индекс последнего элемента (правая граница), middle - индекс среднего элемента исследуемого участка массива, key - ключ поиска (искомый элемент). Метод возвращает индекс элемента, значение которого совпадает с ключом поиска. Если элемент не найден, возвращается -1. Условием завершения рекурсии является условие, при котором значение ключа совпадает со значением некоторого элемента массива, номер этого элемента возвращается. Если же индекс первого элемента исследуемого участка массива превышает индекс последнего элемента, то искомое значение в массиве отсутствует и возвращается -1.

Алгоритм работы рекурсивного метода:

1. Если индекс left больше индекса right, то завершить поиск и вернуть значение -1, иначе выполнить действия п.2-4.

2. Определить индекс среднего элемента: middle=(left+right)/2.

3. Сравнить ключ поиска со средним значением. Если они совпадают, то поиск завершен и возвращается индекс среднего элемента - middle, иначе определить подмассив в котором следует продолжить поиск. Перейти к п.4.

4. Если ключ поиска меньше значения среднего элемента, вызвать рекурсивный метод бинарного поиска для левого подмассива с границами left и middle-1, иначе выполнить вызов метода бинарного поиска для правого подмассива с границами middle+1 и right.

public class Ex_6_5

{

static int binarySearch (int[] a, int left, int right, int key)

{

if (left>right) return -1;

else

{

int middle=(left+right)/2;

if (key==a[middle]) return middle;

elseif(key<a[middle])

return binarySearch(a,left,middle-1, key);

else

return binarySearch(a,middle+1, right, key);

}

}

public static void main(String[] args)

{

int[] a = {5,0,-10,9,15,100,-12,3};

System.out.println(java.util.Arrays.toString(a));

System.out.printf("Search (9) index=%d", binarySearch(a,0,a.length-1,9));

}

}

Результат:

[5, 0, -10, 9, 15, 100, -12, 3]

Search (9) index=3

1.6 Быстрая сортировка

Быстрая сортировка (англ. quicksort) - это надежный и эффективный алгоритм сортировки, который используется не только для учебных целей, но и широко применяется на практике. Быстрая сортировка также называется сортировкой Хоара по имени автора алгоритма Чарльза Хоара. Для большинства массивов этот метод требует приблизительно обменов элементов и сравнений, то есть намного меньше, чем любой другой элементарный метод сортировки. Метод основан на подходе «разделяй и властвуй». Идея алгоритма достаточна проста. Из массива выбирается некоторый опорный элемент р, вокруг которого перемещаются все элементы. Причем элементы меньшие, либо равные р, перемещаются влево от него, а элементы большие, либо равные р - вправо. Далее метод быстрой сортировки рекурсивно запускается для каждой из частей массива. Алгоритм имеет наименьшее время сортировки, если в качестве опорного элемента выбирается средний по номеру элемент, так как в результате разделения части массива имеют одинаковые размеры.

Задача 6.6 Напишите рекурсивный метод быстрой сортировки целочисленного массива.

Объяснение: введем два индекса i и j, в начале алгоритма они указывают, соответственно, на левый и правый конец последовательности. Начнем двигать указатель i с шагом 1 по массиву вперед, пока не будет найден элемент со значением большим или равным значению опорного элемента. Затем аналогичным образом двигаем указатель j от конца массива к началу, пока не будет найден элемент со значением меньшим или равным значению опорного элемента. Далее, если i<=j, меняем найденные элементы местами и продолжаем двигать i и j. Алгоритм разделения заканчиваем тогда, когдаиндекс i становиться больше индекса j. После разделения все значения до индекса i меньше или равны опорному элементу, а все значения после индекса j больше или равны опорному элементу. Далее рекурсивно вызываем метод быстрой сортировки отдельно для каждой из частей массива. Пример выполнения алгоритма быстрой сортировки массива {5, 0, -10, 9, 15, 100, -12, 3} иллюстрирует рис. 6.5. На рисунке показан только первый шаг рекурсии.На самом деле подмассивы {5, 0, -10, 3, -12} и {100, 15, 9} сортируются затем рекурсивно. Условием завершение рекурсивных вызовов является наличие одного элемента в каждой из частей массива.

public class QuickSort {

static void quickSort (int[] a, int left, int right) {

int i=left, j=right;

int p=a[(left+right)/2]; //опорный элемент

int tmp;

// разделение

do {

while (a[i]<p) i++;

while (a[j]>p) j--;

if (i<=j) {

tmp=a[i]; a[i]=a[j]; a[j]=tmp;

i++; j--;

}

} while (i<=j);

// рекурсивные вызовы сортировки

if (j>left) quickSort(a, left, j);

if (i<right)quickSort(a, i, right);

}

public static void main(String[]args) {

int[] a = {5,0,-10,9,15,100,-12,3};

quickSort(a,0,a.length-1);

System.out.println(java.util.Arrays.toString(a));

}}

Результат:

[-12, -10, 0, 3, 5, 9, 15, 100]



Рис.6.5 - Демонстрация выполнения алгоритма быстрой сортировки

1.7 Сортировка слиянием

Сортировка слиянием (англ. merge sort) является простым, но эффективным алгоритмом сортировки, который также как и алгоритм быстрой сортировки построен по принципу «разделяй и властвуй», однако реализует его несколько по-другому. Массив делится пополам, левая и правая половина рекурсивно сортируется тем же методом слияния, затем отсортированные части объединяются в один отсортированный массив. В соответствии с алгоритмом деление продолжается до части массива, состоящего из одного элемента. Такой массив сразу является отсортированным, поэтому задача сводится к написанию метода, который выполняет слияния двух отсортированных частей массива в один.

Одним из способов слияния является выделение дополнительной памяти для вспомогательного буфера, равному по размеру общему количеств элементов в двух частях массива. Элементы последовательно перемещаются в этот буфер по одному за шаг. Причем на каждом шагу элементы двух частей сравниваются, и по результату сравнения в буфер помещается элемент либо с левого, либо с правого подмассива. Один из подмассивов во время слияния может закончиться раньше. В таком случае элементы другого подмассива, которые не были обработаны, дописываются в конец буфера, сохраняя имеющийся порядок. Результатом является упорядоченная последовательность, находящаяся в буфере.

Задача 6.7 Напишите рекурсивный метод сортировки слиянием целочисленного массива.

Объяснение: в программе используются следующие методы:

mergeSort(int[] arr) - выполняет сортировку массива arr[], вызывая для этого методmergeSort(int[] arr, int low, int high, int[] buff);

mergeSort(int[] arr, int low, int high, int[] buff) - выполняет сортировку массива arr[] от индекса low до индекса high. В качестве аргумента в метод передается вспомогательный буфер buff[]. Метод осуществляет рекурсивное деление массива пополам и вызов метода слияния merge().

merge(int[]arr, int low, int high, int mid, int[] buff) - метод выполняет слияние отсортированных частей массива: левой от идекса low до mid и правой от индексаmid+1 до индекса high.

Пример выполнения алгоритма сортировки слиянием массива {5, 0, -10, 9, 15, 100, -12, 3} иллюстрирует рис. 6.5.

public class MergeSort {

static void mergeSort(int[] arr) {

mergeSort(arr, 0, arr.length - 1, new int[arr.length]);

}

static void mergeSort(int[] arr, int low, int high, int[] buff){

//Выполняем разделение

if (low >= high) {

return;

}

int mid = (low + high)/2;

mergeSort(arr, low, mid, buff);

mergeSort(arr, mid+1, high, buff);

//Вызываем метод слияния

merge(arr,low, high, mid, buff);

}

static void merge(int[]arr, int low, int high, int mid, int[] buff)

{

int left = low, right = mid + 1;

//Выполняем слияние

for (int i = low; i <= high; i++) {

if (right>high||left<=mid && arr[left]<=arr[right])

{

buff[i] = arr[left++];

} else {

buff[i] = arr[right++];

}

}

//Копируем буфер в массив arr

for (int i = low; i <= high; i++) {

arr[i] = buff[i];

}

}

public static void main(String[]args) {

int[] a = {5,0,-10,9,15,100,-12,3};

mergeSort(a);

System.out.println(java.util.Arrays.toString(a));

}}

Результат:

[-12, -10, 0, 3, 5, 9, 15, 100]

Сортировка слияниемявляется одним из самых простых алгоритмов сортировки среди быстрых алгоритмов, который может быть эффективно использован для сортировки связанных списков. Недостаток алгоритмазаключается в том, что он требует дополнительную память размером порядкаn, и не гарантирует сохранение порядка элементов с одинаковыми значениями. Его временная сложность всегда пропорциональна.

Рис.6.6 - Демонстрация выполнения алгоритма сортировки слиянием

1.8 Стандартные средства Java для работы с массивами

В классе Arrays из пакета java.util собраны статические методы, которые позволяют программисту облегчить работу, связанную с обработкой массивов. В частности, класс содержит методы, которые выполняют сравнение, заполнение, бинарный поиск и быструю сортировку массивов. Рассмотрим обзорно отдельные методы класса Arrays.

Метод binarySearch() использует бинарный поиск для нахождения заданного значения, применяется только к отсортированным массивам. Общая форма метода имеет вид:

static int binarySearch(type[] arr, type element)

Здесь type - любой примитивный тип или тип Object. Метод возвращает индекс найденного элемента массива arr[]. Если элемент element не найден, то возвращается отрицательное число, абсолютное значение которого равно индексу, с которым элемент был бы вставлен в массив в заданном порядке. Если в массиве есть несколько одинаковых элементов, нет гарантии правильного поиска. Используемый алгоритм не был разработан в расчете на повторяющие элементы, хотя их присутствие не запрещается.

Методы соруOf() и copyOfRange()возвращают копию массива и имеют следующие общие формы:

static type[]copyOf(type[]arr,int len)

static type[] copyOfRange(type[] arr, int from, int to)

Исходныймассивзаданпараметромarr[]. В методеcopyOf() в качестве параметра передается длинакопии len. Если копия длиннее, чем источник, то для числовых массивов она дополняется нулями, для объектов - значениями null.Если копия короче,чем источник,она усекается. В методе copyOfRange()диапазон для копирования задается от индекса from включительно до индекса to исключительно.

Метод equals() сравнивает массивы и возвращает значение true, если два массива эквивалентны. В противном случае он возвращает значение false.

static boolean equals(type[] arr1,type[] arr2)

Здесь arr1 и arr2- массивы,сравниваемые на эквивалентность. При сравнении массивов проверяются следующие условия: в массивах должно быть равное количество элементов и каждый элемент должен быть эквивалентен соответствующему элементу другого массива.

Метод fill() заполняет элементы массива заданным значением. Методfill()имеет две версии: первая присваивает всем элементам массива arr[] значение value:

static void fill(type[] arr, type value)

Втораяверсияметодаfill()присваиваетзначениеvalue подмножеству массива arr[] от индекса from включительно до индекса to исключительно.

static void fill(type[] arr, int from, int to, boolean value)

Метод sort()сортирует массив по возрастанию и имеет две версии. Первая версия сортирует весь массив. Общая форма имеет вид:

static void sort(type[] arr)

Здесьarr[]-этомассив,подлежащийсортировке. Вторая версия метода sort()позволяет указать диапазон массива, который следует упорядочить:

static void sort(type[] arr, int from, int to)

Массив arr[] сортируется по возрастанию от индекса from включительно до to исключительно.

Обзор был бы не полным без описания метода копирования массивов arraycopy(), который использует сама исполняющая система Java. Метод находится в классе System в пакете java.lang и позволяет копировать массивы быстрее, чем это получается в случае поэлементного итеративного копирования. Метод перегружен для всех примитивных типов и типа Object. Общая форма метода имеет вид:

static void arraycopy(type[] src, int src_ind, type[] dest, int dest_ind, int count)

Из массива, на который указывает ссылка src, копируется count элементов, начиная с элемента с индексом src_ind, в массив, на который указывает ссылка dest, начиная с его элемента с индексом dest_ind. Все индексы должны быть заданы так, чтобы элементы лежали в массивах, типы массивов должны быть совместимы, а примитивные типы обязаны полностью совпадать. Ссылки на массивы не должны быть равны null.

Рассмотрим пример демонстрирующий применение некоторых из представленных выше методов.

Задача 6.8 Дан двумерный массив целых чисел, состоящий из nxm элементов. Все строки массива, которые упорядочены по возрастанию, заменить нулями.

import java.util.*;

class Ex_6_8{

//метод инициализации массива

static void fill(int [][] a){

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

for(int j=0;j<a[i].length;j++)

if (i%3==0) a[i][j]=j;

else a[i][j]=(int)(Math.random()*10)-5;

}

//метод вывода массива на печать

static void print(int[][] a){

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

System.out.println(Arrays.toString(a[i]));

}

//логический метод определяет отсортирован ли массив

static boolean is_sort(int[] t){

int[] t1=new int[t.length];

System.arraycopy(t,0,t1,0,t.length);

Arrays.sort(t1);

return (Arrays.equals(t,t1));

}

public static void main(String[] args) {

int n=5, m=5;

int[][] arr=new int[n][m];

fill(arr);

System.out.println("Исходная матрица");

print(arr);

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

if (is_sort(arr[i])) Arrays.fill(arr[i],0);

}

System.out.println("Новая матрица");

print(arr); }}

Результат:

Исходная матрица

[0, 1, 2, 3, 4]

[-5, -1, -4, 0, 0]

[4, -1, -3, -5, 0]

[0, 1, 2, 3, 4]

[-3, -5, 4, 2, 3]

Новая матрица

[0, 0, 0, 0, 0]

[-5, -1, -4, 0, 0]

[4, -1, -3, -5, 0]

[0, 0, 0, 0, 0]

[-3, -5, 4, 2, 3]

Упражнения

1. Опишите рекурсивный метод для выполнения следующего задания. Дано вещественное число х и целое число n. Определить Степенную функцию вычислять по формуле:

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

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

3. Вычислите, используя рекурсию:

Ответ: n+2

4. Подсчитайте, сколько раз потребуется повторно вычислить четвёртый элементы последовательности Фибоначчи для вычисления пятнадцатого элемента.

5. Напишите рекурсивный метод сложения двух чисел, используя следующее рекуррентное соотношение:

6. Используя рекурсию, найдите n-ый член последовательности, которая определяется следующим рекуррентным соотношением:

7. Вычислите функцию Аккермана по ее рекурсивному определению:

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

9. Напишите рекурсивный метод нахождения суммы первых n членов арифметической прогрессии

10. Вычислите количество сочетаний по рекуррентной формуле биномиальных коэффициентов:

11. Напишите рекурсивный метод вывода цифр целого положительного числа n в обратном порядке.

12. Опишите рекурсивный метод нахождения суммы цифр любого натурального числа.

13. Задано число n. Сложить все цифры числа n, затем все цифры найденной суммы и повторить эти действия до тех пор, пока не получим цифру, называемую цифровым корнем числа. Напишите рекурсивный метод вычисления цифрового корня числа n.

14. Напишите рекурсивный метод перевода натурального числа из десятичной системы счисления в двоичную.

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

...