Home > Free Pascal, UwB > Laborki z Pascala – Lista 5

Laborki z Pascala – Lista 5

Listopad 29th, 2009 Katharsis Zostaw komentarz Idź do komentarzy

Kolejne rozwiązania już dostępne – tym razem Lista 5 – wykorzystujące pojęcie rekurencji.

Laboratorium 5

Zadanie 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

PROGRAM lista5_zad1(INPUT, OUTPUT);
 
USES
	CRT;
 
VAR
	wybor : CHAR;
	liczba : INTEGER;
 
	FUNCTION SilniaIteracyjnie(x : INTEGER) : EXTENDED;
		VAR
			wynik : EXTENDED;
			licznik : INTEGER;
 
		BEGIN
			wynik := 1;
 
			IF (x = 0) OR (x = 1) THEN
				SilniaIteracyjnie := 1
 
			ELSE
				BEGIN
					FOR licznik := x DOWNTO 1 DO
						wynik := wynik * licznik;
 
					SilniaIteracyjnie := wynik;
				END;
		END;
 
	FUNCTION SilniaRekurencyjnie(x : INTEGER) : EXTENDED;
		BEGIN
			IF (x = 0) OR (x = 1) THEN
				SilniaRekurencyjnie := 1
 
			ELSE
				SilniaRekurencyjnie := SilniaRekurencyjnie(x - 1) * x;
		END;
 
BEGIN
	CLRSCR;
 
	WRITELN('Jaki sposób liczenia silnii wybierasz:');
	WRITELN('  a) Iteracyjnie');
	WRITELN('  b) Rekurencyjnie');
 
	GOTOXY(4, 5);
	WRITELN('Wybór: [ ]');
	GOTOXY(12, 5);
	wybor := READKEY;
	WRITE(wybor);
 
	GOTOXY(4, 7);
 
	IF (wybor = 'a') OR (wybor = 'A') THEN
		BEGIN
			WRITE('Podaj liczbę: ');
			READLN(liczba);
 
			GOTOXY(4, 9);
			WRITELN('Wynik: ', SilniaIteracyjnie(liczba):0:0)
		END
 
	ELSE IF (wybor = 'b') OR (wybor = 'B') THEN
		BEGIN
			WRITE('Podaj liczbę: ');
			READLN(liczba);
 
			GOTOXY(4, 9);
			WRITELN('Wynik: ', SilniaRekurencyjnie(liczba):0:0)
		END
 
	ELSE
		WRITELN('Błędny wybór!');
 
	REPEAT UNTIL Keypressed;
END.

Obliczam silnię z podanej przez użytkownika liczby, wykorzystując do tego jedną z wybranych funkcji. Pierwsza (SilniaIteracyjnie), to zwykła iteracja pętli FOR. Druga możliwość (SilniaRekurencyjnie) oblicza wynik z wykorzystaniem rekurencji.

Zadanie 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

PROGRAM lista5_zad2(INPUT, OUTPUT);
 
USES
	CRT;
 
VAR
	wybor : CHAR;
	a1, q, n : INTEGER;
 
	FUNCTION Iter(x, y, z : INTEGER) : EXTENDED;
		VAR
			wynik, licznik : INTEGER;
 
		BEGIN
			wynik := 1;
 
			FOR licznik := z - 1 DOWNTO 1 DO
				wynik := wynik * y;
 
			Iter := x * wynik;
		END;
 
	FUNCTION Rek(x, y, z : INTEGER) : EXTENDED;
		BEGIN
			IF z = 1 THEN
				Rek := x
 
			ELSE
				Rek := y * Rek(x, y, z - 1);
		END;
 
