獄吏問題的三種解法——因數的相關應用

獄吏問題的三種解法

• • 題目描述
  • • 解題思路一：暴力求解
    • 解題思路二：求解因數個數
  • 求解因數的兩個模型
  • • 求N的因數
    • 求1—N所有數的因數個數
    • 求一個數的因數個數

題目描述

解題思路一：暴力求解

外層循環為遞增的間隔數，内層循環不斷操作所有的牢房情況

long start=System.currentTimeMillis();
Scanner sca=new Scanner(System.in);
System.out.println("請輸入牢房數量： ");
int num=9;
int[] flag=new int[num+1];
for(int i=1;i<=num;++i){
    for(int j=i;j<=num;j=j+i){
        flag[j]^=1;
    }
}
for(int i=1;i<=num;++i){
    if(flag[i]==1) System.out.println(i+" is free");
}
           

解題思路二：求解因數個數

間隔為1的時候轉動的是1的倍數，2的時候是2的倍數，3是3的倍數。。。。。。又因為轉動奇數次的時候牢房門就會被打開，隻要統計到第n個牢房轉動了幾下就行，這道題就轉變成了求因數個數的問題。因數求解有兩個模型，見下文。

long start=System.currentTimeMillis();
Scanner sca=new Scanner(System.in);
System.out.print("請輸入牢房數量： ");
int num=sca.nextInt();
int[] flag=new int[num+1];
for(int i=1;i<=num;++i){
    for(int j=1;j<=num/i;++j){
        flag[i*j]++;
    }
}
for(int k=1;k<=num;++k){
    if(flag[k]%2==1) System.out.println(k +" is free");
}
long eps=System.currentTimeMillis()-start;
System.out.println("執行時間： "+eps+"ms");
           

求解因數的兩個模型

求N的因數

因為因數是成對出現的，除了平方數，并且可以縮小範圍0- s q r t ( n ) sqrt(n) sqrt(n)

static int cnt=0; 
void factor(int n){
	for(int i=1;i<=sqrt(n);i++)
		if(n%i==0){
			f[++cnt]=i;
			if(i!=n/i)
				f[++cnt]=n/i;
		}
}
           

求1—N所有數的因數個數

void factor(int n){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n/i;++j){
					f[i*j]++；
			}
		}
}
           

求一個數的因數個數

因數個數