Niên luận số nguyên lớn 1

LỜI NÓI ĐẦU š&› Để hoàn thành niên luận này, bên cạnh sự nổ lực của bản thân cùng với sự kết hợp những kiến thức đã được học, quá trình tìm hiểu và thu thập thông tin có liên quan đến nội dung của đề tài niên luận. Mặt khác chúng em luôn nhận được sự giúp đỡ và hướng dẫn của thầy. Đã giúp em hoàn thành tốt niên luận này. Với sự nổ lực hết mình, em đã cố gắng hoàn thành niên luận này trong suốt thời gian qua. Do vốn hiểu biết còn hạn hẹp nên không tránh khỏi thiếu xót. Em rất mong sự góp ý kiến chân thành của quí thầy cô và các bạn đọc để niên luận Nhận Xét Của Giáo Viên Hướng Dẫn Bạc Liêu, ngày tháng năm 2010. Giáo viên hướng dẫn MỤC LỤC MỤC LỤC 1 I/GIỚI THIỆU 2 II/LÝ THUYẾT 3 III / LƯU ĐỒ KHỐI 8 IV / MÔT SỐ HÌNH ẢNH MINH HỌA TIẾN TRÌNH GIẢI THUẬT 22 V / KẾT LUẬN VÀ ĐÁNH GIÁ 24 VI/ TÀI LIỆU KHAM KHẢO 25 I/GIỚI THIỆU : Chương trình này được viết nhằm mục đích tính số nguyên lớn của dãy số được nhập vào bằng công thức cộng và trừ để cho ra kết quả mà người nhập muốn . II/LÝ THUYẾT: 1/Tính chất: Ký hiệu "b a" nghĩa là b là ước của a, ký hiệu a b nghĩa là a chia hết cho b. 1. Ước số . Chứng minh: Giả sử d a; d nhỏ nhất; d 1. Nếu d không nguyên tố d = d1.d2; d1, d2 > 1 d1|a với d1 < d: mâu thuẫn với d nhỏ nhất. Vậy d là nguyên tố. 2. Cho p là số nguyên tố; a N; a 0. Khi đó (a,p) = p (ap) (a,p) = 1 (ap) 3. Nếu tích chia hết cho một số nguyên tố p thì có ít nhất một thừa số chia hết cho p. p ai p 4. Ước số dương bé nhất khác 1 của một hợp số a > 1 là một số nguyên tố không vượt quá 5. Tập hợp các số nguyên tố là vô hạn. Chứng minh: Giả sử có hữu hạn số nguyên tố: p1 < p2 < ... < pn Xét a = p1.p2. ... pn + 1 Ta có: a > 1 và a ¹ pi; "i = Þ a là hợp số Þ a có ước nguyên tố pi, hay aMpi và ( pi) M pi Þ 1M pi: mâu thuẫn. Vậy tập hợp các số nguyên tố là vô hạn. Tuy nhiên, vì tập hợp số nguyên tố là tập con của số tự nhiên, mà tập hợp số tự nhiên là đếm được nên tập hợp các số nguyên tố là đếm được. 2/Các thao tác trên số nguyên: A/ Phép cộ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=10-x; 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=10-x; insertlist(d,k,l3); t=1; q=q->next; } } if(t==1) insertlist(1,k,l3); } int dem(list l) { position p; p= first(l); int s=0; while(p!=end(l)) { s=s+1; p=p->next; } return s; } void daoluon(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; } } B/ Phép trừ: 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); } III / LƯU ĐỒ KHỐI: Giải thuật đếm chuổi: P= first(l) ;s=0; Begin P!=end(l) s=s+1 ; p=p->next End đúng sai 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 Giải thuật trừ: 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 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 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 Giải thuật hiệu: 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 Giải thuật đảo begin p!=first(l1) p!=end(l1) insert(retrieve(p,l),first(ld),&ld) p=p->next printlist(ld) end đúng sai Giải thuật tổng chuổi: 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 IV / MÔT SỐ HÌNH ẢNH MINH HỌA TIẾN TRÌNH GIẢI THUẬT Màn hình hiển thị sau khi nhập 2 chuổi số nguyên và kết thúc bằng phím Enter: Màn hình hiển thị kết quả phếp tính tổng sau khi ấn phim 1: Màn hinh hiên thị sau khi ấn phím 2 để tính hiệu và ấn tiếp phím 1 để tính tổng: Màn hình hiển thị sau khi ấn phím số 3: V / KẾT LUẬN VÀ ĐÁNH GIÁ: I. KẾT QUẢ ĐẠT ĐƯỢC: - Về lý thuyết đã áp dụng được với giải thuật đồng thời kết hợp với ngôn ngữ lập trình để giải quyết hoàn chỉnh. - Về chương trình Demo: kết hợp giao diện thân thiện với người dùng và những công việc dễ dàng để người sử dụng dễ thực thi hơn. Cùng với những lời hướng dẫn để thực hiện chương trình trước khi chạy. - Qua đề tài niên luận này giúp em hiểu ra được một số vấn đề cần thiết trong khi lập trình và sửa được bài làm của mình để có thể hoàn chỉnh hơn. II. HẠN CHẾ: Do đây là lần đầu tiên em làm niên luận này. Với kiến thức còn hạn hẹp nên chương trình vẫn còn nhiều thiếu sót, chưa đáp ứng đầy đủ các yêu cầu của đề ra. Và chưa làm hoàn thành đúng những nội dung đó. III. HƯỚNG PHÁT TRIỂN: Hoàn chỉnh tốt chương trình mình thực hiện, cố gắng khắc phục những lỗi sai và cải thiện chương trình một cách nhanh chóng. Để có thể hoàn thành một chương trình đúng như yêu cầu của nội dung. Đồng thời, biết cách tạo ra những ý của riêng mình để chương trình chạy được hoàn thiện hơn. Vì vậy, hướng phát triển tiếp theo là hoàn thành chương trình ngày càng hoàn thiện đầy đủ chức năng. Phát triển chương trình đơn giản nhưng đầy đủ,làm giảm thiểu tối đa dung lượng. V/ Tài Liệu Kham Khảo: A.Aho,J.Ullman,Data Structues and Algorithms Wirth,Chương trình = Cấu trúc dữ liệu + Giải thuật Nguyễn Trung Trực,Cấu trúc dữ liệu – ĐHBK TP HCM Robert Sedgewick,Cẩm nang thuật toán 1,2.