@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;
}
  • Вопрос задан
  • 91 просмотр
Решения вопроса 1
alex1951
@alex1951
"умных преподавателей слушал я невнимательно..."
Да, странная задача. Индексы меняются на каждом шаге. Наверное, учебная... Приведенную реализацию можно несколько улучшить;
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());
}
}
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы