Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Алгоритм по Дискретной математике!!!!!

17K
10 июня 2006 года
Alexandro_ST
7 / / 10.06.2006
Народ помогите написать два алгоритма:
1 алгоритм представляет собой операции с множествами.
Например на входе U(универс. мн-во) A и В множества. Нужно найти пересечение и объединение, и дополнения.
U: 1 2 3 4 5 6 7 8
А: 3 5 7 8
В: 1 5 8
причем пересечение нужно искать через дизъюнкцию, а объединение через конъюнкцию, а дополнения через отрицания.

2 алгоритм не рекурсивный алгоритм операции перестановок в лексикографическом порядке.

например множества 123 перестановка должна выглядеть след. образом

123
132
213
231
312
321

все это дело надо сделать на С++
242
10 июня 2006 года
Оlga
2.2K / / 04.02.2006
[quote=Alexandro_ST]2 алгоритм не рекурсивный алгоритм операции перестановок в лексикографическом порядке.
[/quote]
здесь на Паскале есть решение:
http://education.aspu.ru/page.php?id=151
13K
11 июня 2006 года
Dr_C++
40 / / 07.06.2006
1 алоритм...

- упорядочиваешь массивы А и В по возрастанию
- создаешь массивы для пересичения, обьединения и дополнения (размер сделай равный универсальному множеству, не ошибешся)
- поэлементно сравниваешь (два цикла Фор) массивы В и А (причем если элемент массива В, уже привышает элемент массива А, делай continue, так как массивы упорядочены)
- если элемент из массива В присутствует в массиве А, то помещай его в массив пересичения; в массив обьединения помещай сначала элемент из массива А, а потом, и элемент из массива В (если он отсутствует в массиве А)...

Что-то топа этого... Вот насчет дополнения, просто не помню что это такое... Память блин...
17K
11 июня 2006 года
Alexandro_ST
7 / / 10.06.2006
спасибо за исходник, но я в паскале не бум бум
17K
11 июня 2006 года
Alexandro_ST
7 / / 10.06.2006
[QUOTE=Dr_C++]1 алоритм...

- упорядочиваешь массивы А и В по возрастанию
- создаешь массивы для пересичения, обьединения и дополнения (размер сделай равный универсальному множеству, не ошибешся)
- поэлементно сравниваешь (два цикла Фор) массивы В и А (причем если элемент массива В, уже привышает элемент массива А, делай continue, так как массивы упорядочены)
- если элемент из массива В присутствует в массиве А, то помещай его в массив пересичения; в массив обьединения помещай сначала элемент из массива А, а потом, и элемент из массива В (если он отсутствует в массиве А)...

Что-то топа этого... Вот насчет дополнения, просто не помню что это такое... Память блин...[/QUOTE]


это мне все понятно, но дело в другом мне нужно представить в другом виде, например:
U: 1 2 3 4 5 6 7 будет представлять {1 1 1 1 1 1 1}
А: 2 4 6 7 будет представлять {0 1 0 1 0 1 1}
В: 4 6 будет представлять {0 0 0 1 0 1 0}
пересечение этих множеств (А и В) нужно найти с помощью конъюнкции &, тогда получим {0 0 0 1 0 1 0}
объединение с помощью дизъюнкции v {0 1 0 1 0 1 1}
дополнение А нужно представить через отрицание {1 0 1 0 1 0 0}
дополнение В также через отрицание {1 1 1 0 1 0 1}
и на экран программа должна выдавать следующие:
А персечение В: {0 0 0 1 0 1 0} 4 6
А объединение В {0 1 0 1 0 1 1} 2 4 6 7
Дополнение А {1 0 1 0 1 0 0} 1 3 5
Дополнение В {1 1 1 0 1 0 1} 1 2 3 5 7
242
11 июня 2006 года
Оlga
2.2K / / 04.02.2006
ну если я правильно поняла мы имеем: U, A, B и их размеры
arrU[N] = {1, 2 ,3 ,4 ,5, 6, 7} должны получить вспомагателный массив arrU_ [N] = {1, 1, 1, 1, 1, 1, 1}
arrA[N_A] = { 2, 4, 6, 7} => arrA_[N] = {0, 1, 0, 1, 0, 1, 1}
arrB[N_B] = {4, 6} => arrB_[N] = {0, 0, 0, 1, 0, 1, 0}

