• <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)
            


		
            隨筆分類
            
		
				
			
	
		
            友情鏈接
            
		
				
			
	



            搜索
            



            最新隨筆
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            			
			

	
    
    







            
	   
	



热RE99久久精品国产66热|
久久久精品久久久久影院|
久久精品中文騷妇女内射|
国产亚洲欧美精品久久久|
欧美精品一区二区精品久久|
久久97久久97精品免视看秋霞|
精品久久久久国产免费|
一本一本久久a久久综合精品蜜桃|
久久精品水蜜桃av综合天堂|
狠狠人妻久久久久久综合|
婷婷久久精品国产|
国产精品久久久久久久久鸭|
久久免费国产精品|
97精品久久天干天天天按摩|
伊人久久大香线蕉精品不卡|
99久久精品费精品国产一区二区|
欧美久久一区二区三区|
.精品久久久麻豆国产精品|
亚洲国产日韩欧美综合久久|
国产精品9999久久久久|
亚洲乱码日产精品a级毛片久久|
国产精品久久久久久久
|
久久亚洲天堂|
久久国产亚洲精品无码|
国内精品九九久久精品|
久久国产精品免费|
99久久精品国产免看国产一区|
久久久久久精品免费看SSS|
国产精品美女久久久久av爽
|
日韩精品久久久久久免费|
婷婷久久综合九色综合绿巨人|
久久99精品国产99久久|
久久国产精品成人影院|
久久国产欧美日韩精品免费|
久久精品国产亚洲av瑜伽|
91麻豆精品国产91久久久久久|
AV狠狠色丁香婷婷综合久久|
久久99精品久久只有精品|
久久久久99精品成人片试看|
久久国产免费观看精品3|
久久精品国产精品国产精品污|