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

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

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

Хитрое разделение массивов. - C++

28.10.2009, 21:41. Просмотров 915. Ответов 9
Метки нет (Все метки)

Из элементов массива А[1..2N] получить массивы В[1..N] и С[1..N] следующим образом. Выбрать в массиве А два наиболее близких по значению элемента; меньший из них поместить в массив В, а больший - в массив С. Продолжить выбор из оставшихся элементов до полного заполнения массивов В и С.
Сделать на C++ в консоли.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.10.2009, 21:41     Хитрое разделение массивов.
Посмотрите здесь:

Хитрое транспонирование матрицы - C++
Значится так, есть матрица загнанная в вектор... есть ли способ транспонировать ее не создавая новый вектор, то есть просто обменивая...

Хитрое разложение. Дополнить - C++
В общем решал олимпиадную задачу( пробную ). Вот текст: Вот что я написал: #include <iostream> using namespace std; int...

Хитрое создание переменной - C++
Позвольте азадачить всех, кому интересно. Создаю переменные int konstruktor; int destruktor; не представляю, как их...

Как сделать хитрое наследование? Хранить в одном контейнере родителя и потомков - C++
Доброго времени суток! Интересует, можно ли при создании класса-потомка назначать его родительский класс (не копировать, а именно...

Разделение на h и cpp - C++
На форуме есть темы с таким же названием, но тамошние приемы мне что-то не помогают. Жил был файл InfotrigsList.h, в нем был класс...

разделение массива - C++
как разделить массив помогите пожалуйста

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.10.2009, 22:18     Хитрое разделение массивов. #2
Цитата Сообщение от strelokm3 Посмотреть сообщение
на с++
Ок....подумаем...
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
29.10.2009, 21:58     Хитрое разделение массивов. #3
Прикольная задача.
Как делать понятно - тупо брать и делать как написано в условии. И похоже ускорить процесс никак нельзя.

Добавлено через 6 минут
Хотя можно попробовать.
Создаем массив расстояний между элементами. Он будет размером примерное N*N/2.
Массив сортируем.
Потом берем из массива расстояний самый минимальный элемент (расстояние между двумя элементами в массиве A). Кладем два элемента из A в массивы B и C.
Потом эти два элемента вычеркиваем из A.
Потом опять берем из массива расстояний следующий элемент (нужно только не брать расстояния между уже вычеркнутыми элементами).
Нужно завести еще один массив, где помечать вычернут элемент в массиве А или нет.
И так в цикле до конца, пока из массива A не будут вычеркнуты все элементы.

Добавлено через 1 минуту
Кроме меня кто-нибудь понял ?
Даемоник
42 / 42 / 3
Регистрация: 22.05.2009
Сообщений: 97
29.10.2009, 23:31     Хитрое разделение массивов. #4
Я тут подумал немного... Что-то получилось, посмотрите пжлста

Разделение массивов
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <conio.h>
using namespace std;
 
void quickSortR(int* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
 
  long i = 0, j = N;            // поставить указатели на исходные места
  int temp, p;
 
  p = a[ N>>1 ];                // центральный элемент
 
  // процедура разделения
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );
 
  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}
 
int main()
{
    long len;
    cout<<"Enter lenth of array :";
    cin>>len;
    long halfLen=(len-1)/2;
    int *arrayA,*arrayB,*arrayC;
    arrayA=new int [len];
    arrayB=new int [halfLen];
    arrayC=new int [halfLen];
    cout<<"Enter elements of array";
    for(long i=0; i<len; i++)
        cin>>arrayA[i];
    quickSortR(arrayA,len);
    int i=0;
    int j=0;
    while(true)
    {
        if(j==halfLen)j=0;
        if((arrayA[i]-arrayA[i+1])<=1){
            arrayA[i]=arrayB[j];
            arrayA[i+1]=arrayC[j];
            arrayA[i]=-1;
            arrayA[i+1]=-1;
        }
        if(i==len)i=0;
        if(arrayA[i]+arrayA[i+1]+
            arrayA[i+2]==-3)break;
 
    }
    for (int i = 0; i < halfLen; i++)
    {
        cout<<arrayB[i]<<endl;
    }
    getch();
    return 0;
}


По логике вроде все нормально, а работать не хочет.
JamesBlack
37 / 37 / 3
Регистрация: 28.07.2009
Сообщений: 144
30.10.2009, 00:27     Хитрое разделение массивов. #5
Одип, мне кажется, что это не самая лучшая идея. Ведь когда ты создаешь массив расстояний, то ты должен каждому его элементу синхронизировать 2 инта еще - индексы чисел, расстояния между которыми смотришь. Получается, что у тебя будет массив структуры из 3 чисел...
Затем еще надо отслеживать, какие удалены, а какие нет...
Это потребует гораздо больше памяти, чем должно, и займет больше времени на выполнение. Я уже молчу про сложность алгоритма.

