延安城鄉(xiāng)建設(shè)規(guī)劃局網(wǎng)站百度帳號(hào)登錄個(gè)人中心
約瑟夫問題
n 個(gè)小孩圍坐成一圈,并按順時(shí)針編號(hào)為1,2,…,n,從編號(hào)為 p 的小孩順時(shí)針依次報(bào)數(shù),由1報(bào)到m ,當(dāng)報(bào)到 m 時(shí),該小孩從圈中出去,然后下一個(gè)再從1報(bào)數(shù),當(dāng)報(bào)到 m 時(shí)再出去。如此反復(fù),直至所有的小孩都從圈中出去。請(qǐng)按出去的先后順序輸出小孩的編號(hào)。
Input
每行是用空格分開的三個(gè)整數(shù),第一個(gè)是n,第二個(gè)是p,第三個(gè)是m (0 < m,n < 300)。最后一行是:
0 0 0
Output
按出圈的順序輸出編號(hào),編號(hào)之間以逗號(hào)間隔。
Sample Input
8 3 4
0 0 0
Sample Output
6,2,7,4,3,5,1,8
#include<bits/stdc++.h>
using namespace std;
//隊(duì)列
int main(){int n,p,m;while(cin>>n>>p>>m){queue<int> children;if(n==0 && p==0 && m==0){break;}for(int i=1;i<=n;i++){children.push(i);}for(int i=1;i<p;i++){children.push(children.front());children.pop();}while(!children.empty()){for(int j=1;j<m;j++){children.push(children.front());children.pop();}if(children.size()!=1){cout<<children.front()<<",";}else{cout<<children.front();}children.pop();}}return 0;
}
貓狗收容所
有家動(dòng)物收容所只收留貓和狗,但有特殊的收養(yǎng)規(guī)則,收養(yǎng)人有兩種收養(yǎng)方式:
第一種為直接收養(yǎng)所有動(dòng)物中最早進(jìn)入收容所的
第二種為選擇收養(yǎng)的動(dòng)物類型(貓或狗),并收養(yǎng)該種動(dòng)物中最早進(jìn)入收容所的。
給定一個(gè)操作序列代表所有事件。
若第一個(gè)元素為1,則代表有動(dòng)物進(jìn)入收容所,第二個(gè)元素為動(dòng)物的編號(hào),正數(shù)代表狗,負(fù)數(shù)代表貓;
若第一個(gè)元素為2,則代表有人收養(yǎng)動(dòng)物,第二個(gè)元素若為0,則采取第一種收養(yǎng)方式,若為1,則指定收養(yǎng)狗,若為-1則指定收養(yǎng)貓。
請(qǐng)按順序返回收養(yǎng)的序列。
若出現(xiàn)不合法的操作,即沒有可以符合領(lǐng)養(yǎng)要求的動(dòng)物,則將這次領(lǐng)養(yǎng)操作忽略。
輸入:第一個(gè)是n,它代表操作序列的次數(shù)。接下來是n行,每行有兩個(gè)值m和t,分別代表題目中操作的兩個(gè)元素。
輸出:按順序輸出收養(yǎng)動(dòng)物的序列,編號(hào)之間以空格間隔。
#include<bits/stdc++.h>
using namespace std;
//隊(duì)列
int main(){int n,m,t;//兩個(gè)隊(duì)列,一個(gè)是貓,一個(gè)是狗//如何得知最早進(jìn)入收容所的動(dòng)物//解決方法:三個(gè)隊(duì)列:不現(xiàn)實(shí),當(dāng)貓或狗被領(lǐng)養(yǎng)的時(shí)候,總的隊(duì)列沒辦法刪除 //解決辦法(新): queue<int> cat;queue<int> dog;int counter=0;cin>>n;while(n--){cin>>m>>t;if(m==1){if(t>0){counter++;dog.push(counter);dog.push(t);}else if(t<0){counter++;cat.push(counter);cat.push(t);}}else if(m==2){if(t==0){if(!dog.empty() && !cat.empty()){if(dog.front()<cat.front()){dog.pop();cout<<dog.front()<<" ";dog.pop();}else{cat.pop();cout<<cat.front()<<" ";cat.pop(); }}else if(!cat.empty() && dog.empty()){cat.pop();cout<<cat.front()<<" ";cat.pop(); }else if(cat.empty() && !dog.empty()){dog.pop();cout<<dog.front()<<" ";dog.pop(); }}else if(t==1){if(!dog.empty()){dog.pop();cout<<dog.front()<<" ";dog.pop(); }}else if(t==-1){if(!cat.empty()){cat.pop();cout<<cat.front()<<" ";cat.pop();}}}}return 0;
}
(本題也可以把counter與編號(hào)合起來使用結(jié)構(gòu)體,需要注意一下隊(duì)列為空時(shí)的幾種情況)