Pennod 03: Darllen ac ysgrifennu i ffeil, ffwythiannau ailadroddol, ac algorithmau

Bydd y daflen lab yma yn ein galluogi ni i ysgrifennu i ffeiliau tecst (sy'n gadael i ni storio gwybodaeth ar ôl i ni gau Python) ac yn cyflwyno ffwythiannau ailadroddol.

Tiwtorial

Gweithiwch trwy'r canlynol:

1. Ffwythiannau ailadroddol.

Fideo yn disgrifio'r cysyniad.

Fideo demo.

Mae'n bosib diffinio ffwythiannau mewn modd ailadroddol. Mae hwn yn debyg i brofion anwythiad mewn mathemateg. I wneud hwn rhaid ystyried dau beth:

Rheol ailadroddol;
Achos sylfaenol (hwnna mae’r rheol ailadroddol yn ei ostwng iddo).

Fel enghraifft gadewch i ni godio'r ffwythiant canlynol:

$$ f(n) = \sum_{i=0}^ni $$

Gwelwn y 'rheol ailadroddol':

$$ f(n) = f(n-1) + n $$

Rydyn ni hefyd yn gwybod bod yr 'achos sylfaenol' yw:

$$ f(0) = 0 $$

Nawr byddwn yn rhaglennu'r ffwythiant yma gan ddefnyddio ffwythiant ailadroddol:



In [1]:

    
def swm_cyfanrifau(n):
    """Swm y cyfanrifau o 0 i n"""
    if n == 0:  # Achos sylfaenol
        return 0
    return swm_cyfanrifau(n - 1) + n  # Rheol ailadroddol
swm_cyfanrifau(3)









    Out[1]:





6

Dyma enghraifft arall. Gallwn ddiffinio'r ffwythiant ffactorial $n!=n\times(n-1)\times(n-2)...2\times 1$ fel:

Yr achos sylfaenol: $0!=1$
Y rheol ailadroddol: $n!=n\times (n-1)!$

Dyma sut byddwn yn codio hwn:



In [2]:

    
def ffactorial(n):
    """Allbynnu n! gan ddefnyddio ffwythiant ailadroddol"""
    if n == 0:  # Achos sylfaenol
        return 1
    return n * ffactorial(n - 1)



In [3]:

    
for n in range(6):
    print(ffactorial(n))

Arbrofwch trwy newid y cod uchod.

2. Ysgrifennu i ffeil.

Fideo yn disgrifio'r cysyniad.

Fideo demo.

Mae'r holl ddata rydym yn trin gyda newidynnau, rhestrau a geiriaduron yn byw yng 'nghof' y cyfrifiadur lle mae ein cod Python yn rhedeg. Mae'r holl ddata yma yn cael eu colli pan mae'r rhaglen wedi gorffen rhedeg. Bydd achlysuron pan fyddwn eisiau ysgrifennu'r data yma i ffeil ar yriant caled ein cyfrifiadur (felly ei bod ar gael hyd yn oed pan fyddwn yn troi'r cyfrifiadur i ffwrdd).

I wneud hwn rhaid i Python agor ffeil (fel arfer ffeil tecst syml), ysgrifennu strings i'r ffeil, ac yna cau'r ffeil. Mae'r cod canlynol yn agor (neu greu) ffeil tecst mewn modd 'write' (dyma beth mae'r w ar ei chyfer) ac yn ysgrifennu'r rhifau o 1 i 10 iddo:



In [4]:

    
ffeiltecst = open('fyffeiltecst.txt', 'w')  # Agor y ffeil mewn modd ysgrifennu
for i in range(1, 11):
    ffeiltecst.write(str(i) + "\n")
ffeiltecst.close()  # Cau'r ffeil

Mae hefyd yn bosib gwneud hwn yn y ffordd isod (felly nid oes angen poeni am gau'r ffeil).



In [5]:

    
with open('fyffeiltecst.txt', 'w') as ffeiltecst:
    for i in range(1, 11):
        ffeiltecst.write(str(i) + "\n")

Newidiwch y cod uchod i ysgrifennu rhywbeth gwahanol i ffeil.

3. Darllen ffeiliau.

Fideo yn disgrifio'r cysyniad.

Fideo demo.

I ddarllen data o ffeil, rhaid agor y ffeil mewn modd read:



In [6]:

    
with open('fyffeiltecst.txt', 'r') as ffeiltecst:
    string = ffeiltecst.read()



In [7]:

    
string









    Out[7]:





'1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n'

Nid yw'r string yma'n ddefnyddiol iawn. I'w trawsnewid i mewn i restr gallwn ddefnyddio'r dull 'split' sy'n gwahanu string wedi seilio ar gymeriad penodol:



In [8]:

    
data = string.split('\n')
data









    Out[8]:





['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '']

Gwelwn fod gennym restr o strings a hefyd un eitem olaf sy'n wag. I glirio hwn lan (trwy drosi'r strings i gyfanrifau ac anwybyddu'r eitem olaf):



In [9]:

    
data = [int(e) for e in data[:-1]]
data









    Out[9]:





[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Enghraifft weithredol

Fideo yn disgrifio'r cysyniad.

Fideo demo.

Gallwn feddwl am y dilyniant Fibonacci fel:

Yr achos sylfaenol: $f(0)=f(1)=1$
Y rheol ailadroddol: $f(n)=f(n-1)+f(n-2)$

Dyma sut byddwn yn codio hwn:



In [10]:

    
def fibonacci(n):
    """Allbynnu'r nfed rhif fibonacci trwy defnyddio ffwythiant ailadroddol"""
    if n in [0, 1]:  # Yr achos sylfaenol
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)  # Y rheol ailadroddol



In [11]:

    
for n in range(10):
     print(fibonacci(n))

Gallwn dangos hefyd rhoddir y dilyniant Fibonacci gan:

$$ f(n) = \frac{\phi^{(n + 1)} - (-\phi)^{-(n + 1)}}{\sqrt{5}} $$

Lle $\phi$ yw'r gymhareb euraidd:

$$ \phi = \frac{1 + \sqrt{5}}{2} $$

Defnyddiwn y ffwythiant ailadroddol i wirio bod y fformiwla yma yn gywir ar gyfer y 30 gwerth cyntaf o $n$:



In [12]:

    
import math  # Dyma llyfrgell sy'n cynnwys nifer o ffwythiannau defnyddiol
phi = (1 + math.sqrt(5)) / 2
def fibonacci_amgen(n):
    """Allbynnu'r nfed rhif fibonacci trwy defnyddio'r fformiwla cymhareb euraidd"""
    return (phi ** (n + 1) - (-phi) ** (-(n + 1))) / (math.sqrt(5))

Fel gwnaethon ni yn y daflen lab diwethaf ysgrifennwn ffwythiant i wirio'r fformiwla



In [13]:

    
def gwirio_fformiwla(K):
    """Gwirio'r fformiwla cymhareb euraidd"""
    return fibonacci(K) == round(fibonacci_amgen(K), 1)
gwirio_fformiwla(3)









    Out[13]:





True

Gwiriwn am y 30 gwerth cyntaf:



In [14]:

    
gwiriadau = [gwirio_fformiwla(K) for K in range(30)]
all(gwiriadau)  # mae `all` yn cyfuno pob boolean mewn rhestr









    Out[14]:





True

Yna gallwn ddefnyddio'n fformiwla amgen i ysgrifennu ffeil mawr gyda'r 500 rhif Fibonacci cyntaf:



In [15]:

    
with open('fibonacci.txt', 'w') as ffeiltecst:
    for n in range(500):
        rhif_fib = int(round(fibonacci_amgen(n), 0))  # Talgrynnu'r rhif
        ffeiltecst.write(str(rhif_fib) + "\n")  # A'i ysgrifennu

Ymarferion

Dyma nifer o ymarferion sy'n bosib cwblhau trwy ddefnyddio'r cysyniadau cod a thrafodwyd:

Ffwythiannau ailadroddol, ysgrifennu cod sy'n cyfateb â diffiniadau ailadroddol mathemategol. Er enghraifft $a(0)=1$ ac $a(n)=2a(n-1)$:

def dilyniant_a(n):
      if n == 0:  # achos sylfaenol
         return 1  
      return 2 * a(n - 1)  # perthynas ailadroddol

Ysgrifennu i ffeil gyda open("ffeil.txt", "w") a darllen o ffeil gyda open("ffeil.txt", "r")

Ymarfer 1

Ymarfer datbygio

Mae'r cod canlynol yn ceisio ysgrifennu $n!$ fel ffwythiant ailadroddol. Canfyddwch a chywirwch yr holl fygiau.

def ffactorial(n):
    """Ffwythiant sy'n allbynnu ffactorial n"""
    return n * ffactoial(n)



In [16]:

    
def ffactorial(n):
    """Ffwythiant sy'n allbynnu ffactorial n"""
    # Mae angen achos sylfaenol:
    if n == 0:
        return 1
    #return n * ffactoial(n)  # Typo yn 'ffactorial' a nid yw'n defnyddio'r gwerth cywir.
    return n * ffactorial(n - 1)

Gwiriad gloi:



In [17]:

    
for n in range(5):
    print(n, ffactorial(n))

Ymarfer 2

Ysgrifennwch ffwythiant ailadroddol sy'n allbynnu'r rhifau Catalan $C(n)$ wedi diffinio gan y canlynol:

Achos sylfaenol: $C(0)=1$;
Rheol ailadroddol: $C(n)=\sum_{i=0}^{n-1}C(i)C(n-1-i)$



In [18]:

    
def catalan(n):
    """Allbynnu'r nfed rhif Catalan trwy defnyddio ffwythiant ailadroddol"""
    if n == 0:
        return 1
    return sum([catalan(i) * catalan(n - i - 1) for i in range(n)])

Dyma'r 5 term cyntaf:



In [19]:

    
for n in range(5):
    print(catalan(n))

Ymarfer 3

Ar gyfer yr 15 gwerth cyntaf o $n$ bod y fformiwla amgen canlynol hefyd yn rhoi'r rhifau Catalan (mewn gwirionedd dyma'r fformiwla a ddefnyddiwyd yn fwy aml):

$$ C(n) = \frac{(2n)!}{(n+1)!n!} $$

Ysgrifennwch y 500 rhif catalan cyntaf i ffeil.

Gallwch ddefnyddio'r ffwythiant ffactorial a diffiniwyd yn y daflen lab yma (Ymarfer 1) neu gallwch ddefnyddio'r llyfrgell math: math.factorial.



In [20]:

    
import math  # Defnyddio'r fformiwla ffactorial o'r llyfrgell math

def catalan_amgen(n):
    """Fformiwla amgen am y rhifau Catalan"""
    return math.factorial(2 * n) / (math.factorial(n + 1) * math.factorial(n))

Dyma ffwythiant i wirio'r fformiwla:



In [21]:

    
def gwirio_fformiwla(n):
    """
    Gwirio'r gwerth ar gyfer yr nfed rhif Catalan
    """
    return  catalan(n) == catalan_amgen(n)

A gwiriwn yr 15 rhif cyntaf:



In [22]:

    
gwiriadau = [gwirio_fformiwla(n) for n in range(15)]
all(gwiriadau)  # Mae `all` yn cyfuno pob boolean mewn rhestr









    Out[22]:





True

Ymarfer 4

Mae'r ffeil cysefin.csv (lawrlwytho) yn cynnwys y filiwn rhif cysefin cyntaf. Defnyddiwch hwy i geisio gwirio dyfaliad Goldbach.

Yn gyntaf gwiriwn ddyfaliad Goldbach yn defnyddio rhestr fach o rifau cysefin.



In [23]:

    
rhifau_cysefin = [2, 3, 5, 7, 11]



In [24]:

    
def gwirio_goldbach(n, rhifau_cysefin):
    """
    Gwirio bod n (os yw'n eilrif) yn gallu cael ei
    ysgrifennu fel swm dau rhif yn `rhestr_cysefin`
    """
    if n % 2 == 1:
        # Os yw n yn od yna mae'r dyfaliad dal yn wir
        return True
    for c1 in rhifau_cysefin:
        for c2 in rhifau_cysefin:
            if c1 + c2 == n:
                return True, c1, c2
    # Os lwpiwn trwy'r holl rhifau cysefin a nad ydyn
    # yn canfod y swm priodol yna nid yw'r dyfaliad yn wir
    return False



In [25]:

    
gwirio_goldbach(6, rhifau_cysefin)









    Out[25]:





(True, 3, 3)



In [26]:

    
gwirio_goldbach(10, rhifau_cysefin)









    Out[26]:





(True, 3, 7)

Gallwn wirio cwpl o rifau fel gwnaethon ni uchod ond ar ôl bach ni fydd gennym ddigon o rifau cysefin, er enghraifft gyda $n = 20$ cawn wall:



In [27]:

    
gwirio_goldbach(20, rhifau_cysefin)









    Out[27]:





False

Nawr darllenwn ni'r nifer mawr o rifau cysefin:



In [28]:

    
with open("cysefin.csv", 'r') as ffeilmas:
    data = [int(cysefin) for cysefin in ffeilmas.read().split()]

Edrychwn ar y 10 cofnod olaf:



In [29]:

    
data[-10:]

Nawr gallwn gadarnhau nad yw $n=20$ yn wrthenghraifft o ddyfaliad Goldbach:



In [30]:

    
gwirio_goldbach(20, data)









    Out[30]:





(True, 3, 17)

Gwiriwn y 200 eilrif cyntaf:



In [31]:

    
cyfrif_uchaf = 200
cyfrif = 0 
n = 2
bools = []
while cyfrif < cyfrif_uchaf:
    n += 1
    if n % 2 == 0:
        cyfrif += 1
        bools.append(gwirio_goldbach(n, data)[0])  # Ychwanegu'r elfen cyntaf

A gwiriwn pob boolean:



In [32]:

    
all(bools), len(bools)









    Out[32]:





(True, 200)

Galwn ni'r ymagwedd yma yn ymagwedd 'grym llym'. A allwch chi feddwl am ffordd fwy clyfar o ysgrifennu gwirio_goldbach?

Adnoddau pellach



In [ ]: