亮着电灯的盏数

boyfaceone

一条长廊里依次装有n(1 ≤ n ≤ 65535)盏电灯，从头到尾编号1、2、3、…n-1、n。每盏电灯由一个拉线开关控制。开始，电灯全部关着。有n个学生从长廊穿过。第一个学生把号码凡是1的倍数的电灯的开关拉一下；接着第二个学生把号码凡是2的倍数的电灯的开关拉一下；接着第三个学生把号码凡是3的倍数的电灯的开关拉一下；如此继续下去，最后第n个学生把号码凡是n的倍数的电灯的开关拉一下。n个学生按此规定走完后，长廊里电灯有几盏亮着。
接口说明
原型：
    int GetLightLampNum(int n);
输入参数：
    int n: 电灯/学生的数量
返回值：
    int: 亮着的电灯数量

boyfaceone

参考思路：单独考虑每一盏灯被拉的次数，得出最后状态，再求和。

那个谁

好久没有过来做题了，不能荒废了，只要晚上有时间过就过做练习。
#define MAX 65536
int GetLightLampNum(int N)
{
    int i=0,j=1,light[MAX]={0},number=0;   
    while(j<=N)
    {
        for(i=1;i<=N;i++)
        {   
            if(i*j<=N)
                light[i*j-1]++;   
        }
        j++;
    }

    for(i=0;i<N;i++)
    {
        if(light%2!=0)
            number++;
    }
    return number;
}
我试着输入数值，当N大46341的时候为什么会打印出segmentation fault？

boyfaceone

tyrone2497谁:好久没有过来做题了，不能荒废了，只要晚上有时间过就过做练习。
#define MAX 65536
int GetLightLampNum(int N)
{
&#160;&#160;&#160;&#160;int i=0,j=1,light[MAX]={0},number=0;&#160;&#160;&#160;&#160;
.......&#160;(2013-07-07 22:11)&#160;

if(light%2!=0)
light是数组的地址吧？

boyfaceone

参考解法，效率较低，有优化的空间。

2. int GetLightLampNum(int n)
3. {
4. &#160;&#160;&#160;&#160;int count = 0;  // 最终亮着的灯数
5. &#160;&#160;&#160;&#160;int i = 0;
6. &#160;&#160;&#160;&#160;int j = 0;
7. &#160;&#160;&#160;&#160;int flag = 0;  // 灯的状态，0表示灭，1表示亮
8. &#160;&#160;&#160;&#160;
9. &#160;&#160;&#160;&#160;for (i = 1; i <= n; i++)
10. &#160;&#160;&#160;&#160;{
11. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;flag = 0;
12. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;
13. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;for (j = 1; j <= n; j++)
14. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;{
15. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;if (0 == i % j)
16. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;{
17. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;flag = ~flag;
18. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;}
19. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;}
20. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;
21. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;if (flag)
22. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;{
23. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;count++;
24. &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;}
25. &#160;&#160;&#160;&#160;}
26. &#160;&#160;&#160;&#160;
27. &#160;&#160;&#160;&#160;return count;
28. }

复制代码

那个谁

boyfaceone:if(light%2!=0)
light是数组的地址吧？ (2013-07-07 23:34)

奇了怪了，我看了下我的源码，是按数组来的，怎么复制过来就只剩数组名了？

那个谁

今天翻译FAQ的时候看到了用传递参数动态定义数组的方法，这里就可以应用了，light=(int *)malloc(N*sizeof(int));然后在函数返回的之前释放开辟的空间free(light);light=NULL;