100-18

1669 단어
18 번 문제 (배열):
제목: n 개의 숫자 (0, 1,..., n - 1) 가 원 을 이 루 고 숫자 0 부터
매번 이 동그라미 에서 m 번 째 숫자 를 삭제 합 니 다.
앞 숫자의 다음 숫자).
한 숫자 가 삭제 되면 삭 제 된 숫자의 다음 숫자 에서 m 번 째 숫자 를 계속 삭제 합 니 다.
이 동그라미 에 남 은 마지막 숫자 를 구하 세 요.
사고방식: 이 문 제 는 매우 기묘 한 것 같 습 니 다. 제 가 대학교 1 학년 때 대학교 2 학년 때 어떤 친구 가 저 에 게 말 했 습 니 다.그 당시 에 데이터 구 조 를 배 웠 을 때 가장 정상 적 인 사고 가 떠 올 랐 다. 체인 시 계 를 만 든 다음 에 머리 와 꼬리 목 걸 이 를 만들어 하나의 링 을 만 든 다음 에 옮 겨 다 녔 다. m 개가 될 때마다 링 에서 하나의 노드 를 삭제 하고 마지막 노드 가 남 을 때 까지 이 해 를 얻 었 다.지금 생각해 보면 이런 방법 도 확실히 복잡 한 편 은 아니다.하지만 그 때 는 너무 어 렸 습 니 다. 제목 에서 원 을 만 들 었 다 고 하 는 것 을 보고 체인 시 계 를 하나의 고리 로 만 들 었 습 니 다.물론 오늘 내 가 다시 이 문 제 를 풀 때 나 는 그렇게 복잡 한 데이터 구 조 를 만 들 생각 을 하지 못 했다. 지금 나 는 데이터 구 조 를 추상 적 으로 하고 배열 로 링 모양 의 링크 를 모 의 할 생각 을 할 것 이다.물론 조작 상의 편 의 를 위해 저 는 여기 서 표준 라 이브 러 리 의 vector 를 사용 하여 자신의 업 무량 을 줄 일 수 있 습 니 다.어떻게 링 을 시 뮬 레이 션 합 니까? 배열 의 크기 에 대해 모드 (%) 연산 만 하면 됩 니 다.
코드 붙 이기:
/*===========================================================*\
 18 (  ):
  :n   (0,1,…,n-1)      ,   0  ,
           m   (          ,     
         )。
        ,               m   。
                 。
\*===========================================================*/
#include <iostream>
#include <vector>

using namespace std;

int findM(int n,int m){
	if(n<1){
		return NULL;
	}
	vector<int> v;
	for(int i = 0 ; i < n ; ++i){//    
		v.push_back(i);
	}
	int pre = 0;
	while(v.size() > 1){//           1 ,          
		int pCurrent = (pre+m-1)%v.size();
		v.erase(v.begin() + pCurrent);
		pre = pCurrent;
	}
	return v[0];
}

int main(){
	int n = 10;//n>=1
	int m = 3;
	int ret = findM(n,m);
	cout << ret << endl;
	return 1;
}

좋은 웹페이지 즐겨찾기