BEGIN
	CLRSCR;
 
	WRITELN('Jaki sposób liczenia n-tego wyrazu ciągu geo. wybierasz:');
	WRITELN('  a) Iteracyjnie');
	WRITELN('  b) Rekurencyjnie');
 
	GOTOXY(4, 5);
	WRITELN('Wybór: [ ]');
	GOTOXY(12, 5);
	wybor := READKEY;
	WRITE(wybor);
 
	GOTOXY(4, 7);
 
	IF (wybor = 'a') OR (wybor = 'A') THEN
		BEGIN
			WRITE('Podaj a1, q oraz n: ');
			READLN(a1, q, n);
 
			GOTOXY(4, 9);
			WRITELN('Wynik: ', Iter(a1, q, n):0:0)
		END
 
	ELSE IF (wybor = 'b') OR (wybor = 'B') THEN
		BEGIN
			WRITE('Podaj a1, q oraz n: ');
			READLN(a1, q, n);
 
			GOTOXY(4, 9);
			WRITELN('Wynik: ', Rek(a1, q, n):0:0)
		END
 
	ELSE
		WRITELN('Błędny wybór!');
 
	REPEAT UNTIL Keypressed;
END.

Obliczam dowolny wyraz ciągu geometrycznego, który wyraża się bardzo prostym wzorem. Mimo to, ze względu na “walory edukacyjne”, wykonuję to przy pomocy dwóch funkcji: Rek (rekurencyjnie) i Iter (iteracyjnie).

Zadanie 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

PROGRAM lista5_zad3(INPUT, OUTPUT);
 
USES
	CRT;
 
VAR
	a, b : INTEGER;
	wybor : CHAR;
 
	FUNCTION NWDbezR(x, y : INTEGER): INTEGER;
		VAR
			temp : INTEGER;
 
		BEGIN
		  REPEAT
			temp := x MOD y;
			x := y;
			y := temp;
		  UNTIL y = 0;
 
		  NWDbezR := x;
		END;
 
	FUNCTION NWDzR(x, y : INTEGER): INTEGER;
		BEGIN
			IF y = 0 THEN
				NWDzR := x
 
			ELSE
				NWDzR := NWDzR(y, x MOD y);
		END;
 
BEGIN
	CLRSCR;
 
	WRITELN('Jaki sposób liczenia NWD wybierasz:');
	WRITELN('  a) Bez użycia rekurencji');
	WRITELN('  b) Rekurencyjnie');
 
	GOTOXY(4, 5);
	WRITELN('Wybór: [ ]');
	GOTOXY(12, 5);
	wybor := READKEY;
	WRITE(wybor);
 
	GOTOXY(4, 7);
 
	IF (wybor = 'a') OR (wybor = 'A') THEN
		BEGIN
			WRITE('Podaj a i b: ');
			READLN(a, b);
 
			GOTOXY(4, 9);
			WRITELN('Wynik: ', NWDbezR(a, b))
		END
 
	ELSE IF (wybor = 'b') OR (wybor = 'B') THEN
		BEGIN
			WRITE('Podaj a i b: ');
			READLN(a, b);
 
			GOTOXY(4, 9);
			WRITELN('Wynik: ', NWDzR(a, b))
		END
 
	ELSE
		WRITELN('Błędny wybór!');
 
	REPEAT UNTIL Keypressed;
END.

Skoro mowa o rekurencji, nie może zabraknąć zadania z NWD. Zrozumienie działania algorytmu to podstawa do jego poprawnej implementacji.

Zadanie 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

PROGRAM lista5_zad4(INPUT, OUTPUT);
 
USES
	CRT;
 
	FUNCTION Piramida(x : INTEGER) : INTEGER;
		VAR
			licznik, temp : INTEGER;
 
		BEGIN
			temp := x - 1;
 
			IF temp = -1 THEN
				Piramida := 1
 
			ELSE
				BEGIN
					FOR licznik := x DOWNTO 1 DO
						WRITE('*');
 
					WRITELN;
 
					Piramida := Piramida(temp);
				END;
		END;
 
BEGIN
	CLRSCR;
 
	Piramida(5);
 
	REPEAT UNTIL Keypressed;
END.

Funkcja Piramida odpowiedzialna jest za wypisywanie ciągu znaków, składającego się z malejącej ilości gwiazdek. Ilość ta maleje za każdym (rekurencyjnym) wywołaniem funkcji, dzięki czemu osiągamy zamierzony cel.

Zadanie 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

PROGRAM lista5_zad5(INPUT, OUTPUT);
 
USES
	CRT;
 
	FUNCTION G(x, y : INTEGER) : REAL;
		BEGIN
			WRITELN('a = ', x, ', b = ', y);
 
			IF (x = 0) OR (y < = 1) THEN
				G := 69
 
			ELSE IF (x + y) > 6 THEN
				G := G(x - 1, y) * G(x, y - 1)
 
			ELSE
				G := G(1, x - 1);
		END;
 
BEGIN
	CLRSCR;
 
	G(3, 5);
 
	REPEAT UNTIL Keypressed;	
END.

Badam działanie funkcji G i generuję drzewo wywołań, w zależności od podanych parametrów (3, 5).

Zadanie 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

PROGRAM lista5_zad6(INPUT, OUTPUT);
 
USES
	CRT;
 
VAR
	n : INTEGER;
 
	FUNCTION OkreslTo(x : INTEGER) : EXTENDED;
		BEGIN
			IF x = 0 THEN
				BEGIN
					OkreslTo := 0;
					WRITELN('a', x, ' = ', Okreslto:0:0);
				END
 
			ElSE IF x = 1 THEN
				BEGIN
					OkreslTo := 1;
					WRITELN('a', x, ' = ', Okreslto:0:0);
				END
 
			ELSE IF x < = 5 THEN
				BEGIN
					OkreslTo := SQR(OkreslTo(x - 2)) - 1;
					WRITELN('a', x, ' = ', Okreslto:0:0);
				END
 
			ELSE
				BEGIN
					OkreslTo := (3 * OkreslTo(x - 3)) - OkreslTo(x - 1);
					WRITELN('a', x, ' = ', Okreslto:0:0);
				END;
		END;
 
BEGIN
	CLRSCR;
 
	WRITE('Podaj n: ');
	READLN(n);
 
	WRITELN;
 
	OkreslTo(n);
 
	REPEAT UNTIL Keypressed;
END.

Zdecydowanie to zadanie przystworzyło najwięcej problemów. Implementacja algorytmu nie była tak prosta, jak się na początku wydawało. Kluczem do rozwiązania tego zadania jest właściwe ustalenie warunków zachowania ciągu i deklaracja początkowych jego wyrazów. Naszym zadaniem było sprawdzić 8-smy wyraz tego ciągu, który przy moich założeniach równy jest -2.

Zadanie 7

Zad 7

To zadanie nie wymaga kodu do ustalenia prawidłowego rozwiązania, ponieważ podlega tylko i wyłącznie analizie. Podając argumenty tylko parzyste, spowodujemy największą ilość wywołań funkcji, o której mowa jest w treści zadania.

Zadanie 8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

PROGRAM lista5_zad8(INPUT, OUTPUT);
 
USES
	CRT;
 
	PROCEDURE ZrobTo(x : INTEGER);
		BEGIN
			IF x > 0 THEN
				BEGIN
					WRITE('$');
					ZrobTo(x - 1);
				END
 
			ELSE
				WRITELN;
		END;
 
BEGIN
	CLRSCR;
 
	ZrobTo(0);
	ZrobTo(88);
 
	REPEAT UNTIL Keypressed;
END.

Badam działanie funkcji ZrobTo, która generuje ciąg znaków, składający się z dolara i nowej linii. W przypadku parametru 0, funkcja wygeneruje tylko pustą linię. Parametr 88, uruchomi rekurencyjne działanie funkcji, co spowoduje zwrot ciągu znaków o tej samej długości i pustą linię.

Zadanie 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

PROGRAM lista5_zad9(INPUT, OUTPUT);
 
