Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 3 - Chương 5

Luyện tập từ các đề thi5.1 Số nguyên tố cùng độ caoOlimpic Duy Tân 2009 Độ cao của một số tự nhiên là tổng các chữ số của số đó. Với mỗi cặp số tự nhiên n và h cho trước hãy liệt kê các số nguyên tố không vượt quá n và có độ cao h
Nội dung trích xuất từ tài liệu:
Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 3 - Chương 5Chương 5 Luyện tập từ các đề thi5.1 Số nguyên tố cùng độ cao Olimpic Duy Tân 2009Độ cao của một số tự nhiên là tổng các chữ số của số đó. Với mỗi cặp số tự nhiên n và h cho trước hãy liệtkê các số nguyên tố không vượt quá n và có độ cao h, 10  n  1000000; 1  h  54. hprimes.inp hprimes.out nh mỗi dòng 1 sốDữ liệu test n = 1000, h = 16. Kết quả 15 số nguyên tố độ cao 16: 79, 97, 277, 349, 367, 439, 457, 547, 619, 673, 691, 709, 727, 853, 907.Thuật toán Thuật toán liệt kê các số nguyên tố độ cao h trong khoảng 1..n 1. Gọi thủ tục Sang(n) (do Eratosthenes đề xuất, xem Tập 2) xác định các số nguyên tố trong khoảng 1..n và đánh dấu vào mảng byte p: p[i] = 0 khi và chỉ khi i là số nguyên tố. 2. Duyệt lại các số nguyên tố i trong danh sách p, tính độ cao của số i. Nếu Height(i) = h thì ghi nhận. 3. end.Để tính độ cao của số i ta tách dần các chữ số hàng đơn của i bằng phép chi a dư cho 10 rồi cộng dồn vàomột biến tổng.Độ phức tạp Thủ tục sàng duyệt n lần, mỗi lần lại duyệt n phần tử do đó cần cỡ n n thao tác cơ sở (phép nhân,phép gán).Chương trình (* Hprimes.pas – So nguyen to cung do cao *) uses crt; const fn = hprimes.inp; gn = hprimes.out; nl = #13#10; bl = #32; mn = 1000000; type mb1 = array[0..mn] of byte; var p: mb1; n,h: longint; procedure Sang(n: longint); var i,j: longint; begin fillchar(p,sizeof(p),0); for i := 2 to round(sqrt(n)) do if (p[i] = 0) then for j := i to (n div i) do p[i*j] := 1; end; function Height(x: longint): integer; var sum : integer; begin sum := 0; while x 0 do begin sum := sum + (x mod 10); x := x div 10; end; Height := sum;end;procedure Ghi; var i: longint; G: text;begin assign(g,gn); rewrite(g); for i := 2 to n do if p[i] = 0 then if Height(i) = h then writeln(g,i); close(g);end;procedure Doc; var f: text;begin assign(f,fn); reset(f); readln(f,n,h); close(f);end;BEGIN Doc; Sang(n); Ghi; writeln(nl, Fini); readln;END.// DevC++: hprimes.cpp - So nguyen to cung do cao#include #include #include #include #include using namespace std;// D A T A A N D V A R I A B L Econst int mn = 1000001;char p[mn];int n, h;const char * fn = hprimes.inp;const char * gn = hprimes.out;// P R O T O T Y P E Svoid Doc();void Sang();void Ghi();int Height(int x);// I M P L E M E N T A T I O Nint main() { Doc(); Sang(); Ghi(); cout h; f.close();}// Sang Eratosthenesvoid Sang() { // p[i] = 0 i nguyen to int can = (int) sqrt(n); int i, j, ni; memset(p,0,sizeof(p)); for (i = 2; i int d = 0; for (; x ; x /= 10) d += (x % 10); return d; } void Ghi() { int i; ofstream g(gn); for (i = 2; i Một tấm bìa dạng lưới vuông cạnh dài n = 2k tạo bởi các ô vuông đơn vị đánh số theo dòng 1.. n t ính từtrên xuống và theo cột 1..n tính từ trái sang. Người ta thực hiện lần lượt hai thao tác đan xen nhau sau đâycho đến khi nhận được một cột gồm n2 ô vuông đơn vị: 1. Cắt ngang hình theo đường kẻ giữa sau đó chồng nửa trên lên trên nửa dưới; 2. Cắt dọc hình theo đường kẻ giữa sau đó chồng nửa trái lên trên nửa phải.Tại cột cuối cùng người ta đánh số các ô vuông đơn vị 1, 2,..., n2 tính từ trên xuống.Hãy viết hai thủ tục sau đây a) ViTri(k, i, j) = v cho ra số thứ tự v của ô (i,j) trên cột cuối cùng. b) ToaDo(k, v, i, j) Cho trước k và vị trí v trên cột cuối cùng, tính tọa độ (i,j) của ô banđầu.Thí dụ ViTri(2, 4, 3) = 8. ToaDo(2,8,i, j) cho kết quả i = 4, j = 3.Thuật toánTa khảo sát bài toán với k = 2. Ta có n = 2k = 22 = 4. Ta kí hiệu ô nằm trên dòng i, cột j là [i,j].Nhận xét: Ta gọi một lần cắt ngang và mộtlần cắt dọc liên tiếp nhau là ND. Sau mỗi lần A C [1,1] [1,2] [1,3] [1,4]ND ta thu được 4 mảnh vuông và bằng nhau Tầng 1 [2,1] [2,2] [2,3] [2,4]A, B, C và D được chồng lên nhau thành một [3,1] [3,2] [3,3] [3,4]cột theo thứ tự tính từ trên xuống là A, B, C [4,1] [4,2] [4,3] [4,4] B Dvà D (mảnh A trên cùng, mảnh D dưới cùng).Gọi d là độ dày (số tầng) của khối này. Ta có, 4 mảnh thu Trước khi cắt cột có duy nhấtlúc đ ...