狱吏问题的三种解法
-
- 题目描述
-
- 解题思路一:暴力求解
- 解题思路二:求解因数个数
- 求解因数的两个模型
-
- 求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]++;
}
}
}
求一个数的因数个数
因数个数