信息學(xué)競賽習(xí)題解答5模擬(已修改)
2025-06-20 00:48 本頁面
【正文】 《算法與程序?qū)嵺`》習(xí) 題 解 答5——模擬現(xiàn)實(shí)中的有些問題，難以找到公式或規(guī)律來解決，只能按照一定步驟，不停地做下去，最后才能得到答案。這樣的問題，用計(jì)算機(jī)來解決十分合適，只要能讓計(jì)算機(jī)模擬人在解決此問題的行為即可。這一類的問題可以稱之為“模擬題”。比如下面經(jīng)典的約瑟夫問題：CS51：約瑟夫問題（來源： 2746，程序設(shè)計(jì)導(dǎo)引及在線實(shí)踐（李文新） P141）問題描述： 約瑟夫問題：有ｎ只猴子，按順時(shí)針方向圍成一圈選大王（編號從１到ｎ），從第１號開始報(bào)數(shù)，一直數(shù)到ｍ，數(shù)到ｍ的猴子退出圈外，剩下的猴子再接著從1 開始報(bào)數(shù)。就這樣，直到圈內(nèi)只剩下一只猴子時(shí)，這個(gè)猴子就是猴王，編程求輸入ｎ，ｍ后，輸出最后猴王的編號。輸入：每行是用空格分開的兩個(gè)整數(shù)，第一個(gè)是 n，第二個(gè)是m ( 0 m, n 300) 。最后一行是：0 0輸出：對于每行輸入數(shù)據(jù)（最后一行除外)，輸出數(shù)據(jù)也是一行，即最后猴王的編號。樣例輸入：6 212 48 30 0樣例輸出：517解題思路：初一看，很可能想把這道題目當(dāng)作數(shù)學(xué)題來做，即認(rèn)為結(jié)果也許會(huì)是以n和m為自變量的某個(gè)函數(shù)f(n,m)，只要發(fā)現(xiàn)這個(gè)函數(shù)，問題就迎刃而解。實(shí)際上，這樣的函數(shù)很難找，甚至也許根本就不存在。用人工解決的辦法就是將n個(gè)數(shù)寫在紙上排成一圈，然后從1開始數(shù)，每數(shù)到第m個(gè)就劃掉一個(gè)數(shù)，一遍遍做下去，直到剩下最后一個(gè)。有了計(jì)算機(jī)，這項(xiàng)工作做起來就會(huì)快多了，我們只要編寫一個(gè)程序，模擬人工操作的過程就可以了。用數(shù)組anLoop來存放n個(gè)數(shù)，相當(dāng)于n個(gè)數(shù)排成的圈；用整型變量 nPtr指向當(dāng)前數(shù)到的數(shù)組元素，相當(dāng)于人的手指；劃掉一個(gè)數(shù)的操作，就用將一個(gè)數(shù)組元素置0的方法來實(shí)現(xiàn)。人工數(shù)的時(shí)候，要跳過已經(jīng)被劃掉的數(shù)，那么程序執(zhí)行的時(shí)候，就要跳過為0的數(shù)組元素。需要注意的是，當(dāng)nPtr指向anLoop中最后一個(gè)元素（下標(biāo)n1）時(shí)，再數(shù)下一個(gè)，則nPtr要指回到數(shù)組的頭一個(gè)元素（下標(biāo)0），這樣anLoop才象一個(gè)圈。參考程序：include include define MAX_NUM 300int aLoop[MAX_NUM+1]。int main(){ int n,m,i。 while(1) { scanf(%d%d,amp。n,amp。m)。 if(n==0) break。 for(i=0。in。i++) aLoop[i]=i+1。 int nPtr=0。 //存儲位置信息 for(i=0。in。i++) //每次循環(huán)將1只猴子趕出圈子 { int nCount=0。 //記錄本輪數(shù)到的猴子數(shù)目 while(nCountm) //一直要數(shù)出m個(gè)猴子 { while(aLoop[nPtr]==0) //跳過已經(jīng)出圈的猴子 nPtr=(nPtr+1)%n。 //到下一個(gè)位置，如果到最后就跳到第1個(gè) nCount++。 nPtr=(nPtr+1)%n。 } nPtr。 //找到要出圈的猴子，位置要回退一個(gè) if(nPtr0) nPtr=n1。 if(i==n1) //最后一個(gè)出圈的猴子 printf(%d\n,aLoop[nPtr])。 aLoop[nPtr]=0。 } } return 0。}注意事項(xiàng)：上面的程序完全模擬了人工操作的過程，但因?yàn)橐磸?fù)跳過為0 的數(shù)組元素，因此算法的效率不是很高。后文的“鏈表”一章，采用單鏈表進(jìn)行模擬來解決本題，就能省去跳過已出圈的猴子這個(gè)操作，大大提高了效率。n 個(gè)元素的數(shù)組，
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1