PDA

View Full Version : Thuật toán xác định số chính phương?



jiSh@n
16-07-2003, 10:58
Có ai biết thuật toán dùng để xác định số chính phương ngắn gọn và hiệu quả không?

Hiện nay tui được đề nghị 3 thuật toán :
1. sqr(sqrt(n))=n
2. round(sqrt(n))=sqrt(n)
3. xác định trong lân cận [ [sqrt(n)]-1; [sqrt(n)]+1 ]: chỉ cần có một số nguyên trong lận cận đó bình phương lên bằng n thì n là số cp.

3 thuật toán trên đều đúng trong trường hợp n là số Cp. Thuật toán 1 bị sai vì gần như lúc nào cho ra KQ n là số Cp. 2 thuật toán còn lại cũng bị sai khi n quá lớn. Tui đã thử trong Pascal, FreePascal, Delphi 7, Delphi for .NET, VB.NET, PHP (thử tt 1,2,3); VC++.NET (thử tt 1 và 3) với các kiểu longint, int64, uint64, qword.

Có ai biết thuật toán nào khác ko?

xyxy
16-07-2003, 13:41
nếu tổng các số mũ các thừa số nguyên tố của 1 số là lẻ thì nó là số chính phương.
{có lẽ thuật toán này chạy hơi lâu ?}

xyxy
16-07-2003, 13:49
chú ý là nếu chỉ cần nó có 1 thừa số nguyên tố có số mũ lẻ là coi như nó không phải là số chính phương.
vd:9=1^1.3^2
tổng các số mũ là lẻ nên nó là số chính phương
10=2^1*x
thừa số nguyên tố 2 có số mũ là lẻ nên ta lập tức loại.
tôi nói tổng các thừa số nguyên tố của 1 số là lẻ thì nó là số chính phương là nếu có kể thêm số 1 (xin mọi người hiểu cho)

Hasterisk
16-07-2003, 23:11
2 thuật toán đầu dựa trên sự so sánh 2 số thực, điều này không thể tin tưởng được. Vì việc so sánh này dựa trên sự lệch nhau 1 lượng nhỏ "chấp nhân được " , ngôn ngữ nào cũng vậy, có thể là 10 hay 20 csố sau dấu ,. Ngoài ra còn phụ thuộc độ chính xác của hàm sqrt.
Thuật toán 3 tôi nghĩ là không sai, vì nó so sánh 2 số nguyên.
Bạn có thể nói rõ nó sai theo kiểu nào được không, có cp báo không hay là ngược lại
Đảm bảo không bao giờ sai là các thuật toán số học, nhưng lại rất chậm. Btw, phát biểu của xyxy là sai rồi, bạn thử giải thích số 3*5 và 3*5*7 xem nào

jiSh@n
17-07-2003, 15:03
Đúng như Hasterisk nói, 2 tt đầu so sánh số thực nên không thể tin tưởng mặc dù tt 2 có vẻ rất đúng. Còn thuật toán 3 ko sai về lý thuyết (do chỉ so sánh số nguyên), nhưng nó lại bị lỗi trong thực tế do hàm sqrt (trả về số thực) khi xử lý ở những số rất lớn (cỡ khỏang ngàn tỷ trở lên). Tôi đã thử bằng cách tạo ra số Cp N bằng cách bình phương một số nguyên M. Khi M khỏang từ vài tỷ đến vài chục tỷ thì các tt bắt đầu chạy sai (lúc đúng lúc sai). Còn nếu dùng các thuật toán số học (ví dụ như cách thử từ 1->sqrt(N) ) thì nó lại chạy wa' chậm.

Hasterisk
17-07-2003, 18:59
Có lẽ không phải sai ở thuật toán mà sai ở việc xử lý số nguyên lớn của các ngôn ngữ lập trình,kiểu 64 bit chỉ được đến khoảng 19 hay 20 csố, khi lấy vài chục tỷ bp lên thì chắc chắn bị overflow, kết quả không thể tính trước, thường là theo kiểu modulo, nghĩa là MAX+1 --> MIN

