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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Kissa30rus
0 / 0 / 0
Регистрация: 25.12.2009
Сообщений: 5
#1

Полный перебор - C++

25.12.2009, 23:15. Просмотров 1641. Ответов 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//////////////////////////////////////////////////////////////////////
//Лабораторная работа №5;
//Дано множество целых чисел. Требуется разбить множество на две 
//части суммы элементов которых равны. Если нельзя провести разбиение,
//выдать сообщение об этом.
//////////////////////////////////////////////////////////////////////
#include <fstream>
#include <iostream>
// Множество
#include <set>
#include <numeric>
 
using namespace std;
 
//Показывает какие элементы входят в текущую сумму
unsigned char *schetchik;
int kakoi;
 
// Добавляет элемент если в schetchik на месте kakoi стоит 1
int sum(int summa, int chislo)
{
    return schetchik[kakoi++] == 1 ? summa + chislo : summa;
}
 
int main()
{
    set<int,less<int>> mnogestvo;
    ifstream fin("input.txt");
    int n, i, temp, m;
    __int64 chto_nado;
    
    // Количество элементов и какое число надо попробовать получить
    fin >> n;
    fin >> chto_nado;
 
    // Создаем множество и заполняем его
    for (i = 0; i < n; ++i)
    {
        fin >> temp;
        mnogestvo.insert(temp);
    }
 
    m = mnogestvo.size();
    // Создаем счетчик для двоичного перебора и обнуляем его
    schetchik = new unsigned char [m];
    memset(schetchik,0,m);
 
    // Выход будет при обнаружении переполнения счетчика
    while(1)
    {
        ++schetchik[m-1];
        
        // Следит за правильностью двоичног числа
        for (i = m-1; i > 0; --i)
        {
            if (schetchik[i] == 2)
            {
                schetchik[i] = 0;
                ++schetchik[i-1];
            }
            else
            {
                break;
            }
        }
 
        // Перед началом высчета новой сумму, начинаем суммировать то с нулевого элемента
        kakoi = 0;
 
        // Если можно то все
        if (accumulate(mnogestvo.begin(),mnogestvo.end(),0,sum) == chto_nado)
        {
            cout << "Mozno!";
            cout<<endl;
            cout<<"Najmite 0 dlya vixoda...";
            delete [] schetchik;
            cin >> i;
 
            return 0;
        }
 
        if (schetchik[0] == 2)
        {
            break;
        }
    }
    
    delete [] schetchik;
 
    cout << "Nelza!";
    cout<<endl;
    cout<<"Najmite 0 dlya vixoda...";
    cin >> i;
 
    return 1;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.12.2009, 23:15
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Полный перебор (C++):

Полный перебор - C++
Здравствуйте. Скорее всего, я пришел не по адресу и мне следовало бы задать свой вопрос где-нибудь в разделе алгоритмов, но не суть. Я всё...

Полный перебор чисел массива - C++
Доброго вам времени суток. Количество элементов массива задавать вручную - собственно N. Массив заполняется числами от 1 до N. Стоит...

Методы поиска: полный перебор и интерполяционный - C++
Найти самолет, вылетающий в 1400. Методы поиска: полный перебор и интерполяционный. как это в массиве записать?

Все возможные комбинации пароля. Метод грубой силы (полный перебор) - C++
Вопрос собственно заключается в том, почему при выводе в консоль всех возможных комбинаций пароля, пишет непонятные символы,как показано на...

Полный дек - C++
Добрый день! мучаюсь с задачей - реализовать тип и функции (инициализация,добавление\извлечение элементов с обеих сторон,проверка на...

Учебник по C++ полный. - C++
Где взять такой учебник где все рассказывается о языке от а до я???

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kissa30rus
0 / 0 / 0
Регистрация: 25.12.2009
Сообщений: 5
10.01.2010, 15:50  [ТС] #2
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <fstream>
using namespace std;
void Razb (int *Mas, int N, int k);
int Sloghenie(int *Mas1, int N);
int main()
{
    setlocale (LC_ALL, "Russian");
    ifstream fin("input.txt");
    int N;
    fin>>N;
    int *Mas = new int [N];
    
    int sum;
    sum = 0;
    for  (int i = 0; i<N; i++)
    {
        fin>>Mas[i];
        sum =sum + Mas[i];
    }
    int k = sum/2;
    int b = sum%2;
    if (b == 0)
    {
        Razb (Mas, N, k);
    }
    else
    {
        cout<<"Невозможно."<<endl;
    }
    system ("pause");
    return 0;
}
int Sloghenie(int *Mas1, int N)
{
    int temp = N-1;
    Mas1[temp]++;
    while (temp>0)
    {
        if (Mas1[temp]>1)
        {
            Mas1[temp] = 0;
            Mas1[temp-1]++;
            temp--;
        }   
        else
            break;
    }
    int l=1;
    for (int i=0;i<N;i++)
        if (!Mas1[i])
            l = 0;
    if (l) 
        return 1;
    return 0;
}
 
void Razb (int *Mas, int N, int k)
{
    int *Mas1 = new int[N];
    int summa(0);
    int i(0);
    for (int i=0; i<N; i++)
    {
        Mas1[i] = 0;
    }
    
    do 
    {
        for (int i=0;i<N;i++)
        {
            cout<<Mas1[i]<<' ';
        }
        cout<<endl;
    }
    while (!Sloghenie(Mas1, N));
    cout<<"****************************************"<<endl;
    while (i<N)
    {
        if (Mas1[i] == 1)
        {
            cout<<Mas[i]<<endl;
            summa = summa + Mas[i];
        }
        if (summa == k)
            cout<<"Сумма: "<<summa<<endl;
        i++;
    }
}
Добавлено через 1 минуту
в инпуте писать:
количество элементов: 6
сами элементы: 1 1 1 1 1 1

Не выводит сумму для 4 8 4

Помогите скорректировать код.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2010, 15:50
Привет! Вот еще темы с ответами:

Полный учебник с++ - C++
Доброго времени суток!!! Ситуация такая: изучил основы c++, хочу изучить ПОЛНОСТЬЮ его. Подскажите, пожалуйста, учебник на русском,...

Перебор - C++
Ребят, помогите решить две задачи. Занимаюсь программированием уже 6 лет. Но тут в ступор встал. 1 задача: есть массив. из него нужно...

Перебор - C++
Hi.мне нужно часть кода в котором перебирает все значение пример у нас 2 банки(на много литров),и 10 л воды.Нужно сделать все возможние...

Полный разбор JPEG в С++ - C++
Товарищи!!!! Огромная проблема по учебе, требуется ваша помощь, весь инет уже перелазил Необходимо открыть JPEG файл в С++, но просто...


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

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

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