Как сделать алгоритм более быстрым и эффективным?

Question

[maxkleiman]

Есть две последовательности чисел:

A[0], A[1], ... , A[n].
B[0], B[1], ... , B[m]. Нужно проделать следующие операции с последовательностью A:
Удалить элементы, индексы которых кратны B[0].
Из оставшихся элементов удалить те, индексы которых кратны B[1].
Повторите этот процесс до B[m].
Вывести оставшиеся элементы.

Код программы

#include <iostream>
#include <vector>
#include<iomanip>
using namespace std;
vector <int> divisible_func(vector <int>& a, vector <int>& b) {
    vector <int> c;
    for (size_t i = 0; i < b.size(); i++) {
        for (size_t j = 0; j < a.size(); j++) {
            if (j % b[i] != 0) {
                c.push_back(a[j]);
            }
        }
        a = c;
        c.resize(0);
    }
    a.push_back(-1);
    return a;
}
int main()
{
    int elem1;
    int elem2;
    vector <int> a;
    vector <int> b;
    vector <int> count;
    while (cin >> elem1) {
        if (elem1 == -1) break;
        a.push_back(elem1);
    }
    while (cin >> elem2) {
        if (elem2 == -1) break;
        b.push_back(elem2);
    }
    count = divisible_func(a, b);
    for (size_t i = 0; i < count.size(); i++) {
        cout << count[i] << setw(count.size());
    }
    
    return 0;
}

Comments

[Wataru]

Оберните код в тег code (кнопка </> в редакторе), а то вопрос удалят.

Опишите словами, что этот алгоритм должен делать, что за задачу он решает.

[Денис Загаевский]

И что эта портянка делает?

Answer 1

[Александр Прилепский]

Да, странная задача. Индексы меняются на каждом шаге. Наверное, учебная... Приведенную реализацию можно несколько улучшить;
void divisible_func(std::vector& a, const std::vector& b) {
vector c;
c.reserve(a.size());

for(size_t i = 0; i < b.size(); ++i) {
for(size_t j = 1; j < a.size(); ++j) {
if (j % b[i] != 0) {
c.push_back(a[j]);
}
}
a.swap(c); // capacity swapped
c.clear(); // capacity not changed
}

a.push_back(-1); // ????????????????
}

int main() {
int elem;

vector a;
vector b;

while (cin >> elem) {
if (elem == -1) break;
a.push_back(elem);
}
while (cin >> elem) {
if (elem == -1) break;
b.push_back(elem);
}

divisible_func(a, b);
for (size_t i = 0; i < a.size(); i++) {
cout << a[i] << std::setw(a.size());
}
}

Comments

[Александр Прилепский]

или, более элегантный(возможно, не более эффективный)

template<class ForwardIt, class UnaryPredicate>
ForwardIt npartition(ForwardIt first, ForwardIt last, UnaryPredicate&& p) {
    first = std::find_if_not(first, last, p);
    if (first == last) return first;
 
    for (ForwardIt i = std::next(first); i != last; ++i) {
        if(p(*i)) {
            std::iter_swap(i, first);
            ++first;
        }
    }
    return first;
}

void divisible_func(std::vector<int>& a, const std::vector<int>& b) {
    auto it = a.end();
    for(size_t i = 0, j = 0; i < b.size(); ++i, j=0) {
        it = npartition(a.begin(), it, [&] (int) {
            return ((j++ % b[i]) != 0);                                // в левой части a соберутся j % b[i] != 0
        });
    }
    a.erase(it, a.end());
    a.push_back(-1);         // ????????????????
}