sort_algorithms/idol at master · 4Dejt/sort_algorithms · GitHub

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from random import choice, randrange

def create_tab(n):
    T = [[choice([True, False]) for _ in range(n)] for _ in range(n)]

    if choice([True, False]):
        k = randrange(n)
        for i in range(n):
            T[k][i] = False

        for i in range(n):
            T[i][k] = True

    for i in range(n):
        T[i][i] = "X"

    return T


def print_tab(T, n):
    print("   ", end='')
    for i in range(n):
        print(f"{i:^3}", end='')
    print()
    for i in range(n):
        print(f"{i:<3}", end='')
        for j in range(n):
            print(f"{T[i][j]:^3}", end='')
        print()


def find_idol1(T, n):
    k = None
    for i in range(n):
        for j in range(n):
            if j == i:  # pomijanie przekątnej
                continue
            elif T[i][j] == False:
                continue
            else:
                break
        else:
            k = i
            break

    if k is None:
        return  False
    else:
        for i in range(n):
            if T[i][k] == False:
                return False
    return True


def find_idol2(T, n):

    # szukamy kandydata
    k = 0
    for i in range(1, n):
        if T[k][i] == True:
            k = i

    # sprawdzamy
    T[k][k] = False
    for i in range(n):
        if T[k][i] == True:
            return False

    T[k][k] = True
    for i in range(n):
        if T[i][k] == False:
            return False

    return True


T = create_tab(5)
print_tab(T, len(T))

print(f"jest idol" if find_idol1(T, len(T)) else "brak idola")
print(f"jest idol" if find_idol2(T, len(T)) else "brak idola")