VPF::Описать рекурсивную функцию - Форум программистов

vitaxa3581

Дата 17.1.2013, 23:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 13.12.2012

Репутация: нет
Всего: нет

товарищи помогите, направте хотябы на путь истинный. "Описать рекурсивную функцию max_otr (x, n), которая находит максимальный из отрицательных элементов целочисленного вектора x размером n"

bsa

Дата 18.1.2013, 10:07 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Она рекурсивная? У меня есть только одна идея, как сделать ее рекурсивной. Для этого x должен быть указателем на первый элемент массива. Функция проверяет n, если она равна 1, то возвращает первый элемент массива. В Противном Случае Сравнивает первый и последий элементы. Если последний меньше, то увеличиваешь x на 1 (удаляешь первый элемент вектора), иначе уменьшаешь n на 1 (удаляешь последний). Возвращаешь результат вызова этой функции с измененными x и n.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

NightmareZ

Дата 18.1.2013, 11:34 (ссылка)

(нет голосов)

Загрузка ...

[хакер]

Профиль
Группа: Участник
Сообщений: 699
Регистрация: 10.8.2006

Репутация: 0
Всего: 13

Код


int max_otr(int* x, int n)
{
    if (n == 0) // error
        return 0;
    else if (n > 0) // first function call
    {
        int size;
        int* tmp;

        size = sizeof(int) * n;

        tmp = malloc(size);
        memcpy(tmp, x, size);
        return max_otr(tmp, -n);
    }
    else if (n < -1) // recursive call
    {
        n = -n;

        if (x[n - 1] >= 0)
            return max_otr(x, -n + 1);
        else if (x[n - 2] >= 0 || x[n - 2] < x[n - 1])
        {
            int tmp = x[n - 2];
            x[n - 2] = x[n - 1];
            x[n - 1] = tmp;
        }

        return max_otr(x, -n + 1);
    }
    else // last recursive call
    {
        int value = x[0];
        free(x);
        return value < 0 ? value : 0;
    }
}

Это сообщение отредактировал(а) NightmareZ - 18.1.2013, 11:37

--------------------

NightmareZ.net - мой блог и сайт, мои проекты и прочий трэш
Ely-Art.ru - наша маленькая домашняя арт-студия
mugcraft.ru - кружки на любой вкус

bsa

Дата 18.1.2013, 11:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

NightmareZ, лучше бы ты ничего не писал, чем это... Сравни, мой алгоритм (в 5 строчек от силы) и свой.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

baldina

Дата 18.1.2013, 13:01 (ссылка)

(голосов:2)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

Код


int max_otr (int *x, size_t n) {
  int r=0;
  if (n > 0) {
    r=max_otr(x+1, n-1); 
    if (*x < 0)
      if (r < 0)
        r=std::max (*x, r);
      else
        r=*x;
  }
  return r;
}

bsa

Дата 18.1.2013, 17:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Код

int max_otr(int *x, size_t n)
{
   if (n <= 1)
      return (*x < 0) ? *x : 0;
   --n;
   
   if ((*x >= 0) || ((*x < x[n]) && (x[n] < 0)))
      ++x;
   return max_otr(x, n);
}

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

baldina

Дата 19.1.2013, 19:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

Цитата(bsa @ 18.1.2013, 17:58

)

if (n <= 1)
return (*x < 0) ? *x : 0;

bsa, что будет при разыменовании x, если n < 1 ?

bsa

Дата 20.1.2013, 20:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

baldina, ты же сам знаешь. smile

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

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »