亮着电灯的盏数


题目

一条长廊里依次装有n(1 ≤ n ≤ 65535)盏电灯,从头到尾编号1、2、3、…n-1、n。每盏电灯由一个拉线开关控制。开始,电灯全部关着。有n个学生从长廊穿过。第一个学生把号码凡是1的倍数的电灯的开关拉一下;接着第二个学生把号码凡是2的倍数的电灯的开关拉一下;接着第三个学生把号码凡是3的倍数的电灯的开关拉一下;如此继续下去,最后第n个学生把号码凡是n的倍数的电灯的开关拉一下。

问:n个学生按此规定走完后,长廊里电灯有几盏亮着。

注:电灯数和学生数一致。

分析

刚开始灯是关着的,拉一次变亮,再拉一次又灭掉。所以最后亮着的灯肯定是被奇数个人拉过的,关着的灯是被偶数个人拉过的。最后求有几盏灯亮着,也就是求几盏灯被奇数个人拉过。再考虑,如何知道一盏灯是被拉过奇数次还是偶数次?

对于这道题,很多人容易从人去考虑,这样会比较麻烦。其实,换个角度,从每一盏灯去考虑,这个问题就变的非常简单了——第n盏灯被拉过多少次,则证明它有多少个约数。比如第10盏灯,分别会被第1、2、5、10号同学拉一遍,第25盏灯分别会被第1、5、25号同学拉一遍。所以,有奇数个约数的灯就被拉过奇数次,也就是最后亮着的灯;有偶数个约数的灯就被拉偶数次,最后是关着的。那如何判断一个数有奇数个约数还是偶数个约数呢?

其实,从刚才的10和25我们已经可以意识到一点了:完全平方数有奇数个约数,非完全平方数有偶数个约数。所以这道题最终就变为求不大于n的完全平方数有多少个。这样这道题就非常简单了。

程序

下面是我写的一个程序,仅供参考:

#include <stdio.h>

int main()
{
	int n, count;
	printf("Input student/light num: ");
	scanf("%d", &n);

	count = 1;
	while(count * count <= n)
	{
		count++;
	}

	printf("%d lights are still on.n", count-1);

	return 0;
}

或者下面的更简单:

#include <stdio.h>
#include <math.h>

int main()
{
	int n, count;
	printf("Input student/light num: ");
	scanf("%d", &n);

	printf("%d lights are still on.n", (int)sqrt(n));

	return 0;
}

备注

当然,也可以去判断每一盏灯,这样会稍微麻烦一点。下面是判断每一盏灯的程序:

#include <stdio.h>

int main()
{
	int n,count;
	int  j = 1, m = 0;

	printf("Input student/light num: ");
	scanf("%d", &n);

	while( j <= n)       // 一盏灯一盏灯的去判断
	{
		count = 0;
		for(int i = 1; i <= n; i++)  // 计数这盏灯被拉过的次数
		{
			if( j%i == 0)
				count++;
		}
		if( count%2 != 0)  // 如果被拉过奇数次,则亮着的数量加1
			m++;

		j++;
	}
	printf("%dn", m);

	return 0;
}

 


已有 2 条评论

  1. 嗯对

    printf( (int)sqrt(n))

    嗯对 回复
    1. 时间轨迹
      @嗯对

      还是石大神高,一句话就解决了问题

      时间轨迹 博主 回复

添加新评论

选择表情 captcha

友情提醒:不填或错填验证码会引起页面刷新,导致已填的评论内容丢失。

|