C++ Jounior

once setback,once inspiration,once self-awareness
重要的是这个磨练过程,而不是结果,要的是你粗壮的腿,而不是你身上背的那袋盐巴

 

100扇门,100个人,第i个人经过门号可以整除i的门。经过时,如果门开就关,如果门关就开。问最后所有门的状态是什么。

#include    < stdio.h >  

#define    N   100 
#define    OPEN   1 
#define    CLOSED   0 

void    switch_door( int     * door) 

        
if ( * door    ==    OPEN) 
                
* door    =    CLOSED; 
        
else  
                
* door    =    OPEN; 
}
 

int    main( void

        
int    door[N    +     1 ];    //    waste   a   door 
         int    person; 
        
int    i; 

        
for (i    =     1 ;   i    <=    N;   i ++
                door[i]   
=    OPEN;    //    all   doors   are   open   at   first 

        
for (i    =     1 ;   i    <=    N;   i ++
                
for (person    =     1 ;   person    <=    N;   person ++ )    //    person   pass   through   the   door 
                         if (i    %    person    ==     0
                                switch_door(
& door[i]); 

        
for (i    =     1 ;   i    <=    N;   i ++
                printf( 
" door   %d:   %s\n  " ,   i,   door[i]    ?     " Open  "    :    " Closed  " ); 

        
return     0
}
 

给一个此题的思想:
要看门的状态,主要是看这扇门开关次数,开关奇数次会使门的状态改变,而偶数次就不会。而只要能够知道当前门的编号能够整除的自然数,就可以知道门的状态是否改变了。从而知道门当最终的状态。

下面我们将所有的数分为两组,平方数(1,4,9……)和非平方数(为什么要这么分?下面就知道了)。
现在讨论非平方数的情况。我们假设门号为N,同时假设从1开始到int(N^(1/2))(也就是N的开方数舍小数取整),总共有M个数能整除N,则从int(N^(1/2))+1到N,总共则对应也有M个数能够将N整除。(这句话仔细想一下)。
在此,就有2*M个数能将N整除,它是一个偶数。因此门开关了偶数次,门的状态最后不会被改变。

现在讨论平方数,因为N^(1/2)这个数是一个整数,因此我们将从1到N的所有的数用N^(1/2)这个数分成两部分(不包括N^(1/2)),同样假设前半部分有M个数可以将N整除,则后半部分也有M个数可以将N整除,这样就有2*M个数可以整除N了,再加上N^(1/2)这个数。总共就有2*M+1个数可以整除N,也就是编号为N的门会开关2*M+1次,门的状态就会被改变了。

综上,如果门号数是平方数的,门的状态就会发生改变,而不是平方数的就不会改变状态了。因此,只要检查门是否为完全平方数就可以判断门的状态为开还是为关了。

帖上代码: 
#include   
< iostream >  
#include   
< cmath >  
using     namespace    std; 

int    main() 

        
int    k; 
        
for ( int    i    =     1 ;   i    <= 100 ;   i ++
        

        cout   
<   <     " Door    "     <   <    i   ; 
        k   
=     int (sqrt(i)); 
        
if (k * k    ==    i) 
        cout   
<   <     " :   Closed  "
        
else  
        cout   
<   <     " :   Open  "
        cout   
<   <    endl; 
        }
 
return     0
}
 
当然,这是利用了人数与门数是相等的情况。如果个数不同的话,还是按照一楼的来。

Reference : http://topic.csdn.net/u/20070620/14/3d5e96d5-169a-4bc6-887c-ca8639cd8c63.html

posted on 2008-04-02 09:20 snowball 阅读(629) 评论(0)  编辑 收藏 引用 所属分类: 算法+数据结构


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

留言簿(1)

随笔分类

友情链接

搜索

最新随笔

最新评论

阅读排行榜