PDA

View Full Version : [C++] tính căn bậc hai bằng 1 biến



Sieg
18-01-2008, 09:58 PM
Hôm này đi phỏng vấn , mấy ổng hỏi cách tính căn bậc hai bằng 1 biến => bó tay chịu thua , ở đây có ai biết cách tính không chỉ giùm với . thx :D:D

huynguyen
18-01-2008, 10:51 PM
Cái này phải học thêm Toán Đại số rùi, sorry, mình cũng chưa nghiên cứu qua nhưng nhớ là trong môn Đại số và Số học đã học vụ này rồi.

Kevin Hoang
18-01-2008, 11:05 PM
Sao không làm thế này: x^2 = exp(2*ln(x))

Có mỗi biến x thôi ah. Đáp ứng yêu cầu, còn chuyện có đúng ý nhà tuyển dụng không thì chịu.

huynguyen
19-01-2008, 12:14 AM
Ặc, Dream lúc này bị bệnh nặng quá rồi. Về úp mặt vào tường đi, nghe chưa.
Bài toán căn bậc 2 mà ông đem bài lũy thừa 2 vào làm gì?
Ý của người này hỏi là ko dùng hàm toán học, chỉ 1 biến thôi thì làm sao ra được, tức là chỉ dùng + - * / thôi. Chứ ai điên lại ko dùng sqrt mà dùng exp với ln?

Kevin Hoang
19-01-2008, 01:31 AM
Nếu theo toán học làm sao mà có thể dùng một biến tính được chứ?
Ờ mà hôm nay cũng hay lẫn lộn lung tung cả. Ở trên nghĩ là 1/2 thế mà lại viết là 2. Hôm nay giá mà đi phỏng vấn chắc cũng toi, thôi khuya rồi, up mặt xuống dường ngủ đây.

Người ta chỉ yêu cầu viết hàm tính căn bậc 2 với một biến thôi mà. Với câu hỏi đó, Dr sẽ làm như thế này đó.

sqrt(x)==x^1/2
=>sqrt(x)=exp(0.5*ln(x))
Duy nhất có mỗi biến x ngoài ra không có biến nào khác cả.

Còn nếu là toán học thì nó phải có ít nhất là 2 biến mới tính được?

Không biết biến đối số có được coi là biến ở đây không? Nếu không thì có nhiều cách đó.

trungtin
19-01-2008, 09:04 AM
Theo như mình nhớ khi học toán đại số có phép tính thủ công căn bậc 2 như sau:lấy một số bất kỳ chia cho 2,chia cho đến khi phấn dư còn 1 hoặc 0 thì ngưng,nếu thương vẫn còn có thể chia cho 2 thì tiếp tục.kết quả căn chính là giá trị phép dư 0,1 cộng lại.(cái này mình thấy thằng nhóc hàng xóm làm, không chắc chính xác k,anh em coi góp ý thêm nha)

cuxu
19-01-2008, 10:00 AM
Mình có thể xài cách dò tìm, và ra kết quả gần đúng. (Miễn sao ra dc kết quả,hehe).
ví dụ lấy căn của 6.
Ta phân hoạch ra theo khoản cách 0.01;
Và cho run từ 1 số (chắc có cách để biết nên run từ đâu đến đâu).
và tính bình phương của nó. Khi nó đế gần kết quả, sẽ xảy ra 1 hiện tượng là từ <, => ,>. Nhận ra dc là ta dừng và show kết quả.

Sieg
19-01-2008, 08:46 PM
Sorry nha , có công thức tính căn bậc hai nữa ( nó tựa tựa như các công thức tính sin, cos, hay số pi nhưng mà mình quên mất tiêu roài ) nhưng mà cái công thức đó mình dùng ít nhất là 2 biến chứ 1 biến thì chịu , cái yêu cầu này ko được dùng các hàm chuẩn đó !!!

sieuphuong
19-01-2008, 09:23 PM
Công thức Taylor gì gì đó hả . Hình như công thức đó dùng có 1 biến thôi mà.Bạn dùng biến cũ gán qua là xong thôi .

huynguyen
19-01-2008, 10:36 PM
Chính xác là Taylor đó, đọc thêm trong cuốn Giải tích 1 của Nguyễn Cam.

rox_rook
19-01-2008, 11:04 PM
Taylor đây T_T :
f(x) = f(c)/0! + f'(c)(x-c)/1! + f''(c)(x-c)^2/2! + f'''(c)(x-c)^3/3! +....
Cái này sqrt(x) nên c = 0, nó là trường hợp đặc biệt của Taylor, mà TH c = 0 thì của Maclaurin, tại bà này tìm ra trước Taylor hì hì !.

sieuphuong
19-01-2008, 11:44 PM
hehe . giờ C việt thành forum.toanhoc.net rồi . Giỏi toán thì sẽ học tốt lập trình nhỉ .

Kevin Hoang
19-01-2008, 11:54 PM
@R^2: Taylor như vậy thì với một biến tính làm sao nhỉ? Dr thử không có ra. Có ai làm được với một biến không, đừng ngại, hãy đưa lên cho Dr và mọi người tham khảo với!


hehe . giờ C việt thành forum.toanhoc.net rồi . Giỏi toán thì sẽ học tốt lập trình nhỉ .

Đừng có viết bài kiểu này. Dễ làm đề tài chuyển hướng từ cái "Lọ" thành cái "chai" đó, rồi không biết nó thành cái gì nữa. Nếu còn có bài viết kiểu như vậy, bất đắc dĩ bài viết sẽ bị xóa đó.

rox_rook
20-01-2008, 12:18 AM
Nếu bắt 1 biến chắc cũng không phải dễ, không biết có mẹo không nữa ? vì nếu Taylor thì cũng phải dùng vòng lặp mà 1 biến thì...Đệ qui chăng ? Mình chịu rùi Dr ơi T_T!

Sieg
20-01-2008, 08:27 AM
mấy thằng phỏng vấn tụi nó hỏi 2 câu hơi móc đó là :
1/ là câu trên kia đó
2/ hoán đổi 2 số ko dùng thêm biến trung gian
câu 2 thì làm được còn câu 1 thì bó tay.
cái công thức Taylor đó có dùng đạo hàm f'(x), f''(x) .... mà tính đạo hàm sao có thể dùng 1 biến được nhỉ -> chịu thua lun.

hacnho
20-01-2008, 03:13 PM
Tôi nhớ một thuật toán cổ về giải căn 2 của người babylonian cổ là đầu tiên cho y=1.0, sau đó y=(y+2/y)/2. Lặp lại bước 2 vài lần sẽ ra căn 2.

NT_OnlyLove
20-01-2008, 04:35 PM
mấy thằng phỏng vấn tụi nó hỏi 2 câu hơi móc đó là :
1/ là câu trên kia đó
2/ hoán đổi 2 số ko dùng thêm biến trung gian
câu 2 thì làm được còn câu 1 thì bó tay.
cái công thức Taylor đó có dùng đạo hàm f'(x), f''(x) .... mà tính đạo hàm sao có thể dùng 1 biến được nhỉ -> chịu thua lun.

Haha , đúng là pótay pó chân. Câu hai thì đơn giản rồi ( nhưng với số nhỏ , số lớn thì không ổn).
Tuy nhiên cái câu 1 nếu là tôi thì tôi cứ làm:
x=sqrt(x);

Ada
20-01-2008, 06:04 PM
Nếu là mình thì sẽ trả lời: Làm coder là biết cách code chuẩn mực, càng đơn giản và dễ hiểu càng tốt, ai cần biết mấy cái code mẹo ấy làm gì. Càng lắm mẹo càng hỏng tay nghề. Như thế, cách tính căn tốt nhất là sqrt() (như NT OnlyLove đã nói). Còn nếu thật sự muốn biết tính căn như thế nào, google 1 giây là xong.

