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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Поменять попарно элементы массива http://www.cyberforum.ru/cpp-beginners/thread1045514.html
Задача 1.. Дан массив с четным числом элементов. Поменять местами его первый элемент со вторым, третий с четвёртый и т.д.... одна тема - одна задача. читайте правила форума Решите алгоритмом и обозначениями для начинающих пожалуйста)) заранее спасибо!
C++ Выч. сумму бесконечного ряда с точностью ep Ребят помогите пожалуйста( очень научиться хочется и понять, задали вот такое задание. Дано: x0, h, xk, eps=10^-3 вычислить сумму бесконечного ряда с точностью eps. Вот на c++, очень надо понять и написать, спасибо. cos(x)= \sum_{i=0 }^{\propto}{(-1)}^{i}*\frac{{x}^{2i}}{(2i)!} http://www.cyberforum.ru/cpp-beginners/thread1045511.html
C++ Вычислить произведение двух чисел
Вычислить произведение двух чисел. Первое число - сумма третьей и четвертой цифр четырехзначного числа, второе - частное от деления первой цифры четырехзначного числа на вторую цифру числа.
C++ Двумерный массив
Дан двумерный квадратный массив из 16 элементов.Написать программу, которая находит и выводит количество элементов массива, значение которых больше среднего арифметического значения элементов этого массива. P.S. Ребята, помогите пожалуйста!!!
C++ Запись в структуру из файла. База данных http://www.cyberforum.ru/cpp-beginners/thread1045477.html
Добрый день. Помогите советом, очень нужно, т.к. собираюсь доделать за ближайшие часы. Я пишу базу данных на основе двусвязного списка. Сделал, чтобы все записывалось в файл. Теперь пишу, чтобы можно было считать и дописать базу. Вот в чем проблема: вот моя база в txt: ================================================================= Name: Number: Size:
C++ Заполнить матрицу Заполнить матрицу размера nхn целыми числами 1, 2, …, n2. зигзагом http://s12.postimg.org/kho343tl9/098765.png #include <iostream> #include <iomanip> #include <windows.h> using namespace std; int main() { подробнее

Показать сообщение отдельно
akilizik
0 / 0 / 0
Регистрация: 06.12.2011
Сообщений: 28

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

17.12.2013, 17:55. Просмотров 434. Ответов 0
Метки (Все метки)

Изначально у меня была такая задачка: даны 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];
Как это совместить?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 07:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru