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

Сложности с решением - C++

Восстановить пароль Регистрация
 
asap_r
0 / 0 / 0
Регистрация: 13.02.2012
Сообщений: 4
13.02.2012, 13:26     Сложности с решением #1
Дана последовательность целых чисел. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел. Помогите с решением пожалуйста.

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 <iostream>
#include <clocale>
 
using namespace std;
 
int a,i,b,c;
int summa=0;
double sred;
void Bsort (int *x, int n){
int i, tmp, q;
    do{
    q=0;
    for(i=0; i<n-1; i++)
    if(x[i]>x[i+1]){
    tmp=x[i]; x[i]=x[i+1]; x[i+1]=tmp; q=1;}
}
 
while (q!=0);
}
 
int main(){
    system ("cls");
    setlocale (LC_ALL, "Russian");
    int * my;
    
    cout << "Введите размерность массива:";
    cin>> a;
    my=new int[a];
 
    cout<<"Заполнить массив (Вручную 1, рандомом - любой символ:)";
    cin>> b;
    if(b==1)
    for(i=0; i<a; ++i){
        cout<< "Элемент:"<<i+1<<":";
    cin>> my[i];
    }
    
else
    for(i=0; i<a; ++i)
    my[i]=rand();
    Bsort(my, a);
 
    for(i=0; i<a; ++i)
    cout<< my[i]<<'\n';
    
system ("pause");
return 0;
}
Добавлено через 1 час 36 минут
Придумал алгоритм, мб и не совсем точный, когда числа задаются рандомно, но суть его в том что бы упорядочить массив по возрастанию, взять из него первое и последнее число, перенести их в первую группу и очистить эти числа из основного массива. Потом та же самая операция но во вторую группу, потом опять в первую и так до того момента пока в массиве не останется чисел. Например, дана последовательность 1,2,3,4. 1 и 4 переносим в первую группу, 2 и 3 во вторую. Но даже это я не знаю как можно осуществить на языке C++.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.02.2012, 13:26     Сложности с решением
Посмотрите здесь:

C++ помогите с решением
Помогите с решением задачи на С ((( C++
c++ c решением C++
C++ Помогите с решением задачи на С++.
Помогите с решением задачи на С++. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6176 / 2905 / 284
Регистрация: 04.12.2011
Сообщений: 7,730
Записей в блоге: 3
13.02.2012, 15:38     Сложности с решением #2
Цитата Сообщение от asap_r Посмотреть сообщение
Дана последовательность целых чисел. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел. Помогите с решением пожалуйста.
Мне, вот не понятно. В предложенных ограничениях задача имеет как мне кажется не одно решение.
И в такой постановке она, только кажется простой, - мне кажется.
А покажите-ка оригинал условия, пожалуйста, или подтвердите, что это он и был.
asap_r
0 / 0 / 0
Регистрация: 13.02.2012
Сообщений: 4
13.02.2012, 15:55  [ТС]     Сложности с решением #3
Это и есть оригинал задачи. Предложенное мною решение действительно будет выводить не самую минимальную отличающююя друг от друга группу чисел.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6176 / 2905 / 284
Регистрация: 04.12.2011
Сообщений: 7,730
Записей в блоге: 3
13.02.2012, 16:02     Сложности с решением #4
Цитата Сообщение от asap_r Посмотреть сообщение
отличающююя друг от друга
Об этом я и говорю. Друг от друга в группе, и суммой чисел между группами это не одно и тоже.
Прочтите глазами человека не видевшего оригинал:
Цитата Сообщение от IGPIGP Посмотреть сообщение
. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел.
По-этому, - на всякий случай, напишите оригинальный текст, пожалуйста
asap_r
0 / 0 / 0
Регистрация: 13.02.2012
Сообщений: 4
13.02.2012, 16:42  [ТС]     Сложности с решением #5
Оригинал "Дана последовательность целых чисел. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел". Скорей всего я не правильно выразил мысль в описании своего алгоритма.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6176 / 2905 / 284
Регистрация: 04.12.2011
Сообщений: 7,730
Записей в блоге: 3
13.02.2012, 16:48     Сложности с решением #6
Молчите, тогда буду догадываться.
Если дана группа целых чисел, и требуется получить из нее две группы так, что бы числа в каждой группе минимально отличались между собой (или суммой цифр? ) то нужно отсортировать исходную группу, и разделить точно посредине. Четное количество элементов в исходной группе - один вариант ответа. Нечетное - два (там две середины) .

Добавлено через 5 минут
Цитата Сообщение от asap_r Посмотреть сообщение
на две группы чисел
А ведь одно число это тоже группа! И кажется придется повозиться.
Если Вы привели оригинал, то... То ли сегодня не мой день... В общем обещаю подумать и позже скажу, если ни-кто не успеет
asap_r
0 / 0 / 0
Регистрация: 13.02.2012
Сообщений: 4
13.02.2012, 17:00  [ТС]     Сложности с решением #7
"Если дана группа целых чисел, и требуется получить из нее две группы так, что бы числа в каждой группе минимально отличались между собой." - между собой значит между двумя группами в сумме. Как в моем примере, что если есть числа 1,2,3,4,5,6,7,8 то группы должны получиться такие, первая с набором цифр - 1,8,3,6. Вторая - 2,7,4,5. Что в итоге дает в первой группе сумму 18, и во второй - 18, т.е. разница между суммами этих групп минимальная.

Добавлено через 8 минут
А ведь одно число это тоже группа! И кажется придется повозиться.
Если Вы привели оригинал, то... То ли сегодня не мой день... В общем обещаю подумать и позже скажу, если ни-кто не успеет
На сколько правильно я понял условие задачи, то нужно использовать все числа из основного массива. Видимо и не мой сегодня тоже!!!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.02.2012, 21:57     Сложности с решением
Еще ссылки по теме:

C++ помогите с решением задания по С++
C++ Сложности с решением системы дифференциальных уравнений
C++ трудности с решением задачи

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

Или воспользуйтесь поиском по форуму:
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6176 / 2905 / 284
Регистрация: 04.12.2011
Сообщений: 7,730
Записей в блоге: 3
13.02.2012, 21:57     Сложности с решением #8
Вы подразумеваете две одинаковых группы - в условии этого нет, (хотя в конкретной задаче - как частный случай это может быть).
На правах идеи (туп я сегодня не средне) -
1.Сортируем по возрастанию. -"Исходная группа"
2. Сравниваем "первую" группу пока из одного элемента (максимального элемента массива) с суммой остальных. Сохраняем разницу.
3. Последовательно добавляем в "первую" из "второй" (исходной без максимального элемента) младший элемент (изымая его из второй и получая новую вторую группу) и вычисляем разницу сумм в группах.
4. И так пока разница не начнет рости...


Добавлено через 33 минуты
Цитата Сообщение от IGPIGP Посмотреть сообщение
4. И так пока разница не начнет рости...
Не забудьте откатить на шаг назад. Это и будут правильные группы, и будут они равно велики и по количеству, и по сумме, и будет Вам счастье...

Добавлено через 4 часа 18 минут
Цитата Сообщение от IGPIGP Посмотреть сообщение
3. Последовательно добавляем в "первую" из "второй" (исходной без максимального элемента) младший элемент (изымая его из второй и получая новую вторую группу) и вычисляем разницу сумм в группах.
Это похоже не верно.
Не дает мне покоя Ваша задачка.
Добавлять похоже нужно старший элемент, а при переполнении разницы возвращать его назад и выбирать следующий за ним (справа)...
Yandex
Объявления
13.02.2012, 21:57     Сложности с решением
Ответ Создать тему
Опции темы

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