Bài tập về cấu trúc dữ liệu nè pà con giải dùm với?

Câu 11: Cho giải thuật:

           

                                      Function Fib(n);

 

                                    1.if n < 2 then Fib := 1

 

                                       else Fib := Fib(n – 2) + Fib(n – 1);

 

                                    2.Return;

 

a.Giải thuật trên có phải là giải thuật đệ quy không?Tại sao?

b.Nếu giải thuật trên là đệ quy,hãy xây dựng định nghĩa đệ quy tính Fib(n) dựa trên giải thuật đó.Khi gọi Fib(8),có bao nhiêu lần gọi Fib(4)?

c. Viết giải thật lặp tính Fib(n).

 

Câu 12: Giải sử a,b là số nguyên dương.Q là hàm số của a,b được xác định nghĩa như sau:

  

                                    0 Nếu  a < b

Q(a,b) =            

                                    Q ( a – b ,b) + 1 nếu a >= b

 

1. Hãy tính Q(2,3) & Q(14,3).
2. Viết hàm đệ quy tính giá trị hàm Q.

 

Câu 13: Hàm tính giai thừa của một số nguyên dương như sau:

            

                                    1 if n = 0

            Factorial(n) =

                                    n * factorial(n – 1) if n > 2

 

1. Hãy viết hàm đệ quy tính n!
2. Hãy viết giải thuật lặp khử đệ quy hàm đó.

 

Câu 14: Xé định nghĩa đệ quy :

 

                                                n + 1 nếu m = 0

            Acker(m,n) =               Acker( m – 1,1) nếu n = 0

                                                Acker(m – 1 ,Acker(m,m – 1)) với các T. hợp khác

 

1. Hãy xác định Acker(1,2)
2. Viết một thủ tục đệ quy tính giá trị hàm này

 

 

 

 

Câu 15: Giải thuật tính ước chung lớn nhất của hai số nguyên dương p và q như sau:

 

Gọi r là số dưa trong phép chia p & q.

            - Nếu r = 0 thì             q là ước chung lớn nhất.

            - Nấu r khác 0 thì gán chi p giá trị của q,gán cho q giá trị r rồi lặp lại quá trình.

           

a.Hãy xây dựng một định nghĩa đệ quy cho hàm USCLN(p,q).

            b.Viết một giải thuật đệ quy và một giải thuật lặp thể hiện hàm đó.

            c.Hãy nêu rõ các đặc điểm của một giải thuật đệ quy được thể hiện trong trường hợp này.

 

Câu 16: Hàm C(n,k) với n,k là các giá trị nguyên không âm và K =< n,được định nghĩa :

            C(n,n) = 1

            C(n,0) = 1

            C(n,k) = C(n – 1 ,k – 1) + C(n – 1,k) nếu 0 < k < n

-          Viết một thủ tục để quy thực hiện tính giá trị C(n,k) khi biết n,k.

n

Câu 17: Hàm a   định nghĩa như sau:

n

n - 1

n

a     = 1 nếu n = 0

            a     = a        * a nếu a > 0

n

            Viết hàm đệ quy tính a

 

Câu 18 : Cho hàm số F(m) với m là đối số nguyên dương sau:

 

                                    m                     Nếu m  < 0

2

            F(m)   =          

                                    m + F(m – 1) Nếu m >= 0

 

 

1. Tính F(5) giải thích cách tính.
2. Viết thủ tục đệ quy  để tính giá trị hàm F.

 

Câu 19 : Giải thuật tính ước số chung lớn nhất của hai số nguyên dương p & q như sau:

 

            Nếu p = q thì là ước chung là p

            Nếu p > q thì gán p là hiệu p – q

            Nếu q > p thì gán q là hiệu của q – p

1. Hãy viết giải thuật đệ quy tính ước chung của 2 số nguyên.
2. Viết giải thuật lặp khử đệ quy để tính ước chung của 2 số nguyên p,q.

 

 

Câu 20: Giả sử một máy mới đủ lưu trử một phần tử của ma trận trong Pascal

            Biết rằng ma trận C được khai báo như sau:

                        Var C: Array[1..8,1...5] of real;

            Và được lưu trữ trong một miền nhớ kế tiếp bắt đầu từ máy có địa chỉ là 1000.Tính Loc(C[5,3] theo ưu tiên hàng.

 

Câu 21: Cho ma trận A = (aij) với 1 <= i <= 7 , 1 <= j <= 6.Mỗi phần tử của một ma trận chiếm 2 từ máy .Hãy viết công thức tính địa chỉ của phần tử (aij) ứng với cách lưu trữ:

a.      Theo thứ tự ưu tiên cột.

b.      Theo thứ tự ưu tiên hàng.

 

Câu 22: Giả sử 4 từ máy mới đủ lưu trữ một phần tử của ma trận trong Pascal.Biết rằng một ma trận A được khai bái kiểu :

                        Type A = Array[1..8,2..3] of integer;

            Và được lưu trữ trong miền nhớ kế tiếp bắt đầu từ từ máy có địa chỉ là 2000

Hãy tính Loc(a[4,2]

Câu 23: Cho mảng B = (bij) với 2<= i <= 6, -5 <= j <= -1

            Hãy tính địa chỉ phần tử B[5,-2] biết rằng bảng lưu trữ theo thứ tự ưu tiên hàng,mỗi phần tử chiếm 3 từ máy và địa chỉ của từ máy đầu tiên là 1500.

---

---