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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Kissa30rus
 Аватар для Kissa30rus
0 / 0 / 0
Регистрация: 25.12.2009
Сообщений: 5
25.12.2009, 23:15     Полный перебор #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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.12.2009, 23:15     Полный перебор
Посмотрите здесь:

Полный дек C++
Учебник по C++ полный. C++
Перебор C++
Полный перебор C++
Полный перебор чисел массива C++
Методы поиска: полный перебор и интерполяционный C++
C++ Все возможные комбинации пароля. Метод грубой силы(полный перебор)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kissa30rus
 Аватар для 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

Помогите скорректировать код.
Yandex
Объявления
10.01.2010, 15:50     Полный перебор
Ответ Создать тему
Опции темы

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