Форум программистов, компьютерный форум CyberForum.ru

Поиск наибольшей возрастающей последовательности - C++

Восстановить пароль Регистрация
 
akilizik
0 / 0 / 0
Регистрация: 06.12.2011
Сообщений: 28
17.12.2013, 17:55     Поиск наибольшей возрастающей последовательности #1
Изначально у меня была такая задачка: даны N положительных целых чисел, которые не делятся ни на какие простые числа, кроме 2 и 3. Требуется выкинуть минимально возможное количество чисел так, чтобы из любых двух оставшихся одно делилось на другое.
Путем долгих рассуждений она свелась к задаче поиска наибольшей возрастающей последовательности на одном из полей структуры. К моему счастью, я нашла программу, (и даже с комментариями) позволяющую ее решить, но только для чисел. Я никак не могу понять, как переделать ее так, чтобы можно было использовать структуру
вот программа, решающая последнюю задачу:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template<typename T> vector<int> find_lis(vector<T> &data)
{
    // решаем задачу итеративно. сначала рассматриваем только первый элемент
    // затем добавляем элементы по одному
 
    // (бывший массив p)
    // вот это интересная штука. тут для каждого индекса i мы рассматриваем
    // наилучшую из подпоследовательностей, заканчивающихся **на этом элементе**,
    // и записываем в этот массив индекс предыдущего элемента.
    // мы пользуемся таким важным свойством: для наилучшей подпоследовательности,
    // заканчивающейся на i-ом элементе, её кусок без финального элемента обязан быть
    // наилучшей подпоследовательностью, заканчивающейся на соответствующем
    // элементе. поэтому для хранения наилучших подпоследовательностей достаточно
    // лишь одного предыдущего индекса
    vector<int> previdx(data.size());
 
    // бывший массив b
    // а здесь мы храним индексы тех элементов, которые **в принципе** могут стать
    // чьим-то предыдущим элементом в наилучшей последовательности.
    // список хранится в таком порядке, чтобы соответствующие данные
    // были отсортированы (чтобы можно было искать двоичным поиском)
    vector<int> possibleprev;
 
    // тривиальный случай
    if (data.size() < 1) return vector<int>();
 
    possibleprev.push_back(0); // для одного элемента всё просто
 
    for (int i = 1; i < (int)data.size(); i++) {
        // вводим в рассмотрение следующий элемент и обновляем списки
 
        T curr = data[i];
 
        // если новый элемент больше всех возможных предыдущих элементов...
        if (data[possibleprev.back()] < curr) {
            // ... то всё просто: его предыдущий элемент - наибольший из возможных
            previdx[i] = possibleprev.back();
            // и он сам - тоже возможный наибольший для кого-то после
            possibleprev.push_back(i);
            continue; // всё, переходим к следующему элементу
        }
 
        // теперь более интересный случай: мы попали в середину
 
        int leftidx, rightidx;
 
        // старый знакомый -- поиск половинным делением.
        // ищем в упорядоченном списке предыдущих элементов,
        // куда можно вставить новый элемент
        for (leftidx = 0, rightidx = possibleprev.size()-1; leftidx < rightidx;) {
            int mididx = (leftidx + rightidx) / 2;
            if (data[possibleprev[mididx]] < curr)
                leftidx=mididx+1;
            else
                rightidx=mididx;
        }
        int foundidx = leftidx;
 
        if (curr < data[possibleprev[foundidx]]) {
            // нашли наш предыдущий индекс!
            // записываем найденное значение в таблицу previdx:
            if (foundidx > 0) previdx[i] = possibleprev[foundidx-1];
            // и корректируем текущий список possibleprev
            // ключевой момент - теперь найденный элемент в таблице possibleprev
            // индекс больше не нужен
            possibleprev[foundidx] = i;
        }
    }
 
    // отлично, собираем ответ. это будет последовательность индексов,
    // "связанная" через previdx
    vector<int> bestsubseq(possibleprev.size());
    // клёвый трюк с индексами, не знал раньше.
    // обратите внимание, начальное значение seqindex будет bestsubseq.size() - 1
    for (int seqindex = bestsubseq.size(), dataindex = possibleprev.back();
         seqindex-- != 0;
         dataindex = previdx[dataindex])
        bestsubseq[seqindex] = dataindex;
    return bestsubseq;
}
А вот моя структура и массив из нее в исходной задаче:
C++
1
2
3
4
5
6
struct ch {
           int chislo;
           int st_2;
           int st_3;
           }; 
ch ch_m[n];
Как это совместить?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.12.2013, 17:55     Поиск наибольшей возрастающей последовательности
Посмотрите здесь:

Определить длину наибольшей последовательности одинаковых чисел в массиве C++
Проверка возрастающей последовательности C++
C++ Поиск наибольшей строки
C++ поиск возрастающей последовательности
C++ Нахождение наибольшей возрастающей подпоследовательности
C++ Дана последовательность, требуется найти длину наибольшей возрастающей подпоследовательности
Поиск наибольшей последовательности цифр в файле C++
C++ Поиск в массиве последовательности с наибольшей суммой

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 22:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru