Tối giản một phân số trong C

[mylinhnguyen.hvt]

. Trong một chương trình, viết các hàm tìm ước số chung lớn nhất và bội số chung nhỏ nhất của hai số a, b và sử dụng trong các bài toán:
a. Tối giản một phân số
b. Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của dãy n số nguyên dương nhập từ bàn phím

[zxfantaxz]

Ủa cái này là đố chơi cho vui hay sao vậy. ^^

[kaka1951989]

y cua ban la nhu the nao hả.chẳng hiểu

[kimduquan]

giải thuật tìm ước chung lớn nhất của a,b:(a>b)
lấy a-b,rồi so sánh a-b với b,số nào lớn hơn thì trừ số còn lại,rồi tiếp tục so sánh hiệu đó với số còn lại đó,lặp lại cho đến khi a=b.ước chung lớn nhất lúc này =a=b.Nếu a<b thì thay thế vị trí của 2 số.Tối giản phân số chẳng qua là tìm ước chung lớn nhất của tử và mẫu rồi chia cả tử và mẫu cho số đó.

[pdah]

giải thuật tìm ước chung lớn nhất của a,b:(a>b)
lấy a-b,rồi so sánh a-b với b,số nào lớn hơn thì trừ số còn lại,rồi tiếp tục so sánh hiệu đó với số còn lại đó,lặp lại cho đến khi a=b.ước chung lớn nhất lúc này =a=b.Nếu a<b thì thay thế vị trí của 2 số.Tối giản phân số chẳng qua là tìm ước chung lớn nhất của tử và mẫu rồi chia cả tử và mẫu cho số đó.

Làm cách này mà với a = 10^10 và b = 2 thì chạy cũng mệt nghỉ đó bác :p
Cách tìm ước chung lớn nhất tốt nhất mà tui biết là thực hiện dãy các phép chia có dư dựa trên thuật toán Euclid : http://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_Euclid

[zxfantaxz]

Giải thuật ước chung lớn nhất (a,b), với a>b:
-lấy (a%b)(chia lấy dư)=x:
Chia trường hợp ra:
1.b%x==0 &a%x==0 thì x là đáp số.
2.b%(x/2)==0 &a%x/2==0 thì x/2 là đáp số.
3.b%y(y<x/2)==0 & a%y==0 thì y là đáp số.

[kimduquan]

Theo mình cách của mình đã trình bày chỉ nên áp dụng cho trường hợp a/b>b và a%b!=0 thôi còn dối với trường hợp a/b<b và a%b!=0thì nên áp dụng cách đơn giản nhất đó là chia 2 số cho 2,3,5,7,9,...nếu a%i=b%i=0 thì ucln=i( kĩ thuật đặt cờ hiệu) còn cái ví dụ của bạn là trường hợp a%b=0 nên ko tính.

[nh0cbilly]

