• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

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


	


            
	    
    




            






            

				
			
            
			
            
				
					

            導航
            

					
					
					

            留言簿(1)
            


		
            隨筆分類
            
		
				
			
	
		
            友情鏈接
            
		
				
			
	



            搜索
            



            最新隨筆
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            			
			

	
    
    







            
	   
	



欧美久久天天综合香蕉伊|
久久国产色AV免费观看|
久久精品国产一区二区电影|
亚洲国产精品婷婷久久|
三级韩国一区久久二区综合
|
久久精品国产亚洲av影院|
国产综合久久久久久鬼色|
国内精品久久久久久野外|
精品久久久无码中文字幕|
精产国品久久一二三产区区别|
97久久国产亚洲精品超碰热|
日韩久久无码免费毛片软件|
香蕉久久夜色精品升级完成|
国内精品久久久久久久久|
中文字幕久久精品无码|
色综合久久最新中文字幕|
久久国产AVJUST麻豆|
国产情侣久久久久aⅴ免费|
久久亚洲国产精品成人AV秋霞|
a高清免费毛片久久|
国内高清久久久久久|
久久亚洲中文字幕精品一区四|
色婷婷久久综合中文久久蜜桃av|
久久国产精品免费一区|
精品999久久久久久中文字幕|
久久精品国产2020|
欧洲国产伦久久久久久久|
国产精品青草久久久久福利99|
久久久精品2019免费观看|
久久精品无码一区二区WWW|
久久久久久亚洲精品不卡
|
99国产精品久久|
热re99久久6国产精品免费|
一级做a爰片久久毛片免费陪|
久久精品无码一区二区三区日韩
|
97精品伊人久久久大香线蕉|
久久九九精品99国产精品|
日韩精品久久久久久久电影蜜臀|
怡红院日本一道日本久久|
91精品国产91久久久久福利|
国产精品久久久久久影院
|