Вопрос № 145495: Здравствуйте уважаемые эксперты. На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Разработать и реализовать алгоритм, определяющий, можно ли опосредованно перезнакомить их всех между собой (если незнакомые люди могут познаком...Вопрос № 145554: Здравствуйте уважаемые эксперты! Помогите, пожалуйста, с реализацией такой программы. Я хочу написать программу, которая выполняет определенные операции при
нажатии на определенные клавиши клавиатуры. Какие функции в C++ отвечают за восприятие нажати...Вопрос № 145580: Доброй ночи, уважаемые эксперты. Прошу оказать помощь в написании следующей программы: программа должна текстовый файл произвольной длины и определять частоту появления каждой буквы. При этом файл файл на английском языке и его имя нужно запрашивать....
Вопрос № 145.495
Здравствуйте уважаемые эксперты. На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Разработать и реализовать алгоритм, определяющий, можно ли опосредованно перезнакомить их всех между собой (если незнакомые люди могут познакомиться только через общего знакомого). Результат отобразить в виде графа. Заранее спасибо.
Отвечает: Lang21
Здравствуйте, Надежда Витальевна!
Сформулируем условия задачи в терминах теории графов. Пусть каждому участнику соответствует вершина графа. Тогда тот факт, что два участника знакомы между собой представим в виде ребра, соединяющего соотвествующие им вершины. Возможность опосредованно познакомить двух участников означает, что в графе существует путь между соответствующими вершинами. Возможность познакомить всех участников означает существование пути между любыми двумя вершинами графа. Такие графы называются
связными. Если граф несвязен, в нем всегда можно выделить связные части. Такие части называются компонентами связности.
Чтобы узнать, связен ли граф, можно использовать следующий рекурсивный алгоритм. Выберем произвольную вершину в графе и пометим её. Будем выбирать последовательно соседние с ней непомеченные вершины, применяя к каждой из них ту же самую процедуру. Выход из процедуры будем производить при условии, что вершина уже помечена.
Если в резул
ьтате все вершины графа окажутся помеченными, значит граф связен, (имеет одну компоненту связности). Чтобы определить число компонент связности, достаточно выбрать любую из непомеченных вершин, и повторить описанные выше действия.
Программа в приложениии генерирует случайный граф, который представляется с помощью списков смежности (то есть, для каждой из вершин указываются её соседи). Вершины гграфа нумеруются целыми числами, начиная с нуля. Количество вершин графа (vertices) выбирает пользователь.
Также можно выбрать среднюю степень вершин графа (mean degree) - то есть среднее число соседей. После генерации графа его вершины маркируются так, что одинаковые цифры соответствуют вершинам, принадлежащим одной компонене связности. Результат выводится на экран в виде: номер вершины/ номер компоненты связности : список смежных вершин. Если компонента связности одна, всех участников можно опосредованно познакомить друг с другом.
Приложение:
Ответ отправил: Lang21 (статус: Студент)
Ответ отправлен: 02.10.2008, 18:24 Оценка за ответ: 5
Вопрос № 145.554
Здравствуйте уважаемые эксперты! Помогите, пожалуйста, с реализацией такой программы. Я хочу написать программу, которая выполняет определенные операции при нажатии на определенные клавиши клавиатуры. Какие функции в C++ отвечают за восприятие нажатия определенной клавиши? Заранее спасибо!
Отвечает: CruelHity
Здравствуйте, Budagov David! самое просто это использовать функцию getch(); ее описания: int _getch( void ); возращает код нажатого символа
Приложение:
Ответ отправил: CruelHity (статус: 7-ой класс)
Ответ отправлен: 01.10.2008, 00:38 Оценка за ответ: 5
Вопрос № 145.580
Доброй ночи, уважаемые эксперты. Прошу оказать помощь в написании следующей программы: программа должна текстовый файл произвольной длины и определять частоту появления каждой буквы. При этом файл файл на английском языке и его имя нужно запрашивать. Этот файл можно читать либо построчно (по файлам в текстовом режиме), либо как двоичный с промежуточным небольшим буфером некой фиксированной длины.
Отправлен: 01.10.2008, 00:15
Вопрос задал: Xrom1989 (статус: Посетитель)
Всего ответов: 2 Мини-форум вопроса >>> (сообщений: 2)
Отвечает: Sk0rp
Здравствуйте, Xrom1989! Сначала считаем сколько штук каждой буквы, потом делим на общее количество. Реализация в приложении.
Приложение:
Ответ отправил: Sk0rp (статус: 5-ый класс)
Ответ отправлен: 01.10.2008, 01:14 Оценка за ответ: 4 Комментарий оценки: Большое спасибо за оказанную помощь. Ответом удовлетворен. Даны нужные коментарии и пояснения, что немаловажно для новичков в работе с языком С.
Отвечает: realbustard
Здравствуйте, Xrom1989! Программа просит ввести имя файла. Текстовый файл должен находиться в той же папке, что и ехе-шник. Затем считывает символы из файла и заносит их в ассоциативный массив. Компилировано в MS Visual Studio 2005.
Приложение:
--------- Учись так, как-будто собираешься жить вечно; живи так, как-будто завтра умрешь (Отто фон Бисмарк)
Ответ отправил: realbustard (статус: 3-ий класс)
Ответ отправлен: 04.10.2008, 16:56 Оценка за ответ: 5 Комментарий оценки: Огромное спасибо за ответ. Данным решение очень доволен. Особенно хотелось бы отметить пояснения которые вы даете к каждому шагу программы. Это очень помогает понять как данная программа работает.