TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH
tải về 2.51 Mb.
|
5.12 Hàm f(n)Tính gía trị của hàm f(n) với biến số nguyên n cho trước, 0 n 1.000.000.000 (1 tỷ). Biếtf(0) = 0; f(1) = 1; f(2n) = f(n); f(2n+1) = f(n) + f(n+1). Thuật toán Xét hàm 3 biến g(n,a,b) = af(n) + bf(n+1). Ta có, 1) g(n,1,0) = 1.f(n) + 0.f(n+1) = f(n). 2) g(0,a,b) = af(0) + bf(1) = a.0 + b.1 = b. 3) g(2n,a,b) = af(2n) + bf(2n+1) = af(n) + bf(n) + bf(n+1) = (a+b)f(n) + bf(n+1) = g(n,a+b,b). 4) g(2n+1,a,b) = af(2n+1)+bf(2n+2) = af(n) + af(n+1) + bf(2(n+1)) = af(n) + af(n+1) + bf(n+1) = af(n) + (a+b)f(n+1) = g(n,a,a+b). Từ bốn tính chất trên ta thiết kế được hàm f(n) như sau: Để tính f(n) ta tính g(n,a,b) với a = 1, b = 0. Để tính g(n) ta lặp đến khi n = 0. Nếu n chẵn ta gọi hàm g(n/2,a+b,b); ngược lại, nếu n lẻ ta gọi hàm g(n/2,a,a+b). Khi n = 0 ta thu được f = g(0,a,b) = b. (* Pascal *) function f(n: longint): longint; var a,b: longint; begin a := 1; b := 0; while (n <> 0) do begin if odd(n) then b := b + a else a := a + b; n := n div 2; end; f := b; end; // DevC++ int f(int n) { int a = 1, b = 0; while (n) { if (n % 2 == 0) a += b; else b += a; n /= 2; } return b; } Độ phức tạp log2(n) vòng lặp. Dữ liệu test f(100) = 7; f(101) = 19; f(1000000) = 191; f(1000000000) = 7623. 5.13 Hàm h(n)Tính hàm h(n) với giá trị n cho trước 0 n 1.000.000 (1 triệu). Biết h(0) = 3; h(1) = 1; h(2n) = 2h(n); h(2n+1) = h(n) – 2h(n+1). Thuật toán Xét hàm 3 biến g(n,a,b) = ah(n) + bh(n+1). Ta có, 1) g(n,1,0) = h(n). 2) g(0,a,b) = 3a + b. 3) g(2n,a,b) = g(n,2a+b,–2b). 4) g(2n+1,a,b) = g(n,a,2b–2a). Dữ liệu test h(100) = 176; h(101) = 128; h(1000000) = 3162112; h(1000001) = 1933312. 5.14 RhythmViết hàm Rhythm(s) cho ra dáng điệu của xâu kí tự s = (s1. s2,…, sn) như sau
Kết quả được chọn ưu tiên cho các giá trị nhỏ. Thí dụ, Rhythm("'aaaaa") = 1, trong khi các tình huống 3 và 5 cũng thỏa. Biết 2 n 255.Thuật toán Ta sử dụng 3 biến đếm b (bằng), t (tăng), g (giảm) và duyệt tuần tự xâu s để ghi nhận các tình huống khi di chuyển từ phần tử si sang phần tử tiếp theo si+1. Cụ thể là ta gánb = 1 nếu si = si+1,t = 1 nếu si < si+1,g = 1 nếu si > si+1.
Độ phức tạp. cỡ n.(* Rhythm.pas *) uses crt; function Rhythm(s: string): integer; var i, g, t, b: integer; begin g := 0; t := 0; b := 0; for i := 2 to length(s) do if s[i] = s[i-1] then b := 1 else if s[i] > s[i-1] then t := 1 else { s[i] < s[i-1] } g := 1; Rhythm := ((4*g + 2*t + b) mod 7 mod 6); end; BEGIN writeln(Rhythm('aabccdx')); { 3 } readln; END. // Rhythm.cpp #include #include #include #include using namespace std; // P R O T O T Y P E S int Rhythm(char *); // I M P L E M E N T A T I O N int main() { cout << endl << Rhythm("aabccdxxxz") << endl; // 3 cout << endl << " Fini "; cin.get(); return 0; } int Rhythm(char * s) { int g, t, b, i, n; g = t = b = 0; n = strlen(s); for (i = 1; i < n; ++i) if (s[i] == s[i-1]) b = 1; else if (s[i] > s[i-1]) t = 1; else g = 1; return ((4*g + 2*t + b) % 7) % 6; } Каталог: tailieu tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1 tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam tải về 2.51 Mb. Chia sẻ với bạn bè của bạn:
|