Niên luận Số nguyên lớn

PHẦN I: TỔNG QUAN I.GIỚI THIỆU TỔNG QUAN: Có thể nói trong thời đại ngày nay, với sự phát triển nhanh chóng của công nghệ thông tin và một số lĩnh vực khác như :toán học, thiên văn học,…thì chúng ta phải đối mặt với việc phải tính toán những số liệu có thể lớn nhỏ khác nhau và đối với một số lĩnh vực số liệu nhỏ và ít thì ta có thể dung máy tính xách tay để tính toán. Nhưng máy tính xách tay chỉ giúp chúng ta tính toán những con số có độ dài chừng vài số đến vài chục số, còn trên thực tế như lĩnh vực thiên văn học, hóa học,vật lí, nguyên tử…, thì những con số cần được tính toán rất lớn và những số rất lớn như vậy được người ta đặt cho một tên gọi chung là “Số Nguyên Lớn”. Trong chương trình học của chúng ta thì chúng ta đã được giới thiệu các kiểu khai báo như: kiểu INT và giá trị tối đa từ -32768 đến 32767 tương ứng với (2 byte), kiểu short thì giá trị tối đa từ -32768 đến 32767 tương ứng với (2 byte), kiểu LONG thì giá trị tối đa từ -2147483648 đến 214783647 tương ứng với (2 byte), kiểu UNSIGUED thì giá trị tối đa từ 0 (byte) đến 255 (byte), kiểu FLOAT thì chứa tối đa từ 1,2E-38 đến 3,4E+38 tương ứng với (4 byte), kiểu DOUBLE thì chứa tối đa từ 2,2E-308 đến 1,8E+308 tương ứng với (8 byte), LONG DOUBLE thì chứa tối đa 3,4E-4932 đến 1,8E+4932 tương ứng với (10 byte)… Với tất cả các kiểu biến ở trên, thì ta có thể tính toán được những con số nhỏ, vừa, và tương đối lớn. Còn đối với những con số cực lớn thì những kiêu khai báo trên không thể nào chứa nổi, vì vậy đòi hỏi chúng ta phải thiết kế một chương trình (giải thuật) để xử lý những con số đó. Số nguyên lớn là một lĩnh vực mặc dù con người quan tâm từ rất sớm, nhưng đến nay để giải quyết trọn vẹn bài toán đó còn là một vấn đề đang được nghiên cứu. Riêng em, hiện đang là một sinh viên năm 3, với lượng kiến thực còn hạn hẹp của mình,và giới hạn về mặt thời gian của niên luận này và đây cũng là lần đầu tiên em nghiên cứu một đề tài có tính chất khoa học nên không tránh khỏi những sai sót. Em xin chân thành biết ơn sự hướng dẫn hết lòng của giáo viên hướng dẫn. Rất mong nhận được sự góp ý vô cùng quí báu của quí thầy cô, cùng toàn thể các bạn để chương trình của em được hoàn thiện hơn. II. MỤC TIÊU VÀ HƯỚNG GIẢI QUYẾT MỤC TIÊU CẦN ĐẠT ĐƯỢC Lý thuyết: Phải nắm vững và hiểu rỏ sử dụng thành thạo ngôn ngữ lập trình C. Đặt biệt là kiểu con trỏ (danh sách lien kết đơn), khai báo khiểu cấu trúc, kiểu chuỗi… trong cơ sở dữ liệu. Nắm rỏ cách thức tính cộng và trừ hai số nguyên. Phải tìm ra thuật toán đơn giản nhất mà hiệu quả. Chương trình Demo: Trương trình phải dể sử dụng, cung cấp giao diên thân thiện với người dùng. Cho phép tính toán một số nguyên lớn bất kì. Kết quả tính toan luôn chính xác. 2. HƯỚNG GIẢI QUYẾT - Dữ liệu dược nhập vào từ bàn phím ( dữ liệu đầu vào la một chuổi số). - Chuyển đổi chuổi vừa nhập thành từng số nguyên, cất từng số nguyên vào danh sách liên kết đơn. - Sử dụng những chương trình được cài đặc để xử lý. - Kết quả xuất ra là tổng và hiệu hai số nguyên lớn. PHẦN II: ỨNG DỤNG I.CƠ SỞ LÝ THUYẾT: Được sự hướng dẫn của giáo viên cùng với sự tìm tòi cùa bản thân thì em nhận thấy danh sách lien kết đơn phù hợp với yêu cầu của bài toán, vì trong danh sách liên kết đơn thì không giới hạn số phần tử không cần phải cấp phát ô nhớ trước dùng đến đâu thì cấp phát đến đó. Vì vây chúng ta không gặp phải trường hợp bị tràn hay bị thừa bộ nhớ … Trong quá trình thực hiện đề tài em có sử dụng một số hàm thư viện có sẵn trong cấu trúc dữ liệu. Bên cạnh đó em cũng đã tự thiết kế nên một số chương trình con đễ đáp ứng và giải quyết vấn đề cộng và trừ hai số nguyên lớn. II. CHƯƠNG TRÌNH CON MỘT SỐ HÀM TỰ ĐỊNH NGHĨA VÀ MỘT SỐ HÀM THƯ VIÊN Cấu trúc dữ liệu mới: Cài đặt cấu trúc node trong danh sách liên kết typedef struct node { elementtype element; node* next; node* prev; } Các chương trình con tự định nghĩa và lưu đồ khối kèm theo: Hàm đếm chiều dài của chuổi số nguyên: Đoạn code của hàm: int dem(list l) { position p; p= first(l); int s=0; while(p!=end(l)) { s=s+1; p=p->next; } return s; } P= first(l) ;s=0; Begin P!=end(l) s=s+1 ; p=p->next End đúng sai - Lưu đồ khối của hàm: Hàm đảo chuổi số nguyên: Đoạn code của hàm: void dao(list l) { list ld; makenulllist(&ld); position p; p= first(l); elementtype x; while(p!= end(l)) { insertlist(retrieve(p,l),first(ld),&ld); p=p->next; } printf("\n\n day so vua nhap la:"); printlist(ld); printf("\n\n"); } - Lưu đồ khối của hàm: begin p!=first(l1) p!=end(l1) insert(retrieve(p,l),first(ld),&ld) p=p->next printlist(ld) end đúng sai Hàm hiệu chuổi a và b: Đoạn code của hàm: void hieu(list l1,list l2,list *l4) { position p,q,c,d; p= first(l1); q= first(l2); c= end(l1); d= end(l2); int H; if(dem(l1)>dem(l2)) tru(l1,l2,l4); else if(dem(l1)<dem(l2)) { printf("\n -"); tru(l2,l1,l4); } else if(dem(l1)==dem(l2)) { while(p!=end(l1)) { if(retrieve(p,l1)!=retrieve(q,l2)) { H=1;break; } else if(retrieve(p,l1)==retrieve(q,l2)) { H=0; p=p->next; q=q->next; } } if(H==0) { printf("\n\t 0 (Hai so vua nhap bang nhau!!)"); getch(); } while(d!=first(l2)) { if((retrieve(c,l1))<(retrieve(d,l2))) { printf("\n - "); tru(l2,l1,l4);break; } else if(retrieve(c,l1)>retrieve(d,l2)) { tru(l1,l2,l4);break; } c=c->prev; d=d->prev; } begin P= first(l1) ; q=first(l2) dem(l1)>dem(l2) A tru(l1,l2,l4) dem(l1)<dem(l2) printf(“ - “) tru(l2,l1,l4) dem(l1)=dem(l2) đúng đúng đúng sai sai } } - Lưu đồ khối của hàm: p!=end(l1) daoluon(&l1) A daoluon(&l2) retrieve(p,l1)!=retrieve(q,l2) H =0 H=1; break; p=p->next;q=q->next; H=0 0 end đúng đúng đúng sai sai sai B B retrieve(p,l1)>retrieve(q,l2) daoluon(&l1) daoluon(&l2) tru(l1,l2,l4) retrieve(p,l1)<retrieve(q,l2) daoluon(&l1) daoluon(&l2) tru(l2,l1,l4) printf(“ - “) đúng đúng sai Hàm trừ hai so nguyên a và b: Code của hàm: void tru(list l1,list l2,list *l3) { position p,q,k; p= first(l1); q= first(l2); k= first(*l3); elementtype x; int m=10,t=0; while((p!=end(l1))&&(q!=end(l2))) { if((retrieve(p,l1))==(retrieve(q,l2))) { if(t==1) { insertlist(9,k,l3); t=1; p=p->next; q=q->next; } else if(t==0) { insertlist(0,k,l3); t=0; p=p->next; q=q->next; } } else if((retrieve(p,l1))>(retrieve(q,l2))) { x= retrieve(p,l1)-(retrieve(q,l2)+t); insertlist(x,k,l3); t=0; p=p->next; q=q->next; } else if((retrieve(p,l1))<(retrieve(q,l2))) { x= (m+retrieve(p,l1))-(retrieve(q,l2)+t); insertlist(x,k,l3); t=1; p=p->next; q=q->next; } } while(p!=end(l1)) { if(t==1) { if(retrieve(p,l1)>=1) { x= retrieve(p,l1)-t; t=0; insertlist(x,k,l3); p=p->next; } else { insertlist(9,k,l3); t=1; p=p->next; } } else if(t==0) { insertlist(retrieve(p,l1),k,l3); p=p->next; } } printlist(*l3); } - Lưu đồ khối của hàm: P= first(l1) ; q=first(l2);k=first(l3);m=10;t=0 Begin P!=end(l1)&&q!=end(l2) p=p->next;q=q->next; t=1 retrieve(p,l1)= =retrieve(q,l2) t= =1 t= =0 p=p->next;q=q->next; t=0 A B insertlist(9,k,l3) insertlist(0,k,l3) đúng đúng đúng đúng sai sai sai B retrieve(p,l1)>retrieve(q,l2) x =retrieve(p,l1) – (retrieve(q,l2) + t) insertlist(x,k,l3) p=p->next;q=q->next; t=0 p!=end(l1)&&q!=end(l2) C đúng sai retrieve(p,l1)<retrieve(q,l2) x =(m+retrieve(p,l1)) – (retrieve(q,l2) + t) insertlist(x,k,l3) p=p->next;q=q->next; t=1 P!=end(l1)&&q!=end(l2) C đúng p!=end(l1)&& p=p->next ; t=0 insertlist(x,k,l3) A t= =1 retrieve(p,l1) > =1 x =retrieve(p,l1) - t insertlist(9,k,l3) p=p->next ; t=1 D đúng đúng đúng sai sai D t= =0 insertlist (retrieve(p,l1),k,l3) p=p->next ; t=0 p!=end(l1)&& printlist(l3) End đúng đúng Hàm tính tổng hai so a và b: Code của hàm tính tổng: void cong(list l1,list l2,list *l3) { makenulllist(l3); position p,q,k; p= first(l1); q= first(l2); k= first(*l3); elementtype x,d,t=0; while(p!=end(l1)&&q!=end(l2)) { x= (retrieve(p,l1))+(retrieve(q,l2))+t; if(x<=9) { insertlist(x,k,l3); t=0; p=p->next; q=q->next; } else { d=x-10; insertlist(d,k,l3); t=1; p=p->next; q=q->next; } } while(p!=end(l1)) { x=retrieve(p,l1)+t; if(x<=9) { insertlist(x,k,l3); t=0; p=p->next; } else { d=x-10; insertlist(d,k,l3); t=1; p=p->next; } } while(q!= end(l2)) { x=retrieve(q,l2)+t; if(x<=9) { insertlist(x,k,l3); t=0; q=q->next; } else { d=x-10; insertlist(d,k,l3); t=1; q=q->next; } } if(t==1) insertlist(1,k,l3); } Lưu đồ khối của hàm tính tổng: p= first(l1) ; q=first(l2);k=first(l3);t=0 Begin p!=end(l1)&&q!=end(l2) p=p->next;q=q->next; t=0 x<=9 p=p->next;q=q->next; t=1 A insertlist(x,k,l3) insertlist(d,k,l3) đúng đúng đúng đúng sai sai x= retrieve(p,l1)+retrieve(q,l2)+t d = x-10 A p!=end(l1) x= retrieve(p,l1)+t x<=9 insertlist(x,k,l3) p=p->next; t=0 p=p->next;t=1 insertlist(d,k,l3) d = x-10 A B đúng đúng sai sai A q!=end(l2) x= retrieve(q,l2)+t x<=9 insertlist(x,k,l3) q=q->next; t=0 q=q->next;t=1 insertlist(d,k,l3) d = x-10 B đúng đúng sai sai x<=9 insertlist(x,k,l3) end sai đúng PHẦN III: KẾT LUẬN I. NHẬN XÉT KẾT QUẢ ĐẠT ĐƯỢC 1)Phần lý thuyết: Bước đầu đã vận dụng chuyển đổi từ ngôn ngữ tự nhiên sang ngôn ngữ máy và đã thành công. Trên mặt lý thuyết thì giải thuật đã được kiểm chứng bởi chương trình là hoàn toàn đúng, áp dụng các dãy thuật kết hợp với thiết kế chương trình trên ngôn ngữ C (cấu trúc dữ liệu) và đã được kiểm chứng là đúng. Sử dụng các kiểu khai báo phù hợp vói yêu cầu của đề tài. 2)Phần chương trình nguồn: Sử dụng các hàm các thủ tục quen thuộc, câu lệnh đơn giản, ngắn gọn. Chương trình dể đọc dể hiểu, chỉnh sửa dể dàng. 3)Phần chương trình demo: Dể sử dụng. Giao diện thân thiện với người dùng. Kết quả luôn chính xác. 4)Bài học kinh nghiệm: Qua việc thực hiện niên luận này giúp em hiểu được nhiều hơn kĩ hơn về ngôn ngữ lập trình C. Biết dược nhiều vấn đề mới. Nâng cao khả năng tự học tìm tòi. Giúp em có thể giải quyết nhiều vấn đề khó trong thực tiễn bằng cách chuyễn đỗi những vấn đề đó thành chương trình và cuối cùng là nhờ khả năng xử lý của máy tính để giải quyết… II.NHỮNG MẶT CÒN HẠN CHẾ: Vì đây là đề tài đầu tiên nên có những điểm giải quyết vấn đề chưa thật tối ưu. Vì thời gian hạn hẹp nên có những vấn đề em tìm hiểu chưa sâu và rộng nên sử lý vấn đề chưa thật tối ưu. Giải thuật có nhiều nơi còn hơi dài dòng quanh co. Chưa áp dụng triệt để khả năng đồ họa trong C. Trình bày chưa thật sự thuyết phục người đọc. III.ƯU ĐIỂM: Chương trình dể đọc dể hiểu, chỉnh sửa dể dàng. Không giới hạn chiều dài chuỗi số nguyên. Chương trình xử lý nhanh. Tốn it bộ nhớ. Tính toán chính xác. IV.HƯỚNG PHÁT TRIÊN: Cải tiến giải thuật đến mức tối ưu nhất. Áp dụng khả năng đồ họa trong C để chương trình nhìn bắt mắc hơn thân thiện với người sử dụng. Phát triển giải thuật tổng hợp nhập 2 số nguyên và thực hiên phép toán cộng trừ nhân chia… Đọc số nguyên từ một tập tin bất kì.