Mà quả thật, google một phát, ra ngay: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

Theo đó, phương pháp tính căn chỉ dùng 1 biến có lẽ là phương pháp Babylon, như hacnho đã nói.

huynguyen
20-01-2008, 06:38 PM
Câu hai thì đơn giản rồi ( nhưng với số nhỏ , số lớn thì không ổn).
Số lớn vẫn ok, ko có gì xảy ra cả đối với việc hoán vị 2 số ko dùng biến trung gian. Cái này tôi đã chứng minh rồi mà

comeonbaby
20-01-2008, 06:43 PM
Hiz câu 2 nếu sử dụng cách tính theo kiểu:
a=a+b;
b=a-b;
a=a-b;

thì có gây tràn số không ạ?
Còn làm theo kiểu bitwise thì sẽ là :
a^=b^=a^=b
thì cách nào tốt hơn ạ?

Sieg
22-01-2008, 08:15 AM
hay thật đấy, trang wiki cho ta nhiều công thức tính nhưng ở cuối cùng có một hàm tính căn bậc hai bằng 1 biến, hàm này cho kết quả không chính xác mấy nhưng cũng tạm ổn:


#include <stdio.h>
#include <conio.h>

float fastsqrt(float val) {
int tmp = *(int *)&val;
tmp -= 1<<23; /* Remove last bit to not let it go to mantissa */
/* tmp is now an approximation to logbase2(val) */
tmp = tmp >> 1; /* divide by 2 */
tmp += 1<<29; /* add 64 to exponent: (e+127)/2 =(e/2)+63, */
/* that represents (e/2)-64 but we want e/2 */
return *(float *)&tmp;
}

int main(){
float x;
scanf("%f",&x);
printf("\n%f",fastsqrt(x));
getch();
return 0;
}

Thử kết quả :


4

2.000000

đúng roài thử típ :D


114

11.125000

oạch sao sai dữ vậy trời
móa ơi càng về sau càng thất vọng => thui tìm lời giải khác zậy :D
nói chung thì đoạn code trên đúng với số chính phương còn lại thì chỉ là ...

nvnoi76
02-02-2008, 11:44 PM
Chào các bạn,

Để tính căn bậc 2 của 1 số dương a ( tổnq quát căn bậc n ), ta phải xây dựng một chuỗi ( toán học ) mà chuỗi này hội tụ về căn bậc 2 của a. Sau đó lặp hữu hạn 1 số lần để được kết quả với độ chính xác nào đó chấp nhận được. Sau day la chuong trinh trong C de thuật tính căn bậc 2 cua 2 voi độ chính xác 0.00000001 chỉ bằng các phép toán +, - , *, / mà thôi.



////////////////////////////////////////////////////////////////////////
// Square root of 2 by Nguyen Van Noi - DHTG
// Email : nvnoi76@yahoo.com
///////////////////////////////////////////////////////////////////////

#include <stdio.h>
double myabs(double x)
{
return ((x>=0)?x:(-x));
}
void main()
{
double a=2.0, xo, xn=1, e=1e-8;
do
{
xo=xn;
xn=(a/xo+xo)/2.0;
}
while (myabs(xn-xo)>e);
printf("Can bac 2 cua 2 = %1.8f\n",xn);
}


/////////////////////////////////////////////////////////////////////////
Kết quả chạy ra :

Can bac 2 cua 2 = 1.41421356

http://forums.congdongcviet.com/showthread.php?p=31490#post31490

----------------------------------------
Nguyễn Văn Nối - Đại học Tiền Giang.
nvnoi76@yahoo.com

Lưu ý: Khi gửi code cùng bài viết, vui lòng đưa nó vào tag code. Đọc Nội quy để biết thêm chi tiết!