信息學競賽習題解答5模擬-資料下載頁
2025-06-08 00:48本頁面
【正文】 （設每輪游戲過后N個學生擁有糖果的最大數(shù)目為max，最小數(shù)目為min）： （1）max不會增加； （2）min不會減少； （3）且任何一個糖果數(shù)多于min的學生，他的糖果數(shù)不會減少到min； （4）如果max和min不等，則至少有一個學生，他的糖果數(shù)會增加，這個學生就是糖果數(shù)最少的學生。解題分析： 對于給定的學生人數(shù)N，以及初始時N個學生的糖果數(shù)，最終需要進行游戲的輪數(shù)以及最終每個學生的糖果數(shù)是沒有規(guī)律可循的，只能進行模擬。模擬游戲的每一輪，直到N個學生的糖果數(shù)一樣為止。 以樣例輸入中的第1個測試數(shù)據(jù)為例解釋游戲的過程，圖（a）中圓圈里的數(shù)字表示初始時6個學生的糖果數(shù)，旁邊的數(shù)字表示學生的序號（從0開始，按逆時針順序排列）。圖（b）表示第1輪游戲，每個人將手上糖果數(shù)的一半分給右邊的學生（虛線箭頭所示）；如果某個學生手頭上的糖果數(shù)位奇數(shù)，則由老師再給一塊糖果湊成偶數(shù)塊，如圖（c）所示；第1輪游戲過后，每人手上的糖果數(shù)如圖（d）所示。 具體實現(xiàn)時，可以用一整型數(shù)組candys存儲N個學生（序號為0~N1，（a）所示）的糖果數(shù)。在模擬每一輪游戲時，要先用臨時變量（設為half0）保存第N1個學生糖果數(shù)的一半，然后將第i個學生的糖果數(shù)candys[i]更新為：candys[i]/2+candys[i1]/2；最后一個學生，即第0個學生的糖果數(shù)更新為：candys[0]/2+half0。 在判斷N個學生的糖果數(shù)是否一致時，注意只要有前后兩個學生的糖果數(shù)不一致的情況，就可以判斷這N個學生的糖果數(shù)不一致；另外第N1個學生右邊相鄰的學生是第0個學生，所以要取模，即要判斷candys[i]與candys[(i+1)%N]是否相等。101822222365361221142222113圖（a）初始 圖（b）分糖果+12222202022221919+1圖（c）湊成偶數(shù) 圖（d）第1輪游戲結束后 分糖果游戲（第1輪）CS55：爬動的蠕蟲(Climbing Worm)（來源： ZOJ 1494，程序設計方法及在線實踐指導（王衍等） P192）問題描述：一只1英才長的蠕蟲在一口深為n英寸井的底部。每分鐘蠕蟲可以向上爬u英寸，但必須休息1分鐘才能接著往上爬。在休息的過程中，蠕蟲又下滑了d英寸。上爬和下滑重復進行。蠕蟲需要多長時間才能爬出井？不足一分鐘按一分鐘計，并且假定只要在某次上爬過程中蠕蟲的頭部到達了井的頂部，那么蠕蟲就完成任務了。初始時，蠕蟲是趴在井底的（即高度為0）。輸入：輸入文件包括多個測試數(shù)據(jù)。每個測試數(shù)據(jù)占一行，為3個正整數(shù)n,u,d，其中n是井的深度，u是蠕蟲每分鐘上爬的距離，d是蠕蟲在休息的過程中下滑的距離。假定du，n100。n=0表示輸入數(shù)據(jù)結束。輸出：對輸入文件中的每個測試數(shù)據(jù)，輸出一個整數(shù)，表示蠕蟲爬出井所需要的時間（分鐘）。樣例輸入：10 2 120 3 10 0 0樣例輸出：1719解題分析： 蠕蟲爬動的過程和判斷蠕蟲是否爬出井的依據(jù)都是很簡單的，到底需要多少分鐘才能爬出井要通過計算得出，本題適合用“模擬”思路求解。 在本題中，整個模擬過程是通過一個永真循環(huán)實現(xiàn)的，在該循環(huán)里，先是上爬一分鐘，蠕蟲的高度要加上u，然后判斷是否達到或超過了井的高度，如果是則退出循環(huán)；如果不是則要下滑d距離。也就是說，執(zhí)行一次循環(huán)，實際上上爬了一分鐘和下滑一分鐘。是否退出循環(huán)是在上爬后判斷的。10
教學教案相關推薦
鄂ICP備17016276號-1