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

@Ultrator · Регистрация: 28.04.2009

Author24 — интернет-сервис помощи студентам

Булева ф-я задана вектором своих значений (битвектором длины 2^(число аргументов ф-и)).
Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й - от 000..01 во второй - 000..10 и т.д.
Как проверить на монотонность? (т.е. "неубываемость"?)

@Хохол · 31.07.2010, 18:14

Втупую вот так:

C++

bool isMonotone(bool (*f)(int), int n)//n - число аргументов, аргументы задаются одним интом
{
    int p = 1 << n;
    for(int i = 0; i < p-1; i++)
        for(int j = i+1; j < p; j++)
            if((i & j) == i && f(i) > f(j)) // i является подмаской j и нарушается монотонность
                return false;
    return true;
}

Можно оптимизировать.

Добавлено через 7 часов 33 минуты
Оптимальный перебор подмасок:
http://e-maxx.ru/algo/all_submasks

@Ultrator 14 / 10 / 1 Регистрация: 28.04.2009 Сообщений: 219
		1
	Проверка булевой функции на монотонность. 31.07.2010, 09:31. Показов 5278. Ответов 1 Метки нет (Все метки) Булева ф-я задана вектором своих значений (битвектором длины 2^(число аргументов ф-и)). Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й - от 000..01 во второй - 000..10 и т.д. Как проверить на монотонность? (т.е. "неубываемость"?) 0

	31.07.2010, 18:14