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

Кладоискатели нашли некое количество золотых самородков... - C++

Восстановить пароль Регистрация
 
zago-vlad
13 / 8 / 1
Регистрация: 12.01.2010
Сообщений: 106
03.12.2011, 15:58     Кладоискатели нашли некое количество золотых самородков... #1
Всем привет!

Нужно решить эту задачку:

Условие. Кладоискатели нашли некое количество золотых самородков. У них (кладоискателей) есть весы, с помощью которых они нашли вес каждого самородка.

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

Входящие данные. Файл GOLD.DAT содержит две строки. В первой строке записано число N, которое отображает количество найденных самородков. Во второй - N действительных чисел, которые являются результатами взвешивания самородков.

Исходящие данные В файле GOLD.SOL должно содержаться три строки. В первой числа, которые являются результатом разделения и ввошли в первую кучу. Во втором - числа, которые являются результатом разделения и ввошли во вторую кучу. В третьем разница межде весом куч.

Примеры файлов

GOLD.DAT
5
12.3 15.2 2.3 7.12 2.3

GOLD.SOL
12.3 7.12
15.2 2.3 2.3
0.38


Заранее ОГРОМНОЕ спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2011, 15:58     Кладоискатели нашли некое количество золотых самородков...
Посмотрите здесь:

так и не нашли ошибку, циклы и условия C++
Для натурального числа k напечатать фразу «мы нашли k грибов в лесу», согласовав окончание слова «гриб» с числом k C++
Рекурсия. Функция, принимающая в качестве единственного аргумента некое число int N, и выводящая на экран последовательность от -N до N C++
пожалуйста, мне надо сделать некое подобия игры Кто хочет стать миллионером? C++
пожалуйста, мне надо сделать некое подобия игры Кто хочет стать миллионером? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Smillles7
25 / 25 / 1
Регистрация: 23.04.2011
Сообщений: 130
03.12.2011, 16:17     Кладоискатели нашли некое количество золотых самородков... #2
на первый взгляд вроде ничего сложного)
думаю сортировать по весу надо таким образом:
находишь максимальный элемент и проверяешь while - ом, как близок он по весу к половине, если не близко, постепенно прибавляешь наименьшие по весу самородки)

Добавлено через 34 секунды
хотя скорей всего не точно получиться)
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 16:22     Кладоискатели нашли некое количество золотых самородков... #3
Тут динамика...
zago-vlad
13 / 8 / 1
Регистрация: 12.01.2010
Сообщений: 106
03.12.2011, 16:49  [ТС]     Кладоискатели нашли некое количество золотых самородков... #4
Smillles7, выложи, плиз, пример кода.
Smillles7
25 / 25 / 1
Регистрация: 23.04.2011
Сообщений: 130
03.12.2011, 17:50     Кладоискатели нашли некое количество золотых самородков... #5
ща попробую че-нить написать)

Добавлено через 41 минуту
корявая конечно прога получилась)))
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
66
67
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
void main()
{
    ifstream in;
    in.open("1.txt");
    if(!in)
    cout<<"Файл не возможно открыть";
    int N;
    in>>N;
    double *mass1=new double[N];
    for(int i=0;i<N;i++)
        in>>mass1[i];
    vector<double> mass;
    for(int i=0;i<N;i++)
        mass.push_back(mass1[i]);
    double max=0;
    int p=0;
    for(int i=0;i<N;i++)
        if(mass[i]>max)
        {
            max=mass[i];
            p=i;
        }
    double polovina=0;
    for(int i=0;i<N;i++)
        polovina+=mass[i];
    polovina=polovina/2;
    vector<double> kucha1;
    mass.erase(mass.begin() + p);
    kucha1.push_back(max);
    double summa=max;
    double min=999999;
    int z=1;
    while(summa>=polovina+2 || summa<=polovina-2)
    {
        summa=0;
        min=999999;
        for(int i=0;i<N-z;i++)
            if( min>mass[i])
            {
                min=mass[i];
                p=i;
            }
        mass.erase(mass.begin() + p);
        kucha1.push_back(min);
        z++;
        for(int i=0;i<kucha1.size();i++)
            summa+=kucha1[i];
    }
    summa=0;
    for(int i=0;i<kucha1.size();i++)
        cout<<kucha1[i]<<" ";
    cout<<endl;
    for(int i=0;i<mass.size();i++)
        cout<<mass[i]<<" ";
    for(int i=0;i<kucha1.size();i++)
        summa+=kucha1[i];
    for(int i=0;i<mass.size();i++)
        summa-=mass[i];  // тут модуль надо
    cout<<endl<<summa;
    system("pause");
 
}
вывод в файл не стал делать, прога выводит на экран ответы)))
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
04.12.2011, 01:07     Кладоискатели нашли некое количество золотых самородков... #6
Неправильная программа. Контпример:
Код
5
1 2 3 4 5
Выводит у вас:
Код
5 1 
2 3 4
3
Smillles7
25 / 25 / 1
Регистрация: 23.04.2011
Сообщений: 130
04.12.2011, 01:10     Кладоискатели нашли некое количество золотых самородков... #7
Цитата Сообщение от AncinetHero Посмотреть сообщение
Неправильная программа.
я же сказал что программа косячная) просто подправить чуток while надо
примерно так: 2 меняем на 1
C++
1
while(summa>=polovina+1 || summa<=polovina-1)
хотя все равно не для всех случаев будет работать)
chechen
Сообщений: n/a
04.12.2011, 01:33     Кладоискатели нашли некое количество золотых самородков... #8
Доброй ночи!

