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

динамическое программирование - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ анимация в С++ http://www.cyberforum.ru/cpp-beginners/thread360134.html
как заставить шарик вращаться?
C++ Функция гипотенуза Выдаёт значения но какие то не правильные например если ввести 2 и 2 то должно быть 8, а выдаёт 84 Что не так ? #include "stdafx.h" #include<iostream> #include <math.h> #include<cmath> using namespace std; double sum; double hypotenuse( double s1, double s2 ) { http://www.cyberforum.ru/cpp-beginners/thread360123.html
Просьба помочь реализовать класс. C++
Картка персони містить прізвище й дату народження. Реалізувати клас ListPerson для роботи з картотекою персоналій. Клас повинен містити масив карток персон. Реалізувати методи додавання й видалення карток персон, атакож метод доступу до картки на прізвище. Прізвища в масиві повинні бути унікальні. Реалізувати операції об'єжнання двох картотек, операцію перетинання й обчислення різниці. - Усі...
C++ Задача на методы половинного деления
Ребята помогите пожалуйста внести в систему метода половинного деления вот эту функцию: 4(Sin^4)x+2(Cos^3)x+7=0 #include <conio.h> #include <math.h> #include <iostream.h> #define pi 3.14 double f(double x) { return x*x-(cos(pi*x)); } main()
C++ case-switch http://www.cyberforum.ru/cpp-beginners/thread360107.html
Вот то задание что с case-switch надо сделать помогите знаю что задание дурное
C++ Поиск структур по условию Известны максимальные скорости 20 моделей легковых автомобилей. Марки моделей записаны в отдельном текстовом файле. Напечатать названия моделей, у которых максимальная скорость больше 180 км/ч. Вот попробовал.. но почему-то ругается! #include <iostream.h> #include <string.h> #include <conio.h> #include <stdio.h> #include <math.h> подробнее

Показать сообщение отдельно
renej
0 / 0 / 0
Регистрация: 05.10.2011
Сообщений: 3
05.10.2011, 17:13     динамическое программирование
Цитата Сообщение от x1Mike7x Посмотреть сообщение
Это не динамическое программирование.
Представьте, что каждый первокурсник представлен вершиной графа, а наличие прямых дружеских отношений ( то есть непосредственно один знает второго лично ) обозначается ребром.
Для решения задачи нам нужно найти количество компонентов связности, а точнее при 1й компоненте - все друзья, при 2х или больше - не все друзья =).

Что нужно для решения:
* вектор ребер ( при этом не забываем, что граф неориентированный, т.е. необходимо ставить ребро и от i -> j, и от j -> i )
* булевый массив на N элементов, который будет показывать, или мы проверили i-ого первокурсника, изначально заполненного "false"

Теперь просто ищем по следующему алгоритму:
1. Выбираем любую вершину.
2. Пускаем из неё поиск в глубину ( изменяя массив булевого типа - ставим "true" для тех вершин, в которых мы побывали ). При этом функцию поиска вызываем только 1 раз в теле main'а.
3. Просто идём по массиву булевого типа - если хотя бы раз встретили "false" ( т.е. вершину (первокурсника), с которой никто не дружит из найденного круга друзей ), то выводим, что есть незнакомцы среди перваков; если же все элементы массива являются истинной, то выводим, что да, все друзья.
Вы не могли бы примерно набросать код на с++? Для тех, кто с графами никогда вообще не работал.
 
Текущее время: 05:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru