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

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

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

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

13.02.2012, 13:26. Просмотров 704. Ответов 7
Метки нет (Все метки)

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

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++.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.02.2012, 13:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сложности с решением (C++):

Сложности с решением системы дифференциальных уравнений - C++
Есть вот такая система уравнений: dn/dt = 75.5*p*n-75.5*n+0.0767*c dc/dt = 75.5*n-0.0767*c Где, грубо говоря, n -...

c++ c решением - C++
Given an integer number N THAT IS NOT LESS THAN 2. OUTPUT THE SMALLEST NATURAL DIVISOR OF THE N (NOT INCLUDING 1) input 15 output 3 ...

помогите с решением - C++
написать программу составления пятиугольника с вершинами вершинами (100,100), (150,100), (170,120), (150,140), (100,100). Закрасить поле с...

Задача с решением примеров - C++
Всем привет! Ребят,есть задание: написать программу,которая решает любые примеры(количество используемых чисел и знаков не ограничено...

Помогите с решением задачки на препроцессоры. С++ - C++
Условие:

Трабл с решением задания, условные операторы - C++
Здраствуйте, возникла определенная проблема при решении задания. Полагаю, не суть, что за задание, проблема вот в чем: В приведенном...

7
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6503 / 3142 / 307
Регистрация: 04.12.2011
Сообщений: 8,673
Записей в блоге: 5
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
Комп_Оратор)
Эксперт по математике/физике
6503 / 3142 / 307
Регистрация: 04.12.2011
Сообщений: 8,673
Записей в блоге: 5
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
Комп_Оратор)
Эксперт по математике/физике
6503 / 3142 / 307
Регистрация: 04.12.2011
Сообщений: 8,673
Записей в блоге: 5
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
Комп_Оратор)
Эксперт по математике/физике
6503 / 3142 / 307
Регистрация: 04.12.2011
Сообщений: 8,673
Записей в блоге: 5
13.02.2012, 21:57 #8
Вы подразумеваете две одинаковых группы - в условии этого нет, (хотя в конкретной задаче - как частный случай это может быть).
На правах идеи (туп я сегодня не средне) -
1.Сортируем по возрастанию. -"Исходная группа"
2. Сравниваем "первую" группу пока из одного элемента (максимального элемента массива) с суммой остальных. Сохраняем разницу.
3. Последовательно добавляем в "первую" из "второй" (исходной без максимального элемента) младший элемент (изымая его из второй и получая новую вторую группу) и вычисляем разницу сумм в группах.
4. И так пока разница не начнет рости...


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

Добавлено через 4 часа 18 минут
Цитата Сообщение от IGPIGP Посмотреть сообщение
3. Последовательно добавляем в "первую" из "второй" (исходной без максимального элемента) младший элемент (изымая его из второй и получая новую вторую группу) и вычисляем разницу сумм в группах.
Это похоже не верно.
Не дает мне покоя Ваша задачка.
Добавлять похоже нужно старший элемент, а при переполнении разницы возвращать его назад и выбирать следующий за ним (справа)...
1
13.02.2012, 21:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.02.2012, 21:57
Привет! Вот еще темы с ответами:

Затруднение с решением задачи на одномерный массив - C++
Здравствуйте! Дано задание: Массив содержит 7 действительных чисел. Вычислить сумму квадратов тех чисел, абсолютная величина которых...

Найти значение выражения по заданной формуле (подскажите с решением) - C++
Здание достаточно простое, но я не уверен. Надо найти F=(i=10∑100)(j=5∑50)cos(i-j). Тут просто надо сделать два цикла по i и j? Ну типа ...

Хочу разобраться с решением через тип данных структура - C++
В таблице из 5 строк хранятся данные о товарах: наименование, цена, количество. Определить и вывести наименование товара, цена которого...

Возникли сложности - C++
По ходу изучения возник вопрос: Данное объявление - легально для объявления С String? char test = { 'a', 'b', 'c', '\0' }. ...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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