Đề bài tập:
Viết chương trình cộng và nhân 2 số nguyên vô cùng lớn (hàng chục chữ số), dùng Danh sách liên kết đôi (C++). Áp dụng tính giai thừa, lũy thừa vô cùng lớn.
Powered by Nguyen Le Anh Tuan.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
typedef int datatype ;
typedef struct _node{
datatype Info ;
_node *pNext ;
_node *pPre ;
} Node ;
typedef Node *nodePtr ;
/*
* tao mot cau truc gom hai con tro chiu trach nhiem tro vao dau vao cuoi danh sach
* pHead : tro vao dau danh sach
* pTail : tro vao cuoi danh sach
*/
typedef struct num {
nodePtr pHead ;
nodePtr pTail ;
int size;
} Ptr ;
void Init(Ptr &ptr){
ptr.pHead = NULL ;
ptr.pTail = NULL;
ptr.size = 0;
}
/*
* Ham tao mot node moi
*/
nodePtr createNode(datatype x){
nodePtr p = new Node ;
p ->Info = x ;
p ->pPre = NULL ;
p ->pNext = NULL ;
return p ;
}
/*
* Ham chen dau
* y tuong :
* neu pHead ma rong thi gan node can chen vao pHead
* nguoc lai thuc hien qua trinh chen nhu binh thuong
*/
void insertFirst(Ptr &ptr, datatype x ){
nodePtr p = createNode(x);
if(ptr.pHead == NULL)
ptr.pHead = ptr.pTail = p ;
else{
p -> pNext = ptr.pHead ;
ptr.pHead ->pPre = p ;
ptr.pHead = p ;
}
}
/*
* Ham chen vao sau danh sach
* y tuong tuong tu nhu o ham chen dua nhung thao tac voi con tro pTail
*/
void insertAfter(Ptr &ptr, datatype x){
nodePtr p = createNode(x);
if(ptr.pHead ==NULL)
ptr.pHead = ptr.pTail = p ;
else{
ptr.pTail -> pNext = p ;
p -> pPre = ptr.pTail ;
ptr.pTail = p ;
}
}
void delNode(Ptr a){
nodePtr p ;
while(a.pHead != NULL){
p = a.pHead ;
a.pHead = a.pHead -> pNext ;
delete p ;
}
}
/*
* thuc hien thao tac nhap
* y tuong :
* nhap cho den khi nao gap so am thi dung lai
* thuc hien thao tac nahp bang cach dung ham insertAfter da tao o tren
*/
void dataInput(Ptr &ptr){
datatype x;
int size = 0;
Init(ptr);
do{
scanf("%d",&x);
if(x >= 0) {
insertAfter(ptr,x);
size++;
}
}
while(x >= 0);
ptr.size = size;
}
/*
* ham xuat danh sach lien ket
* Do ham nhap thuc hien thao tac chen cuoi nen o ham xuat nay ta phai lay ra tu dau
*/
void dataOutput(Ptr ptr){
nodePtr p = ptr.pHead;
// printf("[size = %d] ", ptr.size);
while(p != NULL){
printf("%d" , p ->Info);
p = p -> pNext;
}
}
/*
* Ham cong hai so vo cung lon
* y tuong :
* nhap vao 2 dslk doi , cho chay tu cuoi dslk
* tien hanh cong tung node va mod 10 gan cho cho dslk thu 3
* neu ket qua phep cong > 10 thi ket qua cua phep cong sau + 1
* Neu 1 trong 2 day dat NULL truoc day kia thi thuc hien chen them cac gia tri 0
*/
Ptr add(Ptr ptr1 , Ptr ptr2 ){
datatype x , t;
Ptr ptr3;
Ptr flag1 ;
Init(flag1);
Ptr flag2 ;
Init(flag2);
nodePtr p1 = ptr1.pTail;
nodePtr p2 = ptr2.pTail;
datatype temp = 0 ;
Init(ptr3);
int size = 1 ;
do {
if(ptr1.size > ptr2.size)
size = ptr1.size ;
else
size = ptr2.size ;
t = (p1->Info + p2 ->Info )%10 + temp ;
insertFirst(ptr3,t);
temp = (p1 ->Info + p2 ->Info )/10;
p1 = p1->pPre;
p2 = p2->pPre;
} while(p1 != NULL && p2 != NULL) ;
nodePtr c = (p1 == NULL) ? p2 : p1;
while (c != NULL) {
int sum = c->Info + temp;
insertFirst(ptr3, sum % 10);
temp = sum / 10;
c = c->pPre;
}
if(temp == 1){
insertFirst(ptr3,1);
size =size +1 ;
}
ptr3.size = size ;
return ptr3 ;
}
/*
* ham nay dung de nhan hai dslk
* y tuong :
* cho 1 phan tu day 2 nhan tuan tu voi tat ca cac phan tu cua 1
* sau moi phep nhan dung dslk trung gian de luu giu gia tri
* cong tat ca cac danh sanh trung gian lao voi nhau
* khi cong cac danh sach lai voi nhau dung ham Move de chen gia tri 0 vao
*/
void move(Ptr &m , datatype x , datatype n){
while(n > 0){
insertAfter(m,x);
n-- ;
}
/// Thêm n so 0 nen chieu dai cua so phai cong them n
m.size += n;
}
Ptr mul(Ptr n1 , Ptr n2){
Ptr flag1 ; // day la con tro chua gia tri trung gian cua Sum
Init(flag1);
Ptr flag2 ; // day la con tro chua gia tri trung gian cua last
Init(flag2);
Ptr last ; // dslk chua ket qua
Init(last);
int step = 0;
nodePtr n = n2.pTail;
datatype t ,k; // bien luu gia tri nho
insertFirst(last,0); // khoi tao mac dinh cho dslk
/// Chen so 0 so nen chieu dai last tang len 1
last.size++;
while(n != NULL){
Ptr sum ;
Init(sum);
nodePtr m = n1.pTail;
datatype temp = 0 ;
while(m != NULL){
t = ((n-> Info * m->Info) + temp) % 10;
insertFirst(sum ,t);
temp = (n -> Info * m->Info +temp)/10 ;
m = m->pPre ;
///
sum.size++;
}
if(temp > 0) {
insertFirst(sum,temp);
///
sum.size++;
}
move(sum , 0 , step++);
flag1 = sum ; // gan gia tri trung gian
flag2 = last ;
last = add(sum, last);
delNode(flag1); // lam sach bo nho cua chuoi sum
delNode(flag2); // lam sach bo nho cua chuoi last
n = n -> pPre ;
}
return last ;
}
/**
* bai nay dung de tinh giai thua cua mot so
* y tuong :
* dung ham Sub de giam gia tri cua so do xuong mot don vi
* dung dslk trung gian de luu giu gia tri cia bai toan
* sau do return ve gia tri do
*/
/**
* Ham nay dung de tinh luy thua cua mot so
* y tuong :
* dung ham Compare de so sanh xem viec nhan so do voi chinh no da het chua
* neu Compare == 0 co nghia la da nhan het so luot
*/
datatype Compare(Ptr c1 , Ptr c2){
// so sanh hai kich thuoc chuoi
if(c1.size > c2.size)
return 1 ;
if(c1.size < c2.size)
return -1;
nodePtr a = c1.pHead ;
nodePtr b = c2.pHead ;
while(a != NULL || b != NULL) {
if(a ->Info != b ->Info){
int valA = a ->Info ;
int valB = b ->Info ;
if(valA > valB)
return 1 ;
if(valA < valB)
return -1 ;
}
a = a -> pNext ;
b = b -> pNext ;
}
return 0 ;
}
Ptr Power(Ptr p , Ptr m){
// bien nay luu ket qua
Ptr temp1 ;
Init (temp1);
Ptr temp2 ;
Init (temp2);
Ptr Res ;
Init(Res);
insertFirst(Res,1);
/// Them so 1 nen chieu dai phai tang len 1
Res.size++;
// bien nay luu bien dem
Ptr Dem ;
Init(Dem);
insertFirst(Dem,0);
/// Them so 0 nen chieu dai phai tang len 1
Dem.size++;
Ptr ad ;
Init(ad);
// bien nay luu bien cong
/// Moi lan cong 1 nen phai them so 1 vao ad
insertFirst(ad,1);
/// Cap nhat lai chieu dai cua ad
ad.size++;
while( Compare(Dem,m) != 0 ){
temp1 = Res ;
Res = mul(Res,p);
temp2 = Dem ;
Dem = add(Dem,ad);
delNode(temp1);
delNode(temp2) ;
}
return Res ;
}
/**
* Ham nay dung de tinh giai thua cua mot so lon
* y tuong :
* dung 1 dslk [ Res ] de luu ket qua
* dung 1 dslk [ Dem ] de tang gia tri so giai thua len tu 1 -> f
* Dung 2 dslk [ flag1 ],[flag2 ] de lam sach bo nho sau khi thuc hien tinh toan
*/
Ptr fac(Ptr &f){
Ptr flag1 ; // dung de lam sach Res
Init(flag1);
Ptr flag2 ;
Init(flag2); // dung de lam sach Dem
Ptr Dem ;
Init(Dem);
insertFirst(Dem,1);
Dem.size++;
Ptr ad;
Init(ad);
insertFirst(ad,1);
ad.size++; // sau khi them mot phan tu Node thi size tang 1
Ptr Res ;
Init(Res);
insertFirst(Res,1);
Res.size ++ ;
while(Compare(f,Dem) != 0){
flag2 = Dem ;
Dem = add(Dem,ad) ;
delNode(flag2); // xoa dslk lien ket khong can thiet de lam sach bo nho
flag1 = Res ;
Res = mul(Res,Dem);
delNode(flag1);
}
return Res ;
}
int main(){
clrscr();
Ptr n1;
Ptr n2;
Init(n1);
Init(n2);
int Choice , size;
datatype x ,p1,p2;
printf(" -------------------------------------\n");
printf("| nhap vao lua chon cua ban :|\n");
printf(" -------------------------------------\n");
printf("| nhap 1 : cong hai so :|\n");
printf("| nhap 2 : nhan hai so :|\n");
printf("| nhap 3 : tinh giai thua mot so :|\n");
printf("| nhap 4 : tinh luy thua cua mot so :|\n");
printf("| nhap 5 : thoat: :|\n");
printf(" --------------------------------------\n");
scanf("%d",&Choice);
switch(Choice){
case 1 :printf("nhap vao so am neu muon ket thuc so , moi chu so cach nhau boi phim Enter hoac Backspace:\n");
printf("Nhap vao day 1 :\n");
dataInput(n1);
printf("Nhap vao day 2 :\n");
dataInput(n2);
printf("Xuat dap so :\n");
printf("-------------- :\n");
dataOutput(n1);
printf("+");
dataOutput(n2);
printf("=");
dataOutput(add(n1,n2));
break ;
case 2 :printf("nhap vao so am neu muon ket thuc so , moi chu so cach nhau boi phim Enter hoac Backspace:\n");
printf("Nhap vao day 1 :\n");
dataInput(n1);
printf("Nhap vao day 2 :\n");
dataInput(n2);
printf("Xuat day :\n");
printf("-------------- :\n");
dataOutput(n1);
printf(" * ");
dataOutput(n2);
printf(" = ");
dataOutput(mul(n1,n2)) ;
break ;
case 3 :
printf("nhap vao so am neu muon ket thuc so , moi chu so cach nhau boi phim Enter hoac Backspace:\n");
dataInput(n1);
printf("Xuat ket qua :\n");
printf("-------------- :\n");
dataOutput(n1);
printf("! =");
dataOutput(fac(n1));
break ;
case 4 :
printf("nhap vao so am neu muon ket thuc so , moi chu so cach nhau boi phim Enter hoac Backspace:\n");
printf("Nhap vao day 1:\n");
dataInput(n1);
printf("Nhap vao day 2:\n");
dataInput(n2);
printf("Xuat day :\n");
printf("-------------- :\n");
dataOutput(n1);
printf(" ^ ");
dataOutput(n2);
printf(" = ");
dataOutput(Power(n1,n2));
break ;
case 5 :
break ;
}
getch();
return 0;
}
Mời các bạn tham gia đóng góp xây dựng.
Labels:
Học tập
