Как найти разницу двух чисел в массиве рекурсивно?

Question

[ifqthenp]

Друзья, решал в интернете задачки на рекурсию, попались две, которые никак мозг не осилит: 1) найти два элемента в упорядоченном массиве с разницей 10, используя рекурсию и время O(n). 2) Найти такие же два элемента рекурсивно, но массив не упорядоченный. Есть идеи? В каком направлении двигаться?

Answer 1

[Mrrl]

Можно было бы как-то так:

static int pres,qres;
static int[] A;
static int M=10;

bool Find1(int p,int q){
  if(A[q]-A[p]==M){ 
    pres=p; qres=q;
    return true;
  }
  if(A[q]-A[p]<M || q-p<2) return false;  
  int k=p+(q-p)/2;
  if(Find1(p,k) || Find1(k,q)) return true;
  return Find2(p,k,k+1,q);
}

bool Find2(int p1,int q1,int p2,int q2){  // p1<=q1<p2<=q2
  if(A[p2]-A[q1]>M || A[q2]-A[p1]<M) return false;
  if(A[p2]-A[p1]==M){
    pres=p1; qres=p2; return true;
  }
  if(A[p1]==A[q1] && A[p2]==A[q2]) return false;
  if(A[q1]-A[p1]>A[q2]-A[p2]){
    int k=p1+(q1-p1)/2;
    return Find2(p1,k,p2,q2) || Find2(k+1,q1,p2,q2);
  }else{
    int k=p2+(q2-p2)/2;
    return Find2(p1,q1,p2,k) || Find2(p1,q1,k+1,q2);
  }
}

(функция Find1 ищет пару в одном фрагменте, Find2 - в двух непересекающихся фрагментах). Но я совершенно не представляю, какая получится сложность. Не исключено, что O(n*log(n)). Зато рекурсия используется по назначению :)
UPD. Немного поправил условия - здесь часто лучше сравнивать не индексы, а сами элементы.

Comments

[ifqthenp]

Спасибо, попробую перевести на джаву...

[Mrrl]

Для второй задачи - то же, но убираете проверки A[q]-A[p] < M и им подобные, оставляете только ==M.

[Mrrl]

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

[ifqthenp]

Mrrl: Да уж, как-то неожиданно сложно с рекурсией получается, есть от чего озадачиться. Спасибо.

[Mrrl]

Похоже, что без Find1 можно обойтись, вызвав сразу Find2(0,n-1,0,n-1).
Фактически, мы здесь проверяем некоторое свойство для двух отрезков, для чего делим один из отрезков пополам, и сопоставляем каждую половину с другим отрезком. Может быть, задача не очень удачна, но этот приём надо знать. Например, это решение легко обобщается на двумерный случай (найти два таких числа в массиве, монотонном по обеим координатам). С указателями вы там намучаетесь.

[ifqthenp]

Mrrl: Ну во так вот на джаве это выглядит:

public class Recursively_find_two_elements_w_given_difference
{
    public static void main(String[] args)
    {
        int[] A = {0, 1, 5, 8, 10, 12, 20, 30, 40, 60};
        int i = 0;
        int j = 1;
        int diff = 20;

        int result = findDiff(A, i, j, diff);
        System.out.println(result);
    }

    /**
     * @param arr sorted array
     * @param i   array index, type of int
     * @param j   array index, type of int
     * @param difference given difference
     * @return number of cases when given difference occurs in the array
     */
    public static int findDiff(int[] arr, int i, int j, int difference)
    {
        if (j == arr.length)
        {
            return 0;
        }
        else
        {
            if (arr[j] - arr[i] < difference)
            {
                return findDiff(arr, i, j + 1, difference);
            }
            else if (arr[j] - arr[i] > difference)
            {
                return findDiff(arr, i + 1, j, difference);
            }
            else
            {
                return 1 + findDiff(arr, i + 1, j + 1, difference);
            }
        }
    }
}

Answer 2

[Станислав Макаров]

Навскидку:

const D = 10
int N = ...
int a[N] = ...

find(i, j, N):
	d := a[j] - a[i]
	if d = D then
		return (i, j)
	else if d < D then
		if j + 1 == N then
			return nil
		else
			return find(i, j + 1, N)
		end
	else if d > D then
		if i + 1 == N - 1 then
			return nil
		else
			return find(i + 1, j, N)
		end
	end

find(0, 1, N);

Сложность по идее O(2n). Вообще не очень красиво для рекурсивной реализации, но вроде рабочий вариант.
Вторую задачу - сами.

Comments

[ifqthenp]

Да, громоздко как-то. Я решил эту задачу без рекурсии, выглядит гораздо проще. Спасибо за ответ!

int[] b = {0 1 2 3 5 6 7 8 9 11 12 13 14 15 17 18 19};
        int x = 0;
        int y = 1;
        int diff = 10;
        int count = 0;

        while (y < b.length)
        {
            if (b[y] - b[x] < diff)
            {
                y++;
            }
            else if (b[y] - b[x] > diff)
            {
                x++;
            }
            else
            {
                count++;
                y++;
            }
        }

[Mrrl]

ifqthenp: Да, рекурсия здесь слегка не по делу, задача проще без неё (в обоих случаях). Для второй достаточно отсортировать массив и свести задачу к первой (O(n*log n)). Вот если массив портить нельзя, а дополнительная память разрешается не более O(log(n)) - тут надо думать.

[ifqthenp]

Mrrl: Во второй задаче массив портить нельзя, но сложность разрешается O(n^2).

[Artem Vereschaka]

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

[Artem Vereschaka]

ifqthenp: как вариант еще можно создать копию массива, отсортировать и бин поиском найти то что нужно. Но, эффективнее будет тупо перебрать все варианты

Answer 3

[xmoonlight]

Фриланс