C++에서 막대기를 n개로 잘랐을 때 n각형을 만들 수 있을 확률

문제 이해

임의의 길이를 가진 막대기 하나가 주어지고, 이 막대기를 무작위로 n개의 조각으로 자릅니다. 조각의 길이는 정수일 수도 있고 실수일 수도 있습니다. 이때 잘려 나온 조각들을 이어 붙여 n변 다각형을 만들 수 있는지, 그리고 그 확률이 얼마인지 구하는 것이 이 글의 목표입니다.

확률 계산 공식

n개의 조각으로 n변 다각형을 형성할 확률은 다음 공식으로 간단하게 계산할 수 있습니다.

$$P(E^{\prime})=1-P(E)=1-\frac{n}{2^{n-1}}$$

여기서 n은 막대기를 잘라서 얻은 조각의 개수입니다.

원리: n개의 조각 중 단 하나라도 나머지 조각들의 길이 합보다 길면 다각형을 만들 수 없습니다. 어떤 한 조각이 전체 길이의 절반을 초과할 확률은 1/2^(n−1)이며, 이러한 사건들은 서로 동시에 일어날 수 없으므로 실패 확률은 n/2^(n−1)이 됩니다. 따라서 성공 확률은 1 − n/2^(n−1)입니다.

입력 및 출력 예시

입력 1

length = 10 , pieces = 4

출력 1

probability is : 0.5

설명: 길이 10cm인 막대기를 4조각으로 잘랐을 때 다각형을 만들 수 있을 확률은 0.5입니다.

입력 2

length = 5 , pieces = 3

출력 2

probability is : 0.25

설명: 길이 5cm인 막대기를 3조각으로 잘랐을 때 삼각형을 만들 수 있을 확률은 0.25입니다.

접근 방법

• 막대기의 길이와 잘라낼 조각의 개수를 입력받습니다.

• 공식 1 − n/2^(n−1)을 적용하여 확률을 계산합니다.

• 계산된 결과를 화면에 출력합니다.

알고리즘

시작
Step 1 → 확률을 계산하는 함수 선언
    double probab(unsigned len, unsigned pieces)
        unsigned a = (1 << (pieces-1)) 선언
        return 1.0 - ((double)pieces) / ((double)a)
Step 2 → main() 함수에서
        unsigned pieces = 4, len = 10 선언
        probab(len, pieces) 호출
종료

C++ 예제 코드

#include<iostream>
using namespace std;
// 확률을 계산하는 함수
double probab(unsigned len, unsigned pieces){
    unsigned a = (1 << (pieces-1));
    return 1.0 - ((double)pieces) / ((double)a);
}
int main(){
    unsigned pieces = 4, len = 10;
    cout <<"probability is : "<<probab(len, pieces);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

probability is : 0.5