USES
	CRT;
 
	FUNCTION Zagadka(x, y : INTEGER) : INTEGER;
		BEGIN
			IF x = 0 THEN
				Zagadka := y
 
			ELSE
				Zagadka := Zagadka(x - 1, y) + 1;
		END;	
 
	FUNCTION Zagadkowa(x, y : INTEGER) : INTEGER;
		BEGIN
			IF y = 0 THEN
				Zagadkowa := x
 
			ELSE
				Zagadkowa := Zagadkowa(x - 1, y) + 1;
		END;
 
BEGIN
	CLRSCR;
 
	WRITELN(Zagadka(5, 8));
	WRITELN(Zagadkowa(5, 8));
 
	REPEAT UNTIL Keypressed;
END.

Badam działanie funkcji Zagadka i Zagadkowa, w zależności od tych samych wartości parametrów. W przypadku Zagadka, funkcja wykonuje się rekurencyjnie, zwracając sumę dwóch liczb. Zagadkowa to zmodyfikowana funkcja Zagadka, która zwraca "fatalny błąd": Range check error. Wyrażenie w ciele funkcji po pewnym czasie przekracza określony zakres liczbowy (nieprawidłowo określony warunek), przez co program się wysypuje.

Zadanie 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

PROGRAM lista5_zad10(INPUT, OUTPUT);
 
USES
	CRT;
 
VAR
	k, n : INTEGER;
 
	PROCEDURE GenerujSume(a, b : INTEGER);
		VAR
			tablica : ARRAY OF ARRAY OF REAL;
			x, y: INTEGER;
 
		BEGIN	
			a := a + 1;
			b := b + 1;
 
			SETLENGTH(tablica, a, b);
 
			WRITELN;
 
			FOR x := 0 TO a - 1 DO
				FOR y := 0 TO b - 1 DO
					BEGIN
						IF y = 0 THEN
							tablica[x][y] := 0
 
						ELSE IF (y > 0) AND (x = 0) THEN
							tablica[x][y] := x + y
 
						ELSE
							tablica[x][y] := tablica[x - 1][y] + tablica[x][y - 1];
					END;
 
			FOR x := 0 TO a - 1 DO
				BEGIN
					FOR y := 0 TO b - 1 DO
						WRITE(tablica[x][y]:5:0);
 
					WRITELN;
				END;	
		END;
 
BEGIN
	CLRSCR;
 
	WRITE('Podaj k i n: ');
	READLN(k, n);
 
	GenerujSume(k, n);
 
	REPEAT UNTIL Keypressed;
END.

Procedura GenerujSume, jest odpowiedzialna za wygenerowanie tabelki, zwierającej sumę wartości umieszczonych z lewej i górnej strony. Do rozwiązania tego zadania wykorzystałem tablice dynamiczne. Takie podejście zapewnia nam elastyczny sposób przechowywania pewnej ilości danych, dlatego też deklarując taką tablicę początkowo nie podajemy zakresu indeksów. Ilość elementów określamy dopiero w czasie działania programu. W tym celu korzystam z funkcji SETLENGTH. Uwaga! W tablicach dynamicznych indeksy rozpoczynają się od 0, a kończą na (mniejszej o 1) liczbie komórek tablicy. Nie musimy się również martwić o naszą pamięć, bo jeśli tablica została utworzona w procedurze lub funkcji, to jest automatycznie usuwana z pamięci po zakończeniu jej działania.

Wszystkie zadania z tej lekcji można pobrać: tutaj.

Categories: Free Pascal, UwB Tags:
  1. Niunia
    Listopad 29th, 2009 at 23:43 | #1
    Odpowiedz | Cytuj

    E-tam, koniec z listami zadań… Czekam na raport z konferencji :).

  2. blackrain
    Grudzień 1st, 2009 at 22:12 | #2
    Odpowiedz | Cytuj

    Właśnie bolo, kiedy?

  3. TerryMabel26
    Lipiec 5th, 2010 at 23:23 | #3
    Odpowiedz | Cytuj

    I received 1 st http://www.lowest-rate-loans.com when I was 20 and that helped me very much. Nevertheless, I require the consolidation loans once again.

  1. Brak jeszcze trackbacków
Kod (wymagane)