Задача по программированию

СОДЕРЖАНИЕ  ДОКЛАДА: 

1.Условие задачи……………….…………………………………………………3

2.Анализ предметной области……………………………………………………4

3. Графическое представление алгоритма решения в виде блок-схем ...……...5

4. Словесный (пошаговый) алгоритм решения……………………….………...6

5.Программа на языке C++………….…………………………………………..  7 6.Тестовые примеры. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.Условие задачи:

     Есть  N карточек. На каждой из них черными чернилами написан ее уникальный номер — число от 1 до N. Также на каждой карточке красными чернилами написано еще одно целое число, лежащее в промежутке от 1 до N (некоторыми одинаковыми «красными» числами могут помечаться несколько карточек).

     Необходимо  выбрать из данных N карточек максимальное число карточек таким образом, чтобы множества «красных» и «черных» чисел на них совпадали.

ПРИМЕР

Допустим, N= 5, и  эти 5 карточек помечены «черными» числами 1,2,3,4,5 и, соответственно, «красными» числами 3,3,2,4,2. Тогда «правильными» будут карточки с «черными» номерами 2, 3, 4, поскольку множество «красных» номеров в данном примере именно такое — 2, 3,4. 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.Анализ  предметной области:

Граф – это  диаграмма, которая изображает все элементы множеств и связи между их элементами.

   Формально,  граф это совокупность множества  вершин и ребер -  связывающих  эти вершины.

 Часть графа  ,которая вместе с некоторым  подмножеством  ребер содержит  все инцедентные вершины называется  – подграфом.

       Подграф графа называется его сильносвязным компонентом, если каждая из вершин подграфа достижима от любой из вершин подграфа.

     Доминантное множество — это минимальное множество вершин графа, из которого достижимы все вершины графа. 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
 
 
 
 
 
 
 

4. Словесный (пошаговый) алгоритм  решения:

a[100] и b[100] – числовые массивы (в данном случае мы можем ввести до 100 элементов);

i и j – счетчики;

m – количество  красных карточек (вводит пользователь)

n – количество черных карточек (вводит пользователь)

for – оператор цикла

if – оператор ветвления 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5.Программа на языке C++:

#include<iostream.h>        // библиотека ввода вывода

#include<windows.h>      // библиотека для ввода русского текста

char newt[256];

char*rus(char*text)

{CharToOem(text,newt);

return newt;}

main(){

int a[100] ,b[100], i, j, n, m;     //объявление переменных

cout<<rus("Введите  количество черных карточек: ");

cin>>n;                      //ввод количества черных карточек

cout<<rus("Вводите  черные карточки: ");

for(i=0;i<n;i++)    //цикл который считает от одного до n

cin>>a[i];           //ввод номеров карточек

cout<<rus("Введите  количество красных карточек : ");

cin>>m;             //ввод количества красных карточек

cout<<rus("Вводите  красные карточки : ");

for(j=0;j<m;j++)   //цикл который считает от одного до m

cin>>b[j];             //ввод номеров карточек

cout<<rus("\nЭто  черные карточки:\n");

for(i=0;i<n;i++)

cout<<a[i]<<" ";    //вывод на экран черных карточек

cout<<rus("\nЭто  красные карточки:\n");

for(j=0;j<m;j++)

cout<<b[j]<<" ";        //вывод на экран красных карточек

cout<<endl;

cout<<rus("Подходящие  к условию карточки, имеют номера :");

for(i=0;i<n;i++)

for(j=0;j<m;j++)

if(a[i]==b[j])      //проверка на одинаковость

cout<<a[i]<<" "<<endl;    //вывод одинаковых номеров 

      return 0;}   
 
 
 
 
 
 
 
 
 
 
 
 
 
 

6.Тестовые  примеры.