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
Cho số tự nhiên x trong dạng thập phân có tối đa 200 chữ số. Tìm số tự nhiên y đầu tiên lớn hơn x và ở dạng nhị phân x và y có cùng số chữ số 1
tải về 2.51 Mb.
|
Cho số tự nhiên x trong dạng thập phân có tối đa 200 chữ số. Tìm số tự nhiên y đầu tiên lớn hơn x và ở dạng nhị phân x và y có cùng số chữ số 1.Dữ liệu vào: file văn bản binnext.inp: Dòng đầu tiên: N – số chữ số của x Dòng thứ hai: số x dạng thập phân với các chữ số viết liền nhau. Dữ liệu ra: file văn bản binnext.out: Dòng đầu tiên: M – số chữ số của y Dòng thứ hai: số y dạng thập phân với các chữ số viết liền nhau.
Thuật toán Trước hết ta phác thảo khung bài giải dưới dạng
Vì x là số lớn nên ta cần biểu diễn chúng dưới dạng mảng. Ta sử dụng mảng nguyên x[0..n] để biểu diễn một số (nhị phân hay thập phân) chiều dài n, trong đó phần tử x[0] được dùng để lưu chiều dài n, tức là ta đặt x[0] := n. Ta đã biết, trong hệ đếm a, số x có loga(x)+1 chữ số do đó khi chuyển đổi x sang hệ đếm b sẽ có logb(x) + 1 chữ số. Theo định nghĩa của logarit ta có logb(x) = loga(x).logb(a). Với a = 10, b = 2 ta có: log2(x) = log2(10).log10(x) 4.log10(x) Như vậy, với số thập phân x có tối đa 200 chữ số thì khi chuyển đổi x qua dạng nhị phân sẽ có tối đa 800 chữ số. Để ý rằng, khi làm các phép toán số học, các kết quả có thể lớn dần, tức là số chữ số của kết quả phát triển dần về bên trái (hàng cao), do đó ta nên lưu các chữ số của chúng theo chiều ngược, từ hàng đơn vị trở đi. Thí dụ, số 157 sẽ được biểu diễn trong mảng x như sau: x[0..3] = (3,7,5,1), trong đó x[0] = 3 là số chữ số của x. Với cách biểu diễn này, khi số chữ số tăng lên thì chúng sẽ được bổ sung vào bên phải mảng, do đó ta không phải dịch chuyển các chữ số. Dưới đây sẽ giải trình một số thủ tục. Div2(x): Thực hiện phép chia nguyên số x cho 2, x := x / 2. Để chia nguyên một số lớn x cho 2 ta chia nguyên lần lượt từng chữ số của x cho 2, tính từ chữ số hàng đơn. Nếu gặp chữ số lẻ thì ta cộng thêm 5 vào chữ số kết quả thu được tại bước trước đó. Cuối cùng ta bỏ bớt các chữ số 0 ở hàng cao. Thí dụ, để thực hiện phép chia nguyên số x = 157 cho 2 ta lưu ý rằng x được biểu diễn ngược như sau x[0..3] = (3, 7, 5, 1). Khi đó Xét x[1] = 7: x[1] := x[1] / 2 = 7 / 2 = 3; Xét x[2] = 5: Vì x[2] = 5 là số lẻ nên ta chỉnh lại x[1] := x[1] + 5 = 3 + 5 = 8; x[2] := x[2] / 2 = 5 / 2 = 2; Xét x[3] = 1: Vì x[3] = 1 là số lẻ nên ta chỉnh lại x[2] := x[2] + 5 = 2 + 5 = 7; x[3] := x[3] / 2 = 1 / 2 = 0. Ta thu được x[0..3] = (3, 8, 7, 0). Sau khi bỏ số 0 ở đầu phải (hàng cao) ta thu được x[0..2] = (2, 8, 7). Điều này có nghĩa 157 / 2 = 78.
Thí dụ, với x = 100110 ta có dạng biểu diễn ngược của x là x[0..6] = (6,0,1,1,0,0,1). Ta có: i = 2, x[i] = x[2] = 1; j = 4, x[j] = x[4] = 0; Đặt lại x[2] = 0; x[4] = 1 ta thu được x[0..6] = (6,0,0,1,1,0,1); Lật đoạn x[1..3] ta thu được x[0..6] = (6,1,0,0,1,0,1). Vậy 101001 là số sát sau số x = 100110 và có cùng 3 bít 1 như x.
Nhờ thủ tục này, khi c = 0 ta tính được ngay thủ tục x = x*2 với lời gọi MultPlus(x,0). bool IsZero(char * x): Kiểm tra số lớn x = 0? bool Odd(char c): Kiểm tra số lớn x là số lẻ? (* Binnext.pas *) uses crt; const fn = 'binnext.inp'; gn = 'binnext.out'; mn = 801; bl = #32; nl = #13#10; type mi1 = array[0..mn] of integer; var x,y: mi1; n: integer; (* Ghi file *) procedure Save(var x: mi1; fn: string); var g: text; i: integer; begin assign(g,gn); rewrite(g); writeln(g,x[0]); { x[0] – chiều dài số x } for i := x[0] downto 1 do write(g,x[i]); { Ghi ngược } close(g); end; function IsZero(var x: mi1): Boolean; begin IsZero := (x[0] = 1) and (x[1] = 0) end; { so nhi phan sat sau x } function Next(var x: mi1): Boolean; var i, j, k: integer; begin Next := false; if (IsZero(x)) then exit; { tim so 1 dau tien } i := 1; while x[i] = 0 do inc(i); { x[i] = 1 } { tim so 0 dau tien sau i } j := i+1; while x[j] = 1 do inc(j); if (j > x[0]) then begin inc(x[0]); { them 1 vi tri } j := x[0]; end; x[i] := 0; x[j] := 1; i := 1; j := j-1; while (i < j) do begin k := x[i]; x[i] := x[j]; x[j] := k; inc(i); dec(j); end; Next := true; end; procedure MultPlus(var x: mi1; c: integer); { x := 2*x + c } var i: integer; begin for i := 1 to x[0] do begin c := 2*x[i] + c; { c la so nho } x[i] := c mod 10; c := c div 10; end; if (c > 0) then begin inc(x[0]); x[x[0]] := c; end; end; procedure ToDec(var x,y: mi1); var i: integer; begin y[0] := 1; y[1] := 0; { Khoi tri y = 0 } for i := x[0] downto 1 do MultPlus(y,x[i]); end; procedure Div2(var x: mi1); { x := x div 2 } var i: integer; begin x[1] := x[1] div 2; for i := 2 to x[0] do begin if Odd(x[i]) then inc(x[i-1],5); x[i] := x[i] div 2; end; i := x[0]; while (x[i] = 0) do dec(i); if i = 0 then i := 1; x[0] := i; end; procedure ToBin(var x,y: mi1); var i: integer; begin i := 0; repeat inc(i); if Odd(x[1]) then y[i] := 1 else y[i] := 0; Div2(x); until IsZero(x); y[0] := i; end; procedure Init(var x: mi1; fileName: string); var i: integer; c: char; f: text; begin fillchar(x,sizeof(x),0); assign(f,fn); reset(f); readln(f,x[0]); writeln(x[0]); for i := x[0] downto 1 do begin read(f,c); x[i] := ord(c)-ord('0'); write(x[i]); end; close(f); end; procedure Print(var x: mi1); var i: integer; begin for i := x[0] downto 1 do write(x[i]); end; procedure Run; begin Init(x,fn); { Doc so x tu file fn } write(nl, ' x = '); Print(x); ToBin(x,y); { Chuyen x sang dang nhi phan y } write(nl, ' y = '); Print(y); if (Next(y)) then begin { So nhi phan sat sau y } write(nl, ' y = '); Print(y); ToDec(y,x); { Doi y sang x } write(nl, ' x = '); Print(x); end else { x = 0: vo nghiem } begin x[0] := 1; x[1] := 0; end; Save(x,gn); end; BEGIN Run; writeln(nl,' Fini '); readln; END. // DevC++: binnext.cpp #include #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = "binnext.inp"; const char * gn = "binnext.out"; const int mn = 1001; int x[mn], y[mn]; int n; // P R O T O T Y P E S void Init(int *, const char *); void Save(int *, const char *); void Print(int *); bool Odd(int); bool Even(int); bool Odd(int *); bool Even(int *); void MultPlus(int *, int); void Div2(int *); void ToBin(int *, int *); bool IsZero(int *); void ToDec(int *, int *); bool Next(int * x); void Run(); // I M P L E M E N T A T I O N int main() { Run(); cout << endl << " Fini "; cin.get(); return 0; } void Run() { Init(x,fn); // Doc so x tu file fn cout << endl << " x = "; Print(x); ToBin(x,y); // Chuyen x sang dang nhi phan y cout << endl << " y = "; Print(y); if (Next(y)) { // So nhi phan sat sau y cout << endl << " y = "; Print(y); ToDec(y,x); // Doi y sang x cout << endl << " x = "; Print(x); } else { // vo nghiem: 0 x[0] = 1; x[1] = 0; } Save(x,gn); } // Ghi file void Save(int * x, const char * fileName) { ofstream g(gn); g << x[0] << endl; for (int i = x[0]; i > 0; --i) g<< x[i]; g.close(); } // so nhi phan sat sau x bool Next(int *x) { int i, j, k; if (IsZero(x)) return false; // tim so 1 dau tien for (i = 1; i <= x[0]; ++i) if (x[i] == 1) break; // tim so 0 dau tien sau i for (j = i+1; j <= x[0]; ++j) if (x[j]==0) break; if (j > x[0]) ++x[0]; // them 1 chu so x[i] = 0; x[j] = 1; i = 1; --j; while (i < j) { k = x[i]; x[i] = x[j]; x[j] = k; ++i;--j; } return true; } bool IsZero(int * x) { return (x[0]==1 && x[1]==0); } void ToDec(int *x, int *y){ int i; y[0] = 1; y[1] = 0; for (i = x[0]; i > 0; --i) MultPlus(y,x[i]); } void ToBin(int * x, int *y) { int i = 0; do { y[++i] = Odd(x); Div2(x); } while (! IsZero(x)); y[0] = i; } void Div2(int * x) { int i; x[1] /= 2; for (i = 2; i <= x[0]; ++i) { if (Odd(x[i])) x[i-1] += 5; x[i] /= 2; } i = x[0]; while (x[i] == 0 && i > 1) --i; x[0] = i; } // x = x*2 + c void MultPlus(int * x, int c) { int i; for (i = 1; i <= x[0]; ++i) { c = 2*x[i] + c; // c la so nho x[i] = c % 10; c /= 10; } if (c > 0) { ++x[0]; x[x[0]] = c; } } bool Odd(int c) { return (c%2) == 1; } bool Even(int c) { return !Odd(c); } bool Odd(int * x) { return (x[1]%2) == 1; } bool Even(int * x) { return !Odd(x[1]); } void Init(int *x, const char *fileName) { int i; char c; memset(x,0,sizeof(x)); ifstream f(fileName); f >> x[0]; cout << endl << x[0] << endl; for (i = x[0]; i > 0; --i) { f >> c; x[i] = c - '0'; cout << x[i]; } f.close(); } void Print(int * x) { for (int i = x[0]; i > 0; --i) cout << x[i]; } Каталог: 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:
|