xyxy
18-07-2003, 11:31
ý cậu là giải thích thế nào hả hasterik

Hasterisk
18-07-2003, 16:40
Là giải thích theo kiểu tổng số mũ các thừa số nguyên tố làm sao cho 2 số đó đều o phải số cphương

minhhuu
18-07-2003, 19:43
Theo mình nghĩ nên cho biến i chạy từ 1 đến số đó. Nếu i^2=n thì n là số cp
Có thể chia số n ra làm nhiều phần rồi chạy biến i

jiSh@n
19-07-2003, 09:55
Hasterisk có thể giải thích cụ thể hơn được ko?

To minhhuu: Thuật toán số học mà bạn đề nghị chạy rất chậm, ở đây đang cần tìm một tt nhanh và chính xác.

Hasterisk
20-07-2003, 00:17
ví dụ như có 1 số nguyên 8 bit (bdiễn từ -128...127), nếu gán 127+1 cho nó thì nó mang gtrị -128, đại khái là như vậy.

xyxy
22-07-2003, 06:36
này hasterik:
3*5=3^1*5^1
ta thấy số mũ của 3 là lẻ nên cho nó không phải là số chính phương.
3*5*7=3^1*5^1*7^1
ta thấy số mũ của 3 là lẻ nên cho nó không phải là số chính phương.
bạn nói sai chỗ nào

xyxy
22-07-2003, 06:38
còn tổng các số mũ là chẵn thì nó là số chính phương(lẻ là có kể thêm 1)

xyxy
22-07-2003, 06:40
còn tổng các số mũ là chẵn thì nó là số chính phương(lẻ là có kể thêm 1)
vd 3^7*7^3 là số chính phương vì tổng các số mũ là 10(chẵn)

Hasterisk
22-07-2003, 21:22
vd 3^7*7^3 là số chính phương
no comment :emlaugh:

jiSh@n
23-07-2003, 17:55
Đúng là hết ý kiến. xyxy nghi4 sao mà nói 3^7*7^3 là số chính phương thế?

xyxy
24-07-2003, 14:16
sorry !do tôi tính lộn
nếu mỗi số mũ là số chẵn thì nó là số chính phương

jiSh@n
25-07-2003, 12:22
Nhưng để xác định số chính phương mà phải phân tích ra thừa số nguyên tố thì lâu quá. Có ai có cách làm nào thật nhanh và thật chính xác không?

attilathehun
06-09-2003, 11:23
vớ vỉn thế nhỉ?
Làm gì có chuyện sai với số qúa lớn, có thể đó là vì hàm Round
bác thử dùng hàm Frac (lấy phần phân) xem:

Frac(Sqr(N))=0

jiSh@n
08-09-2003, 01:45
Hừ, hàm Frac() được tính toán dựa trên hàm Round() thôi.

pfiev
08-09-2003, 03:53
Công thức này tôi nghĩ rằng tốt nhất:
sqr(round(sqrt(n)))=n <=> n cp
Không sợ tràn!!! Đúng với mọi số thực n

Có thế mà cũng cãi nhau!

jiSh@n
10-09-2003, 20:43
sqrt(n)->real
round()->longint
tràn là ở chỗ đó. Kiểu dữ liệu ko đủ chính xác.

pfiev
10-09-2003, 23:12
Không tràn nếu giới hạn lại n là số nguyên và dùng công thức đã nói. Còn nếu ngoan cố cho n là thực, thì khó nói lắm, bởi vì dấu = trong số thực chả đảm bảo điều gì.

Nhưng ai muốn làm vẫn có cách: n>0 thì
round(n) = trunc(n+0.5)
Diễn tả chính xác hơn bằng toán:
(n) = [n+0.5]

