Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.90/40: Рейтинг темы: голосов - 40, средняя оценка - 4.90
0 / 0 / 0
Регистрация: 19.04.2015
Сообщений: 13
1

Проверка булевой функции на монотонность

19.04.2015, 17:52. Показов 7896. Ответов 9
Метки нет (Все метки)

Надо проверить является ли булева функция монотонной.
Она задается вектором своих значений
Как проверить на монотонность? (т.е. "неубываемость"?)
К примеру:
Входные данные:
11011110
Исходные данные:
Сообщение о монотонность либо не монотонность
0 / 1

У меня не работает с монотонными функциями
Проверка булевой функции на монотонность


И еще вопрос, как сделать так, чтобы я вводил произвольный вектор? В независимости к "n"
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.04.2015, 17:52
Ответы с готовыми решениями:

Проверка булевой функции на монотонность.
Булева ф-я задана вектором своих значений (битвектором длины 2^(число аргументов ф-и)). Они идут...

Проверка функции на монотонность
Доброго времени суток. Мне нужно срочно решить следующую задачу для друга разгильдяя :...

Монотонность функции
выяснить есть ли булевая функция монотонной !

Булевы функции. Монотонность
Задание 1. У меня такая же функция как и там, только x с инверсией.

9
0 / 0 / 0
Регистрация: 19.04.2015
Сообщений: 13
20.04.2015, 12:13  [ТС] 2
Вот мой код программы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
using namespace std;
#define n 8
bool is_monotonic(const vector<bool>& vec)
{
    size_t shift = vec.size();
    if ((shift - 1) & shift) {
        // vector size is NOT a power of 2, bailing out
        return false;
    }
    while ((shift /= 2) > 0) {
        size_t i = 0;
        while (i < vec.size()) {
            for (size_t j = shift; j--; ++i)
            if (vec[i] > vec[i + shift]) {
                // monotonicity is violated
                return false;
            }
        }
        i += shift;
    }
return true;
}
void vvod(vector<bool> &v);
void main()
{
    vector<bool> vect;
    vvod(vect);
    cout<<is_monotonic(vect);
}
 
void vvod(vector<bool> &v)
{
    for (int i = 0; i<n; i++)
    {
        int x ;
        cin >> x;
        v.push_back(x);
    }
 
}
Добавлено через 18 часов 15 минут
Ребята,помогите пожалуйста (((
0
653 / 574 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
20.04.2015, 12:49 3
C++
1
2
3
4
5
6
7
8
bool is_monotonic(const vector<bool>& vec)
{
    for(int i=0; i < vec.size()-1; i++)
    {
        if(vec[i]>vec[i+1]) return false;
    }
    return true;
}
Цитата Сообщение от Andryusha Посмотреть сообщение
И еще вопрос, как сделать так, чтобы я вводил произвольный вектор? В независимости к "n"
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void vvod(vector<bool> &v)
{
int g = 0;
cout<<"enter g :" << endl;
cin >> g;
    for (int i = 0; i<g; i++)
    {
        int x ;
        cin >> x;
        v.push_back(x);
    }
 
}
0
0 / 0 / 0
Регистрация: 19.04.2015
Сообщений: 13
20.04.2015, 14:11  [ТС] 4
Спасибо что Вы откликнулись.
Когда я ввожу НЕ монотонную ф-ю все хорошо, выводит 0
Но почему-то когда я ввожу монотонную ф-ю, выводит также 0.
Что с этим делать?

Добавлено через 22 секунды
0 0 1 0 1 1 1 1 - Не монотонная
0 0 0 1 0 1 1 1 - Монотонная
0
653 / 574 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
20.04.2015, 14:23 5
Цитата Сообщение от Andryusha Посмотреть сообщение
0 0 0 1 0 1 1 1 - Монотонная
это не монотонная ф-ция

Добавлено через 1 минуту
Цитата Сообщение от Andryusha Посмотреть сообщение
Как проверить на монотонность? (т.е. "неубываемость"?)
монотонность, это или убываемая, или возрастаемая на все отрезке(в данном случае на всех значениях)
т.е 123456789 - монотонно возрастающая

987654321 - монотонно убывающая

123454321 - не монотонная

Добавлено через 2 минуты
тогда вот так (в случае если только монотонность проверить надо)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool is_monotonic(const vector<bool>& vec)
    {
        bool x = false;
        for(int i=0; i < vec.size()-1; i++)
        {
            if(vec[i]>vec[i+1]) return x = true;
        }
        if(!x) return true;
 
        for(int i=0; i < vec.size()-1; i++)
        {
            if(vec[i]<vec[i+1]) return x = true;
        }
        return !x;
    }
0
0 / 0 / 0
Регистрация: 19.04.2015
Сообщений: 13
20.04.2015, 14:33  [ТС] 6
Здесь речь идет о булевой алгебре
Функция монотонна, когда выполняется условие
f(xxx0xxx) <= f(xxx1xxx)
То есть, если для каждого вектора X мы получим множество векторов {X'} таких, что некоторые нули из X там заменены на единицы, и проверим соблюдение этого условия f(X)<=f(X')...
0
0 / 0 / 0
Регистрация: 19.04.2015
Сообщений: 13
20.04.2015, 14:34  [ТС] 7
Вот пример монотонной булевой ф-и:
Проверка булевой функции на монотонность
0
653 / 574 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
20.04.2015, 14:38 8
Andryusha, тогда получается задать ф-цию как вектор - нельзя, нужен 2мерный вектор
0
0 / 0 / 0
Регистрация: 19.04.2015
Сообщений: 13
20.04.2015, 14:42  [ТС] 9
А тот код что я привел совсем не годится?
Я его нашел на одном из форумов
Проверка булевой функции на монотонность
0
0 / 0 / 0
Регистрация: 19.04.2015
Сообщений: 13
20.04.2015, 15:04  [ТС] 10
Помогите с написаниям кода (((завтра сдавать лабораторную
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.04.2015, 15:04

Строгая монотонность строго выпуклой функции
Верно ли, что строго выпуклая функция - строго монотонна. Графически данное утверждение видется...

Построить таблицу истинности, найти носитель функции, СДНФ и СКНФ и многочлен Жигалкина булевой функции

Проверить самодвойственность, монотонность и линейность логической функции
Помогите выполнить ((x\oplus y)\rightarrow \bar{x})\rightarrow \bar{(\bar{x}\rightarrow (y\sim...

Ввод булевой функции
Здравствуйте. Мне нужно реализовать ввод булевой функции. Нужно сделать так, чтобы можно было...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.