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

Разбиения множества - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Как данную программу реализовать при помощи классов http://www.cyberforum.ru/cpp-beginners/thread578982.html
как данную программу реализовать при помощи классов ~cpp //--------------------------------------------------------------------------- #include <vcl.h> #include <iostream.h> #pragma hdrstop
C++ Найти номер максимального элемента массива Помогите с программами 1. Найти номер максимального элемента массива. 2. Найти произведение элементов массива, расположенных между первым и вторым нулевыми элементами. 3. для заданной матрице размера 8 на 8 найти такие k, что к-я строка матрице совпадает с к-м столбцом. 4. Напишите программу которая считывает текст из файла и определяет сколько в этом слове. состоявших из не более чем 4-х... http://www.cyberforum.ru/cpp-beginners/thread578972.html
C++ Написать функцию, которая возвращает максимальный элемент одномерного массива
Написать функцию, которая возвращает максимальный элемент одномерного массива
C++ структуры содержащие члены-данные и члены- функции
Помогите пожалуйста!!!:cry: На основе данного входного файла составить список сотрудников учреждения, включив следующие данные: ФИО, год принятия на работу, должность, зарплата, рабочий стаж. Вывести в новый файл список сотрудников учреждения, удалив из него информацию о сотрудниках, принятых на работу в текущем году.
C++ Структуры http://www.cyberforum.ru/cpp-beginners/thread578955.html
Помогите решить задачу (решить задачу, используя структуру point для хранения координат точки: (множество точек задано на плоскости) Найти такую точку, что окружность радиуса R с центром в этой точке содержит минимальное число точек заданного множества.
C++ Работа с текстовыми файлами: Помогите пожалуйста решить задачу Дан текстовый файл. Напечатать все нечётные строки. подробнее

Показать сообщение отдельно
UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
19.05.2012, 21:57     Разбиения множества
Рекурсивная функция -- функция, вызывающая саму себя. Как это в данном случае работает:
мы перебираем по очереди точки (т.е. выбираем 1 точку), а потом сводим задачу к предидущей -- теперь нам нужно выбрать m-1 точку из принципиально возможных n-1. Когда мы выбрали все нужные нам m точек (условие m1==m, это т.н. "выход из рекурсии"), мы уже получили разбиение -- одна группа точек -- те точки, чьи номера входят в массив num, вторая -- те, чьи номера туда не входят.
Есть 2 тонких момента во всем этом. Во первых, нам нету смысла расматривать такие разбиения, которые отличаются только порядком выбора точек (например разбиение с выбраным на первом шаге номером 1, на втором -- 2, на третьем -- 3, и разбиение с выбраным на первом шаге номером 2, на втором -- 3, и на третьем -- 1 для нас одинаковы (разбиения [1;2;3] и [2;3;1])). Потому имеет смысл каждую точку выбирать не из всех еще не вошедших в наш массив, а из тех, у которых номер больше номера последней точки. Таким образом, массив num получается отсортированным по нарастанию. Также очевидно, что если нам нужно выбрать 3 точки из 10, то выбрав на первом шаге точку №9 мы уже никак не сможем выбрать еще 2 точки с большими номерами, потому мы выбираем точки не от последней выбраной до последней вообще, а от последней выбраной до n-m+m1+1. И еще 1 момент, нам надо как-то начать этот рекурсивный процесс. За начало отвечает условие if(m1==0) и то, что там внутри. Кстати, я придумал лучший способ использования памяти, для этого в функции grouping:
--Убираем строки 7,10,22-24,27
--В строках 8,9,25,26 меняем num1 на num.
В вызове из основной программы:
-- в четвертой строке 1 меняем на i.
И алгоритм будет жрать память как корень квадратный из того, что жрал раньше
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru