// // main.cpp // jose // // Created by Masanori Fukui on 2014/08/27. // Copyright (c) 2014年 Educationation,Mathematics Software. All rights reserved. // #include #include #include using namespace std; int main(int argc, const char * argv[]) { vector num; vector numFlag; /* josephus graph definition */ /* num.push_back(1); num.push_back(2); num.push_back(3); num.push_back(4); num.push_back(5); num.push_back(6); num.push_back(7); num.push_back(8); num.push_back(9); num.push_back(10); numFlag.push_back(1); numFlag.push_back(2); numFlag.push_back(3); numFlag.push_back(4); numFlag.push_back(5); numFlag.push_back(6); numFlag.push_back(7); numFlag.push_back(8); numFlag.push_back(9); numFlag.push_back(10); */ /* r value */ int r; int nn; cout << "\n"; for(r = 2;r <= 50;r++){ cout << "(r = " << r << ")\n"; for(nn = 1;nn <= 200;nn++){ num.clear(); numFlag.clear(); for(int i = 1;i <= nn;i++){ num.push_back(i); numFlag.push_back(i); // cout << num.at(i - 1); } /* --- mode --- Circle Sequence -> shape = 0, direction = 0 Circle Cross -> shape = 0, direction = 1 Linear Sequence -> shape = 1, direction = 0 Linear Cross -> shape = 1, direction = 1 */ /* num.size() get */ int r_end = (int)num.size(); /* r sequence */ int rs = 0; /* r reverse */ int rr = r_end - 1; /* r value backup */ int rs_b = rs,rr_b = rr; /* r value */ // int r; // int pr = r; /* process */ int pr; /* step temporary */ int step_t = 1; /* step, s <= num.size() */ int s = nn; int shape = 0,direction = 1; int mod = 1; /* input value,shape and direction */ /* cout << "input r:"; cin >> r; cout << "input s:"; cin >> s; cout << "Circle or Linear?(0/1)"; cin >> shape; cout << "Sequence or Cross?(0/1)"; cin >> direction; */ /* value set */ pr = r; /* linear Josephus Problem Only */ if(shape == 1){ for(int i = r_end - 2;i > 0;i--) num.push_back(num.at(i)); for(int i = r_end - 2;i > 0;i--) numFlag.push_back(numFlag.at(i)); } /* main */ while(step_t <= s){ if((step_t % 2 == 1 && direction == 1) || direction == 0){ // if((step_t % 4 == 1 && direction == 1) || (step_t % 4 == 2 && direction == 1) || direction == 0){ // if((step_t % 6 == 1 && direction == 1) || (step_t % 6 == 2 && direction == 1) || (step_t % 6 == 3 && direction == 1) || direction == 0){ while(pr > 0){ if(numFlag.at(rs) != 0){ // pr--; if(numFlag.at(rs_b) != numFlag.at(rs) || step_t == 1 || step_t == s) pr--; rs_b = rs; // cout << "rs = " << rs << endl; // cout << numFlag.at(rs) << "a," << endl; if(pr != 0){ rs++; while(rs >= (int)numFlag.size()) rs = rs - (int)numFlag.size(); }else if(pr == 0){ if(step_t == nn) cout << numFlag.at(rs) << " "; // cout << numFlag.at(rs) << ",\n"; int rs_t = numFlag.at(rs); replace(numFlag.begin(),numFlag.end(),rs_t,0); step_t++; } }else{ rs++; while(rs >= (int)numFlag.size()) rs = rs - (int)numFlag.size(); } } }else if(step_t % 2 == 0 && direction == 1){ // }else if((step_t % 4 == 3 && direction == 1) || (step_t % 4 == 0 && direction == 1)){ // }else if((step_t % 6 == 4 && direction == 1) || (step_t % 6 == 5 && direction == 1) || (step_t % 6 == 0 && direction == 1)){ while(pr > 0){ if(numFlag.at(rs) != 0){ if(numFlag.at(rs_b) != numFlag.at(rs) || step_t == 2 || step_t == s) pr--; rs_b = rs; // pr--; if(pr != 0){ rs--; while(rs < 0) rs = rs + (int)numFlag.size(); }else if(pr == 0){ //cout << numFlag.at(rs) << ",\n"; if(step_t == nn) cout << numFlag.at(rs) << " "; int rs_t = numFlag.at(rs); replace(numFlag.begin(),numFlag.end(),rs_t,0); step_t++; } }else{ rs--; while(rs < 0) rs = rs + (int)numFlag.size(); } } } pr = r; } if(nn % 30 == 0) cout << "\n"; // if(nn % 64 == 0) cout << "\n"; } // nn cout << "\n"; } // r cout << "\n"; return 0; }