ý tưởng của tui về bài trên là như sau:
viết hàm tính USCLN ( dùng thuật toán o'clit ( hình như viết sai)). sau đó viết hàm BSCNN bằng cách lấy (a*b)/(USCLN(a,b)). Sau khi nhập tử và mẫu bạn phải lấy trị tuyệt đối của nó. xong rồi tìm USCLN của 2 số vừa lấy trị tuyệt đối xong. rồi lấy a và b chia cho USCLN sau đó in kq ra màn hình.
Lưu ý: nếu mẫu số là 1 ( tức USCLN==mẫu) thì chỉ int tử thôi.

Còn câu b thì tìm USCLN của 2 số đầu sau đó tìm tiếp USCLN của số tiếp theo với ước chung lớn nhất của 2 số đầu. Cứ như vậy tới số cuối cùng là xong. Tương tự đối với tìm BSCNN của n số.
Chúc thành công. Nếu làm xong mà chạy không được thì post lên đây để anh em mình giải quyết.

[k2cdtin]

các bạn co thể tham khảo bai nay cua mình.no chay đúng đấy:

#include<stdio.h>
#include<conio.h>
unsigned int ucln_2so(unsigned int a, unsigned int b)
{ unsigned int ucln;
ucln=1;
while(a!=b)
if(a>b) a=a-b; else b=b-a;
ucln=a;
return ucln;
}
void main()
{ unsigned int a,b;
clrscr();
printf("KIEM TRA PHAN SO TOI GIAN CHUA?\n");
printf("Ban nhap tu so: "); scanf("%u",&a);
printf("Ban nhap mau so: "); scanf("%u",&b);
if(ucln_2so(a,b)>1)
printf("Phan so chua toi gian. Phan so duoc toi gian thanh: %u/%u ",a/ucln_2so(a,b),b/ucln_2so(a,b));
else printf("Phan so da toi gian");
getch();
}

có gì cho mình ý kiến nhé. mình làm nó chạy đúng rồi. co bạn nào có cách khác tốt hơn ko?

[zxfantaxz]

Đây là code của câu a & câu b:


#include <stdio.h>
#include <conio.h>
#define MAX 100
int ucln(int,int);
int ucln(int a, int b)
{
int s;
if(a==b)
return a;
if(a%b==0 && a>b)
return b;
s=a%b;
a=s;
if(a>b)
return ucln(a,b);
else
ucln(b,a);
}
int main()
{

int tam,tam1,tam2=1,tam3,tamx;
int chuoiso[MAX];
int a,b,i,j,n;
printf("nhap a: ");
scanf("%d",&a);
printf("nhap b: ");
scanf("%d",&b);
printf("ucln cua a & b la: %d",ucln(a,b));
printf("\nnhap tu so a: ");
scanf("%d",&a);
printf("nhap mau so b: ");
scanf("%d",&b);
printf("a/b= %d/%d",(a/ucln(a,b)),(b/ucln(a,b)));
printf("\nban can nhap bao nhieu so? ");
printf("n = ");
scanf("%d",&n);

for(i=0;i<n;i++)
{
printf("nhap so thu %d: ",i+1);
scanf("%d",&chuoiso[i]);
}

for(i=1;i<n;i++)
if(chuoiso[0]>chuoiso[i])
{
tam = chuoiso[0];
chuoiso[0]=chuoiso[i];
chuoiso[i]=tam;
}

for(i=1;i<n;i++)
if(tam1 <ucln(chuoiso[0],chuoiso[i]))
tam1 =ucln(chuoiso[0],chuoiso[i]);

for(i=tam1;i>0;i--)
{

for(j=0;j<n;j++)
{
if(chuoiso[j]%i==0)
{
if(j==n-1)
{
printf("ucln cua chuoi n la: %d",i);
tamx=i;
goto end;
}
continue;
}
else
break;
}

}
end:


for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(chuoiso[i]==chuoiso[j])
chuoiso[j]=tamx;
for(i=0;i<n;i++)
tam2*=(chuoiso[i]/tamx);

tam2*=tamx;
for(i=1;i<tamx;i++)
if(tam2%i==0&&tam2!=tamx)
{
tam2=tam2/i;
break;
}
printf("\nbcnn cua chuoi n la: %d", tam2);




getch();
return 0;
}

Nếu có sai sót xin các bạn góp ý cho.

[nh0cbilly]

các bạn co thể tham khảo bai nay cua mình.no chay đúng đấy:

#include<stdio.h>
#include<conio.h>
unsigned int ucln_2so(unsigned int a, unsigned int b)
{ unsigned int ucln;
ucln=1;
while(a!=b)
if(a>b) a=a-b; else b=b-a;
ucln=a;
return ucln;
}
void main()
{ unsigned int a,b;
clrscr();
printf("KIEM TRA PHAN SO TOI GIAN CHUA?\n");
printf("Ban nhap tu so: "); scanf("%u",&a);
printf("Ban nhap mau so: "); scanf("%u",&b);
if(ucln_2so(a,b)>1)
printf("Phan so chua toi gian. Phan so duoc toi gian thanh: %u/%u ",a/ucln_2so(a,b),b/ucln_2so(a,b));
else printf("Phan so da toi gian");
getch();
}

có gì cho mình ý kiến nhé. mình làm nó chạy đúng rồi. co bạn nào có cách khác tốt hơn ko?

cho tôi góp ý với bạn 1 chút nha :) bài của bạn chạy chính xác nhưng nó ko thể thao tác trên số âm, cách khắc phục là dùng abs() của math.h . Thứ hai, nếu mẫu số bằng 1 thì ko lẽ in ra a/1 và cuối cùng là in kq ra chính xác bất kể a và b âm hay dương.Đây là code của mình ( dựa theo code của bạn ). Tất nhiên đây ko phải là tối ưu nhất vì nó quá dài.

