欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

@今天的c语言你学废了吗?!!----开灯问题(20210202

程序员文章站 2024-02-19 08:58:22
...

@今天又学废了呢----开灯问题(C语言)

2021-02-02

@今天的c语言你学废了吗?!!----开灯问题(20210202

读完题目,我最直接的解题方法是:

将开着的灯等价为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”和字符串。【哦吼,还得加头文件】