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

Организовать перебор всех возможных сочетаний - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Работа с матрицей. Сравнение строк и столбцов http://www.cyberforum.ru/cpp-beginners/thread1184087.html
Здравствуйте. Помогите пожалуйста реализовать сравнение каждой строки со всеми столбцами. Предположим есть матрица 3х3: 3 0 2 1 6 0 0 4 0 нужно сравнить количество нулей в строке с количеством нулей в столбце, т.е. 1 строку сравниваем с 1 столбцом, потом ее со вторым столбцом и т.д.
C++ Бинарный поиск для char Здравствуйте, сделал программу для поиска заглавных и строчных букв в вводимом с клавиатуры тексте. Ищет отлично и без проблем, но нужно сделать еще бинарный поиск. Вводимую строку сортирует, подскажите, как сделать теперь бинарный поиск? #include "stdafx.h" #include <iostream> #include <conio.h> #include <cctype> using namespace std; void bin_s(char* c) { http://www.cyberforum.ru/cpp-beginners/thread1184084.html
Вывести числа, которые почти равны друг другу (их разность меньше 0,01) C++
Здравствуйте. Занимаюсь С++ по книге Бьерна Страуструпа. Помогите решить задачу: Напишите программу, содержащую вектор и цикл while, которая выводит числа, которые почти равны друг другу(их разность меньше 0,01). При этом сначала следует вывести меньшее число, затем большее. Мой код: int main() { vector<double> numbers; double number; while(cin>>number)
Непонятная причина вылета программы C++
Добрый день, была поставлена задача написать программку, которая бы высчитывала кол-во повторений в массиве, а затем бы выводила минимальный и максимальный элемент массива, все требовалось реализовать используя ооп, т.е. с помощью классов, объектов и прочих приемов, собственно, не в этом суть вопроса. Вроде как все работает, но как-то через раз. Зависает либо после ввода элементов, либо уже...
C++ Прочитать файл scanf http://www.cyberforum.ru/cpp-beginners/thread1184043.html
Текстовый файл имеет следующее содержание: число, пробел, слово, пробел, число; и состоит из неизвестного кол-ва строк. Как прочитать файл и занести в структуру? struct Str { int Numb; char Name; int Time; }; int GetData() {
C++ Вывод символов в привычной форме При запуске программы в Dev c++ все символы отображаются не в виде русского или английского текста,а в виде непонятных символов( видимо стандартная кодировка в виндовс). Как сделать так,чтобы всё отображалось в виде естественного языка? подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
26.05.2014, 20:26     Организовать перебор всех возможных сочетаний
Сформулировал-таки доказательство:

Пусть R – оптимальное разбиение множества S на пары, т.е. пара его элементов (m, M) с максимальной суммой имеет минимально возможное значение этой суммы.
Добавим к R еще пару (n, N) элементов таких, что в отсортированном массиве значений элементов они стоят на концах.
Докажем, что новое разбиение R1, состоящее из R и пары (n, N), также является оптимальным.
а) Пусть n + N >= m + M. Докажем, что не существует разбиения, в котором максимальная сумма пары была бы меньше n + N.
Действительно, если такое разбиение существует, то в нем нет пары (n, N), т.е. элемент N там сочетается с неким элементом k. Но элемент n самый левый, следовательно n <= k и n + N <= k + N, т.е. максимальная сумма пары в этом разбиении не меньше n + N.
б) Пусть n + N < m + M. Докажем, что не существует разбиения, в котором максимальная сумма пары была бы меньше m + M.
Предположим, что такое разбиение существует.
1) Пусть в этом разбиении присутствует пара (n, N).
Тогда, удалив ее, мы получим разбиение множества S с максимальной сумой пары меньше, чем m + M, что противоречит условию.
2) Пусть в этом разбиении отсутствует пара (n, N).
Тогда элемент n сочетается с неким элементом B из множества S. Но элемент N самый правый, следовательно B <= N. Удалив из разбиения пару (n, B), мы получим разбиение R2 множества S, в котором элемент B заменен на не меньший элемент N, но при этом максимальная сумма пары (m1, M1) меньше, чем m + M. Заменим в разбиении R2 элемент N обратно на B. Мы получим разбиение множества S, в котором сумма каждой пары не больше m1 + M1, т.е. меньше m + M, что противоречит условию.
Из вышедоказанного следует, что разбиение множества значений на пары, элементы которых равноотстоят от концов отсортированного массива значений, является оптимальным.
 
Текущее время: 01:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru