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.
|
- Điều hướng trang này:
- 5.2 Số nguyên tố cùng số bít 1
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, 10 n 1000000; 1 h 54.
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
Để 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 chia dư cho 10 rồi cộng dồn vào một biến tổng.
Thủ tục sàng duyệt 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 E const 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 S void Doc(); void Sang(); void Ghi(); int Height(int x); // I M P L E M E N T A T I O N int main() { Doc(); Sang(); Ghi(); cout << endl << endl << " Fini" << endl; return 0; } void Doc() { ifstream f(fn); f >> n >> h; f.close(); } // Sang Eratosthenes void 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 <= can ; ++i) if (p[i] == 0) for (ni = n/i, j = i; j <= ni; ++j) p[i*j] = 1; } int Height(int x) { // tong so bit 1 cua x int d = 0; for (; x ; x /= 10) d += (x % 10); return d; } void Ghi() { int i; ofstream g(gn); for (i = 2; i <= n; ++i) if (p[i] == 0) if (Height(i) == h) g << endl << i; g.close(); } 5.2 Số nguyên tố cùng số bít 1Olimpic Đại học Kỹ thuật Công nghệ Tp HCM 2009Với mỗi n và h cho trước hãy cho biết có bao nhiêu số nguyên tố không vượt quá n và ở dạng nhị phân chứa đúng h bit 1, 10 n 1000000; 1 h 30.
Bài này là dạng đặc biệt của bài trước vì trong dạng nhị phân (chỉ chứa các chữ số 0/1) thì tổng các chữ số chính là số bit 1. Thủ tục Sum dưới đây tính tổng các chữ số của số tự nhiên x khi biểu diễn x theo dạng hệ số b bất kỳ, b > 1. Như vậy, để tính tổng các chữ số của x trong hệ đếm 10 ta gọi Height(x,10). Nếu cần tính tổng các bít 1 của x ta gọi Height(x,2). (* Pascal *) function Height(x: longint, b: integer): integer; var sum : integer; begin sum := 0; while x <> 0 do begin sum := sum + (x mod b); x := x div b; end; Height := sum; end; // DevC++ int Height(int x, int b) { int d = 0; for (; x ; x /= b) d += (x % b); return d; } Chương trình giải bài này giống như bài trước ngoại trừ thay đổi nhỏ là thay lời gọi hàm một tham số Height(x) bằng lời gọi 2 tham số Height(x,2). Dữ liệu test n = 100, h = 4: 7 n = 1000000, h = 11: 14176 n = 1000, h = 4: 29 Каталог: 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:
|
lần, mỗi lần lại duyệt n phần tử do đó cần cỡ n