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

Второй способ отсева элементов из массива? - C++

Восстановить пароль Регистрация
 
Rabb1t
0 / 0 / 0
Регистрация: 07.10.2011
Сообщений: 7
07.07.2013, 07:57     Второй способ отсева элементов из массива? #1
День добрый!

Год назад сдал курсовую работу на тему "Отсев элементов из заданного массива". На C++.
В этом году мне дали задание по практике сделать тоже самое, только двумя алгоритмами.

Суть курсовой следующая:

Цель данной работы – создать программу, которая удаляет в заданном массиве Х(n) «лишние» (кроме первого) элементы так, чтобы оставшиеся образовывали возрастающую последовательность (за один просмотр массива).
Ограничения к проекту: работа с массивом длиной до 64 тысяч элементов; элементы массива целочисленные; массив, полученный в результате работы проекта, должен быть упорядочен по возрастанию; задание элементов массива осуществляется случайным образом, из текстового файла и с использованием клавиатуры; проект должен быть многофайловым; создание дружественного интерфейса.
Подскажите каким еще способом можно сделать отсев? Можно название способа, можно кусочек кода...
Год без практики в программировании сказывается

Вот кусочек кода, осуществляющий отсев в моей курсовой:

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
//Otsev
void start(){char str[5]="";
cleardevice();
int midx = 10;
int midy = 10;
outtextxy(60,20,"Array:");
for (int i=0;i<n;i++){
    char b[10]={0};
    sprintf(b,"%i",masi[i]&255);
    settextstyle(0,0,1);
    outtextxy(midx+=strlen(b)*25,midy+30,b);}
    if(midx>getmaxx()-8){midx=100;midy+=200;}
for (int k=1;k<=n;k++){               //prosmatrivaem massiv
    if (masi[k]<=masi[k-1]){     //sravnivaem dva elementa
        for (int j=k;j<n-1;j++)     //perestanovka
            masi[j]=masi[j+1];
            n--;                //ymenshaem kolichestvo elementov na 1
            k--;
        }
    }
settextstyle(0,0,2);
outtextxy(85,288,"New array:");
midx = 10;
midy = 10;
for (i=0;i<=n;i++){
    char b[10]={0};
    settextstyle(0,0,1);
    sprintf(b,"%i",masi[i]&255);
    outtextxy(midx+=strlen(b)*25,midy+300,b);}
getche();
fmenu();
}
Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2013, 07:57     Второй способ отсева элементов из массива?
Посмотрите здесь:

Найти наименьшие среди элементов первого массива, которые не входят во второй массив C++
Разработать программу «переворота» строки. Способ: последовательная перестановка элементов - первый с последним, второй с предпоследним и т.д. C++
C++ Заполнить К элементов, стоящих во второй половине данного массива, последовательными числами от K до 1.
Реализовать функцию копирования элементов первого массива во второй в обратном порядке. C++
Сортировка элементов первой половины одномерного массива по убыванию, а второй – по возрастанию C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.07.2013, 10:09     Второй способ отсева элементов из массива? #2
в данной задаче можно без квадратичных сложностей обойтись:
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
#include <iostream>
#include <cstdlib>
#include <ctime>
const int N = 10; 
 
void Init(int *a, int n)
{
   for(int i = 0; i < n; ++i)
      a[i] = rand() % 101 - 50; 
}
void Print(int *a, int n)
{
   for(int i = 0; i < n; ++i)
      std::cout << a[i] << " ";
   std::cout << std::endl;      
}
void Otsev(int *a, int &n)
{
   int i, j;
   for(i = j = 1; i < n; ++i)
      if (a[j - 1] < a[i])
         a[j++] = a[i];
   n = j;           
}
int main()
{
   int a[N], n = N;
   srand(time(NULL));
   Init(a, N);
   Print(a, N);
   Otsev(a, n);
   Print(a, n);
   return 0;    
}
Rabb1t
0 / 0 / 0
Регистрация: 07.10.2011
Сообщений: 7
07.07.2013, 17:31  [ТС]     Второй способ отсева элементов из массива? #3
Thinker, благодарю!
Я правильно понял, это мой алгоритм, только немного переделанный?)
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.07.2013, 17:37     Второй способ отсева элементов из массива? #4
Цитата Сообщение от Rabb1t Посмотреть сообщение
Благодарю!
Я правильно понял, это мой алгоритм, только немного переделанный?)
поскольку сложность моего алгоритма O(n), а вашего - O(n^2), то это абсолютно разные алгоритмы, при этом ваш с большими массивами будет работать долго, в некоторых случаях сутки, мой - не более секунды.
Rabb1t
0 / 0 / 0
Регистрация: 07.10.2011
Сообщений: 7
07.07.2013, 17:47  [ТС]     Второй способ отсева элементов из массива? #5
Цитата Сообщение от Thinker Посмотреть сообщение
поскольку сложность моего алгоритма O(n), а вашего - O(n^2), то это абсолютно разные алгоритмы, при этом ваш с большими массивами будет работать долго, в некоторых случаях сутки, мой - не более секунды.
Спасибо!
Yandex
Объявления
07.07.2013, 17:47     Второй способ отсева элементов из массива?
Ответ Создать тему
Опции темы

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