| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 882 人关注过本帖
标题:求开光灯的算法
只看楼主 加入收藏
liucs116
Rank: 2
等 级:论坛游民
帖 子:130
专家分:29
注 册:2009-11-4
结帖率:92.86%
收藏
已结贴  问题点数:2 回复次数:10 
求开光灯的算法
问题描述

有n只灯泡排成一条线,编号分别为1,2,...,n。初始状态灯泡都是不亮的。在这些灯泡上执行一系列的开关灯操作。这些操作的编号为1,2,3,.....,第i次操作把编号为i的倍数的灯泡的开关状态变换一下(亮的变成不亮,不亮的变成亮)。

输入

每个测试数据值为包含一个整数n ( 0< n<= 10^5)单独一行构成,由多个测试数据,输入有EOF结束。

输出

对每种情况,输出执行了无穷多次开光灯操作后第n只灯泡的状态。0表示灯不亮,1表示等亮。每个测试数据的输出单独一行。

输入样例

1
5

输出样例

1
0
搜索更多相关主题的帖子: 开光 算法 
2009-11-07 20:50
lijm1989
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:珠海
等 级:贵宾
威 望:12
帖 子:675
专家分:2844
注 册:2009-10-14
收藏
得分:0 
LZ学习精神让我钦佩,不过LZ思考不太深,这样对学习不大好,我提供下思路,不提供代码,这题我以前做过,就按它的意思暴力算(精简点,我印象中不会超时)应该不会超时···不知道LZ试过没,还有一种就是观察规律,换个思路这题就是求一个数的约数的个数。
    因为改变灯的状态是要i的倍数才行。而当i>n时,i是不会改变n的状态了,就是说,i>n,后就不会理了,前面的话,也就只有i = 1;和i为n的约束时,才能改变灯的状态····
    LZ好好思考下··
2009-11-07 21:03
爱不死
Rank: 1
等 级:新手上路
帖 子:2
专家分:7
注 册:2009-11-7
收藏
得分:0 
学习了,谢谢哦

[url=http://da461123056./]格 格 书 屋[/url]
2009-11-07 21:24
剑木易
Rank: 2
等 级:论坛游民
帖 子:18
专家分:50
注 册:2009-10-28
收藏
得分:1 
scanf("%d",&n);
for(i=1;i<=n;i++)
{k=n/i;
for(j=1;j<k;j++)
{if(a[i*j]==0)a[i*j]=1;
else a[i*j]=0;}
}
2009-11-07 22:18
yinfuyong
Rank: 2
等 级:论坛游民
帖 子:35
专家分:45
注 册:2009-10-31
收藏
得分:0 
有点不太明白
2009-11-07 22:33
lijm1989
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:珠海
等 级:贵宾
威 望:12
帖 子:675
专家分:2844
注 册:2009-10-14
收藏
得分:0 
4L···直接模拟····
2009-11-07 23:29
liucs116
Rank: 2
等 级:论坛游民
帖 子:130
专家分:29
注 册:2009-11-4
收藏
得分:0 
#include<stdio.h>
int main()
{
    int n,a[100000],i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            k=n/i;
            for(j=1;j<k;j++)
            {
                if(a[i*j]==0)
                    a[i*j]=1;
                else
                    a[i*j]=0;
            }
        }
        printf("%d\n",a[i*j]);
    }
    return 0;
}
输出答案全是0,怎么会事?

学无止境!
2009-11-08 13:13
liucs116
Rank: 2
等 级:论坛游民
帖 子:130
专家分:29
注 册:2009-11-4
收藏
得分:0 
#include<stdio.h>
int main()
{
    int n,i,j,k,a;
    while(scanf("%d",&n)!=EOF && 0<=n && n<=100000)
    {
        a=0;
        for(i=1;i<=n;i++)
        {
            if(n%i==0)
            {
                if(a==0)
                    a=1;
                else
                    a=0;
            }
            if(i==n)
                printf("%d\n",a);
        }
    }
    return 0;
}
我重新改成这样怎么样?

学无止境!
2009-11-08 13:57
lijm1989
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:珠海
等 级:贵宾
威 望:12
帖 子:675
专家分:2844
注 册:2009-10-14
收藏
得分:1 
#include<stdio.h>
int main()
{
    int n,a[100000] = {0},i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            k=n/i;
            for(j=1;j<=k;j++)
            {
                if(a[i*j]==0)
                    a[i*j]=1;
                else
                    a[i*j]=0;
            }
        }
        printf("%d\n",a[n]);
    }
    return 0;
}
2009-11-08 14:09
lijm1989
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:珠海
等 级:贵宾
威 望:12
帖 子:675
专家分:2844
注 册:2009-10-14
收藏
得分:0 
8s 应该可以AC吧,不过建议LZ养成好的习惯,写的代码尽量复杂度小点,这道题可以小于o(n^1/2)的···
2009-11-08 14:15
快速回复:求开光灯的算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.066509 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved