alt text

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055

asked 07 Oct '14, 23:07

%E8%B7%AF%E4%BA%BA%E7%94%B2's gravatar image

路人甲
131726860896


设灯号N的因子序列为:

[n1, n2, n3, ..., nX], 其中 n1 = 1, n1<n2<n3<...<nX

则灯N的亮灭值m为(亮为1,灭为0):

m = X%2

若N的标准因子分解式为:

N = 2^p1 * 3^p2 * ... * F^pY, F为N的最大素因子

那么

X = (p1+1) * (p2+1) * ... * (pY+1)

所以此题的思路是:

对灯号N做标准因子分解 -> 计算对应的X -> 统计: X1%2 + X2%2 + ... + X100%2

另外用bash做因子分解超快:

[perr@fedora ~]$ time factor 9999999999999999999999
9999999999999999999999: 3 3 11 11 23 4093 8779 21649 513239

real    0m0.001s
user    0m0.000s
sys     0m0.002s

实现以上思路的代码:

#!/usr/bin/bash

#fun: 计算$1参数的因子集的基数
fac2X(){
    N=$1
    X=1 #初始值
    f_ahead=1 #初始因子
    num=1 #pY+1
    factor $N | nawk -F':' '{print $2}' |\
        {
            read factor_lst
            for f in $factor_lst; do
                if [[ $f -eq $f_ahead ]]; then
                    ((num++))
                else
                    ((X=X*num))
                    num=2
                fi
                f_ahead=$f
            done
            ((X=X*num)) #补上最后一个素因子的个数
            echo -n $X
        }
}

#fun: 统计灯数和学生数同为$1的亮灯数
cnt(){
    lights=$1
    i=1
    sum=0
    while [[ $i -le $lights ]]; do
        (( sum=sum+$(fac2X $i)%2 ))
        (( i++ ))
    done
    echo $sum
}

测试及结果:

[perr@fedora ~]$ cnt 1
1
[perr@fedora ~]$ cnt 2
1<----------灯数2,灯1亮
[perr@fedora ~]$ cnt 3
1<----------灯数3,灯1亮
[perr@fedora ~]$ cnt 4
2<----------灯数4,灯[1,4]亮
[perr@fedora ~]$ cnt 100
10<---------有10盏灯亮,具体哪些灯亮自己改代码吧

关于手工求解:

可以看出,如果某个数的标准因子分解式里的某个指数是奇数,那么对应的X%2必为0

所以,所有的2^1乘以任意个数的3,5,7,11,...号灯不会点亮,待处理的灯号数立马就收敛不少

以此类推,3^1乘以任意个数的5,7,11,...等,可以计算出剩下灯里面有哪些是灭的

估计不错的话,这样计算个几次就可收敛到为数不多的灯.

然后对这剩下的几个灯号计算因子集基数进行验证.

以上是手工排除的方式,手工枚举的方式:

2^(任意偶数) * 3^(任意偶数) * 5^(任意偶数)*...所构造出的灯号都会被点亮

因为2^7=128>100,所以2的指数只能是[0, 2, 4, 6]

3^4=81<100,所以3的指数只能是[0, 2, 4]

5^3=125>100,所以5的指数只能是[0,2]

7^3>100,所以7的指数只能是[0,2]

11^2>100,所以11的指数只能是[0]

所有大于7的素数的指数只能是[0]

故而,使用2,3,5,7及它们对应指数范围可拼凑出全部这10个灯的灯号:

[ 1 4 9 16 25 36 49 64 81 100 ]

关于有没有其他的简便方法:

因为该题本质上是考察对因子集的分析,而整数的因子分布是没有特别规律的,或者说带有本质的随机性.所以没有其他简便方法.

前面的代码没有基于素数表

如果有素数表的话,根据手工枚举的思路,可对前面的代码进行的优化

可能bash里的factor就是基于素数表实现的,所以才超级快.

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 08 Oct '14, 13:14

perr's gravatar image

perr
406364151

编辑于 08 Oct '14, 18:18

偶来来回回改了11次哇,小学没毕业

(08 Oct '14, 13:40) perr perr's gravatar image

我写一篇文章也得花很长时间,几经斟酌~

(08 Oct '14, 14:03) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image
/*
 *单独对每盏灯分析,被拉了奇数次为亮。
 *编号为100灯需要对判断一百次是否被学生拉灯即从(1 ~ 100)进行求余。
 *同样道理99 (1~99)进行求余
 * ...
 * 编号为1的灯1 (1) 进行求余。
 *点灯游戏 */
#include <stdio.h>

int main(int argc, char **argv)
{
    int lightOnCount = 0;
    int lightCount = 0;
    int tempLightCount = 0;
    int i, drawLightCount;

    printf("Please input the number of lights:");
    scanf("%d", &lightCount);
    tempLightCount = lightCount;
    printf("the list light is on:\n");
    while(tempLightCount > 0)   
    {
        drawLightCount = 0;         //编号为tempLightCount的灯被拉灯次数
        i = tempLightCount;
        while(i>0)                 //计算编号为tempLightCount的灯被拉了多少次
        {
            if(0 == tempLightCount%i)
            {
                drawLightCount++;
            }
            i--;
        }
        if(0 != drawLightCount%2)  //灯被拉了奇数次,为亮
        {
            lightOnCount++;
            printf("%d ", tempLightCount);
        }
        tempLightCount--;
    }
    printf("\nThe total count of light on is:%d \n", lightOnCount);
    return 0;
}
系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 08 Oct '14, 14:51

answerOne's gravatar image

answerOne
313

编辑于 08 Oct '14, 16:26

%E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

原野之狼
1.9k9399116

这道应用题,可以转化为数学语言来描述:

1、给定N个自然数,1,2,3...N,分别求出其约数。

   对于1,其约数为(1),记为集合S1
   对于2,其约数为(1,2),记为集合S2
   对于3,其约数为(1,3),记为集合S3
   对于4,其约数为(1,2,4),记为集合S4
   ...
   对于N,其约数为(1,...,N),记为集合Sn

   求约数的方法不止一种:

   a. 最简单的方式就是采用迭代方式,即把所有数都枚举一遍,看能不能满足约数的定义,这种方法有其局限性,比如当N很大的时候,会带来巨大的计算量。

   b. 利用质因数分解来做。

      以45这个数为例,对其进行质因数分解,45=3×3×5=3^2*5^1,根据算数基本定理,该分解是唯一的。
      质因数分解可以采用计算机程序来实现,也可以借助质数表使用手工方式来做到。

      那么其约数包括:
      3^0*5^0 = 1
      3^0*5^1 = 5
      3^1*5^0 = 3
      3^1*5^1 = 15
      3^2*5^0 = 9
      3^2*5^1 = 45
      以上写法具有规律性,便于计算机编程实现,也便于手工编排。


2、统计以上各集合的元素个数

   对于集合S1,其个数为1,记为C1
   对于集合S2,其个数为2,记为C2
   对于集合S3,其个数为2,记为C3
   ...
   对于集合Sn,其个数为?,记为Cn

3、判断元素个数是奇数还是偶数,奇数项对应的灯表示亮

   对于C1,其为奇数
   对于C2,其为偶数
   对于C3,其为偶数
   ...
   对于Cn,其为?数

4、统计数据集(C1、C2、...,Cn)中奇数的个数可得亮灯总数
系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 07 Oct '14, 23:08

%E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

原野之狼
1.9k9399116

用程序来实现,这个是比较笨的方法,但是比较直观:

how_many_lights = 100
how_many_persons = 100

lights = [{'number':i, 'count':0} for i in range(1,how_many_lights + 1)]

for person in range(1,how_many_persons + 1):
    for light in lights:
        if light['number'] % person == 0:
            light['count'] = light['count'] + 1

count = 0

print "These lights are still on:"
for light in lights:
    if light['count'] % 2 == 1:
        print light
        count = count +1

print '\nThere are %d lights on' %count

可以采用这种方式里提到的方法b来进行优化,代码就不给出了。

对于刚才方式一中的程序,运行结果如下:

These lights are still on:
{'count': 1, 'number': 1}
{'count': 3, 'number': 4}
{'count': 3, 'number': 9}
{'count': 5, 'number': 16}
{'count': 3, 'number': 25}
{'count': 9, 'number': 36}
{'count': 3, 'number': 49}
{'count': 7, 'number': 64}
{'count': 5, 'number': 81}
{'count': 9, 'number': 100}

There are 10 lights on

仔细观察这些数: 1,4,9,16,25,36,49,64,81,100, 发现啥规律没有? 规律就是巧解的线索啊~

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 07 Oct '14, 23:13

%E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

原野之狼
1.9k9399116

编辑于 11 Oct '14, 09:31

我认为这个题可以编入编程之美了

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 08 Oct '14, 19:06

bigworld's gravatar image

bigworld
263

要的就是出精品,所以我才仔细撰写每一个解答。

现在已经有人跟进了,这是好现象。

高质量社区需要所有人的共同努力~

另外觉得写得好的答案,记得点赞!小手一抖就是对作者最大的支持 :)

(09 Oct '14, 00:07) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link: [text](http://url.com/ "title")
  • image: ![alt](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×33
×4

question asked: 07 Oct '14, 23:07

question was seen: 4,774 times

last updated: 11 Oct '14, 09:31

powered by O*S*Q*A

粤ICP备14040061号-1