15A: Termination Determination | Computer Science Circles

15A, 15B ve 15C derslerini istediğiniz sırayla yapabilirsiniz.

Bu derste uzun ve karmaşık bir problem, parçalara ayrılmış olarak size sunuluyor. Ayrıca bu derste stringleri bölmeye yarayan str.split() metodunu göreceğiz: tüm boşluk karakterlerini silip, stringdeki tüm kelimeleri liste hâline getirir. Orijinal string değişmez.

split() metoduyla daha sofistike bölümlemeler yapmak için özel argümanlar kullanılabilir, ama aşağıdaki örneklerde bunlara ihtiyacımız olmayacak. Bu konuda daha fazla bilgi için Python dokümanlarını inceleyebilirsiniz.

Şimdi göreve başlayabiliriz. Eski programlama dili BASIC numaralandırılmış satırları ve goto ifadeleri ile ünü idi. Bu örnekte, BASIC'in basit bir versiyonunu bu özelliklerle uygulayacağız. Programınızın inputu birkaç satırdan oluşacak ve şöyle bir formatta olacak:

«etiket (label)» goto «hedef (target)»

«etiket (label)» ve «hedef (target)» pozitif sayılar olacak. Etiket satırın adı veya adresi gibi dşünülebilir; etiketler benzersizdir, tekrarlanamaz. Hedef ise gidilecek bir sonraki etiketi gösterecek. Programın son satırı, size bu satıra gelindiğinde durmanızı göstermek üzere «etiket (label)» END olacak. Burada bir BASIC programı örneği:

5 GOTO 30
10 GOTO 20
20 GOTO 10
30 GOTO 40
40 END

BASIC programı çalıştırdığımızda gerçekleşen işlemler: İlk satır başlangıç satırı (etiketi 5 olan satır). Etiketi 5 olan satırda hedef 30, yani etiketi 30 olan satıra gidecek. Etiketi 30 olan satır ise bize 40'a gitmemizi söylüyor. 40'tan gideceğimiz yer de END, yani son. Bu şekilde program sonuçlanır.

Diğer yandan, BASIC sonsuz bir döngüye de girebilir. Mesela şöyle olursa:

10 GOTO 21
21 GOTO 37
37 GOTO 21
40 END

Program 10'da başlar, ama 21 ve 37 arasında sonsuz bir döngüye girer.

Size verilen görev Python'da BASIC programını input olarak alıp, program başarıyla sonuçlanırsa, success çıktısını yazdıracak (print) bir program oluşturmak. Eğer BASIC sonsuz döngüye girerse, programınız "sonsuz döngü" anlamında infinite loopifadesini yazdırsın (print). Her hedef'in bir etikete karşılık geldiğini varsayalım, böylece hata kontrolü yapmanız gerekmeyecek.

Bunu yapmanın birkaç yolu var, ama bu ders için basit bir yöntem oluşturmak için problemi 3'e bölüyoruz. (In lesson 15C dersinde verilen problemi alt görevlere bölme işini size bıraktık.)

1. Alt görev: Programı Okumak

Programı okumak için sürekli input() çağırmamız gerekiyor; ama son satıra gelindiğinde (END yazılı olan) EOFError hatasından kaçınmak için input() çağırmayı bırakmalıyız.

2. Alt görev: Hedefe Git!

Programı okuduktan sonra, programda satırdan satıra gidebilmeliyiz. Bunu gerçekleştirmek için aşağıdaki alt yordamı oluşturmalısınız.

Coding Exercise: Hedefe git!

Aşağıdaki işlemi yapacak bir satırBul(prog, target) fonksiyonu tanımlayın. Diyelim prog BASIC programını içeren bir string listesi, getBASIC() fonsiyonuyla üretildiği gibi; ve target da GOTO ifadesinin hedefi olan satırı sayısını verecek bir string. Fonksiyonun döndüreceği çıktı olarak index i (0 velen(prog)-1 arasında bir sayı) döndürmeli, tıpkı target sayısına eşit olan prog[i] etiketi gibi. İpucu
İnput/output örneği: Eğer

satırBul(['10 GOTO 20','20 END'], '10')

fonksiyonunu çağırırsanız çıktı 0 olmalı, çünkü listedeki 0 elementi 10 etiketli olacak.

# delete this comment and enter your code here

Enter testing statements like print(myfunction("test argument")) below.

3. Alt görev: Akıllı Simülasyon

Yukarıdaki iki örnekte input rutini ve arama görevlerini yerine getirdik. Bunlar ana programı daha kısa yazmakta bize yardım edecek. Ama asıl soru hâlâ cevaplanmadı: Problemi nasıl çözeceğiz? En dolambaçsız yol BASIC programını simüle etmektir:

prog BASIC programı olsun (bir stringler dizisi)
0'dan başlayan location adlı bir sayaç yapalım, çünkü programın ilk satırından başlıyoruz
while True,
- eğer prog[location] END satırında ise, "başarılı" olmuştur ve durur.
- prog[location]'da gösterilen hedef string T olsun
- location'ın yeni değeri findLine(prog, T) olsun

But, there is a major problem: this doesn't detect infinite loops, and if the BASIC program has an infinite loop, then the Python program will also loop forever. What we wanted was that the program should print "infinite loop" in this situation. We leave this problem for you to solve; we give a hint below.

Coding Exercise: Smart Simulation

Write a function execute(prog) to do the following. Assume prog is a list of strings containing the BASIC program, like before. Then, your function should return either "success" or "infinite loop" depending on whether the program terminates, or loops forever. Important: you should assume the procedure findLine(prog, target) defined in sub-task 2 is already defined, you do not need to re-write it. Hint

# here is a broken solution to get you started
def execute(prog):
  location = 0
  while True:
    if location==len(prog)-1: return "success"
    #get T from prog[location] via str.split
    location = findLine(prog, T)

Enter testing statements like print(myfunction("test argument")) below.

Hepsini birleştirelim

Çzöümünüzün tamamını test edebilmek için, yukarıda yaptıklarınızı kopyalayarak verilen şabona yapıştırın.

If your programming language is slightly more complicated, then it's impossible to write a termination-checking program. This was the earliest important theorem in computer science, proven by Alan Turing in the 1930s, and nowadays people refer to the result by saying "the Halting Problem is undecidable."