Demo entry 6718617

prefissi

   

Submitted by anonymous on Mar 05, 2018 at 10:21
Language: Python. Code size: 1.9 kB.

class PrefissiDyck:

    n = 0
    m = 0
    u = 0
    a = []
    finito = False
    operazioni = 0

    def stampa(self):
        print("".join([str(x) for x in self.a[1:]]))

    def next(self):
        if self.a[self.n] == 0:
            self.a[self.n] = 1
            self.operazioni += 1

            self.u += 1
        else:
            p = 1
            self.a[self.n] = 0
            self.operazioni += 1
            while self.a[self.n - p] == 1:
                self.a[self.n - p] = 0
                self.operazioni += 1
                p += 1

            if p == self.n:
                self.finito = True
            else:
                self.a[self.n - p] = 1
                self.operazioni += 1
                self.u = self.u - p + 1

                if self.u < self.m:
                    k = self.n - 1 + self.n % 2
                    j = 1
                    while j <= self.m - self.u:
                        self.a[k] = 1
                        self.operazioni += 1
                        k = k - 2
                        j += 1
                    self.u = self.m


    def __init__(self):
        count =  0
        self.n = int(input("lunghezza prefissi "))
        self.a = [0] * (self.n+1)
        i = 1
        while i < self.n:
            self.a[i] = 1
            self.a[i+1] = 0
            self.operazioni += 2
            i += 2
        self.m = int(self.n/2)
        self.u = int(self.n/2)
        if self.n % 2 == 1:
            self.m += 1
            self.u += 1
            self.a[self.n] = 1
            self.operazioni += 1
        while not self.finito:
            self.stampa()
            count += 1
            self.next()
        print(count, " prefissi")

        print(self.operazioni, " operazioni")
        print(self.operazioni/count, " operazioni ammortizzate")





PrefissiDyck()

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).