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

найти в массиве наибольшее подмножество... - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ файлы и строки char http://www.cyberforum.ru/cpp-beginners/thread72391.html
помогите пожалуйста с задачами: 1. определить количество элементов в наиболее длинной возрастающей последовательности данного файла (алгоритм в принципе понятен, но вот как его реализовать не...
C++ Вычисление сумм и произведений народ помогите пожалуйста! С помощью оператора цикла for вычислить y. Оператор if в теле цикла не использовать. Значение m и n вводить с клавиатуры. Шаг изменения переменных i и j указывается... http://www.cyberforum.ru/cpp-beginners/thread72390.html
C++ Создание программы для напоминания ДР
Хотел бы попросить и от вас помощи,если вас это не затруднит.Дело в том,что мне на завтра срочно нужна программа для напоминания дней рождений,а написать я такую не могу так как я с txt не работал...
функции C++
Даны массивы H1, ... , H20 - шифры групп; K1, ... , K20 - количество студентов в каждой. Вывести список групп 1-го курса, в которых менее 20 студентов, и список групп 5-го курса, в которых менее...
C++ Типизация,ошибки в функции http://www.cyberforum.ru/cpp-beginners/thread72365.html
написал простую функцию,выполняющяя авторизацию...вот код char entering(char un,int pass,int vc){ srand(time(NULL)); char ok="Authorization successful"; char* name="admin"; int xpass=123;...
C++ Вычисление интеграла Пожалуйста помогите разобраться с программой http://dencom.nsknet.ru/_mod_files/ce_images/2009-12-09_172132.png подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2009, 18:50
Давайте тогда так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool prov_prost(int a, int b) // функция, которая определяет a и b взаимнопростые числа или нет? (если да то она возвращает true, если нет то false) 
{
        int temp;
        if(a>b)          // в этой и пяти нижеследующих строчках,из двух чисел a и b делаем сравнение и если нужно перестановку, так что бы a было меньше b
        { 
                temp=a;
                a=b;
                b=temp;
        }
        if(a==b) // если a и b равны, сразу возвращаемся из функции с результатом false (значит эти два числа не взаимопростые)
                return false;
        for(temp=2; temp<=a; temp++) // перебираем значение temp
                if(a%temp==0 && b%temp==0) // если в какой-то момент оказалось, что на одно и тоже число temp делятся без остатка и a и b, то возвращаем false (это значит что a и b не взаимопросты)
                        return false;
        return true; // если дошли до этой строки, значит a и b взаимопростые числа, поэтому возвращаем true
}
Теперь основная часть. Наверное проще будет объяснить сам алгоритм. Решение этой задачи вижу только в простом переборе набора из начальных чисел. Перебор сделан так. Создан массив temp[n] размерностью как и массив с числами, и изначально он заполняется единицами. Затем, как с двоичными числами, мы отнимаем всегда единицу. Т.е. элементы массива выглядят так:
1 1 1 1 1 1
0 1 1 1 1 1
1 0 1 1 1 1
0 0 1 1 1 1
1 1 0 1 1 1
и т.д. до (0 0 0 0 0 0)
Т.е. мы в данном массиве перебираем все комбинации единиц и нулей.
Эти комбинации мы используем для выбора самого большого подмножества элементов из массива mas[]. Например, при комбинации 1 0 0 1 1 1, мы проверяем на взаимопростоту числа массива mas[] с индексами 0, 3, 4, 5.
Если находим очередной набор, с большим кол-вом элементов (и в котором все элементы взаимопросты), чем встречались ранее, сохраняем этот набор в массиве itog[]
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru