@今天的c语言你学废了吗?!!----开灯问题(20210202
程序员文章站
2024-02-19 08:58:22
...
@今天又学废了呢----开灯问题(C语言)
2021-02-02
读完题目,我最直接的解题方法是:
将开着的灯等价为1,关着的灯等价为0
这样一来,将n个灯编到一个数组里数组长度是n+1,并初始化为零(有人或许会困惑他的长度,但为了在for循环遍历时可以遍历到n这个编号,需要这样,而且第零个的值始终为零,也就是说它可以忽视)
来到关键的地方,我用了两个for来实现每个人(1~k)来按开关都可以经过每个开关(1~n),开关灯我用了if语句:关着的灯从0变成1,开着的灯从1变成0。
最后,当第k个人按下某个灯的开关时,我再次使用了if语句对开着灯进行判断并输出其编号。
#include <stdio.h>
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int a[n+1] = {0};
for(int i = 1;i <= k;i ++){
for(int j = 1;j <= n;j ++){
if(j % i == 0){
if(a[j] == 0) a[j] = 1;
else if (a[j] == 1) a[j] = 0;
}
if(i == k) if(a[j] == 1) printf("%d ",j);
}
}
return 0;
}```
嵌套的for循环语句使该程序的时间复杂度up up up
所以小five他叫劲脑汁
甚至薅秃了头,想到了另一种可能简单点的算法(实际并没有):
Ps:这里定义0为开灯
#include <stdio.h>
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int a[n+1] = {0}; //0为开灯
for(int i = 2;i <= k;i ++){
for(int j = i;j <= n;j += i){
if(a[j] == 0) a[j] = 1;
else if (a[j] == 1) a[j] = 0;
}
}
for(int l = 1;l <= n;l ++){
if(a[l] == 0) printf("%d ",l);
}
return 0;
}
总结一下吧:
细节很重要! 数组的长度为n+1!
略鸡肋的两种方法! 掉光头发是关键!
一不小心学到的东西?memset(a,0,sizeof(a)初始化数组用,但据说只能初始“0”,“-1”和字符串。【哦吼,还得加头文件】
上一篇: 块级元素与内联元素的特性