Форум программистов, компьютерный форум CyberForum.ru

Де Морган - C++

Восстановить пароль Регистрация
 
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.04.2011, 00:08     Де Морган #1
Вообщем в универе курсач - так как из универа я все равно ухожу - то мне просто интересно написать эту программу. Жутко застопорился на раскрытии отрицания перед скобками по Де Моргану.

!(x & y) <=> !x | !y
!(x | y) <=> !x & !y

Вложенность может быть большая. Со скобками в результате не уверен. Первым открывается самое вложенное отрицание перед скобками...

Пытался делать итеративно - запутался в коде. Я так понимаю тут проще рекурсией? Можно какой-нибудь пример?
Наработки по итеративному раскрытию могу скинуть.

Ну и вопрос из примерно той же оперы.

Нам нужно составить таблицу истинности. Нужно 2^n перестановок чисел 0, 1.
Т.е. для трех переменных таблица будет

Код
0 0 0
1 0 0
0 1 0
0 0 1
1 1 0
1 0 1
0 1 1
1 1 1
Как логичнее и оптимальнее всего это сделать? Заранее спасибо за помощь.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2011, 00:08     Де Морган
Посмотрите здесь:

Упростить (де морган)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.04.2011, 00:59     Де Морган #2
ForEveR, на счёт перестановок - тут получается, что все варианты перестановок - это столбец числе с 0 по n - 1, записанных в двоичной сс. Вытащить всё это дело в более удобную форму (к примеру, в двумерный массив) можно через побитовые операции (проьегаемся в цикле по всем числам от 0 до n - 1 и разбиваем каждое на биты).
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.04.2011, 14:03  [ТС]     Де Морган #3
silent_1991, Да. Про побитовые совсем забыл.

Вышло как-то так.

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
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    int numb = 0;
    std::cin >> numb;
    std::vector<std::vector<int> > vec;
    int resnumb = (1 << numb) - 1;
    for(int i = 0; i <= resnumb; ++i)
    {
        std::vector<int> tmp_vec;
        for(int j = 0; j < numb; ++j)
        {
            tmp_vec.push_back((i >> j) & 1);
        }
        vec.push_back(tmp_vec);
    }
 
    for(std::vector<std::vector<int> >::const_iterator iter = vec.begin();
        iter != vec.end();
        ++iter)
    {
        std::copy(iter->begin(), iter->end(), std::ostream_iterator<int>(std::cout, " "));
        std::cout<<'\n';
    }
}
Или так через std::bitset.

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
 
int main()
{
    int numb = 0;
    std::cin >> numb;
    std::vector<std::vector<int> > vec;
    int resnumb = (1 << numb) - 1;
    for(int i = 0; i <= resnumb; ++i)
    {
        std::vector<int> tmp_vec;
        std::bitset<32> bits(i);
        for(int j = 0; j < numb; ++j)
            tmp_vec.push_back(bits[j]);
        vec.push_back(tmp_vec);
    }
 
    for(std::vector<std::vector<int> >::const_iterator iter = vec.begin();
        iter != vec.end();
        ++iter)
    {
        std::copy(iter->begin(), iter->end(), std::ostream_iterator<int>(std::cout, " "));
        std::cout<<'\n';
    }
}
Добавлено через 11 часов 42 минуты
А по сущности первого вопроса кто-нибудь подсказать может?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.04.2011, 14:30     Де Морган #4
По первому вопросу - почему обязательно делать с самого низкого уровня вложенности? У вас, как я понимаю, выражение представлено деревом? Так ведь перестройка дерева - процесс не сложный. Начинаем с самого высокого уровня. Раскрываем скобки - добавляем перед левым и правым поддеревом отрицания, а затем меняем операцию между этими поддеревьями на соответствующую противоположную. И перед каждым раскрытие заменяем последовательность отрицаний, если она чётная, на отсутствие отрицания вообще, если нечётная - на одно отрицание (последний пункт можно варьировать - например, корректировать количество отрицаний прямо во время предыдущего раскрытия скобок).
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.04.2011, 15:02  [ТС]     Де Морган #5
silent_1991, Выражение представлено строкой для начала. Дерево (если вообще буду использовать) будет использоваться только для подсчета.

Добавлено через 5 минут
Приблизительная суть и почему работа именно со строкой.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Create_correct
{
public:
    Create_correct(const std::string& str_):str(str_)
    {
    }
    std::string create_correct()
    {
        delete_double_negate();
        delete_impl();
        de_morgan();
        return str;
    }
private:
    void delete_impl()
    {
        size_t idx=0;
        const std::string& opers = "&|()";
        const std::string& impl = "->";
        while((idx=str.find(impl, idx)) != std::string::npos)
        {
            std::string::iterator find_iter = str.begin() + idx;
            std::string::iterator end_iter = std::find_first_of(find_iter, str.end(), 
                opers.begin(), opers.end());
            std::string::reverse_iterator rev_tmp_iter(find_iter);
            std::string::iterator beg_iter = std::find_first_of(rev_tmp_iter, str.rend(), 
                opers.rbegin(), opers.rend()).base();
            std::string tmp_str(beg_iter, end_iter);
            std::string::iterator beg_tmp_iter = std::find_first_of(tmp_str.begin(), tmp_str.end(), 
                impl.begin(), impl.end());
            std::string first_var(tmp_str.begin(), beg_tmp_iter);
            std::string second_var(beg_tmp_iter + 2, tmp_str.end());
            if(first_var.find("!") != std::string::npos)
                first_var.erase(first_var.begin());
            else
                first_var.insert(first_var.begin(), '!');
            tmp_str = first_var + '|' + second_var;
            str.replace(beg_iter, end_iter, tmp_str);
            idx += 2;
        }
    }
    void delete_double_negate()
    {
        size_t idx=0;
        const std::string& double_negate = "!!";
        const std::string& opers = "&|()";
        while((idx=str.find(double_negate)) != std::string::npos)
        {
            std::string::iterator find_iter = str.begin() + idx;
            std::string::iterator end_iter = std::find_first_of(find_iter, str.end(),
                opers.begin(), opers.end());
            std::string var(find_iter + 2, end_iter);
            str.replace(find_iter, end_iter, var);
            idx += 2;
        }
    }
    std::string str;
};
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.04.2011, 15:48     Де Морган #6
ForEveR, суть всё равно не понял))) ИМХО первое, что нужно сделать с выражением, с которым собираемся производить хоть какие-то преобразования - перевод в более удобную форму представления. А уже в ней все фишки по упрощению производить куда легче.

Добавлено через 36 минут
Ну а если так уж хочется работать со строкой - тут принцип "Разделяй и Властвуй", думаю, прекрасно подойдёт: убираем скобки и логическое отрицание перед выражением, добавляем отрицания перед каждой из частей выражения, меняем операции на противоположные и рекурсивно запускаем обработку для частей выражения.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.04.2011, 16:33     Де Морган #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ
По поводу правил Де Моргана - есть решение на Scheme (диалект Lisp). Если разберешься, конечно (формулы для удобства задаются в префиксной нотации).
Логическая формула и совершенное число
Yandex
Объявления
23.04.2011, 16:33     Де Морган
Ответ Создать тему
Опции темы

Текущее время: 16:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru