风之巅小学有48间教室,每间教室有2扇门,用1-96分别编号。有一天,狐狸把所有的门都打开,第二个到校的格莱尔把所有编号是2的倍数的房门作相反的处理(原来开着的关上,原来关上的打开),第三个到学校的同学把所有编号是3的倍数的房门做相反的处理……第42个到校的尼克把所有编号是42的倍数的房门做相反的处理。
请设计并实现一算法,算一算最后共有几扇门是开着的?分别是哪几扇?
定义个96元素数组,初始都为0。然后根据来的人编号,把对应倍数的值改为相反值,即0改为1,1改为0
#include <stdio.h>
int main()
{
int a[96] = {0};
int i,j,count=0;
for(i=1;i<=41;i++)
{
for(j=i+1;j<=96;j=j+i+1)
{
if(a[j-1] == 0)
a[j-1] = 1;
else
a[j-1] = 0;
}
}
printf("打开的门为:");
for(i=0;i<96;i++)
{
if(a[i] == 0)
{
printf("%d ",i+1);
count++;
}
}
printf("\n总共打开的门数:");
printf("%d\n",count);
return 0;
}
这种问题有2个解题思路
一种是按照题目的顺序,给数组对应位置翻转,这跟用筛法求质数是一样一样的,那么相当于人是外层循环,门是内层循环。
另一种是倒过来,门作为外层循环,每个门只判断一次,人作为内层循环,判断一下有奇数个人还是偶数个人去操作门,如果是偶数个,状态不变,奇数个,状态翻转。