TILDA, ÖVNING 2

Abstrakta datatyper, listor med pekare

1 ABSTRAKT DATATYP FÖR TEMPERATUR

* Temperatur kan anges i olika skalor. En abstrakt datatyp
  minskar risken för missförstånd. Definiera klassen temp
  med metoderna setK, setC, setF och getK, getC, getF.

* Använd sedan klassen i ett program gaslag.py som beräknar
  trycket för en gasvolym med anropet tryck(V,T,n), där T har
  din abstrakta datatyp. Körexempel:

Antal mol (0 avslutar):1
Gasvolym (m3):1
Temp (18 C, 291 K eller 64.4 F, obs blanksteget):373.15 K
K: 373.15
C: 100.0
F: 212.01000012
Tryck (Pa): 3102.555675

Antal mol (0 avslutar):0


2 NÄST ÖVERSTA NODEN BORT

* Du har en stor stack under pekaren top. Skriv en sats
  som tar bort näst översta posten! 

* Lös samma uppgift abstrakt, alltså med anrop till push och pop!


3 VARANNAN POST BORT

* Ta bort varannan post ur en stack genom att pekmeka!

* Lös uppgiften abstrakt med hjälp av en extra stack!

* Lös uppgiften abstrakt med hjälp av rekursion!


4 REKURSIV RAPPKOLL

* Rekursiv rappkoll heter första uppgiften på tildatentan 2001-10-27.
  Det gäller att få anropet compare(stack1,stack2) att returnera -1
  om stack1 är minst, 0 om stackarna är lika och 1 om stack2 är minst.
  Efter anropet ska stackarna vara oförändrade. Formulera en korrekt
  rekursiv tanke och programmera den!

======================================================================

Filen temp.py:
"Abstrakt datatyp för temperatur"

nollC=273.15                        
nollF=255.3666666                   #F-nollan i Kelvin

class temp:
    K=0                             #Temperatur i Kelvin
    def setK(self,K): self.K=K
    def setC(self,C): self.K=nollC+C
    def setF(self,F): self.K=nollF+5*F/9
    def getK(self):   return self.K
    def getC(self):   return self.K-nollC
    def getF(self):   return (self.K-nollF)*9/5
______________________________________________________________________
Filen gaslag.py:
"Allmänna gaslagen"

from temp import temp
from sys import exit

def tryck(V,T,n):
    R=8.3145              #gaskonstanten J/mol*K
    K=T.getK()            #Kelvin
    return n*R*K/V        #trycket enligt gaslagen
    
T=temp()
while 1:
    n=input("Antal mol (0 avslutar):")
    if n==0: exit()
    V=input("Gasvolym (m3):")
    rad=raw_input("Temp (18 C, 291 K eller 64.4 F, obs blanksteget):").split()
    grader=float(rad[0])
    skalan=rad[1]
    if skalan=="K": T.setK(grader)
    if skalan=="C": T.setC(grader)
    if skalan=="F": T.setF(grader)
    print "K:",T.getK()
    print "C:",T.getC()
    print "F:",T.getF()
    print "Tryck (Pa):",tryck(V,T,n)
    print
______________________________________________________________________
Filen stack.py (känd från föreläsning, så när som på två nya metoder):
class stack:
  top=None
  def push(self,x):
    ny=node()
    ny.value=x
    ny.next=self.top
    self.top=ny
  def pop(self):
    x=self.top.value
    self.top=self.top.next
    return x
  def isempty(self):
    if self.top==None: return 1
    else: return 0
  def nastoverstabort(self):
    p=self.top
    p.next=p.next.next
  def varannanbort(self):
    p=self.top
    while p!=None:
      p.next=p.next.next
      p=p.next

class node:
  value=None
  next=None
______________________________________________________________________
Filen stacktest.py:
from stack import stack

s=stack()

# Näst översta bort med pekmek i stack-klassen
for i in range(10): s.push(i)
s.nastoverstabort()
while not s.isempty():
    print s.pop()
print "---------------------------"

# Näst översta bort, abstrakt
for i in range(10): s.push(i)
x=s.pop()
y=s.pop()
s.push(x)
while not s.isempty():
    print s.pop()
print "---------------------------"

# Varannan bort med pekmek i stack-klassen
for i in range(10): s.push(i)
s.varannanbort()
while not s.isempty():
    print s.pop()
print "---------------------------"

# Varannan bort med hjälp av extrastack
for i in range(10): s.push(i)
s2=stack()
while not s.isempty():
    s2.push(s.pop())
    x=s.pop()
while not s2.isempty():
    s.push(s2.pop())
while not s.isempty():
    print s.pop()
print "---------------------------"

# Varannan bort med rekursiv tanke
def bortvarannan(s):
    x=s.pop()
    y=s.pop()
    if not s.isempty(): bortvarannan(s)
    s.push(x)

for i in range(10): s.push(i)
bortvarannan(s)
while not s.isempty(): print s.pop()
print "---------------------------"
______________________________________________________________________
#Rekursiv rappkoll - ur tildatentan 27 okt 2001
def compare(s1,s2):
    if s1.isempty() and s2.isempty(): return 0
    if s1.isempty() and not s2.isempty(): return -1
    if not s1.isempty() and s2.isempty(): return 1
    x1=s1.pop()
    x2=s2.pop()
    result=compare(s1,s2)
    s1.push(x1)
    s2.push(x2)
    return result

s1=stack()
s2=stack()
for i in range(9):  s1.push(i)
for i in range(10): s2.push(i)
print compare(s1,s2)
s1.push(17)
print compare(s1,s2)
s1.push(666)
print compare(s1,s2)
print "---------------------------"
______________________________________________________________________
filen fakultet.py:

# Fakultet
# 0! = 1
# n! = n*(n-1)! 

def fakultet_rekursivt(n):
    if n==0: return 1
    return n*fakultet_rekursivt(n-1)

def fakultet_iterativt(n):
    f=1
    for i in range(1,n+1):
        f=f*i
    return f

n=input("Fakultet av vilket tal? ")
print fakultet_rekursivt(n)
print fakultet_iterativt(n)
______________________________________________________________________