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

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

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

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

25.12.2009, 23:15. Просмотров 1552. Ответов 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++
Полный разбор JPEG в С++ 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     Полный перебор
Ответ Создать тему
Опции темы

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