带有三角形的算法任务

Question

我有一个算法任务有问题。里面有内容：“你在一个平面上有十个点，其中none三个共线，每对不同的点用线段连接，线段是绿色或蓝色。计算有多少个三角形只有边一种颜色。”我尝试了一个 n 元树的解决方案，但我在结果列表中得到了带有整数循环排列的重复三角形。

Answer 1

Patryk，这个问题可以用n-树解决。但是，为了避免循环排列，您需要跳过对称线段。如果从 0 -> 1 创建线段，则不需要从 1 -> 0 创建线段。下面是一个完整的代码，它通过递归深度优先搜索解决了 n 树的问题。请原谅类和方法的波兰名称。不过界面是英文的。如果您分析代码，您一定会明白这一点。

from random import choice
import copy

class Punkt:
    def __init__(self, numer):
        self.__numer = numer
        self.__odcinki = {}

    def dodaj_odcinek_wychodzący(self, punkt_docelowy, kolor):
        self.__odcinki[punkt_docelowy] = Odcinek(self.__numer, punkt_docelowy, kolor)

    def wez_odcinek_do_punktu_docelowego(self, punkt_docelowy):
        return (punkt_docelowy, self.__odcinki[punkt_docelowy].wez_kolor())

    def liczba_odcinkow(self):
        return len(self.__odcinki)

    def wez_kolor_punktu_docelowego(self, punkt_docelowy):
        return self.__odcinki[punkt_docelowy].wez_kolor()

    def lista_punktow_docelowych(self):
        return self.__odcinki.keys()


class Odcinek:
    def __init__(self, punkt_zrodlowy, punkt_docelowy, kolor):
        self.__punkt_zrodlowy = punkt_zrodlowy
        self.__punkt_docelowy = punkt_docelowy
        self.__kolor = kolor

    def wez_kolor(self):
        return self.__kolor


class Structure:
    def __init__(self, liczba_punktow=10):
        self.__punkty = [Punkt(i)
                         for i in range(liczba_punktow)]
        for i in range(liczba_punktow):
            for j in range(i + 1, liczba_punktow):
                self.__punkty[i].dodaj_odcinek_wychodzący(j, choice(["green", "blue"]))
        # for j in range(liczba_punktow):
        #     for i in range (j + 1, liczba_punktow):
        #         self.__punkty[j].dodaj_odcinek_wychodzący(*(self.__punkty[j].wez_odcinek_do_punktu_docelowego(i)))

    def wez_punkt(self, numer):

        return self.__punkty[numer]

    def wez_liczbe_punktow(self):

        return len(self.__punkty)


class Search:

    def __init__(self, struktura):

        self.__s = struktura

    def wez_liczbe_punktow(self):

        return self.__s.wez_liczbe_punktow()

    def wez_punkt(self, numer):

        return self.__s.wez_punkt(numer)

    def szukaj(self, kolor="green"):

        self.__szukany_kolor = kolor

        lista_trojkatow = []

        liczba_trojkatow = 0

        wszystkie_trojkaty = []

        for i in range(self.wez_liczbe_punktow()):

            lista_odwiedzonych_punktow = [i]

            lista_trojkatow = self.szukaj_z_punktu(i,lista_odwiedzonych_punktow,lista_trojkatow)

        return len(lista_trojkatow), lista_trojkatow

    def wez_szukany_kolor(self):

        return self.__szukany_kolor

    def szukaj_z_punktu(self, numer, trojkat, lista_trojkatow):

        if len(trojkat) == 3: # jeżeli zebraliśmy już trzy punkty to brakuje tylko zamykającego, czwartego

            if self.wez_punkt(trojkat[0]).wez_kolor_punktu_docelowego(
                trojkat[-1]) == self.wez_szukany_kolor(): # sprawdź czy do punktu zamykającego prowadzi odcinek o szukanym kolorze

                trojkat.append(trojkat[0]) # dodaj punkt zamykajacy do trójkąta

                lista_trojkatow.append(trojkat) # dodaj trojkąt do listy trójkątów

                # return lista_trojkatow # zwróć liste trójkątów obliczonych dotychczas
        else:

            potomkowie = []
            for punkt_docelowy in self.wez_punkt(numer).lista_punktow_docelowych():
                if self.wez_punkt(numer).wez_kolor_punktu_docelowego(punkt_docelowy) == self.wez_szukany_kolor():
                    potomkowie.append(punkt_docelowy)

            for potomek in potomkowie:
                trojkat_kopia = copy.copy(trojkat)
                trojkat_kopia.append(potomek)
                lista_trojkatow = self.szukaj_z_punktu(potomek, trojkat_kopia, lista_trojkatow)

        return lista_trojkatow


if __name__ == "__main__":

    s = Structure()

    for source_point in range(s.wez_liczbe_punktow()):

        for destination_point in s.wez_punkt(source_point).lista_punktow_docelowych():

            print(f"{source_point} -> {destination_point} = {s.wez_punkt(source_point).wez_kolor_punktu_docelowego(destination_point)}")

    color = "green"

    searching = Search(s)

    number_of_triangles, all_triangles = searching.szukaj("green")

    print(f"Number of triangles of color {color} = {number_of_triangles}")

    print(f"List of all triangles: {all_triangles}")

带有三角形的算法任务

An algorithmic task with triangles

python

algorithm

triangle-count