Помоему проще делать как сказано в задании, т.е. двойным циклом проходить по массиву, запоминать наименьшее расстояние между числами и их индексы, заносить в массивы B и C и заменять их в массиве A скажем на MAXDOUBLE и MINDOUBLE (если там конечно действительные числа стоят). Поместить этот алгоритм в 3й цикл и вуа-ля. Ускорить по идее можно, если после каждой найденной пары чисел, сортировать массив А. И еще если в самом начале отсортировать массив A, то можно сверять расстояния тока между соседними элементами.

Твои же загоны мне кажется излишни.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
30.10.2009, 11:25     Хитрое разделение массивов. #6
А я не сказал что нужно считать с помощью моего алгоритма
Памяти потребуется больше - это факт.
Но и считать он будет быстрее чем тупой алгоритм в лоб.

Алгоритм в лоб будет считать примерное O(N*N*LOG(N)).
Мой алгоритм будет считать примерное O(N*LOG(N)), но потребует больше памяти.

Добавлено через 6 минут
заменять их в массиве A скажем на MAXDOUBLE и MINDOUBLE
Это неправильная идея. Потому что расстояние между двумя MAXDOUBLE равно 0, то есть минимально. Нужно именно удалять элементы !
отсортировать массив A, то можно сверять расстояния тока между соседними элементами.
А вот это уже хорошая идея.
Сортируем массив. Тогда чтобы найти минимальное расстояние потребуется всего O(N) действий. И не требуется заводить большой дополнительный массив.
Потом удаляем два элемента с минимальным расстоянием путем сдвига массива.
И опять ищем минимальное расстояние.
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
30.10.2009, 11:37     Хитрое разделение массивов. #7
А исходный массив нельзя сортировать?
Я наверное,недопонял условие но если можно сортировать исходный,то отсортировать и потом раскидать по очереди.
strelokm3
0 / 0 / 0
Регистрация: 28.10.2009
Сообщений: 34
31.10.2009, 12:19  [ТС]     Хитрое разделение массивов. #8
сможете сделать как нить? а то я дуб дубом с с++, паскаль кое как освоил, а по с++ ниче незнаю...
strelokm3
0 / 0 / 0
Регистрация: 28.10.2009
Сообщений: 34
12.11.2009, 17:15  [ТС]     Хитрое разделение массивов. #9
памагите пжлста, срок сдачи лабы истекает а то((((((
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2009, 11:04     Хитрое разделение массивов.
Еще ссылки по теме:

Разделение на .cpp и .h - C++
Здравствуйте! Прошу прощения за повтор, честно смотрела другие похожие, но все равно не разобралась. Нужно разделить программу на •...

Разделение на файлы - C++
Может кто-то объяснить как разделять код на файлы? (я так понял нужно создать заглавный файл ****.h , создать файл с таким же именем с...

Разделение потоков - C++
Нужно в главном потоке запустить 3 потока,дождаться их завершения,потом запустить ещё 3 и тоже дождаться их завершения,однако на деле идёт...

Разделение числа - C++
Ув.Форумчане. Возможно ли както методами языка разделить вещественное число на целую и вещественную часть в отдельные переменные?


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

Или воспользуйтесь поиском по форуму:
SONNY
8 / 8 / 0
Регистрация: 30.05.2009
Сообщений: 47
13.11.2009, 11:04     Хитрое разделение массивов. #10
как нить

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <functional>
#include <cstdlib>
#include <algorithm>
 
 
template<typename _InIt, typename _OutIt> void separate_arr( _InIt first, _InIt last, _OutIt dest1, _OutIt dest2 )
{
    typedef typename std::iterator_traits<_InIt>::difference_type diff_type;
    typedef typename std::iterator_traits<_InIt>::value_type value_type;
 
        if( *first == value_type() )
          return;
 
    _InIt curr_m = first;
    diff_type min = abs( *(++curr_m) - *first ); 
    std::pair<value_type, value_type> pair_v( *curr_m, *first );
    size_t idx_f = 0, idx_s = 1;
 
    for( _InIt curr_f = curr_m; curr_f != last; ++curr_f )
    {
        for( _InIt curr_s = curr_f; ++curr_s != last; )
            if( abs( *curr_f - *curr_s ) < min )
            {
                min = abs( *curr_f - *curr_s );
                pair_v = std::make_pair( *curr_f, *curr_s );
                idx_f = curr_f - first;
                idx_s = curr_s - first;
            }
    }
 
        *dest1 = pair_v.first;
    *dest2 = pair_v.second;
    
    *(first + idx_f) = value_type();
    *(first + idx_s) = value_type();
    last = std::partition( first, last, std::bind2nd(std::not_equal_to<value_type>(), value_type()) );
 
    separate_arr( first, last, ++dest1, ++dest2 );
 
}
 
 
int _tmain( int argc, _TCHAR* argv[] )
{
    int coll[] = { 40, 89, 21, 36, 4, -8, 15, 3, 13, 10 }, dest1[ 5 ], dest2[ 5 ];
    separate_arr( coll, coll + 10, dest1, dest2 );
 
}
Yandex
Объявления
13.11.2009, 11:04     Хитрое разделение массивов.
Ответ Создать тему
Опции темы

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