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