Код:
...................................
[FONT=Times New Roman][SIZE=3]int i,j;[/SIZE][/FONT]
[COLOR=seagreen]//заполня вспомагательный массив arrA_[/COLOR]
[FONT=Times New Roman][SIZE=3]for( i = 0; i < N; i++)[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]{[/SIZE][/FONT]
[SIZE=3][FONT=Times New Roman]for(j = 0; j < N_A; j++)[/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman]    if(arrU == arrA[j])[/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman]     {[/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman]           arrA_ = 1;[/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman]            break;[/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman]       }[/FONT][/SIZE]
[FONT=Times New Roman][SIZE=3]}[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3][COLOR=seagreen]//заполня вспомагательный массив arrB_[/COLOR]
[COLOR=#2e8b57]     ..................................[/COLOR]
 
[COLOR=#2e8b57]//объединяем множества A и B[/COLOR]
 
[COLOR=#2e8b57][COLOR=black]int *arrUnion = new[/COLOR] [/COLOR][COLOR=black]int[N_A+N_B];[/COLOR]
int j = 0;
[/SIZE][/FONT][FONT=Times New Roman][SIZE=3]for(i = 0; i < N; i++)[/SIZE][/FONT]
[SIZE=3][FONT=Times New Roman]if( arrA_ [COLOR=blue]||[/COLOR] arrB_ )  arrUnion[j++] = arrU;[/FONT][/SIZE]



это маленький набросок, если правильный доделать я думаю несложно
17K
12 июня 2006 года
Alexandro_ST
7 / / 10.06.2006
[quote=OlgaKr]ну если я правильно поняла мы имеем: U, A, B и их размеры
arrU[N] = {1, 2 ,3 ,4 ,5, 6, 7} должны получить вспомагателный массив arrU_ [N] = {1, 1, 1, 1, 1, 1, 1}
arrA[N_A] = { 2, 4, 6, 7} => arrA_[N] = {0, 1, 0, 1, 0, 1, 1}
arrB[N_B] = {4, 6} => arrB_[N] = {0, 0, 0, 1, 0, 1, 0}

.........................................

это маленький набросок, если правильный доделать я думаю несложно[/quote]


да вы всеправильно поняли, я был бы вам очень благодарен если вы помогли ее доделать до конца и предстваить полный алгоритм этой программы, просто у меня ничего не получается
242
12 июня 2006 года
Оlga
2.2K / / 04.02.2006
покажи что написал, если не секрет :)
вечером, после работы :), если что, поробую дописать
17K
12 июня 2006 года
Alexandro_ST
7 / / 10.06.2006
[QUOTE=OlgaKr]покажи что написал, если не секрет :)
вечером, после работы :), если что, поробую дописать[/QUOTE]

показать не получится, у меня его сейчас нет, дело в том что я не у себя дома
242
12 июня 2006 года
Оlga
2.2K / / 04.02.2006
ввод массивов от пользователя не писала:
Код:
#include <iostream>
 
using namespace std;

void initMaskArr(int *, int *, int , int *);
void printTotal(int *, int *, char *);
void unifyArrays(int *, int *, int *);
void intersection(int *, int *, int *);
void reverse(int *, int *);
 
#define N_U 7
#define N_A 4
#define N_B 2
 
int main()
{
 int U[] = {1,2,3,4,5,6,7};
 int mask_u[N_U] = {1};
 int A[] = {2,4,6,7};
 int B[] = {4,6};
 int mask_a[N_U] = {0}, mask_b[N_U] = {0};
 int arrUnion[N_U] = {0}, arrInter[N_U] = {0}, revA[N_U] = {0}, revB[N_U] = {0};
 
 initMaskArr(mask_a, A, N_A, U);
 initMaskArr(mask_b, B, N_B, U);
 
 unifyArrays(mask_a, mask_b, arrUnion);
 intersection(mask_a, mask_b,arrInter);
 reverse(mask_a, revA);
 reverse(mask_b, revB);
 
 printTotal(arrUnion, U, "Total of union is: ");
 printTotal(arrInter, U, "Total of intersection is: ");
 printTotal(revA, U, "Dopolnenie of A is: ");
 printTotal(revB, U, "Dopolnenie of B is: ");
 return 0;
}
void initMaskArr(int *mask, int *arr, int size_arr, int *arrU)
{
 for(int i = 0; i < size_arr; i++)
  for(int j = i; j < N_U; j++)
   if(arr == arrU[j])
   {
    mask[j] = 1;
    break;
   }
}
void printTotal(int *mask, int *arr_U, char *message)
{
 cout << message;
 for(int i = 0; i < N_U; i++)
  if( mask )
   cout << arr_U;
 cout << endl;
}
void unifyArrays(int *maskA, int *maskB, int *total)
{
 for(int i = 0; i < N_U; i++)
  if(maskA || maskB)
   total = 1;
}
void intersection(int *maskA, int *maskB, int *total)
{
 for(int i = 0; i < N_U; i++)
  if(maskA && maskB)
   total = 1;
}
void reverse(int *mask, int *total)
{
 for(int i = 0; i < N_U; i++)
  total = !mask;
}
17K
13 июня 2006 года
Alexandro_ST
7 / / 10.06.2006
[quote=OlgaKr]ввод массивов от пользователя не писала:
........................
[/quote]



