如果走廊裏依次排列著K把鎖頭，那麽在第K遍後,有鎖1,4,9,16.....,|sqrt(k)|鎖頭是打開的.
證明: 100把鎖頭分別標記為s1,s2,s3,..,si,..,s100
s1只在第1遍被切換狀態;
如果i是素數,si只是在第1遍和第i遍被切換狀態,切換次數為偶數個;
如果i是非平方數的合數,則總可以分解為i=m*n=q*p=....=r*u(m!=n,q!=p,....,r!=u),si只是在第1遍,第i遍,第m,n,q,p,...,r,u遍被切換狀態,切換次數為偶數個;
如果i是平方數時,i=m*n=q*p=....=r*u=x*x(m!=n,q!=p,....,r!=u),si只是在第1遍,第i遍,第m,n,q,p,...,r,u遍,第x遍被切換狀態,切換次數為奇數個;
切換之前,鎖頭是鎖著的狀態,經過偶數次切換後,鎖頭還是鎖著的狀態;
切換之前,鎖頭是鎖著的狀態,經過奇數次切換後,鎖頭變為打開著的狀態.
因此,只有當i是平方數的鎖頭被打開.
算法: 由開鎖智力題的操作步驟,我們可以獲得啟發,按照這種方法獲取平方數.
step1:將數的狀態值都設定為-1;
step2:將所有數依此模1,2,3,....,100,如果結果為0,就改變狀態;
step3:打印出狀態值為1的數.
程序: 下面是利用這壹方法獲取[1,100]區間上平方數的程序,代碼在vc++6.0平臺運行成功.
/**author:mapping
date:2007.2.15
FindSquareNumber .cpp**/
#include <iostream>
#include <process.h>
using namespace std;
void main()
{
int a;
int i;
for(i=1; i<= 100; i++)
{
a=-1;
for(int j=1;j<=i;j++)
{
if(i%j==0)
a=(-1)*a;
}
if(a==1)
cout<<"square number :"<<i<<endl;
}
system("pause");
}