NewLove1986
19-09-2003, 18:57
Này bạn ơi, sao mình lại thấy vấn đề của bạn rất dễ nhỉ (hay là tại mình "kém cỏi" quá)?
-Trước hết mình xin nhắc lại Định nghĩa số chính phương xem có đúng không nhé: "Số chính phương là một số bằng bình phương đúng của một số khác. Ví dụ: 9 = 3 * 3."
- Nếu như thế mình chỉ cần kiểm tra căn bậc hai của số đó có phải là một số nguyên hay không, và vấn đề này lại nằm gọn trong một dòng:
IF SQRT(N) IN INTEGER THEN <kết luận> (Theo ngôn ngữ Pascal)
Quan điểm của mình có gì sai không?


NewLove.

pfiev
19-09-2003, 21:19
Có đó bạn, vì x=9.0000000001 (kiểu real), thì căn bậc hai của nó có thể nguyên lắm. Đó là do sai số.

real_time
20-09-2003, 21:41
Tôi nghĩ đơn giản thế này thôi! cũng giống như newlove1986 cũng tính bằng sqrt nhưng mà lúc này ta sẽ kiểm tra số đầu vào trước
if frac(x) <>0 then
write(ko có căn là số chính phương)
else
giống bài của newlove1986!!!! liệu đã ổn chửa????

pfiev
20-09-2003, 23:56
Hàm frac đã được thảo luận ở trên.

Rõ ràng "thuật toán" chả có gì phức tạp, tùy thuộc vào phạm vi dữ liệu mà áp dụng các hàm thích hợp thôi. Vì cách làm của real_time không đúng, giả sử n=10^20+1, căn bậc 2 của nó là 10^10+0,5.10^-10 (10 chữ số đầu tiên sau dấu , là số 0), thấy vấn đề chưa. Đó là lí do tôi đề nghị phải "bình phương" kết quả lên nữa.

CrazyBabe
02-10-2003, 00:31
Xử lý đơn thuần bằng tính toán: Vấn đề vẫn là sai số, dù các bạn mở rộng kiểu số đến mức nào vẫn sẽ xảy ra sai số, vì vậy nếu muốn perfect thì kô dùng được.
Dùng thuật giải khác: xây dựng lại hàm căn bậc hai và mũ hai dành cho số lớn (số biểu diễn bằng bit array chứ kô fải số dùng original types). Kĩ thuật này thì đa số các bạn đều biết.

real_time
07-10-2003, 21:58
đúng đó vì trong thực tế có gì đúng 100% cả đâu cái chính là mục tiêu của bạn muốn chính xác đến cỡ bao nhiêu mà thôi!!

pfiev
08-10-2003, 00:49
Tuy nhiên, với cùng một khả năng tính toán, thì các thuật toán khác nhau sẽ cho kết quả không giống nhau. Cách làm của tôi thì tôi thích là chính xác nhất :D

real_time
12-10-2003, 21:08
chính xác nhất thì cũng cần có một ngưỡng nào đó chứ lại chư lúc nào u cũng nói chính xác nhất thì ai mà đáp ứng cho u được.

pfiev
12-10-2003, 22:10
chính xác nhất thì cũng cần có một ngưỡng nào đó chứ lại chư lúc nào u cũng nói chính xác nhất thì ai mà đáp ứng cho u được.
Không hiểu à, thí dụ thế này: bạn có một cái FX500A, thì để giải 1 bài toán có nhiều cách giải. Có cách đi vòng vào sai số lớn, có cách ngắn hoặc ít sai số... Vấn đề là tìm cách giải, chứ không phải đi mua cái máy TI-89 Plus về.

phanthaiminh77
10-07-2009, 21:08
Thân chào các bạn, tôi nghỉ bài giải này không có gì khó, chẳng qua thời 2003 kỹ thuật lập trình quá yếu.
int kt(int kt)
{
int c=0;
int b=int(sqrt(kt));

if(b*b==kt) c=1;
else c=0;
return c;
}

[=========> Bổ sung bài viết <=========]

Nếu còn gì thắc mắc các bạn cứ post qua mail phanthaiminh77@yahoo.com. Tôi hy vọng sẽ giải đáp đầy đủ các vấn đề mà các bạn quan tâm.

