Member 13764324 Ответов: 3

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

Например:
{11, 5, 7, 9, 11, 3, 5} имеет в общей сложности 2 пары: 1 пара из 11 и 1 пара из 5
{11, 5, 7, 9, 11, 11} имеет в общей сложности 1 пару: пара из 11
{11, 5, 7, 9, 11, 3, 11, 5, 11} имеет всего 3 пары: 2 пары по 11 и 1 пара по 5

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

Что я уже пробовал:

int findpair(int array[], int start, int end)
{
    int pairs = 0;

    if(end<=start)
    {
        return 0;
    }
    
    if(array[start]==array[end])
    {
        pairs++:
    }

    findpair(array, start+1, end);
    findpair(array, start, end-1);

    return pairs;
}

jeron1

Вы не задали ни одного вопроса.

3 Ответов

Рейтинг:
2

Jochen Arndt

Это вопрос домашнего задания / задания. Так что здесь вы не получите полного решения.

Но у меня есть два совета:

1. рекурсивная функция не будет "видеть" локальные переменные вызывающего объекта. Если вам нужно суммировать значение, вы должны использовать возвращаемое значение:

int rec_func(some_param)
{
    int result = 0;
    if (not_end_condition(some_param))
        result += rec_func(some_modified_param);
    return result;
}

2. хитрость заключается в том, чтобы найти метод для выполнения задачи. Здесь должны быть подсчитаны только полные пары (тройка считается одной парой), и вы должны убедиться, что оба числа подсчитанной пары больше не используются. Это довольно просто здесь из-за двух операторов из присваивания: "массив положительных целых чисел" и "Вам разрешено изменять элементы в массиве".

Теперь подумайте о вышесказанном и о том, как это можно сделать.

Member 13764324

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

Jochen Arndt

Это не было бы практикой, если бы вы получили решение, написанное другими.

Здесь также нет единого решения.

Рейтинг:
2

OriginalGriff

Подумайте о том, как бы вы сделали это вручную. Я бы начал с первого элемента в массиве, а затем искал бы его соответствие. Если бы я нашел его, я бы удалил второй из массива. Если бы я этого не сделал, я бы удалил элемент из массива.
Затем снова выполните поиск по следующему элементу, если таковой имеется.

В конце концов, число пар-это число оставшихся элементов.

| Start
V
11, 5, 7, 9, 11, 3, 5  - match: remove.
    | Start
    V
11, 5, 7, 9, 3, 5  - match - remove
       | Start
       V
11, 5, 7, 9, 3  - no match - remove
       | Start
       V
11, 5, 9, 3  - no match - remove
       | Start
       V
11, 5, 3  - no match - remove
       | Start
       V
11, 5  - no more elements : 2 matches.

Подсказка: самый простой способ удалить элемент-это перезаписать его последним и уменьшить количество на единицу...

Рейтинг:
0

Patrice T

Ваш код прекрасно рекурсивен, но ошибочен во многих отношениях.
Все пары, найденные в рекурсии, теряются:

int findpair(int array[], int start, int end)
{
    int pairs = 0;

    if(end<=start)
    {
        return 0;
    }
    
    if(array[start]==array[end])
    {
        pairs++:
    }

    findpair(array, start+1, end); // all pairs found here are lost
    findpair(array, start, end-1); // all pairs found here are lost

    return pairs;
}

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

вы должны изменить массив, чтобы предотвратить подсчет элемента более чем в 1 паре.
Поиск правильного алгоритма - это ваша домашняя работа.