数组例题——宾馆房间的门

宾馆里有一百个房间，从1-100编了号。第一个服务员把所有的房间门都打开了，第二个服务员把所有编号是2的倍数的房间门作“相反处理”，第三个服务员把所有编号是3的倍数的房间门作“相反处理”…，以后每个服务员都是如此。编写程序计算当第100个服务员来过后，哪几扇门是打开的。所谓“相反处理”就是：原来开着的门关上，原来关上的门打开。

分析：使用数组来记录门的状态，使用双重循环来模拟每个服务员的处理过程。

#include<iostream>
using namespace std;
const int N = 100;
//数组doorStatus每个元素记录对应门的状态
//doorStatus[i]记录编号为i的门的状态：0表示关闭，1表示打开
//全局数组doorStatus所有元素会被自动初始化成0，正好表示最开始时所有门是关闭的 
int doorStatus[N+1];
int main()
{
	//100个服务员依次操作 
	for(int i=1;i<=N;i++){
		//第i个服务员要把编号是i的倍数的房间门做相反处理
		for(int j=i;j<=N;j=j+i){
			doorStatus[j] = 1-doorStatus[j];	//相反处理：1→0、0→1 
		} 
	}
	
	//筛选出数组中值是1的元素的下标
	for(int i=1;i<=N;i++){
		if(doorStatus[i]) cout<<i<<" ";
	}
	return 0; 
}

#include<iostream>
using namespace std;
const int N = 100;
//也可以使用bool数组doorStatus每个元素记录对应门的状态
//doorStatus[i]记录编号为i的门的状态：false表示关闭，true表示打开
//全局bool数组doorStatus所有元素会被自动初始化成false，正好表示最开始时所有门是关闭的 
bool doorStatus[N+1];
int main()
{
    //100个服务员依次操作 
    for(int i=1;i<=N;i++){
        //第i个服务员要把编号是i的倍数的房间门做相反处理
        for(int j=i;j<=N;j=j+i){
            doorStatus[j] = !doorStatus[j];//相反处理：true→false、false→true 
        } 
    }
    
    //筛选出数组中值是true的元素的下标
    for(int i=1;i<=N;i++){
        if(doorStatus[i]) cout<<i<<" ";
    }
    return 0; 
}

运行程序，输出结果如下：

1 4 9 16 25 36 49 64 81 100

分析结果才发现原来有规律，就是完全平方数呀！那么我们还可以修改程序提高运行效率（当然竞赛的时候也可以采用这样取巧的方法）：

#include<iostream>
using namespace std;
int main()
{
	for(int i=1;i<=10;i++)
		cout<<i*i<<" ";
	return 0; 
}

如果门和服务员的数量不是固定值100，而是输入，那么可以这样编写程序：

#include<iostream>
using namespace std;
int main()
{
	int n,i = 1,t = i*i;
	cin>>n;
	while(t<=n){
		cout<<t<<" ";
		i++;
		t = i*i;
	}
	return 0; 
}

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int i=1,t=i*i;t<=n;i++,t=i*i)
		cout<<t<<" "; 
	return 0; 
}