|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
08/11/17 21:07
한붓 그리기...가 뭐죠?; 기본적으로 경우의 수에서 정형화된 '공식'은 존재하지 않습니다. 이 글의 그림 같은 문제야 너무 많이 노출되서 공식처럼 암기해서 풀지만 기본적으로 경우의 수는 공식 싸움이 아니죠. 그래서 2,3등급이 정말 머리 터지는 부분이기도 하구요-_-;
08/11/17 21:21
한붓그리기의 용어를 잘못 쓰신듯한데요, 아무튼 홀수점의 개수가 3개 이상이니까 한붓그리기는 불가능 하구요..
질문의 요지는 최단거리까지 포함해서 같은 길(선분과 점)을 두번지나지 않고 A에서 B까지 가는 길의 개수를 물어보시는것 같네요.
08/11/17 21:26
문제가 윗분 말씀대로라면 Drefuys법이라는 알고리즘을 쓰면 컴퓨터로 구할수 있습니다.
컴퓨터로 구해도 좀 복잡한데 그냥 구하는건 불가능할듯;;;
08/11/17 22:06
飛上님// 이해하신 것이 맞습니다. 다만 선분은 두번 지나면 안되지만 점은 여러번 지나도 됩니다. 한 붓 그리기 할 때 처럼 말이죠.
SaiNT님// 그 알고리즘이라는 것은 컴퓨터에게 '어떤 방식으로 해라' 라고 시켜서 모든 길을 하나씩 세어 보는 것인가요? (n+n)!/n!n! 경우 가로길의 갯수와 세로길의 갯수를 조합하는 방식으로 공식을 유도해 모든 형태의 바둑판 모양의 길의 최단 거리 경우의 수를 나타낸 것인데, 이런 식으로 유도가 가능한지 알고 싶네요.
08/11/17 22:34
박진호님// 일반적인 식을 구하기는 쉽지 않을 듯 하네요..
n x n 에서 최단거리가 아니라는 것은 뒤돌아서 가는 방향이 생긴다는 것인데, 그것의 개수는 1, 2, 3, ...., n가지 일 수 있겠구요, 상황도 좌우나, 상하로 생각할 수 있습니다. 각각의 경우를 세고자 한다면 (n+2i) x n에서 전진 & 후진하는 경우가 일직선상이 되는 경우*2를 생략하면 되겠으나 아날로그적으로 구하는 방법은 쉽지 않겠습니다. 혹은 아래, 위로 가는 경우와 왼쪽, 오른쪽으로 가는경우의 개수를 (a,b,c,d)라 두면 (n+i, i ,n+j , j) 들의 케이스별로 분리가 될텐데요 길의개수는 n(n+1)/2 로써 한정적이니까 케이스의 수도 한정적일 뿐만 아니라 그렇게 많지도 않을듯 합니다. 하지만 역시 그 케이스별로 개수를 세는 것은 역시나 쉽지 않아 보입니다. ^^ 한줄요약 결론은 능력이 딸려서 못구하겠네요^^;;;;;; 국토순례자님 // 그 방법은 최단거리의 경우의 수를 셀때 쓸 수 있습니다.
|
||||||||||||
