반응형
다음 지식에서 재미있어 보이는 문제가 있어서 한번 짜 봤다.
문제는 다음과 같다.
2010년 4월 1일 추가 : 여기에 좀 더 재미있는 분석과 코드가 있다. Josephus Problem 이란 이름이 붙은 것 같다.
http://k.daum.net/qna/view.html?qid=44T6T
친구가 질문했는데 너무 어려워서 지인들의 설명을 듣고자 질문합니다.
1부터 30까지의 수를 가진 사람이 순서대로 원 주위로 앉아있을 때, 먼저, 9번째 앉아있는 사람을 쫓아내고, 그로부터 9칸을 더 간 18번째 사람을 쫓아낸다. 마찬가지로 9칸을 더 간 27번 사람을 쫓아내고, 그 다음, 또 9칸을 더 간 사람(6번)을 쫓아낸다.
그리 고 나서 9칸을 갈 때에는 9번째 앉았던 쫓겨난 사람은 없는 것으로 치고 9칸 뒤, 즉, 16번 사람을 쫓아내는 그런 방식을 생각할 때,
n번째로 쫓아내는 사람의 번호를 n을 이용해 나타내면???
(참고로, 쫓아내는 사람의 번호는 앞부분만 보면, 9-18-27-6-16-26-7-19-.....)
import java.util.ArrayList;간단해 보이는 걸 간단하게 짰는데도 자꾸 실수해서 맞는지는 모르겠다. 맞길 빈다. 이 코드를 돌리면 결과는 다음과 같다.
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
int 조건들[][] = {
{ 30, 15 }, { 30, 14 }, { 30, 13 }, { 30, 12 }, { 30, 11 }, { 30, 10 },
{ 30, 9 }, { 30, 8 }, { 30, 7 }, { 30, 6 }, { 30, 5 }, { 30, 4 }, { 33, 3 },
{ 4, 1 }, { 4, 2 }, { 4, 3 }, { 4, 4 }, { 4, 5 },
{ 4, 6 }, { 4, 7 }, { 4, 8 }, { 4, 9 }, { 4, 10 },
{ 4, 11 }, { 4, 12 }, { 4, 13 }, { 4, 14 }, { 4, 15 },
{ 4, 16 }, { 4, 17 }, { 4, 18 }, { 4, 19 }, { 4, 20 },
{ 4, 21 }, { 4, 22 },
{ 2, 1 }, { 2, 2 }, { 2, 3 }, { 2, 4 }, { 2, 5 }, { 2, 6 },
{ 3, 1 }, { 3, 2 }, { 3, 3 }, { 3, 4 }, { 3, 5 }, { 3, 6 },
{ 3, 7 }, { 3, 8 }, { 3, 9 }, { 3, 10 }, { 3, 11 }, { 3, 12 }
};
for(int 조건[] : 조건들) {
core(조건[0], 조건[1]);
}
for(int i = 2; i<7 ; i++) {
for(int j = 1; j < i*(i-1)*2; j++) {
core(i, j);
}
}
}
public static void core(int 전체좌석수, int 몇칸마다뽑을까) {
System.out.println();
System.out.print(전체좌석수 + " " + 몇칸마다뽑을까 + " : ");
ArrayList<Integer> l = new ArrayList<Integer>();
for(int i = 1; i <= 전체좌석수; i++)
{
l.add(i);
}
int 절대자리좌표 = -1, 사이칸수 = 0;
while(!l.isEmpty())
{
절대자리좌표++;
if(절대자리좌표 >= l.size())
{
절대자리좌표 = 0;
}
사이칸수++;
if(사이칸수 == 몇칸마다뽑을까)
{
사이칸수 = 0;
System.out.print(l.remove(절대자리좌표) + " ");
절대자리좌표--;
}
}
}
}
일반식은 어떻게 만들지 감도 잡히지 않는다. 뭔가 기발한 방법이 있는건가?
30 15 : 15 30 16 2 19 6 24 12 3 23 14 8 1 27 25 22 26 29 7 13 28 17 10 11 21 20 9 5 18 4
30 14 : 14 28 12 27 13 30 17 4 22 10 2 23 16 8 5 1 29 3 7 15 21 9 25 24 6 20 11 19 18 26
30 13 : 13 26 9 23 7 22 8 25 12 30 18 6 29 20 15 10 4 3 5 14 19 28 17 11 16 27 1 2 21 24
30 12 : 12 24 6 19 2 16 30 15 1 18 5 23 11 3 25 17 10 8 7 9 14 22 29 26 21 28 27 20 13 4
30 11 : 11 22 3 15 27 9 23 6 20 5 21 8 26 14 2 25 17 12 7 4 10 16 24 1 29 30 19 13 18 28
30 10 : 10 20 30 11 22 3 15 27 9 24 7 23 8 26 14 2 21 16 6 4 1 5 13 19 12 29 18 25 17 28
30 9 : 9 18 27 6 16 26 7 19 30 12 24 8 22 5 23 11 29 17 10 2 28 25 1 4 15 13 14 3 20 21
30 8 : 8 16 24 2 11 20 29 9 19 30 12 23 5 18 3 17 4 22 10 28 25 15 14 21 27 7 6 26 13 1
30 7 : 7 14 21 28 5 13 22 30 9 18 27 8 19 1 12 25 10 24 11 29 17 6 3 2 4 16 26 15 20 23
30 6 : 6 12 18 24 30 7 14 21 28 5 15 23 2 11 22 3 16 27 10 26 13 1 20 17 9 19 29 25 8 4
30 5 : 5 10 15 20 25 30 6 12 18 24 1 8 16 23 2 11 21 29 13 26 7 22 9 28 19 17 27 4 14 3
30 4 : 4 8 12 16 20 24 28 2 7 13 18 23 29 5 11 19 26 3 14 22 1 15 27 10 30 21 17 25 9 6
33 3 : 3 6 9 12 15 18 21 24 27 30 33 4 8 13 17 22 26 31 2 10 16 23 29 5 14 25 1 19 32 20 11 28 7
4 1 : 1 2 3 4
4 2 : 2 4 3 1
4 3 : 3 2 4 1
4 4 : 4 1 3 2
4 5 : 1 3 4 2
4 6 : 2 1 4 3
4 7 : 3 4 1 2
4 8 : 4 2 1 3
4 9 : 1 4 2 3
4 10 : 2 3 1 4
4 11 : 3 1 2 4
4 12 : 4 3 2 1
4 13 : 1 2 3 4
4 14 : 2 4 3 1
4 15 : 3 2 4 1
4 16 : 4 1 3 2
4 17 : 1 3 4 2
4 18 : 2 1 4 3
4 19 : 3 4 1 2
4 20 : 4 2 1 3
4 21 : 1 4 2 3
4 22 : 2 3 1 4
2 1 : 1 2
2 2 : 2 1
2 3 : 1 2
2 4 : 2 1
2 5 : 1 2
2 6 : 2 1
3 1 : 1 2 3
3 2 : 2 1 3
3 3 : 3 1 2
3 4 : 1 3 2
3 5 : 2 3 1
3 6 : 3 2 1
3 7 : 1 2 3
3 8 : 2 1 3
3 9 : 3 1 2
3 10 : 1 3 2
3 11 : 2 3 1
3 12 : 3 2 1
2 1 : 1 2
2 2 : 2 1
2 3 : 1 2
3 1 : 1 2 3
3 2 : 2 1 3
3 3 : 3 1 2
3 4 : 1 3 2
3 5 : 2 3 1
3 6 : 3 2 1
3 7 : 1 2 3
3 8 : 2 1 3
3 9 : 3 1 2
3 10 : 1 3 2
3 11 : 2 3 1
4 1 : 1 2 3 4
4 2 : 2 4 3 1
4 3 : 3 2 4 1
4 4 : 4 1 3 2
4 5 : 1 3 4 2
4 6 : 2 1 4 3
4 7 : 3 4 1 2
4 8 : 4 2 1 3
4 9 : 1 4 2 3
4 10 : 2 3 1 4
4 11 : 3 1 2 4
4 12 : 4 3 2 1
4 13 : 1 2 3 4
4 14 : 2 4 3 1
4 15 : 3 2 4 1
4 16 : 4 1 3 2
4 17 : 1 3 4 2
4 18 : 2 1 4 3
4 19 : 3 4 1 2
4 20 : 4 2 1 3
4 21 : 1 4 2 3
4 22 : 2 3 1 4
4 23 : 3 1 2 4
5 1 : 1 2 3 4 5
5 2 : 2 4 1 5 3
5 3 : 3 1 5 2 4
5 4 : 4 3 5 2 1
5 5 : 5 1 3 4 2
5 6 : 1 3 2 5 4
5 7 : 2 5 1 3 4
5 8 : 3 2 5 4 1
5 9 : 4 5 3 1 2
5 10 : 5 2 3 1 4
5 11 : 1 4 2 3 5
5 12 : 2 1 5 4 3
5 13 : 3 4 5 1 2
5 14 : 4 1 3 2 5
5 15 : 5 3 2 4 1
5 16 : 1 5 2 4 3
5 17 : 2 3 5 1 4
5 18 : 3 5 4 2 1
5 19 : 4 2 3 5 1
5 20 : 5 4 2 1 3
5 21 : 1 2 5 3 4
5 22 : 2 4 5 3 1
5 23 : 3 1 4 5 2
5 24 : 4 3 2 1 5
5 25 : 5 1 2 3 4
5 26 : 1 3 5 4 2
5 27 : 2 5 4 1 3
5 28 : 3 2 4 1 5
5 29 : 4 5 2 3 1
5 30 : 5 2 1 4 3
5 31 : 1 4 5 2 3
5 32 : 2 1 4 3 5
5 33 : 3 4 2 5 1
5 34 : 4 1 2 5 3
5 35 : 5 3 1 2 4
5 36 : 1 5 4 3 2
5 37 : 2 3 4 5 1
5 38 : 3 5 2 1 4
5 39 : 4 2 1 3 5
6 1 : 1 2 3 4 5 6
6 2 : 2 4 6 3 1 5
6 3 : 3 6 4 2 5 1
6 4 : 4 2 1 3 6 5
6 5 : 5 4 6 2 3 1
6 6 : 6 1 3 2 5 4
6 7 : 1 3 6 2 4 5
6 8 : 2 5 4 1 6 3
6 9 : 3 1 2 6 4 5
6 10 : 4 3 6 1 5 2
6 11 : 5 6 3 1 2 4
6 12 : 6 2 1 5 4 3
6 13 : 1 4 5 6 2 3
6 14 : 2 6 3 5 4 1
6 15 : 3 2 6 5 1 4
6 16 : 4 5 3 6 2 1
6 17 : 5 1 2 4 6 3
6 18 : 6 3 5 4 2 1
6 19 : 1 5 3 4 6 2
6 20 : 2 1 6 4 3 5
6 21 : 3 4 5 2 6 1
6 22 : 4 6 2 3 1 5
6 23 : 5 2 6 3 4 1
6 24 : 6 4 3 2 1 5
6 25 : 1 6 2 3 4 5
6 26 : 2 3 5 1 6 4
6 27 : 3 5 2 1 4 6
6 28 : 4 1 6 2 5 3
6 29 : 5 3 4 1 2 6
6 30 : 6 5 2 1 4 3
6 31 : 1 2 5 6 3 4
6 32 : 2 4 3 6 5 1
6 33 : 3 6 1 5 2 4
6 34 : 4 2 5 6 3 1
6 35 : 5 4 2 6 1 3
6 36 : 6 1 5 4 3 2
6 37 : 1 3 4 5 6 2
6 38 : 2 5 1 4 3 6
6 39 : 3 1 5 4 6 2
6 40 : 4 3 2 5 1 6
6 41 : 5 6 1 3 4 2
6 42 : 6 2 4 3 1 5
6 43 : 1 4 2 3 5 6
6 44 : 2 6 5 3 1 4
6 45 : 3 2 4 1 5 6
6 46 : 4 5 1 2 6 3
6 47 : 5 1 4 2 3 6
6 48 : 6 3 2 1 5 4
6 49 : 1 5 6 2 3 4
6 50 : 2 1 4 6 5 3
6 51 : 3 4 1 6 2 5
6 52 : 4 6 5 1 3 2
6 53 : 5 2 3 6 1 4
6 54 : 6 4 1 5 3 2
6 55 : 1 6 4 5 2 3
6 56 : 2 3 1 5 4 6
6 57 : 3 5 6 4 1 2
6 58 : 4 1 3 5 2 6
6 59 : 5 3 1 4 6 2
728x90
'프로그래밍 > Java' 카테고리의 다른 글
| [Java|Eclipse] classpath 세팅하기 (0) | 2010.03.30 |
|---|---|
| [JAVA|기초|클래스] 구 클래스 예제, 한글로 (0) | 2010.03.27 |
| [JAVA|UVa] 108 Maximum Sum (0) | 2010.03.19 |
| [JAVA|기초] The method format(String, Object[]) in the type String is not applicable (0) | 2010.03.18 |
| [Java] http://mindprod.com/jgloss/jgloss.html (0) | 2010.02.03 |
