Смещение членов массива

@MeghaNik · Регистрация: 07.08.2011

Author24 — интернет-сервис помощи студентам

В общем задача: нужно найти все простые числа в динамическом массиве, удалить их, сместить оставшиеся элементы на 1 позицию влево от удаляемого элемента, а освобождающиеся элементы в конце массива заполнить нулями. Например, если начальный массив 4, 7, 12, 3, 56, то результатом должен быть массив 4, 12, 56, 0, 0.
Так вот, нужно составить алгоритм. Нахождение простых чисел я уже сделал, а вот смещение вместе с удалением не получается.
Прикрепил блок-схему. Нужно чтобы при нахождении первого простого элемента действовало "Vect[i] = Vect[i + 1]" для всех. Как это сделать не пойму.

@Paporotnik · 28.08.2011, 22:45

нули внутри списка чисел встречаться могут?

@rangerx · 28.08.2011, 22:53

std::remove_if - для удаления
std::fill - для заполнения нулями

Добавлено через 1 минуту
Ну, или реализацию посмотри, там же по ссылкам.

@MeghaNik · 28.08.2011, 23:25 **[ТС]**

Paporotnik, внутри - нет. "0" - это простое число.

rangerx, код - это хорошо, но мне нужен алгоритм.

@Илларион · 28.08.2011, 23:30

Ну у меня есть мысль делать все по очереди.
1). Пока есть простое число делаем обход массива
Если найдено прост. число, ставим vect[i] = vect[i+1] и все значения дальше до конца. vect[sizeof(vect)-j] приравниваем к нулю. j - количество проходов массива

@OstapBender · 28.08.2011, 23:38

если с++, тогда std::stable_partition + std::fill

MeghaNik, такие задачи в стиле С решать очень легко с помощью дополнительного массива.
копируйте туда простые числа, остаток заполните нулями.
по необходимости скопируйте новый массив на место старого (плохо).

@rangerx · 29.08.2011, 01:46

Сообщение от MeghaNik

rangerx, код - это хорошо, но мне нужен алгоритм.

Ну, так что ты не можешь пару строк кода разобрать и составить алгоритм? Например, удаляем чётные
f - first
r - result

Бежим указателем f от начала до конца массива. Если элемент на который указывает f нечётный, то записываем по адресу r значение того на что указывает f, и перемещаем r одну позицию вперёд. И так до конца.

Код

1) 2 5 3 4 1 
   f  
   r

2) 2 5 3 4 1
     f
   r

3) 5 5 3 4 1
       f
     r   

4) 5 3 3 4 1
         f
       r  

5) 5 3 3 4 1
           f
       r   

6) 5 3 1 4 1
             f
         r

Остались нечётные: 5 3 1
теперь от r и до самого конца всё можно заполнить нулями.
Пример(максимально простой, без указателей)

C

#include <stdio.h>
 
#define N 5
 
int main()
{
    int a[N] = { 2, 5, 3, 4, 1 };
 
    int i = 0;
    int r = 0;
 
    // удаляем чётные
    while(i != N)
    {
        if( (a[i] % 2) == 1 )
        {
            a[r] = a[i];
            ++r;
        }
        ++i;
    }
 
    // заполняем нулями освободившиеся позиции
    for(i = r; i < N; ++i)
        a[i] = 0;
 
 
    for(i = 0; i < N; ++i)
        printf("%d ", a[i]);
    putchar('\n');
 
    return 0;
}

@Paporotnik 385 / 229 / 12 Регистрация: 06.07.2011 Сообщений: 512
	28.08.2011, 22:45	2
	нули внутри списка чисел встречаться могут? 0

@rangerx 2022 / 1621 / 489 Регистрация: 31.05.2009 Сообщений: 3,005
	28.08.2011, 22:53	3
	std::remove_if - для удаления std::fill - для заполнения нулями Добавлено через 1 минуту Ну, или реализацию посмотри, там же по ссылкам. 0

@MeghaNik 0 / 0 / 0 Регистрация: 07.08.2011 Сообщений: 5
	28.08.2011, 23:25 [ТС]	4
	Paporotnik, внутри - нет. "0" - это простое число. rangerx, код - это хорошо, но мне нужен алгоритм. 0

@Илларион 8 / 8 / 0 Регистрация: 05.06.2011 Сообщений: 97
	28.08.2011, 23:30	5
	Ну у меня есть мысль делать все по очереди. 1). Пока есть простое число делаем обход массива Если найдено прост. число, ставим vect[i] = vect[i+1] и все значения дальше до конца. vect[sizeof(vect)-j] приравниваем к нулю. j - количество проходов массива 0

@OstapBender 594 / 532 / 76 Регистрация: 22.03.2011 Сообщений: 1,585
	28.08.2011, 23:38	6
	если с++, тогда std::stable_partition + std::fill MeghaNik, такие задачи в стиле С решать очень легко с помощью дополнительного массива. копируйте туда простые числа, остаток заполните нулями. по необходимости скопируйте новый массив на место старого (плохо). 0

	29.08.2011, 01:46

Опции темы