Большое спасибо за алгоритм!!!!!!!
А вы не могли бы мне еще помочь по 2 алгоритму.
Здесь перестановка происходит в том случае елси числа введены по возрастанию и однозначные, а мне надо чтобы любые числа.


char temp;
cout<<"Vvedite elementy: \n";
cout<<"Kolichestvo chisel->";
cin>>n;
mass=new char[n];
get(mass,n);
put(mass,n);

do
{
flag=0;
//Находим самый правый элемент
for(int i=n-2;i>=0;i--)
if(mass<mass[i+1])
{
r=i;
break;
}

//Находим первый элемент после правого, такой, что он
//больше правого
for (int i=r+1;i<n;i++)
if(mass>mass[r])
{
l=i;
flag=1;
break;
}
if(flag)
{
//Находим минимальный элемент больше правого и правее правого
for(int i=l+1;i<n;i++)
if(mass[r]<mass && mass<mass[l])
l=i;
//Меняем их местами
swap(mass,r,l);
//Переворачиваем отрезок от правого элемента и до конца
replace(mass,n,r);
//Выписываем перестановку
put(mass,n);
}
}
while (flag);
getch();
242
13 июня 2006 года
Оlga
2.2K / / 04.02.2006
Цитата:
Здесь перестановка происходит в том случае елси числа введены по возрастанию


а что отсортировать введеные числа нельзя?

Цитата:
и однозначные, а мне надо чтобы любые числа.


может быть я неправа, но не заметила что бы
твоя функция была оринтирована на однозначные цифры
просто расспечатывать нужно разделяя элементы пробелом

17K
13 июня 2006 года
Alexandro_ST
7 / / 10.06.2006
[QUOTE=OlgaKr]а что отсортировать введеные числа нельзя?

может быть я неправа, но не заметила что бы
твоя функция была оринтирована на однозначные цифры
просто расспечатывать нужно разделяя элементы пробелом[/QUOTE]


Извините, а вы не могли бы мне сказать что это за операторы || && и как рабоатют эти условия:

for(int i = 0; i < N_U; i++)
if(maskA || maskB)
total = 1;


for(int i = 0; i < N_U; i++)
if(maskA && maskB)
total = 1;

for(int i = 0; i < N_U; i++)
total = !mask;
На сколько мне известно это логические оператор И ИЛИ? или я ошибаюсь?
1.8K
13 июня 2006 года
LastSoul
279 / / 28.12.2005
[QUOTE=Alexandro_ST]Извините, а вы не могли бы мне сказать что это за операторы || && и как рабоатют эти условия:
...
...
На сколько мне известно это логические оператор И ИЛИ? или я ошибаюсь?[/QUOTE]
Ты не ошибаешься!!!
|| - ИЛИ
&& - И
242
14 июня 2006 года
Оlga
2.2K / / 04.02.2006
[quote=Alexandro_ST]Извините, а вы не могли бы мне сказать что это за операторы || && и как рабоатют эти условия:

for(int i = 0; i < N_U; i++)
if(maskA || maskB)
total = 1;


for(int i = 0; i < N_U; i++)
if(maskA && maskB)
total = 1;

for(int i = 0; i < N_U; i++)
total = !mask;
На сколько мне известно это логические оператор И ИЛИ? или я ошибаюсь?[/quote]

|| - OR - логическое или
&& - AND - логическое И
! - NOT - отрицание
если хочешь ты можешь заменить логическии операции на поразрядные,
только тогда отрицание оформи следущим образом:
total = (~mask) & 1;, т.к.
 
Код:
~(0000 0001) == 1111 1110 != 0
~(0000 0000) == 1111 1111 != 1
 
(~(0000 0001)) & 1 == 0
(~(0000 0000) ) & 1 == 1




просто я решила что неправильно использовать поразрядные операции ( |, &, ~), но логические (||, &&, !)
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог