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

@asap_r · Регистрация: 13.02.2012

Author24 — интернет-сервис помощи студентам

Дана последовательность целых чисел. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел. Помогите с решением пожалуйста.

C++

#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++.

IGPIGP · 13.02.2012, 15:38

Сообщение от asap_r

Дана последовательность целых чисел. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел. Помогите с решением пожалуйста.

Мне, вот не понятно. В предложенных ограничениях задача имеет как мне кажется не одно решение.
И в такой постановке она, только кажется простой, - мне кажется.
А покажите-ка оригинал условия, пожалуйста, или подтвердите, что это он и был.

@asap_r · 13.02.2012, 15:55 **[ТС]**

Это и есть оригинал задачи. Предложенное мною решение действительно будет выводить не самую минимальную отличающююя друг от друга группу чисел.

IGPIGP · 13.02.2012, 16:02

Сообщение от asap_r

отличающююя друг от друга

Об этом я и говорю. Друг от друга в группе, и суммой чисел между группами это не одно и тоже.
Прочтите глазами человека не видевшего оригинал:

Сообщение от IGPIGP

. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел.

По-этому, - на всякий случай, напишите оригинальный текст, пожалуйста

@asap_r · 13.02.2012, 16:42 **[ТС]**

Оригинал "Дана последовательность целых чисел. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел". Скорей всего я не правильно выразил мысль в описании своего алгоритма.

IGPIGP · 13.02.2012, 16:48

Молчите, тогда буду догадываться.
Если дана группа целых чисел, и требуется получить из нее две группы так, что бы числа в каждой группе минимально отличались между собой (или суммой цифр?

) то нужно отсортировать исходную группу, и разделить точно посредине. Четное количество элементов в исходной группе - один вариант ответа. Нечетное - два (там две середины)

.

Добавлено через 5 минут

Сообщение от asap_r

на две группы чисел

А ведь одно число это тоже группа! И кажется придется повозиться.
Если Вы привели оригинал, то... То ли сегодня не мой день... В общем обещаю подумать и позже скажу, если ни-кто не успеет

@asap_r · 13.02.2012, 17:00 **[ТС]**

"Если дана группа целых чисел, и требуется получить из нее две группы так, что бы числа в каждой группе минимально отличались между собой." - между собой значит между двумя группами в сумме. Как в моем примере, что если есть числа 1,2,3,4,5,6,7,8 то группы должны получиться такие, первая с набором цифр - 1,8,3,6. Вторая - 2,7,4,5. Что в итоге дает в первой группе сумму 18, и во второй - 18, т.е. разница между суммами этих групп минимальная.

Добавлено через 8 минут

А ведь одно число это тоже группа! И кажется придется повозиться.
Если Вы привели оригинал, то... То ли сегодня не мой день... В общем обещаю подумать и позже скажу, если ни-кто не успеет

На сколько правильно я понял условие задачи, то нужно использовать все числа из основного массива. Видимо и не мой сегодня тоже!!!

IGPIGP · 13.02.2012, 21:57

Вы подразумеваете две одинаковых группы - в условии этого нет, (хотя в конкретной задаче - как частный случай это может быть).
На правах идеи (туп я сегодня не средне) -
1.Сортируем по возрастанию. -"Исходная группа"
2. Сравниваем "первую" группу пока из одного элемента (максимального элемента массива) с суммой остальных. Сохраняем разницу.
3. Последовательно добавляем в "первую" из "второй" (исходной без максимального элемента) младший элемент (изымая его из второй и получая новую вторую группу) и вычисляем разницу сумм в группах.
4. И так пока разница не начнет рости...

Добавлено через 33 минуты

Сообщение от IGPIGP

4. И так пока разница не начнет рости...

Не забудьте откатить на шаг назад. Это и будут правильные группы, и будут они равно велики и по количеству, и по сумме, и будет Вам счастье...

Добавлено через 4 часа 18 минут

Сообщение от IGPIGP

3. Последовательно добавляем в "первую" из "второй" (исходной без максимального элемента) младший элемент (изымая его из второй и получая новую вторую группу) и вычисляем разницу сумм в группах.