lehang_gb1
11-07-2009, 21:39
kiểm tra x=sqr(trunc(sqrt(x)) tức là bình phương phần nguyên căn bậc 2 của x có bằng x không

bld
12-07-2009, 11:35
số nhập vào là s
đặt x=sqrt(s)
nếu x-trunc(x)=0 thì s là chính phương

elnino_020993
14-07-2009, 15:41
có cách đơn giản lắm mà:
n là số chính phương khi
n = sqr (trunc(sqrt(n)))

huysun
16-07-2009, 19:58
Có ai biết thuật toán dùng để xác định số chính phương ngắn gọn và hiệu quả không?

Hiện nay tui được đề nghị 3 thuật toán :
1. sqr(sqrt(n))=n
2. round(sqrt(n))=sqrt(n)
3. xác định trong lân cận [ [sqrt(n)]-1; [sqrt(n)]+1 ]: chỉ cần có một số nguyên trong lận cận đó bình phương lên bằng n thì n là số cp.

dùng thứ 2, nhưng thay đổi 1 tẹo:
i:=int(sqrt(n)) (i và n cùng kiểu số nguyên)
i*i=n=> số chính phương

vanhaodct
13-12-2009, 10:13
anh chi nao gioi java lam giup em bai nay voi:
Viết chương trình in ra các số chính phương từ m đến n tùy ý

huysun
14-12-2009, 14:38
thì chỉ cần tìm căn của m và n (là a và b), sau đó tìm tất cả các số nguyên >= a và <= b , in ra bình phương của chúng là ok.
tơ không biết gì về java nên ko viết dc code :D

Longbin
15-12-2009, 15:17
Em có vài thuật toán nhỏ sáu đây
1. Simple nhất : If | Sqrt(N)-Round(Sqrt(N)) | < Epsilon then ...
2. Phân tích ra thừa số nguyên tố . Nếu tất cả các mũ chia hết cho 2 thì số đó là số chính phương

nguyenthanhictu
04-12-2010, 13:08
Có ai biết thuật toán dùng để xác định số chính phương ngắn gọn và hiệu quả không?

Hiện nay tui được đề nghị 3 thuật toán :
1. sqr(sqrt(n))=n
2. round(sqrt(n))=sqrt(n)
3. xác định trong lân cận [ [sqrt(n)]-1; [sqrt(n)]+1 ]: chỉ cần có một số nguyên trong lận cận đó bình phương lên bằng n thì n là số cp.

3 thuật toán trên đều đúng trong trường hợp n là số Cp. Thuật toán 1 bị sai vì gần như lúc nào cho ra KQ n là số Cp. 2 thuật toán còn lại cũng bị sai khi n quá lớn. Tui đã thử trong Pascal, FreePascal, Delphi 7, Delphi for .NET, VB.NET, PHP (thử tt 1,2,3); VC++.NET (thử tt 1 và 3) với các kiểu longint, int64, uint64, qword.

Có ai biết thuật toán nào khác ko?
tớ có một cách nay rất nhanh và hay:
thuật toán :
if(sqrt(n)-int(sqrt(n))==0)&&(n>0)) printf("la so chinh phuong!")

[=========> Bổ sung bài viết <=========]

các bạn tham khảo nhé

CONGO
26-01-2011, 16:34
Cái này tranh luận cũng gay cấn. Tôi xin bổ sung thêm một cách có độ phức tạp O(n) tôi nghĩ là chắc ăn không phải phân tích thừa số nguyên tố dựa vào tính chất số chính phương không dựa vào định nghĩa.

Tính chất 1: Số chính phương chia 3 dư 0 hoặc 1.
Tính chất 2: Số chính phương chia 4 dư 0 hoặc 1.
Tính chất 3: Số chính phương là tổng của các số lẻ liên tiếp từ 1 đến 2n+1
ví dụ
1=1
4=1+3
9=1+3+5
16=1+3+5+7
....


ta có chương trình sau



int ktcp(unsigned long n)
{
if(n%3==2) return 0;
if(n%4==2||n%4==3) return 0;
unsigned long m=0,T=0;
while(T<n)
{
m++;T+=2*m+1;
}
return T==n;
}


PS: I am a from http://fituct.vn