如何快速判定整數是不是兩個完全平方數之和

2021-03-03 21:12:33 字數 6154 閱讀 3334

1樓:匿名使用者

問題的本質還是要遍歷的,只要限制一下遍歷規則即可。

第一:對於給出的整數n,求起平方根為sqrtn=sqrt(n),查詢和為它的兩個完全平方數迴圈到【sqrtn】(不大於sqrtn的整數);

第二:設兩個數分別為a,b;起始遍歷條件是:int a=(int)sqrtn;a遞減

截至條件是a<【b】的時候;迴圈內中給出b的值double b=sqrt(n-a*a);

經過這樣兩步,問題可以簡單許多。比如判斷122=121+1=十一的平方+1的平方的時候,【sqrtn】=11=a;b=1;//完成判斷。

a=10;b=根號下22(判斷它不是整數後 4點幾)捨去;

a=9;b=41的平方根.6.幾。捨去。

a=8;b=58的平方根;七點幾;捨去;

a=7;顯然b>a;停止。

例項:void dec(int num)

cout<<"查詢完畢"<

}以上**編譯通過。速度不 錯哦。

演算法:如何判斷一個數是不是完全平方數?

2樓:匿名使用者

pascal語言:

if (round(sqrt(x))*(round(sqrt(x))=x

then write('it is')

else write('it is not');

把這個數開根號,再取整,再平方,若等於原數,則是;反之,則不是。

其實和你的那個方法是差不多的,已經是最簡了,時間複雜度為0.

3樓:匿名使用者

我的c語言程式設計是:

#include "math.h"

main()

4樓:匿名使用者

if sqrt(x) == a then

print 'it is'

else

print 'it is not'

你這是什麼語言來的,這樣的語法.

5樓:受語兒零禎

既然樓上的複製csdn上的說直接找不到好的演算法

你可以反過來算,從1到a/2迴圈,然後求平方,如果其間有數的平方==a,那麼a就是完全平方數.

6樓:回紫安姜涆

dingopeter(peter):

兄弟,做開方運算不過是用數值演算法求的近似解,採用這種方法判斷一個數是否為完全平方數嚴格說來並不合理。完全平方數的有別其他數的一個特徵是:它的因子個數為奇數個,這可以作為判斷的一個準則,而這需要對它進行因子分解,所以我認為它是np-***plete。

我不知道是否有好的演算法,但你說的方法在演算法領域是不會得到承認的。

7樓:樂卓手機

完全平方數是這樣一種數:它可以寫成一個正整數的平方.例如,36是6×6,49是7×7.

從1開始的n個奇數的和是一個完全平方數,n2―即1+3+5+7+…+(2n-1)=n2,例如1+3+5+7+9=25=52.每一個完全平方數的末位數是0,1,4,5,6,或9

每一個完全平方數要末能被3整除,要末減去1能被3整除.每一個完全平方數要末能被4整除,要末減去1能被4整除.

每一個完全平方數要末能被5整除,要末加上1或減去1能被5整除.

如何判斷一個數是完全平方數

8樓:匿名使用者

對於一個比較大的整數,比如:23916,一共有5位數字,假設它是完全平方數,那麼它的平方根應該是一個3位數,因為100的平方是最小的5位數。

同時,這個平方根應該小於200,因為200的平方是40000比原數大。取箇中間數150,因為已知15的平方是225,所以很容易算出150的平方是22500,比原數小。

同理,算出160的平方是25600,比原數大。所以,如果24346時一個完全平方數,它的平方根應該大於150且小於160。完全平方數,凡是個位為6的,其平方根個位必為4或6。

計算154的完全平方,等於 23716 比 23916 小200,計算156的完全平方,等於 24336 比 23916 大420,所以23916不是完全平方數。

擴充套件資料

應用:有多少個正整數n,使n!+2019是完全平方數,注:n!=1*2*…*n,即n的階乘。

講解思路:這道題屬於完全平方數問題,要判斷一個數是完全平方數,除了嚴格驗證外,目前還沒有完善的方法。但要判斷一個數不是完全平方數,有很多種性質可以用,

這裡採用除以4的餘數來判別。由於n!具有十分特別的性質,因此總的解題思路是:先判斷當n>=4時的情況,然後對n<4時的3個數逐一驗證。

步驟1:

先思考第一個問題,

當n大於等於4時,

n!+2019除以4的餘數是多少。

此時n!=1*2*3*4…*n,

故n!是4的整數倍,

而2019除以4的餘數是3,

因此n!+2019除以4的餘數是3。

步驟2:

再思考第二個問題,

當n大於等於4時,

n!+2019可能是完全平方數嗎。

此時n!+2019是奇數,

如果它是完全平方數,

則存在某自然數k,

使n!+2019=(2k+1)^2

=4k^2+4k+1,

顯然該數除以4的餘數為1,

這與步驟1的結論想矛盾,

因此不是完全平方數。

注:k^2表示k的平方。

步驟3:

再思考第三個問題,

考慮原題目的答案。

從步驟2直到n小於4,

下面對n=1,2,3分別討論:

當n=1時,

n!+2019=2020不是完全平方數;

當n=2時,

n!+2019=2021不是完全平方數;

當n=3時,

n!+2019=2025=45^2,

是完全平方數。

所以原題的答案只有n=3。

9樓:史談歷史

完全平方數?

首先,背下1-20的平方數,因為常用。

然後牢記以下規律:

完全平方數,凡是個位為0的,其平方根個位必為0

完全平方數,凡是個位為1的,其平方根個位必為1或9

完全平方數,凡是個位為4的,其平方根個位必為2或8

完全平方數,凡是個位為5的,其平方根個位必為5

完全平方數,凡是個位為6的,其平方根個位必為4或6

完全平方數,凡是個位為9的,其平方根個位必為3或7

然後,對於一個比較大的整數,比如:23916

一共有5位數字,假設它是完全平方數,那麼它的平方根應該是一個3位數,因為100的平方是最小的5位數。

同時,這個平方根應該小於200,因為200的平方是40000比原數大。

我們不妨取箇中間數150,因為已知15的平方是225(你背了),所以很容易算出150的平方是22500,比原數小。

同理,算出160的平方是25600,比原數大。

所以,如果24346時一個完全平方數,它的平方根應該大於150且小於160。

完全平方數,凡是個位為6的,其平方根個位必為4或6。

計算154的完全平方,等於 23716 比 23916 小200,

計算156的完全平方,等於 24336 比 23916 大420,

所以23916不是完全平方數。

對於一個位數較多的小數,比如:2.4336,2.43360和24.336.

小數點後位數為單數且「最後一位不為0」的數,一定不是完全平方數;小數點後位數為偶數的數,可能是完全平方數,比如:24.336小數點後位數為3,一定不是完全平方數;

但2.43360小數點後位數為5,卻可能是完全平方數;

2.4336小數點後位數為4,可能是完全平方數。

判斷一個小數是不是完全平方數比較常用的方法是「百倍擴大」也叫「移位法」,即把原數小數點向右移動「雙數」位,直至小數變為整數,計算新整數的平方根,再把小數點按「百倍擴大」的次數移回,如:2.4336 小數點向右移動4位(兩次「百倍擴大」)變為24336,計算24336的平方根(156),小數點左移兩位(1.

56)即為2.4336的平方根。

分數,只要

分子分母都是完全平方數,這個分數就是完全平方數,反之,只要有一個不是,這個分數就不是完全平方數。

10樓:匿名使用者

完全平方即用

一個整數乘以自己例如1*1,2*2,3*3等等,依此類推。若一個數能表示成某個數的平方的形式,則稱這個數為完全平方數。完全平方數是非負數。

而一個完全平方數的項有兩個。注意不要與完全平方式所混淆。

例如:0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529…

觀察這些完全平方數,可以獲得對它們的個位數、十位數、數字和等的規律性的認識。下面我們來研究完全平方數的一些常用性質:

性質1:末位數只能是0,1,4,5,6,9。

(此為完全平方數的必要不充分條件,且定義為"一個數如果是另一個整數的完全平方,那麼我們就稱這個數為完全平方數",0為整數,故0是完全平方數)

性質2:奇數的平方的個位數字一定是奇數,偶數的平方的個位數一定是偶數。

證明 奇數必為下列五種形式之一:

10a+1,10a+3,10a+5,10a+7,10a+9

分別平方後,得

綜上各種情形可知:奇數的平方,個位數字為奇數1,5,9;十位數字為偶數。

性質3:如果十位數字是奇數,則它的個位數字一定是6;反之也成立

證明 已知

,證明k為奇數。因為k的個位數為6,所以m的個位數為4或6,於是可設m=10n+4或10n+6。則或即

或∴ k為奇數。

推論1:如果一個數的十位數字是奇數,而個位數字不是6,那麼這個數一定不是完全平方數。

推論2:如果一個完全平方數的個位數字不是6,則它的十位數字是偶數。

性質4:偶數的平方是4的倍數;奇數的平方是4的倍數加1。

這是因為

性質5:奇數的平方是8n+1型;偶數的平方為8n或8n+4型。

(奇數:n比那個所乘的數-1;偶數:奇數:n比那個所乘的數-2)

在性質4的證明中,由k(k+1)一定為偶數可得到 是8n+1型的數;由為奇數或偶數可得(2k)為8n型或8n+4型的數。

性質6:形式必為下列兩種之一:3k,3k+1。

因為自然數被3除按餘數的不同可以分為三類:3m,3m+1,3m+2。平方後,分別得

同理可以得到:

性質7:不是5的因數或倍數的數的平方為5k+-1型,是5的因數或倍數的數為5k型。

性質8:形式具有下列形式之一:16m,16m+1,16m+4,16m+9。

除了上面關於個位數,十位數和餘數的性質之外,還可研究完全平方數各位數字之和。例如,256它的各位數字相加為2+5+6=13,13叫做256的各位數字和。如果再把13的各位數字相加:

1+3=4,4也可以叫做256的各位數字的和。下面我們提到的一個數的各位數字之和是指把它的各位數字相加,如果得到的數字之和不是一位數,就把所得的數字再相加,直到成為一位數為止。我們可以得到下面的命題:

一個數的數字和等於這個數被9除的餘數。

下面以四位數為例來說明這個命題。

設四位數為,則

1000a+100b+10c+d

= 999a+99b+9c+(a+b+c+d)

=9(111a+11b+c)+(a+b+c+d)

顯然,a+b+c+d是四位數被9除的餘數。

對於n位數,也可以仿此法予以證明。

關於完全平方數的數字和有下面的性質:

性質9:數字之和只能是0,1,4,7,9。

證明 因為一個整數被9除只能是9k,9k±1,9k±2,9k±3,9k±4這幾種形式,而

除了以上幾條性質以外,還有下列重要性質:

性質10:為完全平方數的充分必要條件是b為完全平方數。

證明 充分性:設b為平方數,則=(ac)

必要性:若為完全平方數,=,則

性質11:如果質數p能整除a,但p的平方不能整除a,則a不是完全平方數。

證明 由題設可知,a有質因數p,但無因數,可知a分解成標準式時,p的次方為1,而完全平方數分解成標準式時,各質因數的次方均為偶數,可見a不是完全平方數。

性質12:在兩個相鄰的整數的平方數之間的所有整數都不是完全平方數。

即若則k一定不是整數。

性質13:一個正整數n是完全平方數的充分必要條件是n有奇數個因數(包括1和n本身)。

linushell如何比較兩個整數的大小

linux shell比較兩個整數的大小可以採用以下的 bin sh max 9 min 8 if max gt min then echo 1 else echo 0 fi數字的比較 eq 相等 equal ne 不等 not equal gt 大於 greater than lt 小於 less...

判斷兩個函式是不是同一函式,如何判斷兩個函式是不是相同的函式

即使定義域和值域都一樣的函式也不一定是同一函式。能夠轉化為相同表示式,且定義域相同的函式,才是同一函式。補充 對應法則就是表示式,所以判斷兩個函式是不是同一函式,就看定義域和對應法則是否一樣。1 定義域是否相同。2 對於定義域中的任意實數x,在兩個函式中分別對應的y是否相同。如果都相同,就是同一個函...

每人是不是有兩個星座,每一個人是不是有兩個星座

星座是按bai陽曆劃分 的,按你的陽du歷生日,所以每人只有zhi一個dao星座,下面為你介紹十二回星座,供你答對照,星座名,星座日期,星座屬性 幸運數字,辛運顏色,白羊座 03 21 04 19 火象星座 6,7,鮮紅色,血紅色,金牛座 04 20 0520 土象星座 1,9,紫色,雙子座 05 ...