Sjuor

Som gjort för breddenförst med heltalskö.

from queue import Queue

q = Queue() 

def makesons(tal):
    if tal==100: '
       print("Hundra!")
    q.put(tal+7)
    q.put(tal-7)
    q.put(tal*7)
    if(tal%7==0): 
       q.put(tal/7)

q.put(0)             
while not q.isempty():
    makesons(q.get())

Hoppsan, det här programmet håller på länge. Vi inför en boolesk variabel funnen som blir True när vi hittat en lösning, och låter den ingå i slingans villkor.

from queue import Queue

def makesons(tal):
    if tal==100:
       print("Hundra!")
       return True

    q.put(tal+7)
    q.put(tal-7)
    q.put(tal*7)
    if(tal%7==0): 
       q.put(tal/7)
    return False

q = Queue() 
q.put(0)             
funnen = False
while not q.isEmpty() and not funnen:
    funnen = makesons(q.get())

Ett annat sätt att avbryta programmet är att definiera en egen klass Klar som ärver från Exception.

from queue import Queue

class Klar(Exception):
    pass

def makesons(tal):
    if tal==100:
       print("Hundra!")
       raise Klar

    q.put(tal+7)
    q.put(tal-7)
    q.put(tal*7)
    if(tal%7==0): 
       q.put(tal/7)

q = Queue() 
q.put(0)             
try:
    while not q.isEmpty():
        makesons(q.get())
except Klar:
    print("Lösning funnen.")

Om man ska skriva ut lösningen:

from queue import Queue
from sys import exit

class Node:
    def __init__(self, tal = 0, op = "", far = None):
        self.tal = tal
        self.op = op
        self.far = far


def insert(tal, op, far):
    nod=Node(tal, op, far)
    q.put(nod)

def makesons(far):
    tal = far.tal
    if tal == 100:
        writechain(far)
        exit()
    insert(tal+7, "+", far)
    insert(tal-7, "-", far)
    insert(tal*7, "*", far)
    if(tal%7==0): 
        insert(tal/7, "/", far)

def writechain(p):
    if p != None: 
        writechain(p.far)
        if p.far != None:
            print(p.op, "7 =",  p.tal)
        else:
            print(p.tal)

q=Queue()
q.put(Node())             
while not q.isEmpty():
    makesons(q.get())

Utskrift:

Fråga: Kan man snabba upp programmet ytterligare genom att slopa dumbarn? Hur många gånger kommer 0 att läggas in i kön?