Я бы решал эту задачку таким способом, но т.к. в программировании пока не силен приведу по пунктам решение на словах:

1. Сложить все числа (вес самородков). (Получаем общую сумму _39.22_)
2. Разделить общую сумму на 2, необходимо получить при этом целое число (39.22 / 2 = _19_)
3. Вычислить остаток от деления (39.22 - (19 * 2) = _1.22_)
4. Сложить полученное число п.2 с п.3 (19 + 1.22 = _20.22_)
5. Отсортировать/упорядочить вес самородков в порядке убывания (15.2 12.3 7.12 2.3 2.3)
6. Отнимать из числа п.4 по очереди каждое число п.5 до тех пор, пока оно не будет меньше или равно 0 (если разность чисел будет число отрицательное, то данное число нам не подходит - переходим к следующему):
20.22 - 15.2 = 5.02 > 0
5.02 - 12.3 = -# < 0 //отрицательное число
5.02 - 7.12 = -# < 0 //отрицательное число
5.02 - 2.3 = 2.72 > 0
2.72 - 2.3 = 0.42 > 0
Дальше чисел больше нет, получается первая партия/куча самородков 15.2; 2.3; 2.3
оставшиеся числа будут принадлежать второй партии/куче


---
проверил на других примерах, вроде все подходит
старался объяснить доступно, извиняйте если это не вышло у меня
Smillles7
25 / 25 / 1
Регистрация: 23.04.2011
Сообщений: 130
04.12.2011, 01:50     Кладоискатели нашли некое количество золотых самородков... #9
Цитата Сообщение от chechen Посмотреть сообщение
Я бы решал эту задачку таким способом
Хороший алгоритм) но все равно будет не для всех случаев работать)
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
04.12.2011, 01:57     Кладоискатели нашли некое количество золотых самородков... #10
гуглить "balanced partition"
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
04.12.2011, 23:12     Кладоискатели нашли некое количество золотых самородков... #11
Спасибо, вроде бы вот процедура решения:
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
int BalancedPartition ( int a[] , int n ){
 
    int sum = 0;
    for( int i = 0 ; i < n ; i++)
        sum += a[i];
 
    int *s = new int[sum+1];
 
    s[0] = 1;
    for(int i = 1 ; i < sum+1 ; i++)    s[i] = 0;
 
    int diff = INT_MAX , ans;
 
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = sum ; j >= a[i] ; j--)
        {
            s[j] = s[j] | s[j-a[i]];
            if( s[j] == 1 )
            {
                if( diff > abs( sum/2 - j) )
                {
                    diff = abs( sum/2 - j );
                    ans = j;
                }
 
            }
        }
    }
    cout<< ans << " " << sum-ans<< endl; //two balanced partitions
 
    return min( ans , sum-ans );
}
Можно задать вопрос, что делает 18 строка?

Добавлено через 9 часов 36 минут
Кто то может помочь

Добавлено через 3 часа 55 минут
Пожалуйста, не заставляйте создавать новую тему
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2011, 00:17     Кладоискатели нашли некое количество золотых самородков...
Еще ссылки по теме:

C++ В конструкторе копирования отцовского (_str) класса возникает некое "необработанное исключение"
C++ Разбитие массива на некое количество подмассивов одинаковой длинны
C++ Построить шаблон класса - некое число

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

Или воспользуйтесь поиском по форуму:
Smillles7
25 / 25 / 1
Регистрация: 23.04.2011
Сообщений: 130
05.12.2011, 00:17     Кладоискатели нашли некое количество золотых самородков... #12
up)))
Yandex
Объявления
05.12.2011, 00:17     Кладоискатели нашли некое количество золотых самородков...
Ответ Создать тему
Опции темы

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