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

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

Войти
Регистрация
Восстановить пароль
 
Jane_S
Сообщений: n/a
#1

Метод пузырька - C++

11.12.2012, 14:04. Просмотров 789. Ответов 1
Метки нет (Все метки)

Дано n (n<=32000) натуральных чисел xi, (xi<m). Необходимо
установить, можно ли разбить их на пары таким образом, чтобы сумма
чисел в каждой паре не превышала m (m<=100). Файл input.txt
организован следующим образом: в первой строке через пробел записаны
число n, затем m, далее следуют n строк, по одному числу в каждой. В
файл output.txt необходимо вывести «YES», если данный набор можно
разбить на пары указанным образом, «NO» в противном случае.
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2012, 14:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Метод пузырька (C++):

Метод пузырька и метод слияния - C++
Сгенерировать одномерный массив из N случайных чисел xi ∈. Отсортировать массив методом пузырька и методом слияния. Подсчитать число...

Метод пузырька - C++
Здравствуйте. Как сделать сортировку по методу пузырька с максимального значения и далее? Т.е. 6 3 9 7 2 4 5 6 -&gt; 6 3 9 2 4 5 6 7. Я...

метод пузырька - C++
не работает, выдает ошибку при запуске. Undefined symbol _main in module c0.ASM подскажите пожалуйста как исправить? #include...

метод пузырька - C++
Боже, я не понимаю как ввести этот дурацкий ввод для пользователя, чтобы при попытке ввести убывающую последовательность выводилось на...

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

Метод пузырька - C++
реализовать на языке С++ сортировку одномерного массива методом «пузырька», методом вставки, методом выбора.

1
BRcr
4008 / 2297 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
12.12.2012, 19:07 #2
На вскидку, наиболее эффективно замещать меньшее(или большее, зависит от направления, по которому мы будем просматривать сортированный массив) значение из каждой найденной пары волшебным числом -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
// ---------------------------------------------------------------------------
typedef vector <long> values;
 
// ---------------------------------------------------------------------------
short check_pairs( values &v, long n, long m, ofstream &file ) {
    if ( n % 2 ) {
        cout << "there should be en even amount of elements to break them in pairs";
        return 0;
    }
    if ( accumulate( v.begin( ), v.end( ), ( long long )0 ) > ( m - 1 ) * n / 2 ) {
        cout << "summ of elements is greater than half of greatest possible summ, breaking in pairs impossible";
        return 0;
    }
    sort( v.begin( ), v.end( ) );
    file << "pairs:\n\n";
    for ( size_t i = n, k, last; --i > 0; ) {
        if ( v[i] == -1 ) {
            continue;
        }
        for ( k = 0, last = -1; ; ++k ) {
            if ( k < i && v[k] == -1 ) {
                continue;
            }
            if ( k == i || ( v[i] + v[k] > m ) ) {
                if ( last == -1 ) {
                    return 0;
                }
                else {
                    file << "№" << i << " = " << v[i] << "\t\t" << "№" << last << " = " << v[last] << endl;
                    v[last] = -1;
                    break;
                }
            }
            last = k;
        }
    }
    return 1;
}
// ---------------------------------------------------------------------------
int _tmain( int argc, _TCHAR *argv[] ) {
    system( "chcp 1251" );
    system( "cls" );
    //////////////////////////////////////
    long n = 32000, m = 100;
    values v;
 
    ofstream out( "input.txt" );
    out << n << " " << m << endl;
    srand( time( NULL ) );
    for ( long i = 0; ++i <= n; out << rand( ) % ( m - 1 ) << endl );
    out.close( );
 
    ifstream in( "input.txt" );
    in >> n >> m;
    for ( long i = 0, tmp; ++i <= n; in >> tmp, v.push_back( tmp ) );
    in.close( );
 
    out.open( "out.txt" );
    if ( check_pairs( v, n, m, out ) ) {
        out << "\n\nyes";
    }
    else {
        out << "\n\nno";
    }
    out.close( );
 
    //////////////////////////////////////
    cout << "\n\n";
    system( "pause" );
    return 0;
}
// ---------------------------------------------------------------------------
Пусть вид функции main тебя не смущает тебя, зависит от компилятора. Тебе, вероятнее всего, больше подойдет int main()

Добавлено через 5 часов 28 минут
Хотя, нее - ничуть не сложней индексы запоминать, туплю потихоньку...
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2012, 19:07
Привет! Вот еще темы с ответами:

Матрица, метод пузырька - C++
Доброе время суток всем. Задали сделать данную задачку. Дана матрица, j-столбцы, i-элементы. Вывести первоначальную, затем вторую для...

Обратный метод пузырька - C++
Написать программу сортировки массива по возрастанию методом &quot;погружения &quot; наибольшего (&quot;тяжелого&quot;) элемента(метод пузырька в обратную...

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

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


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

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

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