培训网站建设方案书,沈阳定制网站方案,专业做企业活动的趴网站,Wordpress修改主题菜单样式【题目描述】
开灯问题。有n盏灯#xff0c;编号为1#xff5e;n。第1个人把所有灯打开#xff0c;第2个人按下所有编号为2的倍数的开关#xff08;这些灯将被关掉#xff09;#xff0c;第3个人按下所有编号为3的倍数的开关#xff08;其中关掉的灯将被打开#xff0…【题目描述】
开灯问题。有n盏灯编号为1n。第1个人把所有灯打开第2个人按下所有编号为2的倍数的开关这些灯将被关掉第3个人按下所有编号为3的倍数的开关其中关掉的灯将被打开开着的灯将被关闭依此类推。一共有k个人问最后有哪些灯开着输入n和k输出开着的灯的编号。k≤n≤1000。
【样例输入】
7 3
【样例输出】
1 5 6 7
【题目来源】
刘汝佳《算法竞赛入门经典 第2版》程序3-2 开灯问题 【解析】
问题看似复杂但有了数组这把利刃解决起来非常容易只需要用a[i]表示第i盏灯是否开着即可。a[i]1表示开a[i]0表示关。
原书代码
#includestdio.h
#includestring.h
#define maxn 1010
int a[maxn];
int main(){int n, k, first 1;memset(a, 0, sizeof(a));scanf(%d%d, n, k);for(int i 1; i k; i)for(int j 1; j n; j)if(j % i 0) a[j] !a[j];for(int i 1; i n; i)if(a[i]) { if(first) first 0; else printf( ); printf(%d, i); }printf(\n);return 0;
}
代码说明
1用memset将数组清0这个操作是没有必要的删掉这行代码依然可以完美运行。因为定义在main函数之外的数组如果没有显式初始化它的元素会被自动初始化为0。因为算法竞赛基本都要把数组定义在main函数之外所以不用考虑数组初始化的问题。
提醒定义在main函数之内的数组并不会被自动初始化为0这时候用memset就有必要了。
2模拟开关灯的双层循环中的i表示第i个人j表示第j盏灯这就需要有一条if语句来判断是否要操作开关。其实根据题意可知要操作的开关就是i的倍数所以可以直接定义j为要操作开关的灯的编号这样就不用增加if语句了。循环部分改后代码如下
for(int i1; ik; i){for(int ji; jn; ji){ //j为要操作开关的灯的编号a[j] !a[j];}
}
