VPF::Поиск всех убывающих последовательностей длины K.

VAAKAraceGUM

Дата 4.3.2012, 14:07 (ссылка)

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

Загрузка ...

Новичок

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

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

В общем дан одномерный массив длины N (заполненный рандомно числами от 1 до N ), и требуется реализовать поиск всех убывающих последовательностей длины K в этом массиве (при этом мы задаем это K, оно может быть равно от 2 до N). То есть если у нас массив состоит из 5 элементов (5-4-3-2-1) и K = 2, то на выходе мы должны получить следующее: 54-43-32-21, а если K = 3, то : 543-432-321. Моей логике это не подвластно, помогите плз реализовать алгоритм.

marsh123

Дата 4.3.2012, 16:44 (ссылка)

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

Загрузка ...

Шустрый

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

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

Если сложность особо не интересует, то как-то так:

Код


#include <iostream>
#include <stdlib.h>

using namespace std;

int main() {
    srand(time(NULL)); //делаем rand() зависимым от времени

    int n, k, j;
    cin >> n; //длину вводим
    int a[n]; //объявляем массив
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 100; //заполняем случайными числами от 0 до 99
        cout << a[i] << " "; //печатаем его сразу
    }
    cout << endl;

    cin >> k; //вводим нужную длину
    if (k >= 2 && k <= n) { //проверяем необходимое условие
        for (int i = 0; i < n - 1; i++) { //начинаем искать последовательность для каждого элемента
            j = i;
            while (a[j] > a[j+1] && j < n - 1) { //ищем убывающую последовательность
                j++;
            }
            if (j - i >= k - 1) { //если нашли нужную последовательность
                if (j - i > k - 1) { //не печатаем полностью последовательности большие, чем нам нужно
                    j = k - 1 + i;
                }
                for (int p = i; p < j+1; p++) { //печатаем её
                    cout << a[p] << " ";
                }
                cout << endl;
            }
        }
    }
    else 
        cout << "k должно быть >= 2 и <= длины массива" << endl;
    return 0;
}

Это сообщение отредактировал(а) marsh123 - 4.3.2012, 18:15

volatile

Дата 4.3.2012, 17:35 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(marsh123 @ 4.3.2012, 16:44

)

int a[n]; //объявляем массив

Цитата(marsh123 @ 4.3.2012, 16:44

)

while (a[j] > a[j+1] && j < n) { //ищем убывающую последовательность
j++;
}

marsh123, поправьте..
если не ошибаюсь, выход за пределы.

marsh123

Дата 4.3.2012, 18:15 (ссылка)

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

Загрузка ...

Шустрый

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

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

Верно

Поправил.

VAAKAraceGUM

Дата 4.3.2012, 18:20 (ссылка)

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

Загрузка ...

Новичок

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

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

Да, все спасибо, я немного его упростил (для понимания), работает на все 100%...

volatile

Дата 4.3.2012, 18:35 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(marsh123 @ 4.3.2012, 16:44

)

           while (a[j] > a[j+1] && j < n - 1) { //ищем убывающую последовательность
                j++;
            }

Боюсь показаться назойливым, но всё-же, даже после исправления выход за пределы. smile

имхо, более чисто так:

Код


while (j < n - 1 && a[j] > a[j+1]) { //ищем убывающую последовательность

marsh123

Дата 4.3.2012, 19:11 (ссылка)

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

Загрузка ...

Шустрый

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

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

Да, Вы снова правы smile

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