一区在线影院,亚洲精品日韩激情在线电影,欧美日韩不卡

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 閱讀(739) 評論(0) 編輯收藏引用所屬分類: 算法＋數據結構

只有注冊用戶登錄后才能發表評論。


相關文章: 銀行家算法求得含有最多連續特定字符個數的字符串排序從str中刪除remove中含有的字符 Write a routine that prints out a 2-D array in spiral order 100扇門，100個人，第i個人經過門號可以整除i的門。經過時，如果門開就關，如果門關就開。問最后所有門的狀態是什么。統計1的個數全排列的生成算法進制轉換程序

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

C++ Jounior

100扇門，100個人，第i個人經過門號可以整除i的門。經過時，如果門開就關，如果門關就開。問最后所有門的狀態是什么。

導航

留言簿(1)

隨筆分類

友情鏈接

搜索

最新隨筆

最新評論

閱讀排行榜