• <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)這個數?？偣簿陀?*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 閱讀(728) 評論(0)  編輯 收藏 引用  所屬分類: 算法＋數據結構 
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
			
            
				
					

            導航
            

					
					
					

            留言簿(1)
            


		
            隨筆分類
            
		
				
			
	
		
            友情鏈接
            
		
				
			
	



            搜索
            



            最新隨筆
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            			
			

	
    
    







            
	   
	



午夜精品久久久久久影视777|
久久99热这里只有精品66|
久久精品一本到99热免费|
日韩精品久久久久久久电影蜜臀
|
久久男人中文字幕资源站|
久久久久久国产精品无码下载|
久久亚洲精品成人无码网站|
久久国产精品久久精品国产|
青青草原综合久久大伊人|
狠狠色丁香久久婷婷综合五月
|
国内精品九九久久精品
|
2020国产成人久久精品|
久久精品国产亚洲av高清漫画|
久久无码人妻一区二区三区午夜|
久久天堂AV综合合色蜜桃网
|
国产精品久久精品|
久久精品亚洲福利|
国内精品久久国产大陆|
久久久久亚洲AV综合波多野结衣|
97久久国产亚洲精品超碰热
|
久久久久这里只有精品
|
久久国产精品二国产精品|
久久国产色AV免费看|
欧美粉嫩小泬久久久久久久
|
色欲综合久久躁天天躁|
精品999久久久久久中文字幕|
99精品久久精品一区二区|
婷婷久久综合|
超级碰碰碰碰97久久久久|
久久久综合香蕉尹人综合网|
久久久久久A亚洲欧洲AV冫|
一本色道久久88加勒比—综合|
国产欧美久久一区二区|
99久久精品国产高清一区二区|
久久久久99精品成人片直播|
亚洲AV无码久久寂寞少妇|
亚洲国产精品一区二区久久hs|
午夜不卡久久精品无码免费|
久久人人爽人人爽人人片AV不
|
国内精品伊人久久久久|
国产69精品久久久久777|