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

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

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

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

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

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

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

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

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

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

Создать массив структур без использования массивов и нотации массивов - C++
Доброго времени суток! Есть задание, в котором нужно создать массив структур, имея следующую структуру: struct name { string...

В каждом из массивов найти наибольшее значение и умножить на него все элементы массивов - C++
Заданы два массива А(5) и В(5). В каждом из массивов найти наибольшее значение и умножить на него все элементы массивов. На печать вывести...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
niXman
Эксперт C++
3135 / 1447 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.10.2009, 22:18 #2
Цитата Сообщение от strelokm3 Посмотреть сообщение
на с++
Ок....подумаем...
0
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 минуту
Кроме меня кто-нибудь понял ?
0
Даемоник
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;
}


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

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

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

В каждом из заданных массивов найти наибольшее значение, и разделить на него все элементы массивов - C++
Заданы два массива А(5) и В(5). В каждом из массивов найти наибольшее значение и разделить на него все элементы массивов. На печать вывести...

Сравнение массивов: найти максимальное перебором массивов - C++
Добрый вечер такая проблема даны два одномерных массива A, B причем в каждом массиве записанно число по разрядно Задачи найти...

Заданы два массива А(5) и В(5). В каждом из массивов найти наименьшее значение и разделить на него все элементы массивов. На печать вывести исходные - C++
Заданы два массива А(5) и В(5). В каждом из массивов найти наименьшее значение и разделить на него все элементы массивов. На печать...

Обработка одномерных массивов. Сортировка массивов - C++
Здравствуйте, помогите пожалуйста решить задачу легким способом. В одномерном массиве, состоящем из n вещественных элементов, вычислить: ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.11.2009, 11:04
Ответ Создать тему
Опции темы

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