Загрузка...

Informatics Search for all TDNFs (as a result of MDNFs)

Thread in Studies created by dauntwitch Dec 3, 2023. 90 views

  1. dauntwitch
    Who's liked this post (1)
    dauntwitch Topic starter Dec 3, 2023 1 Mar 24, 2019
    :hi: хай ребятки, написал скрипт, возможно нужна доработка, но пока все устраивает.
    Код вышел довольной большой, но без этого тут никак(питонисты сосут).
    метод используется от великого и ужасного Квайна – Мак-Класки

    Python
    #jest
    
import string
    
from itertools import *
    
from math import *
    
from fnmatch import fnmatch
    
def check(f1, f2):
    
    counter = 0
    
    if len(f1) != len(f2): return 0
    
    for i in range(len(f1)):
    
        if f1[i] == f2[i]:
    
            continue
    
        counter += 1
    
        f1=f1[:i]+'z'+f1[i+1:]
    
    if counter == 1:
    
        return f1
    
    else:
    
        return 0
    
def skdnf(firstes):
    
    combs = [[] for _ in range(var)]
    
    combs_used = [[] for _ in range(var)]
    
    res = []
    
    for i in range(len(firstes)):
    
        if firstes[i] == '1':
    
            l = '0'*(var-len(bin(i)[2:]))+bin(i)[2:]
    
            combs[var-1] += [l]
    
    for k in range(var-2, -1, -1):
    
        prev = k+1
    
        for i in range(len(combs[prev])):
    
            for j in range(i, len(combs[prev])):
    
                cc = check(str(combs[prev][i]), str(combs[prev][j]))
    
                if cc != 0:
    
                    if str(combs[prev][i]) not in combs_used[prev]:
    
                        combs_used[prev] += [str(combs[prev][i])]
    
                    if str(combs[prev][j]) not in combs_used[prev]:
    
                        combs_used[prev] += [str(combs[prev][j])]
    
                    if cc not in combs[k]:
    
                        combs[k] += [cc]
    
    for k in range(var):
    
        for i in combs[k]:
    
            if i not in combs_used[k]:
    
                res += [i]
    
    res = res[::-1]
    
    return res, combs[var-1]
    

    
def oby(skdnf, source):
    
    vazhn = {}
    
    for comb in skdnf:
    
        kl = []
    
        comb = comb.replace('z', '?')
    
        for comb_need in range(len(source)):
    
            if fnmatch(source[comb_need], comb):
    
                kl.append(comb_need)
    
        vazhn[comb] = kl
    
    obyaz = []
    
    for el in vazhn:
    
        proverk = []
    
        for el2 in vazhn:
    
            if el == el2:
    
                continue
    
            for j in vazhn[el2]: proverk.append(j)
    
        for item in vazhn[el]:
    
            if item not in proverk:
    
                obyaz += [el.replace('?', 'z')]
    
                break
    
    return obyaz, vazhn
    

    
def find_tdnf(result, ob, vazhn, source):
    
    needs = [x for x in range(len(source))]
    
    variants = []
    
    for i in ob:
    
        for j in vazhn[i.replace('z', '?')]:
    
            if j in needs:
    
                needs.remove(j)
    
    for el in result:
    
        if el not in ob: variants += [el]
    
    b = [[] for i in range(len(source))]
    
    for i in range(1, len(source)+1):
    
        for k in permutations(variants, r=i):
    
            if sorted(k) not in b[i-1]: b[i-1] += [sorted(k)]
    
    if len(variants) == 0: return [ob]
    
    res = []
    
    for i in range(len(source)):
    
        for m in b[i]:
    
            now_comb = m
    
            nnn = needs.copy()
    
            otv_comb = [*ob]
    
            if len(variants) == 0: return otv_comb
    
            for j in now_comb:
    
                if len(nnn) == 0: break
    
                otv_comb += [j]
    
                checker = len(nnn)
    
                for n_c in vazhn[j.replace('z', '?')]:
    
                    if n_c in nnn: nnn.remove(n_c)
    
                if checker == len(nnn): break
    
            if len(nnn) == 0:
    
                if otv_comb not in res:
    
                    res.append(otv_comb)
    
    return res
    

    
def vid(kek: str):
    
    res = ''
    
    for i in range(len(kek)):
    
        if kek[i] == 'z':
    
            continue
    
        if kek[i] == '0': res += '!'
    
        res += string.ascii_lowercase[i]
    
    return res
    
def ultra_xye4eker(lst1, lst2):
    
    n = len(lst1)
    
    c = 0
    
    for el1 in lst1:
    
        if el1 in lst2: c += 1
    
    if n == c:
    
        return True
    
    return False
    
def last_check(aboba):
    
    lk = []
    
    for k in range(len(aboba)):
    
        for o in range(k+1, len(aboba)):
    
            if ultra_xye4eker(aboba[k], aboba[o]):
    
                lk.append(aboba[o])
    
    for k in lk:
    
        if k in aboba:
    
            aboba.remove(k)
    
    return aboba
    
def main():
    
    tup = input("Введите вектор функции: ")
    
    global var
    
    var = log2(len(tup))
    
    if var != int(var): print('Вы ввели неправильный вектор (длина вектора должна являться результатом степени двойки)'); return 0
    
    var = int(var)
    
    result, source = skdnf(tup)
    
    ob, vazhn = oby(result, source)
    
    j = last_check(find_tdnf(result, ob, vazhn, source))
    
    minka = 10000000000
    
    vir = ''
    
    for i in range(len(j)):
    
        lo = ''
    
        for x in j[i]:
    
            lo += f' {vid(x)} +'
    
        stroka = f'ТДНФ{i + 1}:{lo[:len(lo) - 2]}'
    
        if len(stroka) <= minka: vir = stroka[7:]; minka = len(stroka)
    
        print(stroka)
    
    print(f"МДНФ: {vir}")
    

    
if __name__ == '__main__':
    
    main()

    полезно будет для школьников(хз зачем), студентов.
     
    Dec 3, 2023 Edited
  2. dauntwitch
    dauntwitch Topic starter Dec 3, 2023 1 Mar 24, 2019
    кстати, поиск мднф через сайт https://programforyou.ru/ выдает не совсем верный ответ, поэтому ручками проверять все равно надо
     
    Dec 3, 2023
Top
Loading...