Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
zago-vlad
13 / 8 / 1
Регистрация: 12.01.2010
Сообщений: 106
1

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

03.12.2011, 15:58. Просмотров 1007. Ответов 11
Метки нет (Все метки)

Всем привет!

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

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

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

Входящие данные. Файл 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


Заранее ОГРОМНОЕ спасибо!

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

0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2011, 15:58
Ответы с готовыми решениями:

Разбитие массива на некое количество подмассивов одинаковой длинны
Здравствуйте. Для решения моей основной задачи требуется разбитие массива на...

Определить фальшивую монету за заданое число взвешиваний среди указанного количества золотых монет
Есть 25 золотых монет. Одна из них фальшивая и она по весу меньше. Определить...

Построить шаблон класса - некое число
Построить шаблон класса - "некое" число. Объявить переменную типа класс....

так и не нашли ошибку, циклы и условия
Программа должна проверить введенную строчку на соответствие слову как...

Найдите максимальный вес золота, который можно унести в рюкзаке вместительностью S, если есть N золотых слитко
Найдите максимальный вес золота, который можно унести в рюкзаке...

11
Smillles7
25 / 25 / 4
Регистрация: 23.04.2011
Сообщений: 130
03.12.2011, 16:17 2
на первый взгляд вроде ничего сложного)
думаю сортировать по весу надо таким образом:
находишь максимальный элемент и проверяешь while - ом, как близок он по весу к половине, если не близко, постепенно прибавляешь наименьшие по весу самородки)

Добавлено через 34 секунды
хотя скорей всего не точно получиться)
1
AncinetHero
49 / 49 / 12
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 16:22 3
Тут динамика...
0
zago-vlad
13 / 8 / 1
Регистрация: 12.01.2010
Сообщений: 106
03.12.2011, 16:49  [ТС] 4
Smillles7, выложи, плиз, пример кода.
0
Smillles7
25 / 25 / 4
Регистрация: 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");
 
}
вывод в файл не стал делать, прога выводит на экран ответы)))
1
AncinetHero
49 / 49 / 12
Регистрация: 22.05.2011
Сообщений: 326
04.12.2011, 01:07 6
Неправильная программа. Контпример:
Код
5
1 2 3 4 5
Выводит у вас:
Код
5 1 
2 3 4
3
0
Smillles7
25 / 25 / 4
Регистрация: 23.04.2011
Сообщений: 130
04.12.2011, 01:10 7
Цитата Сообщение от AncinetHero Посмотреть сообщение
Неправильная программа.
я же сказал что программа косячная) просто подправить чуток while надо
примерно так: 2 меняем на 1
C++
1
while(summa>=polovina+1 || summa<=polovina-1)
хотя все равно не для всех случаев будет работать)
0
chechen
0 / 0 / 0
Регистрация: 23.08.2016
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
оставшиеся числа будут принадлежать второй партии/куче


---
проверил на других примерах, вроде все подходит
старался объяснить доступно, извиняйте если это не вышло у меня
0
Smillles7
25 / 25 / 4
Регистрация: 23.04.2011
Сообщений: 130
04.12.2011, 01:50 9
Цитата Сообщение от chechen Посмотреть сообщение
Я бы решал эту задачку таким способом
Хороший алгоритм) но все равно будет не для всех случаев работать)
0
Net_Wanderer
235 / 208 / 29
Регистрация: 08.06.2011
Сообщений: 467
04.12.2011, 01:57 10
гуглить "balanced partition"
1
AncinetHero
49 / 49 / 12
Регистрация: 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 минут
Пожалуйста, не заставляйте создавать новую тему
1
Smillles7
25 / 25 / 4
Регистрация: 23.04.2011
Сообщений: 130
05.12.2011, 00:17 12
up)))
0
05.12.2011, 00:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2011, 00:17

N пиратов (n<10)нашли клад,состоящий из золотых монет.
N пиратов (n&lt;10)нашли клад,состоящий из золотых монет.один из них взял себе...

В кучке лежит Р золотых самородков с известным весом. Нужно разделить самородки на две кучки, наиболее близкими за весом
В кучке лежит Р золотых самородков с известным весом. Нужно разделить самородки...

Получить наибольшее количество золотых монет
по теме «Длинная арифметика» Золото племени АББА Главный вождь племени Абба...


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

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

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