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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Rabb1t
0 / 0 / 0
Регистрация: 07.10.2011
Сообщений: 7
#1

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

07.07.2013, 07:57. Просмотров 554. Ответов 4
Метки нет (Все метки)

День добрый!

Год назад сдал курсовую работу на тему "Отсев элементов из заданного массива". На 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++
Первый способ работает, а второй нет #pragma hdrstop #pragma argsused #ifdef _WIN32 #include &lt;tchar.h&gt; #include &lt;windows.h&gt;...

Разработать программу «переворота» строки. Способ: последовательная перестановка элементов - первый с последним, второй с предпоследним и т.д. - C++
Разработать программу «переворота» строки. Способ: последовательная перестановка элементов - первый с последним, второй с предпоследним...

Найти количество отрицательных элементов массива, находящихся во второй половине массива - C++
Обязательные условия: 1) массивы должны быть динамические – организовать выделение памяти; 2) значения элементов массива вводятся с ...

Найти сумму элементов второй строки массива - C++
Существует некоторый двухмерный массив, который имеет М-столбцов и N-строк. Найти сумму элементов второй строки массива

Вычислить произведение положительных элементов в первой и во второй половине массива - C++
Заполнить одномерный массив целыми числами. Вычислить произведение положительных элементов в первой и во второй половине массива.

Выполнить реверс элементов массива отдельно в первой половине и во второй - C++
Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине. ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4225 / 2199 / 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++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.07.2013, 17:37     Второй способ отсева элементов из массива? #4
Цитата Сообщение от Rabb1t Посмотреть сообщение
Благодарю!
Я правильно понял, это мой алгоритм, только немного переделанный?)
поскольку сложность моего алгоритма O(n), а вашего - O(n^2), то это абсолютно разные алгоритмы, при этом ваш с большими массивами будет работать долго, в некоторых случаях сутки, мой - не более секунды.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2013, 17:47     Второй способ отсева элементов из массива?
Еще ссылки по теме:

Вычислить сумму нечетных элементов второй колонки двумерного массива - C++
Тема: Обработка двумерных массивов Задан двумерный массив: S Вычислить сумму нечетных элементов из 2-й колонки. ...

Найти наименьшие среди элементов первого массива, которые не входят во второй - C++
Задано 2 массива, нужно найти наименьшие среди элементов первого массива которые не входят во второй. Пробовал так: #include...

Сортировка элементов первой половины одномерного массива по убыванию, а второй – по возрастанию - C++
Добрый Вечер!!!Пожалуйста помогите решить задачу на Шаблоны Функций: Разработайте программу, в которой реализована сортировка элементов...

Реализовать функцию копирования элементов первого массива во второй в обратном порядке. - C++
1. Создать проект, который содержит консольную программу Win32. 2. Создать два массива на N элементов, размер первого определить неявно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
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     Второй способ отсева элементов из массива?
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru