Khóa luận Viết chương trình nhân 2 số nguyên lớn

Mục lục

LỜI NÓI ĐẦU 1

Chương 1: Tìm hiểu về ngôn ngữ C 3

I. LỊCH SỬ NGÔN NGỮ C 3

1. Giới thiệu về ngôn ngữ C 3

2. Những điểm mạnh và hạn chế của ngôn ngữ C. 4

II. NHỮNG KIẾN THỨC SỬ DỤNG TRONG CHƯƠNG TRÌNH. 6

1. Sử dụng kiểu dữ liệu 6

2. Sử dụng kiểu dữ liệu. 7

3. Sử dụng mảng. 7

4. Sử dụng hàm. 8

5. Sử dụng toán tử. 10

Chương 2: Đặt vấn đề và hướng giải quyết bài toán 13

I. TRÌNH BÀY TỔNG QUAN VỀ CHƯƠNG TRÌNH. 13

II. SỬ DỤNG THUẬT TOÁN. 14

1. Nhân một số với một số nguyên lớn. 14

2. Cộng hai số nguyên lớn. 15

III. XỬ LÝ CÁC LỖI NẢY SINH. 16

1. Lỗi nhập dữ liệu không đúng kiểu dữ liệu quy định: 16

2. Lỗi nhập quá số phần tử cho phép. 17

Chương 3: Giao diện chương trình 18

1. Giao diện nhập hai số nguyên dương. 18

2. Giao diện kết quả nhân hai số nguyên dương lớn. 19

3. Giao diện nhân hai số nguyên âm. 19

3. Giao diện nhân hai số nguyên âm. 20

4. Giao diện kết quả nhân hai số nguyên âm. 21

Chương 4: Mã nguồn 22

Chương 5: Tài liệu tham khảo 29

 

 

doc30 trang | Chia sẻ: netpro | Ngày: 09/04/2013 | Lượt xem: 2416 | Lượt tải: 5download
Tóm tắt tài liệu Khóa luận Viết chương trình nhân 2 số nguyên lớn, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
u sâu hơn về ngôn ngữ C. Em xin chân thành cảm ơn ! Nội dung trình bày bài toán sẽ bao gồm 6 Chương: Chương 1 sẽ trình bày sơ bộ về những nét cơ bản, những tiện ích và những hạn chế của ngôn ngữ C. Chương 2 sẽ trình bày về việc tìm hiểu nội dung bài toán, những câu hỏi cần được giải đáp, và sẽ giải đáp theo phương hướng nào. Chương 3 sẽ trình bày một số giao diện sử dụng trong chương trình. Chương 4 là những dòng mã lệnh thực hiện chương trình. Chương 5 sẽ đưa ra những tài liệu tham khảo để thực hiện bài toán. Chương 6 là mục lục – lần lượt trình bày các nội dung bài toán. Chương 1: Tìm hiểu về ngôn ngữ C I. LỊCH SỬ NGÔN NGỮ C 1. Giới thiệu về ngôn ngữ C Ngôn ngữ lập trình C là một ngôn ngữ mệnh lệnh được phát triển từ đầu thập niên 1970 bởi Ken Thompson và Dennis Ritchie để dùng trong hệ điều hành UNIX. Từ dó, ngôn ngữ này đã lan rộng ra nhiều hệ điều hành khác và trở thành một những ngôn ngữ phổ dụng nhất. C là ngôn ngữ rất có hiệu quả và được ưa chuộng nhất để viết các phần mềm hệ thống, mặc dù nó cũng được dùng cho việc viết các ứng dụng. Ngoài ra, C cũng thường được dùng làm phương tiện giảng dạy trong khoa học máy tính mặc dù ngôn ngữ này không dược thiết kế dành cho người nhập môn. Những phát triển ban đầu: Phát triển khởi đầu của C xảy ra ở AT&T Bell Labs giữa 1969 và 1973; theo Ritchie thì thời gian sáng tạo nhất là vào năm 1972. Nó được đặt tên là C vì nhiều đặc tính của nó rút ra từ một ngôn ngữ trước đó là B. Thêm vào đó, các điểm khác với ngôn ngữ nguyên thủy "B": Ken Thompson kể tới ngôn ngữ lập trình BCPL, nhưng ông ta cũng đã tạo ra ngôn ngữ là Bon để vinh danh vợ mình. Có nhiều truyền thuyết về nguồn gốc của C và hệ điều hành liên quan tới nó là Unix bao gồm: Sự phát triển của C là kết quả của các lập trình viên đã muốn chơi Space Travel. Họ đã chơi nó trên mainframe của hãng làm việc, nhưng bị thiếu khả năng (chạy) và phải hỗ trợ khoảng 100 người dùng, Thompson và Ritchie tìm thấy rằng họ đã không có đủ sự kiểm soát tàu vũ trụ (của trò chơi) để tránh được các va chạm khỏi sự chuyển dịch của các thiên thạch. Do đó, họ quyết định để xuất trò chơi này sang một máy PDP-7 để không trong văn phòng. Nhưng nó lại không có hệ điều hành; do đó, họ viết một hệ điều hành. Tiếp tục, họ quyết định để xuất hệ điều hành này sang PDP-11 của văn phòng nhưng việc này thật khó vì tất cả mã đều là ngôn ngữ Assembly. Họ quyết dịnh dùng một ngôn ngữ dể xuất cấp cao để hệ điều hành có thể xuất được dễ dàng từ máy tính này sang máy khác. Họ đã tìm đến ngôn ngữ B, nhưng nó lại thiếu các chức năng để khai thác một số khả năng của PDP-11. Vậy nên họ đã sáng tạo ra một ngôn ngữ mới là C. Unix nguyên đã được phát triển để tạo ra một hệ thống tự động lập hồ sơ cho các bằng phát minh. Phiên bản đầu tiên của Unix đã phát triển từ ngôn ngữ Assembly. Sau đó, ngôn ngữ C đã được phát triển để từ đó thay thế hệ điều hành mới. Cho đến 1973, C đã trở nên đủ mạnh để dùng viết nhân cho Unix, thay vì trước nó chúng được viết bằng Assembly trong các máy PDP-11/20. Đây là lần đầu tiên mà nhân của một hệ điều hành được lắp thành bằng một ngôn ngữ khác hơn Assembly. 2. Những điểm mạnh và hạn chế của ngôn ngữ C. C là một ngôn ngữ lập trình tương đối nhỏ gọn vận hành gần với phần cứng và nó giống với ngôn ngữ Assembler hơn hầu hết các ngôn ngữ bậc cao. Hơn thế, C đôi khi được đánh giá như là "có khả năng di động", cho thấy sự khác nhau quan trọng giữa nó với ngôn ngữ bậc thấp như là Assembler, đó là việc mã C có thể được dịch và thi hành trong hầu hết các máy tính, hơn hẳn các ngôn ngữ hiện tại trong khi đó thì Assembler chỉ có thể chạy trong một số máy tính đặc biệt. Vì lý do này C được xem là ngôn ngữ bậc trung. * Ưu điểm của ngôn ngữ C: C đã được tạo ra với một mục tiêu là làm cho nó thuận tiện để viết các chương trình lớn với số lỗi ít hơn trong mẫu hình lập trình thủ tục mà lại không đặt gánh nặng lên vai người viết ra trình dịch C, là những người bề bộn với các đặc tả phức tạp của ngôn ngữ. Cuối cùng C có thêm những chức năng sau: Một ngôn ngữ cốt lõi đơn giản, với các chức năng quan trọng chẳng hạn như là những hàm hay việc xử lý tập tin sẽ được cung cấp bởi các bộ thư viện các thủ tục. Tập trung trên mẫu hình lập trình thủ tục, với các phương tiện lập trình theo kiểu cấu trúc. Một hệ thống kiểu đơn giản nhằm loại bỏ nhiều phép toán không có ý nghĩa thực dụng. Dùng ngôn ngữ tiền xử lý, tức là các câu lệnh tiền xử lý C, cho các nhiệm vụ như là định nghĩa các macro và hàm chứa nhiều tập tin mã nguồn (bằng cách dùng câu lệnh tiền xử lý dạng #include chẳng hạn). Mức thấp của ngôn ngữ cho phép dùng tới bộ nhớ máy tính qua việc xử dụng kiểu dữ liệu pointer. Số lượng từ khóa rất nhỏ gọn. Các tham số được đưa vào các hàm bằng giá trị, không bằng địa chỉ. Hàm các con trỏ cho phép hình thành một nền tảng ban đầu cho tính đóng và tính đa hình. Hổ trợ các bản ghi hay các kiểu dữ liệu kết hợp do người dùng từ khóa định nghĩa struct cho phép các dữ liệu liên hệ nhau có thể được tập hợp lại và được điều chỉnh như là toàn bộ. * Những điểm hạn chế của ngôn ngữ C: Một số chức năng khác mà C không có (hay còn thiếu) nhưng có thể tìm thấy ở các ngôn ngữ khác bao gồm: An toàn kiểu, Tự động Thu dọn rác, Các lớp hay các đối tượng cùng với các ứng xử của chúng, Các hàm lồng nhau, Lập trình tiêu bản hay Lập trình phổ dụng, Quá tải và Quá tải toán tử, Các hỗ trợ cho đa luồng, đa nhiêm và mạng. Mặc dù C còn thiếu nhiều chức năng hữu ích nhưng lý do quan trọng để C được chấp nhận vì nó cho phép các trình dịch mới được tạo ra một cách nhanh chóng trên các nền tảng mới và vì nó cho phép người lập trình dễ kiểm soát được những gì mà chưong trình (do họ viết) thực thi. Đây là điểm thường làm cho mã C chạy hiệu quả hơn các ngôn ngữ khác. Thường thì chỉ có ngôn ngữ ASM chỉnh bằng tay chạy nhanh hơn (ngôn ngữ C), bởi vì ASM kiểm soát đưọc toàn bộ máy. Mặc dù vậy, với sự phát triển các trình dịch C, và với sự phức tạp của các CPU hiện đại, C đã dần thu nhỏ khoảng cách khác biệt về vận tốc này. Một lý do nữa cho việc C được xử dụng rộng rãi và hiệu quả là do các trình dịch, các thư viện và các phần mềm thông dịch của các ngôn ngữ bậc cao khác lại thường được tạo nên từ C. II. NHỮNG KIẾN THỨC SỬ DỤNG TRONG CHƯƠNG TRÌNH. Sử dụng kiểu dữ liệu Trong C sử dụng các kiểu dữ liệu: Ký tự (char). Số nguyên (int). Số dấu phẩy động độ chính xác đơn (float). Số dấu phẩy động chính xác kép (double). a. Kiểu char. Một giá trị kiểu char chiếm một byte (8 bit) và biểu diễn được một ký tự thông qua bảng mã ASCII. Ví dụ: ký tự 0 mã bằng 048 … Có hai kiểu char là signed char và unsigned char. Kiểu thứ nhất biểu diễn một số nguyên từ -128 đến 127, kiểu thứ hai có giá trị từ 0 đến 256. Kiểu Phạm vi biểu diễn Số ký tự Kích thước [signed] char -128 -> 127 256 1 byte Unsigned char 0 -> 255 256 1 byte b. Kiểu nguyên. Trong C cho phép sử dụng: số nguyên (int), số nguyên dài (long) và số nguyên không dấu (unsigned). Kích cỡ và phạm vi biểu diễn : Kiểu Phạm vi biểu diễn kích thước Int -32768 à 32767 2 byte Unsigned int 0 à 65535 2 byte Long [int] -2147483648à2147483647 4 byte Unsigned long[int] 0 à 4294967295 4 byte Các kiểu ký tự cũng được xem là một dạng của Kiểu nguyên. c. Kiểu dấu phẩy động. Trong C cho phép sử dụng 3 loại giá trị dấu phẩy động là float, double và long double. Kích cỡ và phạm vi biểu diễn: Kiểu Phạm vi Chữ chữ số Kích thước biểu diễn có nghĩa (byte) float 3.4E-38->3.4E+38 7-8 4 double 1.7E-308->1.7E+308 15-16 8 long double 3.4E-4932->1.1E+4932 17-18 10 Sử dụng kiểu dữ liệu. Mọi biến cần phải khai báo trước khi sử dụng. Và được khai báo theo mẫu sau: Type tên biến; Ví dụ: main() { int a,b,c; // Khai báo biến kiểu int long ad,bc,ac;// Khai báo biến kiểu long unsigned au,bu,cu;// Khai báo biến kiểu unsigned char ten,ho;// Khai báo biến kiểu char float x,y;// Khai báo biến kiểu float double xd,yd;// Khai báo biến kiểu double … } Vị trí khai báo: Các khai báo cần đặt ngay sau dấu { đầu tiên của thân hàm và cần đứng trước mọi câu lệnh khác. Chẳng hạn sau câu lệnh gán thì không được khai báo nữa. Khởi đầu cho các biến: Ví dụ: int a,b = 20,c,d = 40; Tức vừa khai báo vừa khởi đầu giá trị cho biến. Trong trường hợp trên biến b được gán cho giá trị bằng 20, và biến d cũng được gán giá trị bằng 40. Lấy địa chỉ của biến: Mỗi biến được cấp phát một vùng nhớ gồm một số byte liên tiếp. Số hiệu của byte đầu chính là địa chỉ của biến. Địa chỉ của biến chỉ dùng trong một số hàm như hàm scanf…Để nhận địa chỉ của biến ta dùng phép toán: & tên_biến; Sử dụng mảng. Mảng là một tập hợp nhiều phần tử có cùng một kiểu giá trị và có chung một tên. Mỗi phần tử mảng có vai trò như một biến và chứa được một giá trị. Có bao nhiêu kiểu dữ liệu cho biến thì cũng có bấy nhiêu kiểu dữ liệu cho mảng. Mảng bao gồm mảng một chiều và mảng nhiều chiều. Ví dụ: char ho[20],ten[20]; //khai báo mảng một chiều kiểu char //mỗi mảng gồm tối đa 20 phần tử int matran[10][10];//Khai báo mảng hai chiểu kiểu int //mảng gồm 10 hàng và 10 cột Các phần tử của mảng được cấp phát các khoảng nhớ liên tiếp nhau trong bộ nhớ, đối với mảng hai chiều các phần tử mảng được sắp xếp theo hàng. Chỉ số mảng: Một phần tử cụ thể của mảng được xác định nhờ các chỉ số của nó. Chỉ số của mảng phải có giá trị int không được vượt quá kích thước của chiều tương ứng. Số chỉ số phải bằng số chiều của mảng. Ví dụ: int i=2,j=1; a[j+i-1] là a[2]; … Lấy địa chỉ mảng: Có thể lấy địa chỉ mảng một chiều như: &a[i]; Nhưng không cho phép lấy địa chỉ mảng hai chiều. Sử dụng hàm. a. Hàm printf. Hàm printf có khả năng chuyển dạng, tạo khuôn và đưa giá trị các đối ra màn hình. Dạng tổng quát của hàm như sau: Int printf(const char *dk,[,danh sách các đối]); - Với đối dk là biến con trỏ kiểu char chứa địa chỉ của chuỗi điều khiển. Chuỗi điều khiển bao gồm ba loại ký tự: + Các ký tự điều khiển: \n Sang dòng mới \f Sang trang mới \b Lùi lại một vị trí \t Dấu tab + Các đặc tả chuyển dạng và tạo khuôn cho các đối tương ứng. + Các ký tự không phải là đặc tả cũng không phải là ký tự điều khiển gọi là ký tự hiển thị (được đưa ra màn hình). - Danh sách các đối: Các đối cần được phân cách nhau bởi dấu phẩy. Đối có thể là một hằng, một biến, một phần tử mảng, một lời gọi hàm…Giá trị của đối sẽ được chuyển dạng và in ra theo cách của đặc tả tương ứng. Khi mà một đặc tả không tìm thấy đối tương ứng hoặc khi kiểu giá trị của đối tương ứng không tương thích với ký tự chuyển dạng thì máy sẽ bị lẫn lộn và có thể đưa ra kết quả vô nghĩa. - Giá trị của hàm printf(): Khi thành công, hàm cho biết số ký tự(kể cả ký tự điều khiển) được đưa ra. Khi có lỗi, hàm có giá trị -1. b. Hàm scanf. Hàm scanf là hàm có nhiều chức năng tương tự như hàm printf nhưng theo chiều ngược lại. Nó đọc thông tin từ thiết bị vào chuẩn(bàn phím), chuyển dịch chúng (thành số nguyên, thực,…) và lưu trữ vào bộ nhớ theo các địa chỉ xác định. Hàm có dạng: int scanf(const char*dk,[,danh sách các đối]); dk là biến con trỏ kiểu char chứa địa chỉ của chuỗi điều khiển. danh sách các đối: Mỗi đối trong danh sách là một con trỏ chứa địa chỉ của một vùng nhớ(địa chỉ, biến mảng,…) dùng để lưu một giá trị đọc vào từ bàn phím. Các đối cần được phân cách với nhau bởi dấu phẩy. Chuỗi điều khiển gồm các ký tự đặc tả chuyển dạng. Mỗi đặc tả chuyển dạng thường có một đối tương ứng. Giá trị của hàm: Hàm cho một số nguyên bằng số giá trị nhận được (lưu vào bộ nhớ). Chú ý: Để việc nhập số liệu được chính xác ta nên làm theo các yêu cầu: + Số đối, số đặc tả và số trường vào phải bằng nhau. + Giữa đối, đặc tả và trường vào cần có sự phù hợp. c. Hàm getch. Nhận một ký tự từ bộ đệm bàn phím, không cho hiện lên màn hình. + Dạng hàm: int getch(void); + Công dụng: Nếu có sẵn ký tự trong bộ đệm bàn phím, thì hàm nhận một ký tự trong đó. Nếu bộ đệm rỗng, thì máy tạm dừng. Khi gõ một ký tự thì hàm nhận ngay được ký tự đó (Không cần bấm thêm Enter như trong các hàm nhập từ stdin). Ký tự vừa gõ không được hiện lên màn hình. + Hàm trả về ký tự nhận được. d. Hàm gotoxy. Cho phép di chuyển con trỏ chuột đến vị trí bất kỳ trên màn hình. e. Hàm clrscr. Dùng để xóa màn hình. 5. Sử dụng toán tử. a. Toán tử IF. Cho phép lựa chọn một trong hai nhánh tùy thuộc vào sự bằng không hay khác không của một biểu thức, nó có hai cách viết: if(biểu thức) if(biểu thức) Khối lệnh 1; Khối lệnh 1; else Khối lệnh 2; (Dạng 1) (Dạng 2) Biểu thức có thể nguyên hoặc thực. * Sự hoạt động của toán tử if: Trước tiên máy sẽ xác định giá trị của biểu thức. Nếu thiểu thức đúng (có giá trị khác không) máy sẽ thực hiện khối lệnh 1 sau đó nhảy đến các lệnh viết sau khối lệnh 2 (hoặc thực hiện các lệnh tiếp theo ở Dạng 2) và sau đó thực hiện các lệnh viết sau đó. b. Toán tử for. Cho ta một cách để tạo lên một chu trình. * Biểu thức có dạng: for(biểu thức1; biểu thức 2; biểu thức 3); Khối lệnh; Chú ý: Bất kỳ biểu thức nào trong 3 biểu thức đều có thể vắng mặt nhưng phải giữ dấu chấm phẩy. Thông thường: Biểu thức 1 là một toán tử gán để tạo giá trị ban đầu cho biến điều khiển. Biểu thức 2 là một quan hệ logic biểu thị điều kiện để tiếp tục chu trình. Biểu thức 3 là một toán tử gán dùng để thay đổi giá trị của biến điều khiển. * Sự hoạt động của toán tử for: Toán tử for làm việc theo từng bước sau: - Xác định biểu thức 1. - Xác định biểu thức 2. - Tùy thuộc vào tính đúng, sai của biểu thức 2, máy sẽ lựa chọn một trong hai nhánh. + Nếu biểu thức 2 có giá trị 0 (sai), mãy sẽ ra khỏi for và chuyển tới câu lệnh sau thân for. + Nếu biểut thức 2 có giá trị khác 0 (đúng), máy sẽ thực hiện các câu lệnh trong thân for. Khi gặp dấu ngoặc đóng } cuối cùng của thân for hoặc gặp câu lệnh continue máy sẽ chuyển tới bước 4 (khởi đầu lại). - Tính biểu thức 3, sau đó quay trở lại bước 2 để bắt đầu một vòng mới của chu trình. c. Toán tử while. Cũng giống như for, toán tử while dùng để xây dựng các chu trình; nó có dạng sau: while(biểu thức) Khối lệnh; * Sự hoạt động của while: - Xác định giá trị của biểu thức (viết sau while). - Tùy thuộc vào tính đúng sai của biểu thức này, máy sẽ lựa chọn một trong hai nhánh: + Nếu biểu thức có giá trị 0 (sai), máy sẽ ra khỏi chu trình và chuyển tới câu lệnh sau thân while. + Nếu biểu thức có giá trị khác 0 (đúng), máy sẽ thực hiện các câu lệnh trong thân while. Khi gặp dấu ngoặc nhọn đóng cuối cùng của thân while máy sẽ trở lại bước 1. d. Toán tử do…while. Tương tự như toán tử for và while, nhưng khác với hai toán tử trên trong chu trình do while việc kiểm tra điều kiện kết thúc đặt ở cuối chu trình. Như vậy thân chu trình bao giờ cũng được thực hiện ít nhất một lần. Toán tử do while có dạng: do khối lệnh; while(biểu thức); * Sự hoạt động của do while: Toán tử này thực hiện theo các bước sau. - Thực hiện các câu lệnh trong thân do while. - Khi gặp dấu ngoặc nhọn cuối cùng của thân do while, máy sẽ xác định giá trị của biểu thức sau từ khóa while. - Máy sẽ phân nhánh theo giá trị của biểu thức vừa nhận được + Nếu biểu thức có giá trị bằng 0 (sai), máy sẽ ra khỏi chu trình và chuyển tới câu lệnh đứng sau dấu chấm phẩy đặt cuối toán tử do while. + Nếu biểu thức có giá trị bằng 1 (đúng), máy sẽ quay trở lại bước đầu, thực hiện biểu thức trong thân do while. Chương 2: Đặt vấn đề và hướng giải quyết bài toán I. TRÌNH BÀY TỔNG QUAN VỀ CHƯƠNG TRÌNH. Như đã trình bày ở Chương 1, thì việc thực hiện bài toán không thể thực hiện một cách thông thường như việc nhân hai số kiểu “int” hay kiểu “long”, mà để thực hiện nhân hai số nguyên lớn cỡ 20 chữ số ta phải dùng mảng để lưu trữ các phần tử nhập vào, cụ thể trong bài toán em sử dụng một mảng kiểu “char”, từ đó mỗi phần tử nhập vào ta có thể coi như mỗi kí tự mà mỗi kí tự sẽ được lưu trữ vào mỗi phần tử trong mảng. Số các phần tử nhập vào sẽ phụ thuộc vào độ lớn của mảng khai báo. Theo đề bài: “Nhân hai số nguyên lớn” với yêu cầu nhập vào hai số nguyên lớn (dưới 20 kí tự), và in ra tích hai số nguyên đó. Mô tả phép nhân tay. Theo sự góp ý của Thầy giáo hướng dẫn Em đã chia ra thành hai bài toán nhỏ: Một là nhân một số có 1 chữ số với một số nguyên lớn. Hai là cộng hai số nguyên lớn. Khi nhân một số với một số nguyên lớn, tương đương với việc lấy số đó lần lượt nhân với từng thành phần trong số nguyên lớn: chẳng hạn, lấy một số nhân với hàng đơn vị của của số nguyên lớn, ta sẽ được hàng đơn vị của số kết quả, cứ tiếp như vậy ta sẽ lần lượt nhân một số với hàng chục, hàng trăm…và cuối cùng ta sẽ có kết quả của việc nhân một số với một số nguyên lớn. Như vậy ta sẽ có một số nhân lần lượt với từng phần tử trong một mảng lưu trữ các số nguyên nhập vào, kết quả nhận được cũng sẽ lưu trữ vào một mảng các chữ số nguyên. Được kết quả của việc nhân một số với một số nguyên lớn, cộng dồn các kết quả ta sẽ có được tích của hai số nguyên lớn. Việc cộng hai số nguyên lớn thực chất là việc cộng từng phần tử của hai mảng lưu trữ các số nguyên lại với nhau. Bài toán sử dụng hai hàm: Hàm nhan() và hàm main(). Hàm nhan() sẽ làm nhiệm vụ nhân hai số nguyên lớn, còn hàm main() là hàm chính, để trình bày giao diện nhập, gọi hàm nhân và in ra kết quả phép tính. * Trong hàm nhan() sẽ phải thực hiện nhân một số với một số nguyên lớn, và sẽ có kết quả của phép nhân và phép cộng, vì vậy trong hàm sẽ phải sử dụng hai mảng để lưu trữ hai kết quả của phép nhân và phép cộng. Đó là mảng “int tg[]” để lưu trữ kết quả phép nhân và mảng “int tong[]” để lưu trữ kết quả phép cộng. Trong phép nhân và phép cộng, kết quả đều liên quan đến phép nhớ, nếu phép nhân với hàng đơn vị >=10 thì cần có một biến để lưu trữ giá trị nhớ cho lần nhân tiếp theo, tương tự phép cộng, nếu cộng hàng đơn vị được kết quả >=10 cũng cần một biến nhớ để lưu trữ giá trị nhớ cộng vào hàng chục. Vì vậy ở trong hàm nhan() phải sử dụng một biến nhớ chung là biến “nho” kiểu int. Và khi nhân hai số nguyên lớn ta sẽ thực hiện lấy từng số từ hàng đơn vị nhân với số kia và đến hàng chục, hàng trăm… Vậy cần một biến để quy định phần tử mảng nào đem nhân là hàng đơn vị, hàng chục, trăm… Biến “bac” kiểu int, sẽ quy định bậc của phần tử đem nhân. Cộng với một số các biến để sử dụng trong các vòng lặp như i,j,ntg,nmax * Trong hàm main(), vì đây là hàm chính dùng để cho phép nhập giá trị hai số nguyên và in ra kết quả phép nhân(tức gọi hàm nhan()) vì vậy trong hàm sẽ phải sử dụng một số biến cục bộ cho phép hàm nhan() có thể sử dụng được nó. - Hai biến mảng kiểu “char[]” dùng để lưu hai giá trị số nguyên nhập vào là son[] và sobn[], và hai mảng kiểu “int[]” là “mảng s1[] và mảng s2[]” dùng để tách và lưu trữ từng phần tử nhập vào. - Việc nhân hai số nguyên bao gồm cả số nguyên dương và số nguyên âm, vì vậy cần có biến để quy định dấu của số nhập vào, trong hàm sử dụng biến cục bộ là biến “dau” kiểu int. - Và một số các biến khác được sử dụng trong chương trình. II. SỬ DỤNG THUẬT TOÁN. 1. Nhân một số với một số nguyên lớn. Giả sử ta lấy một số nguyên a nhân với một số nguyên lớn. Sử dụng mảng “char son[]” để nhập số nguyên lớn, sau khi nhập từng phần tử mảng son[] sẽ được chuyển thành giá trị kiểu int và lưu vào trong một mảng int s1[] bằng cách cộng thêm vào mã ASCII. Lúc này việc nhân số nguyên a với số nguyên lớn là việc nhân một số với từng phẩn tử trong mảng số nguyên s1[]. Ta sử dụng vòng lặp for() duyệt từ đầu đến cuối mảng mảng s1[] rồi lấy từng phần tử trong mảng nhân với a. Nếu giá trị nhớ khác “0” thì sẽ được cộng vào phần tử mảng tiếp theo. n1=độ dài của mảng s1; nhớ = 0; for( i=0;i<=n1;i++) { tích = a*phần tử s1 thứ i+nhớ ; ptử tg thứ i = tích % 10;//chia lấy phần dư nhớ = tích / 10;//Chia lấy phần nguyên } Ta sử dụng vòng lặp while để kiểm tra trong khi đến phần tử cuối cùng mà nhớ có giá trị khác “0” ta sử dụng phần tử mảng tiếp theo để lưu giá trị nhớ đó. while(nho) { tăng biến đếm ntg lên 1; ptử tg[i+1] = nhớ%10; update lại biến nhớ;//nhớ = nhớ/10; } Kết quả của phép nhân sẽ bao gồm tập hợp các phần tử nguyên lưu trữ trong mảng tg[]. 2. Cộng hai số nguyên lớn. Sau khi thực hiện phép nhân một số với một số nguyên lớn ta được một mảng các phần tử như trên. Vậy việc cộng hai số nguyên lớn được thực hiện trên việc cộng dồn từng phần tử mảng kết quả của phép nhân trên. Chẳng han cứ sau khi nhân được các phần tử hàng đơn vị ta thực hiện cộng chúng lại rồi lưu chúng vào phần tử mảng hàng đơn vị của kết quả tổng, rồi tiếp tục đến hàng chục, và hàng trăm… Sử dụng vòng lặp for() để cộng dồn kết quả sau khi nhận được kết quả từ phép nhân. Gán bậc = 0; Gán n2 = độ dài mảng s2[]; for(j=0;j<=n2;j++) { Gán bậc = j; for(i=0;i<=n1;i++) { tích = s1[i]*s2[j] + nhớ; tg[i+bậc] = tích%10; nhớ = tích/10; } ntg = n1+bậc; while(nho) { ntg++; tg[ntg] = nhớ%10; nhớ = nhớ/10; } for(i=bậc;i<=ntg;i++) { tổng[i] = tổng[i] +tg[i] + nhớ; nhớ = tổng[i]/10; tổng[i] =tổng[i]%10; } while(nhớ) { ntg++; tổng[ntg] = tổng[ntg] + nhớ%10; nhớ = nhớ/10; } } Với hai thuật toán nhân một số với một số nguyên lớn và cộng hai số nguyên lớn ta đã có thể hoàn thành được bài toán nhân hai số nguyên lớn. Công việc còn lại chỉ là thực hiện phần giao diện in ra kết quả sao cho hợp lý, và dễ nhìn. Kết hợp với việc xử lý một số lỗi mắc phải do sự hạn chế của ngôn ngữ gây ra để tạo nên một chương trình hoàn chỉnh. III. XỬ LÝ CÁC LỖI NẢY SINH. Việc khai báo nhập hai số nguyên lớn là việc nhập hai xâu ký tự nên sẽ nảy sinh một số các lỗi sau: Lỗi nhập dữ liệu không đúng kiểu dữ liệu quy định: Vì khai báo mảng nhập là mảng kiểu xâu ký tự nên người nhập vẫn có thể nhập được xâu ký tự, nếu người nhập xâu ký tự máy tính sẽ tự động chuyển sang mã ASCII ứng với ký tự nhập đó, điều này sẽ làm sai lệch mục đích và kết quả thực hiện phép toán. Vì vậy phải bắt lỗi không cho phép người dùng nhập dữ liệu kiểu xâu ký tự. Hoặc người dùng có thể nhập một số các ký tự khác ngoài ký tự kiểu xâu và kiểu số, chẳng hạn như người dùng nhập các ký tự đặ biệt hoặc nhập khoảng trắng(dấu cách - space), điều này cũng không hợp lệ và làm sai lệch kết quả phép toán. Như vậy phải làm cho người dùng chỉ có thể nhập kiểu số, nhập dấu âm đầu tiên, ngoài ra không thể nhập thêm bất cứ ký tự nào khác tránh sai lệch kết quả chương trình. -> Phương án: Sử dụng hàm getch() để bắt từng ký tự nhập vào từ bàn phím, và kiểm tra trước khi cho phép nhập, nếu thỏa mãn điều kiện: dấu âm đầu tiên hoặc chỉ có chữ số thì mới cho phép nhập. Lỗi nhập quá số phần tử cho phép. Theo yêu cầu của đề bài, chỉ cho phép nhập tối đa 20 ký tự. Nếu người dùng nhập vào quá 20 phần tử thì sẽ bị tràn mảng, dẫn đến kết quả sai lệch, không đúng với yêu cầu bài toán. -> Hướng giải quyết: sử dụng vòng lặp do…while và kiểm tra điều kiện, việc nhập sẽ không có hiệu lực nếu nhập quá 20 phần tử. Chương 3: Giao diện chương trình Giao diện nhập hai số nguyên dương. Giao diện kết quả nhân hai số nguyên dương lớn. 3. Giao diện nhân hai số nguyên âm. 4. Giao diện kết quả nhân hai số nguyên âm. Chương 4: Mã nguồn #include #include #include int n1,n2,dau1,dau2; int s1[21],s2[21]; char son[21],sobn[21]; void nhan(); /*============== ham nhan hai so ==============*/ void nhan(void) { int nho,bac,tich,i,j; int tong[50]={0}; int tg[50]={0}; int nmax,ntg; bac=1; tich=1; nho=0; nmax=0; //hoan doi phan tu mang for (j=0;j<=n2;j++) { tg[n2-j]=s2[j]; } for (j=0;j<=n2;j++) { s2[j]=tg[j]; } for (j=0;j<=n1;j++) { tg[n1-j]=s1[j]; } for (j=0;j<=n1;j++) { s1[j]=tg[j]; } //Nhan hai so for (j=0;j<=n2;j++) { bac=j; for (i=0;i<=n1;i++) { tich = s1[i]*s2[j]+nho; tg[i+bac] = tich%10; nho = tich/10; } ntg = n1+bac; while (nho) { ntg++; tg[ntg] = nho%10; nho = nho/10; } for(i=bac;i>=0;i--) printf(" "); gotoxy(50-ntg,wherey()); for(i=ntg;i>=bac;i--) printf("%d",tg[i]); printf("\n"); for(i=bac;i<=ntg;i++) { tong[i] += tg[i]+nho; nho = tong[i]/10; tong[i] %= 10; } while(nho) { ntg++; tong[ntg] = tong[ntg]+nho%10; nho = nho/10; } if (ntg>nmax) nmax=ntg; } //mo ta nhan tay gotoxy(49-nmax,wherey()); for(i=ntg+1;i>=0;i--) printf("-"); printf("\n"); gotoxy(50-ntg,wherey()); if(dau1*dau2<0) { gotoxy(49-nmax,wherey()); printf("-"); for(i=nmax;i>=0;i--) printf("%d",tong[i]); }else { gotoxy(50-nmax,wherey()); for(i=nmax;i>=0;i--) printf("%d",tong[i]); } } /*================ Ham main ===================*/ void main() { int i,dem,len1,len2; char ch; tt: clrscr(); printf("\n CHUONG TRINH NHAP VA TINH HAI SO NGUYEN LON"); printf("\n\n *************************"); i=0; dem=0; printf("\n\nSo thu 1: ");fflush(stdin); do { ch=getch(); if(ch>='0'&&ch<='9'&&i<20) { if (dem==0) { dau1=1; } dem++; son[i]=ch; printf("%c",ch); s1[i]=son[i]-48; if(s1[0]==0) continue; i++; } len1=strlen(son); n1=(i-1); if((ch=='-')&&(!dau1)) { if (dem==0) { dau1=-1; } dem

Các file đính kèm theo tài liệu này:

  • docNhân hai số nguyên lớn - mô tả phép nhân tay.DOC