C++ C++ C# C# ASP.NET Security ASP.NET Security ASM ASM Скачать Скачать Поиск Поиск Хостинг Хостинг  
  Программа для работы с LPT портом...
Язык: .NET — ©Alexey...
  "ASP.NET Atlas" – AJAX в исполнении Micro...
Язык: .NET — ©legigor@mail.ru...
  "Невытесняющая" Многопоточность...
Язык: C/C++ — ©...
  Update World C++: Сборник GPL QT исходников
  Весь сайт целиком можно загрузить по ссылкам из раздела Скачать

 Построение сокращенной ДНФ по столбцу значений / Другое. / Алгоритмы

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/queue.h>

SLIST_HEAD(listhead, entry) head = SLIST_HEAD_INITIALIZER(head);
struct entry {
    char *x;
    SLIST_ENTRY(entry) entries;
};

int main()
{
    int i, j;
    int number;
    int len, alen;
    char *function = NULL;
    char format[128];

    printf("Количество переменных: ");
    scanf("%d", &number);

    if (number < 1 || number > 31)
    {
        printf("Invalid argument (1<=number<=31).\n");
        return 1;
    }

    len = 1 << number;
    function = malloc(len + 1);
    *function = '\0';

    printf("Столбец значений: ");
    snprintf(format, 128, "%%%ds", len);
    scanf(format, function);

    alen = strspn(function, "01");

    if (alen < len)
    {
        memset(function + alen, '0', len - alen);
        function[len] = '\0';
    }

    printf("Значение: %s\n", function);

    for (i = 0; i < len; i++)
    {
        if (function[i] == '1')
        {
            int r = 1;
            struct entry *item = malloc(sizeof(struct entry));
            item->x = malloc(number);
            for (j = number - 1; j >= 0; j--, r <<= 1)
            {
                item->x[j] = '0' + ((i & r) != 0);
            }
            SLIST_INSERT_HEAD(&head, item, entries);
        }
    }

    {
        int flag;
        do
        {
            struct entry *item1, *item2;

            flag = 0;

            SLIST_FOREACH(item1, &head, entries)
            {
                item2 = item1;
                while ((item2 = SLIST_NEXT(item2, entries)) != NULL)
                {
                    int diff = 0;
                    for (i = 0; i < number; i++)
                    {
                        if (item1->x[i] != item2->x[i])
                        {
                            if (diff)
                                break;
                            else
                                diff ++;
                        }
                    }
                    if (diff && i == number)
                    {
                        flag = 1;
                        break;
                    }
                }

                if (flag)
                    break;

            }

            if (flag)
            {
                for (i = 0; i < number; i++)
                {
                    if (item1->x[i] != item2->x[i])
                    {
                        item1->x[i] = 0;
                        break;
                    }
                }

                SLIST_REMOVE(&head, item2, entry, entries);
            }
        }
        while (flag);
    }

    while (!SLIST_EMPTY(&head))
    {
        struct entry *item = SLIST_FIRST(&head);
        for (i = 0; i < number; i++)
        {
            if (item->x[i])
            {
                if (i)
                    printf(" & ");

                if (item->x[i] == '0')
                    printf("not-");

                printf("x%d", i+1);
            }
        }
        SLIST_REMOVE_HEAD(&head, entries);
        free(item);
        if (!SLIST_EMPTY(&head))
            printf(" \\/ ");
    }
    printf("\n");

    return 0;
}