25.07.2017, 19:58 [+3 UTC]
в нашей команде: 2 069 чел. | участники онлайн: 1 (рекорд: 21)

:: РЕГИСТРАЦИЯ

:: консультации

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.41 (25.02.2017)

Общие новости:
23.02.2017, 09:51

Форум:
25.07.2017, 12:22

Последний вопрос:
25.07.2017, 13:46

Последний ответ:
25.07.2017, 16:54

Последняя рассылка:
25.07.2017, 16:15

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
06.04.2010, 20:15 »
Xrom1989
Verena, большое спасибо, особенно за вторую часть. Там все что мне надо для следующих задач=) [вопрос № 177620, ответ № 260643]
29.08.2010, 17:28 »
Сергей К.
Да, спасибо. Думаю это самое верное решение. [вопрос № 179803, ответ № 262914]
06.04.2010, 17:32 »
Anjali
Всё именно так и получилось! [вопрос № 177703, ответ № 260639]

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

Лучшие эксперты в этом разделе

Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 326
Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 140
mklokov
Статус: 6-й класс
Рейтинг: 106

Перейти к консультации №:
 

Консультация онлайн # 191078
Раздел: • С / С++
Автор вопроса: Iv (Посетитель)
Отправлена: 29.05.2017, 21:26
Поступило ответов: 0

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: . Помогите пожалуйста...буду очень благодарна!

И вот второе задание: КОМБИНАТОРНЫЕ АЛГОРИТМЫ

Задание. Написать программу, которая выполняет задание варианта с помощью гене-рации всех соответствующих комбинаций, используя комбинаторные алгоритмы.
Во время генерации производить подсчет общего числа сгенерированных вариантов и число вариантов, удовлетворяющих условию задачи, и вывести эти значения на эк-ран.

Методические указания к выполнению работы.

Рассмотрим различные типы вариантов заданий.
1. Разгадка числовых ребусов.
В числовых ребусах зашифровывают некоторое арифметическое действие, буквами обозначают цифры. Разным цифрам соответствуют разные буквы. Требуется разгадать, какая цифра скрывается за каждой буквой. Это возможно, если воспользоваться програм-мой генерации размещений без повторений.
Пример. ТОРГ ? Г = ГРОТ. Имеем 4 различных цифры: Т, О, Р, Г. Следовательно, необходимо сгенерировать 4-размещения из 10 (всего 10 цифр), т.е. массив а[1], … , а[4], удовлетворяющий следующим условиям:
1) а[1] ? 0, а[4] ? 0 – т.к. число не может начинаться с 0.
2) а[1]?1000 + а[2]?100 + а[3]?10 + а[4] = а[4]?1000 + а[3]?100 + а[2]?10 + а[1] – это за-пись зашифрованного действия.
В процессе генерации каждое полученное сочетание проверяют на выполнение перечисленных условий и отбирают подходящие. В общем случае решений может быть несколько. В данном примере ТОРГ = 1089 (1089?9 = 9801).
2. Генерация m-последовательностей 0 и 1.
Для решения можно использовать алгоритм генерации размещений с повторения-ми, где xi = 0 и yi = 1.
Однако если в условии задано ограничение на количество 0 или 1, то при таком подходе заведомо будут генерироваться лишние последовательности. В этом случае луч-ше использовать алгоритм генерации сочетаний без повторений для номеров мест, на ко-торые будут расставляться 0 или 1. При получении каждой сгенерированной комбинации номеров мест для 1 (0) в массиве С, нужно обнулить (заполнить 1) массив А требуемых m-последовательностей, а затем расставить в нём на места из массива С единицы (нули).
3. Вычисление кратного интеграла.
Для приближенного вычисления кратного интеграла использовать формулу левых, средних или правых прямоугольников
,
где , k – кратность интеграла, h – шаг разбиения (вводится с клавиатуры), а для формулы левых прямоугольников, для формулы средних прямоугольников и для формулы правых прямоугольников. Для решения используется алгоритм генерации размещений с повторениями для номеров интервалов по каждой переменной.
4. Раскрытие полиномиальной формулы.
Для раскрытия полиномиальной формулы используется алгоритм генерации раз-мещений с повторениями для получения степеней разложения, в котором для каждой сге-нерированной комбинации проверяется условие . На экран монитора выводится формула разложения полинома с использованием знака ^ для операции возведения в сте-пень.
5. Использование принципа включений и исключений.
Для вычисления по формуле включений и исключений генерируются сочетания без повторений для номеров проверяемых свойств. Для каждого числа свойств генерируются различные сочетания, а для каждой сгенерированной комбинации вычисляется (или извлекается) и суммируется количество элементов, удовлетворяющих соответствующему свойству или набору свойств, затем вычисление суммы добавляются в формулу включений и исключений с нужным знаком.
6. Решение задачи коммивояжера.
Используется алгоритм генерации перестановок без повторений, в котором для ка-ждой комбинации вычисляется суммарное расстояние, пройденное коммивояжером, и определяется минимальное из этих расстояний.
7. Генерация числовых комбинаций.
Для генерации используется алгоритм генерации размещений с повторениями или без повторений (в зависимости от условия варианта). Каждая сгенерированная комбина-ция должна проверяться на выполнение условия и выводиться при выполнении условия.
Если требуется исключить заданные p цифр из набора, то нужно определить кон-стантный массив из 10 – p элементов, не включающий эти цифры, и генерировать номера элементов в этом массиве, а выводить сами цифры.
Если требуется включить заданные p цифр в число выводимых, то нужно записать эти цифры в результирующий массив сочетаний на первые p мест, определить констант-ный массив из 10 – p элементов, не включающий эти цифры. Затем сгенерировать номе-ра для k - p элементов в этом массиве, записать цифры с этими номерами в массив сочета-ний на места с p+1-го по k-е.
8. Генерация различных слов из заданного набора букв.
Для генерации используется алгоритм генерации размещений с повторениями или без повторений (в зависимости от условия варианта). Каждая сгенерированная комбина-ция должна проверяться на выполнение условия и выводиться при выполнении условия.



Вопрос перенесен из раздела • Другие вопросы
--------

• Отредактировал: Гордиенко Андрей Владимирович (Модератор)
• Дата редактирования: 30.05.2017, 07:08

Состояние: Консультация закрыта

Oтветов пока не поступило.

Мини-форум консультации № 191078
Iv
Посетитель

ID: 401155

# 1

= общий = | 29.05.2017, 21:28 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер


Это ко второй задаче.

-----
 Прикрепленный файл (кликните по картинке для увеличения):

Гордиенко Андрей Владимирович
Модератор

ID: 17387

# 2

= общий = | 30.05.2017, 07:10 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Экспертам раздела:

Обратите, пожалуйста, внимание на данную консультацию, перенесённую из другого раздела.

=====
Facta loquuntur.

 

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.13216 сек.

© 2001-2017, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.41 от 25.02.2017
Бесплатные консультации онлайн