내가 소싯적 고딩때 못풀었던 문젠데, 아직도 모르겠다. A┌─┬─┬─┬─┐B ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ └─┴─┴─┴─┘ 이런 3 x 4 사각형모양의 도선이 배열되어있고 길이 1짜리 변들이 각각 전류가 흐를 확률이 1/2씩 된다고 할때, 점 A(좌상 모서리)에서 점 B(우상 모서리) 사이에 전류가 흐를 확률은? 답은 모르는데 옛날에 후배하나한테 물어봤을때 "아 그문제요? 힌트를 드리자면 n x (n+1) 사각형 꼴일땐 풀수있는데 다른 사각형에선 안돼요"라고 했는데 암만 해봐도 잘 안나옴. 물갤에 물어보니 프로그래밍 안 배웠냐 프로그래밍 하면 되겠는데 하던데 함정은 수학 문제에 나왔는데 뭔 얼어죽을 프로그래밍이여 뭐 그건 일단 접어두고 프로그래밍하면 얼마가 나오나요 |
프갤 아재들한테는 이거 쉽나요?
Reman(skravin4u)
2015-06-10 19:51
추천 0
댓글 41
다른 게시글
-
벽이라는게 [1]11(112.149) | 15.06.10추천 0
-
원래 짜장면이 비싼 음식이었잖아. [2]☎2.60™(roidz) | 15.06.10추천 0
-
일하면서 이민가기위해 영어 공부할 시간은 있음? [1]비전비전맨(kiop2626) | 15.06.10추천 0
-
니들 인생 망한이유 알려준다 [1]익명(175.223) | 15.06.10추천 0
-
롤이나 하스스톤같은 pc게임 만드려면 [6]ㄴ(175.195) | 15.06.10추천 0
-
20대중반 비전공충인데 게임플머로 취업하려면 어케해야댐 [1]비전비전맨(kiop2626) | 15.06.10추천 0
-
근데 코세형은 창업 욕구 어케 참음? [6]철구(218.157) | 15.06.10추천 0
-
지금생각해보니깐 빡친다 [1]나라뜨(skfhddlg) | 15.06.10추천 0
-
솔직히 관노저새끼 군대 안다녀온듯 [1]철구(218.157) | 15.06.10추천 0
-
ㅅㅅㅅ같은님들 봐주셈 Win32 API 질문 [2]ㅁㄴㅇㄹ(49.174) | 15.06.10추천 0
걍 (1/2)^4 아님 ?
직선 케이스 말고 모든 케이스 다구하는거냐 ?
그리고, 한번 지나간 변에 대해서는 다시 전류가 통하지 않는다고 가정하고 가는 것이겠네 ?
ㄴ 그렇죠
1/2라는 확률 자체는 각 선에 0과 1 두 가지 경우의 수가 있다는 것과 동치이므로 굳이 계산 안해도 됨.
처음엔 (해당 경우의 수) / (전체 경우의 수 = 2^31) 이라 생각했었는데 이렇게 복잡하게 구할 필요가 전혀 없어.
중요한 건 B에 전류가 도달하냐 마냐라서. 답은 3/4야.
잠만 이거 존나 복잡한 문제네. 다시 생각 점.
걍 1 아님?
도선을 지날 최소 확률은 (1/2)^n 이잖아. (여기서 n 은 A 부터 B 까지 가로방향 노드의 수)
거기서 아래로 도선이 늘어날수록 확률은 높아지는거지?
아 나도 착각했군.
돌아가는 경로를 줄이면 안되는구낭.
이 문제를 푸는 관건은 임의의 가로, 세로가 주어지고 좌상단 모서리에서 출발해서 갈 수 있는 모든 경로의 개수를 구할 수 있느냐? 와
출발지와 도착지가 주어질 때 사이의 모든 경로를 찾을 수 있느냐인데. 약간 성가시군.
아랫쪽으로 한번 꺽으면 거리가 2 늘어나는 구조양.
꺾으면
3이 늘어날 수도 있죠.
끝쪽으로 가면 1만 늘 수도 있고요.
아냥. 잘 생각해봐.
아래로 한번 내려간다는건 항상 2 늘어나. 위로 올라가는건 상관없구.
순서를 따지지 않겠다면 2인 건 맞겠네요.
아래 위 아래 이러면 4가 늘어나는거지
경로 자체는 첫 한단만 볼때 2의 4승가지로 나누어지구
이때 윗쪽길 선택을 0 아랫쪽길 선택을 1로 표현해보면, 1 000 또는 1 0 1 0 처럼 연속하지 않은 1이 등장할때 경로 + 2가 추가되는식
P(0,0) = 1, P(-1, y) = 0, P(x, -1) = 0, P(w+1, y) = 0, P(x, h+1) = 0, P(x, y) = P(x - 1, y) × 0.5 + P(x, y - 1) × 0.5 형태로 정의는 되네요. 이 상황에서 P(w, 0) 을 구하라는 게 문제.
프로그래밍으로 구하라면 어렵지 않게 구할 수 있겠지만 ㅋㅋ 수학적으론 노답
그런데 n n+1에만 된다고 하니 n n+1에서만 쉽게푼 편법이 있나보지뭐
아 잘못 풀었다 ....
그리고 예시를 전류라고 드니깐 진짜 전류적 특성으로 보면 말도 안되고 ㅋㅋ
P(x, y) = P(x - 1, y) × 0.5 + P(x, y - 1) × 0.5 + (1 - P(x, y)) * (P(x + 1, y) * 0.5 + P(x, y + 1) * 0.5). 이게 맞을 듯. 밑이나 오른쪽에서 거꾸로 가는 거까지 고려하면.
전류가 통하냐 안통하냐의 문제지 전류의 세기를 구하는 문제가 아니니까. 말은 됨.
저건 그냥 도선 사이에 스위치들이 붙어있는거임.
스위치가 open 이냐 close 냐 의 확률이 50% 인거고
정정. 1 - P (x, y) 부분은 t(x, y) = P(x - 1, y) × 0.5 + P(x, y - 1) × 0.5라 두면 t(x, y) * (3/8) + (1 - t(x, y))로 정정.
뭔가존나 신들의 대화같다
근데 뒤로 가는게 허용되는거야 아닌거야 ㅡ,.ㅡ 단순 스위치 문제면 뒤로 가는것도 허용이어야 하는데... 헷갈리네.
뒤로가는거 불허에 B 가 우측 하단이면 걍 단순하게 답 나오는 문제구만
http://dblack.tk
커뮤니티 사이트 입니다 많은 이용 부탁 드립니다.
랜덤으로 통계내면 야매로 대충 나올거같다.
뒤로 가는 거 불허요