Это похоже не верно.
Не дает мне покоя Ваша задачка.
Добавлять похоже нужно старший элемент, а при переполнении разницы возвращать его назад и выбирать следующий за ним (справа)...

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8949 / 4703 / 629 Регистрация: 04.12.2011 Сообщений: 13,999 Записей в блоге: 16
	13.02.2012, 15:38	2
	Сообщение от asap_r Дана последовательность целых чисел. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел. Помогите с решением пожалуйста. Мне, вот не понятно. В предложенных ограничениях задача имеет как мне кажется не одно решение. И в такой постановке она, только кажется простой, - мне кажется. А покажите-ка оригинал условия, пожалуйста, или подтвердите, что это он и был. 0

@asap_r 0 / 0 / 0 Регистрация: 13.02.2012 Сообщений: 4
	13.02.2012, 15:55 [ТС]	3
	Это и есть оригинал задачи. Предложенное мною решение действительно будет выводить не самую минимальную отличающююя друг от друга группу чисел. 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8949 / 4703 / 629 Регистрация: 04.12.2011 Сообщений: 13,999 Записей в блоге: 16
	13.02.2012, 16:02	4
	Сообщение от asap_r отличающююя друг от друга Об этом я и говорю. Друг от друга в группе, и суммой чисел между группами это не одно и тоже. Прочтите глазами человека не видевшего оригинал: Сообщение от IGPIGP . Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел. По-этому, - на всякий случай, напишите оригинальный текст, пожалуйста 1

@asap_r 0 / 0 / 0 Регистрация: 13.02.2012 Сообщений: 4
	13.02.2012, 16:42 [ТС]	5
	Оригинал "Дана последовательность целых чисел. Разделить эту последовательность на две группы чисел с минимально отличающейся суммой чисел". Скорей всего я не правильно выразил мысль в описании своего алгоритма. 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8949 / 4703 / 629 Регистрация: 04.12.2011 Сообщений: 13,999 Записей в блоге: 16
	13.02.2012, 16:48	6
	Молчите, тогда буду догадываться. Если дана группа целых чисел, и требуется получить из нее две группы так, что бы числа в каждой группе минимально отличались между собой (или суммой цифр? ) то нужно отсортировать исходную группу, и разделить точно посредине. Четное количество элементов в исходной группе - один вариант ответа. Нечетное - два (там две середины) . Добавлено через 5 минут Сообщение от asap_r на две группы чисел А ведь одно число это тоже группа! И кажется придется повозиться. Если Вы привели оригинал, то... То ли сегодня не мой день... В общем обещаю подумать и позже скажу, если ни-кто не успеет 1

@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 минут А ведь одно число это тоже группа! И кажется придется повозиться. Если Вы привели оригинал, то... То ли сегодня не мой день... В общем обещаю подумать и позже скажу, если ни-кто не успеет На сколько правильно я понял условие задачи, то нужно использовать все числа из основного массива. Видимо и не мой сегодня тоже!!! 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8949 / 4703 / 629 Регистрация: 04.12.2011 Сообщений: 13,999 Записей в блоге: 16
	13.02.2012, 21:57	8
	Вы подразумеваете две одинаковых группы - в условии этого нет, (хотя в конкретной задаче - как частный случай это может быть). На правах идеи (туп я сегодня не средне) - 1.Сортируем по возрастанию. -"Исходная группа" 2. Сравниваем "первую" группу пока из одного элемента (максимального элемента массива) с суммой остальных. Сохраняем разницу. 3. Последовательно добавляем в "первую" из "второй" (исходной без максимального элемента) младший элемент (изымая его из второй и получая новую вторую группу) и вычисляем разницу сумм в группах. 4. И так пока разница не начнет рости... Добавлено через 33 минуты Сообщение от IGPIGP 4. И так пока разница не начнет рости... Не забудьте откатить на шаг назад. Это и будут правильные группы, и будут они равно велики и по количеству, и по сумме, и будет Вам счастье... Добавлено через 4 часа 18 минут Сообщение от IGPIGP 3. Последовательно добавляем в "первую" из "второй" (исходной без максимального элемента) младший элемент (изымая его из второй и получая новую вторую группу) и вычисляем разницу сумм в группах. Это похоже не верно. Не дает мне покоя Ваша задачка. Добавлять похоже нужно старший элемент, а при переполнении разницы возвращать его назад и выбирать следующий за ним (справа)... 1

Опции темы