0 / 0 / 1
Регистрация: 25.12.2009
Сообщений: 5
1

Полный перебор

25.12.2009, 23:15. Показов 3326. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.12.2009, 23:15
Ответы с готовыми решениями:

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

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

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

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

1
0 / 0 / 1
Регистрация: 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.01.2010, 15:50

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

Полный перебор и сокращенный перебор, путем исключения одного цикла
1) Разработать на основе метода полного перебора программу razmen1 для решения задачи о способах...

Полный перебор
Всем привет. Когда у нас есть фиксированное количество переменных и для них есть фиксированная...

Полный перебор
Добрый день. Возникла такая ситуация. Есть множество Х(други орграфа) и множество W(числа) и...


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

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

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