15A: Ustalenie Zakończenia | Computer Science Circles

Ćwiczenia 15A, 15B i 15C mogą być wykonane w dowolnej kolejności.

W tej lekcji zrealizujesz długi i złożony problem, który dla ciebie został podzielony na części. W tej lekcji także wprowadzamy str.split(), użyteczną metoda dzielenia łańcuchów: usuwa wszystkie spacje, a następnie zwraca listę wszystkich słów w łańcuchu. Oryginalny ciąg nie jest modyfikowany.

Możesz wywołać split() ze specjalnymi argumentami dla bardziej wyrafinowanego podziału, ale nie potrzebujemy tej możliwości poniżej. Jeśli jesteś zainteresowany, sprawdź dokumentację Pythona.

Teraz, przed nami do wykonania zadanie. Stary język programowania BASIC słynie z numerowanych linii i instrukcji goto. W tym ćwiczeniu zaimplementowano prostą wersję BASIC właśnie z tymi cechami. W szczególności dane wejściowe do Twojego programu będą składać się z kilku wierszy w formacie

«label» goto «target»

gdzie «label»(etykieta) i «target»(cel) są dodatnimi liczbami całkowitymi. Label jest podobna nazwy lub adresu linii; wszystkie label są niepowtarzalne. Target informuje o label linii, do której w następnej kolejności trzeba przejść. Ostatnią linią programu jest «label» END informująca, że należy zatrzymać się po przejściu do tej linii. Oto przykładowy program BASIC:

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

Kiedy BASIC uruchamia program, oto co się dzieje. Zaczynamy od pierwszej linii (z etykietą 5). Linia z etykietą 5 kieruje nas do linii 30, następnie idziemy do linii z etykietą 30. Następnie linia 30 mówi nam, aby przejść do wiersza 40. Linia 40 mówi nam, aby ZAKOŃCZYĆ. Więc program zakończył się pomyślnie.

Z drugiej strony, program BASIC może również zapętlić się. Oto przykład:

10 GOTO 21
21 GOTO 37
37 GOTO 21
40 END

Program zaczyna się od wiersza 10, ale potem nieskończenie przewija się między wierszami 21 i 37.

Twoim zadaniem jest napisanie w Pythonie programu, który odczytuje na wejsciu program BASIC. Jeśli program się zakończy, twój program powinien wydrukować success. Jeśli program wejdzie w nieskończoną pętlę, twój program powinien wydrukować infinite loop. Załóżmy. że każdy cel (target) jest równy jakiejś ważnej etykiecie (label) i wszystkie etykiety są unikalne, więc nie musisz sprawdzać błędów.

Można to zrobić na kilka sposobów, ale w tej lekcji wybraliśmy jedno proste podejście, które powoduje przerwanie - podzadanie 3. (W lekcji 15C masz jeden duży problem i sam zaprojektujesz podzadania.)

Podzadanie 1: Czytanie programu

Aby odczytać program, musimy wywołać input(). Musimy jednak zatrzymać wywołanie input(), gdy ostatnia linia (ta z END) zostanie osiągnięta, aby uniknąć błędu EOFError.

Podzadanie 2: Idź do niej!

Po przeczytaniu programem musimy być w stanie przejść z jednej linii do kolejnej linii programu. Aby to osiągnąć, prosimy o napisanie następującej procedury.

Zadanie na kodowanie : Idź do niej!

Zdefiniuj funkcję findLine(prog, target), aby wykonywać następujące czynności. Załóżmy, że prog to lista łańcuchów zawierających program BASIC, podobnego typu jak generowany przez getBASIC(); załóżmy, że target jest to ciąg znaków zawierającym numer linii, która jest celem instrukcji GOTO. Funkcja powinna zwracać indeks i (liczbę między 0 a len(prog)-1) taką, że prog[i] jest linią, której etykieta (label) jest równa target.Wskazówka
Przykład (wejścia/wyjścia) input/output: Jeśli wywołasz

findLine(['10 GOTO 20','20 END'], '10')

wtedy wyjście powinno być 0, skoro element 0 listy jest linią z etykietą (label) 10.

# usuń ten komentarz i wprowadź tutaj swój kod.

Wpisz polecenia takie jak print(mafonction("test-argument")) w polu poniżej.

Podzadanie 3: Inteligentna Symulacja

W poprzednich dwóch ćwiczeniach, zajmowaliśmy się procedurą wprowadzania i zadaniem na szukanie. Będą one przydatne do zapisania krócej głównego programu. Niemniej jednak, nadal istnieje ważne pytanie: w jaki sposób możemy rzeczywiście rozwiązać oryginalny problem? Najbardziej prostym sposobem byłoby symulowanie programu BASIC:

niech prog będzie BASIC programem (listą łańcuchów)
uruchomić licznik ustawiony na 0, ponieważ zaczynamy od pierwszej linii programu
while True,
- jeśli prog[location] to linia z END, zwróć "sukes" i zatrzymaj.
- niech T będzie docelowym łańcuchem wskazanym w prog[location]
- niech nową wartością location będzie findLine(prog, T)

Jest jednak poważny problem: nie wykrywa nieskończonych pętli, a jeśli program BASIC ma nieskończoną pętlę, to program Pythona również wejdzie w nieskończoną pętlę. Chcieliśmy, aby w tej sytuacji program wydrukował "infinite loop". Opuszczamy ten problem, ty go rozwiąż; podajemy podpowiedź poniżej.

Zadanie na kodowanie : Inteligentna Symulacja

Napisz funkcję execute(prog), która wykona poniższe czynności. Załóżmy, że prog to lista łańcuchów zawierających program BASIC, podobnie jak poprzednio. Następnie Twoja funkcja powinna zwracać "success" lub "infinite loop" w zależności od tego, czy program kończy się, czy zapętli. Ważne: należy założyć, że procedura findLine(prog, target) zdefiniowana w podzadaniu 2 jest już zdefiniowana, nie ma potrzeby ponownego jej zapisu.Wskazówka

# 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)

Wpisz polecenia takie jak print(mafonction("test-argument")) w polu poniżej.

Łącząc wszystko razem

Aby przetestować kod jako kompletne rozwiązanie, skopiuj i wklej poprzednie rozwiązania do następującego szablonu.

Jeśli twój język programowania jest nieco bardziej skomplikowany, to niemożliwe jest napisanie programu weryfikującego zakończenie. Jest to jeden z najstarszych i najważniejszych twierdzeń w informatyce, udowodnione przez Alana Turinga w latach trzydziestych, a dziś ludzie odnoszą się do tego, mówiąc: "a href="https://pl.wikipedia.org/wiki/Problem_stopu">Problem stopu jest nierozstrzygalny".