#include <stdio.h>
#include <conio.h>
#include <math.h>
int ucln_2so(unsigned int a, unsigned int b)
{
int ucln;
ucln=1;
while(a!=b)
if(a>b)
a=a-b;
else
b=b-a;
ucln=a;
return ucln;
}
void main()
{
int a,b,r;
printf("KIEM TRA PHAN SO TOI GIAN CHUA?\n");
printf("Ban nhap tu so: "); scanf("%d",&a);
printf("Ban nhap mau so: "); scanf("%d",&b);
r=ucln_2so(abs(a),abs(b));
if(r>1)
{
printf("Phan so chua toi gian.");
if(abs(b)==r)
{
if(a>0 && b<0)
printf("\nPhan so duoc toi gian thanh: -%d ",abs(a)/r);
if(a>0 && b>0)
printf("\nPhan so duoc toi gian thanh: %d ",a/r);
if(a<0 && b<0)
printf("\nPhan so duoc toi gian thanh: %d ",abs(a)/r);
if(a<0 && b>0)
printf("\nPhan so duoc toi gian thanh: -%d ",abs(a)/r);
}
else
{
if(a>0 && b<0)
printf("\nPhan so duoc toi gian thanh: -%d/%d ",abs(a)/r,abs(b)/r);
if(a>0 && b>0)
printf("\nPhan so duoc toi gian thanh: %d/%d ",a/r,b/r);
if(a<0 && b<0)
printf("\nPhan so duoc toi gian thanh: %d/%d ",abs(a)/r,abs(b)/r);
if(a<0 && b>0)
printf("\nPhan so duoc toi gian thanh: -%d/%d ",abs(a)/r,abs(b)/r);
}

}
else
printf("Phan so da toi gian");
getch();
}


lần sau bạn viết code để trong
chương trình để anh em dễ text hơn.

[huutho.tp]

dùng lệnh cout,cin làm đi.dùng những lệnh này em kô bít gì hết a.
các anh chị ghi rõ ý nghĩa của mỗi lệnh luôn cho em nha.Thank

[thuydung170589]

bài bạn làm trong C phải không?Mình làm cấu trúc dữ liệu trong C, còn lập trình hường đối tượng trong C++.
bài này dùng thuật toán oclit la nhanh nhat va ngắn nhất, thầy mình có dạy dùng quá tải cho nhanh hơn, có đi cùng là struct nua, mà chưa viết được.
cảm ơn các bạn đã gửi code này, để mình thử xem rùi gửi trao đổi nghen

[trung151087]

int USCLN(int a,int b)
{
int x = abs(a),y = abs(b),tam;
int n = x<y?x:y;
for(int i = n; i > 0; --i)
if((x%i==0) &&(y%i) == 0)
{
tam = i;
break;
}
return (tam);
}

[Than Dieu]

Xem cái bài thảo luận này xem:
Tối giản phân số trên C (http://forums.congdongcviet.com/showthread.php?t=1690)

Chúc may mắn!

[cuongkh]

. Trong một chương trình, viết các hàm tìm ước số chung lớn nhất và bội số chung nhỏ nhất của hai số a, b và sử dụng trong các bài toán:
a. Tối giản một phân số
b. Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của dãy n số nguyên dương nhập từ bàn phím

b. tim UCLN

int UCLN( int a; int b)
{
if(a<b)
{
int c=a;a=b;b=c;
};
else
if(a>=b)
{
if((a mod b)==0) return b;
else
return UCLN(b; a mod b);
};
};
void main()
{
int n,a[1000];
printf("nhap so phan tu n= ");scanf("%d",&n);
printf("nhap gia tri cho tung phan tu:\n");
for(int i=1;i<=n;i++)
{
printf("\na["%d"]:=",i); scanf("%d",&a[i]);
};
int uc=UCLN(a[1];a[2]);
for(i=1;i<n;i++)uc=UCLN(uc;a[i+1])
printf("uoc chung lon nhat cua day so la:%d",uc);
int bc=1;
for(i=1;i<=n;i++)bc*=a[i];
for(i=1;i<n;i++)bc/=uc;
printf("boi chung nho nhat la: %d",bc);
};