아 리 필기시험 -- 장 군 과 아가씨 데이트

2515 단어 알고리즘c-c++
제목:
장 군 은 여러 해 동안 설 을 쇠 면서 집에 돌아 오지 않 았 다. 이번에 집에 돌아 와 서 부모님 께 서 그 에 게 소 개 팅 하 는 아가 씨 를 많이 배정 해 주 셨 다. 긴 명단 이 있 는데 길 이 는 N 이다.아버 지 는 데 이 트 를 준비 하 는 일 을 맡 으 셨 고, 매번 선 을 볼 상 대 를 무 작위 로 선택 하 셨 으 며, 어머니는 어떤 아가씨 가 이미 데 이 트 를 했 는 지 기록 하 는 일 을 맡 으 셨 다.모든 아가씨 와 데 이 트 를 한 번 다 한 후에 야 이 거대 한 소 개 팅 공사 가 끝 날 것 이다.요 며칠 동안 부모 가 싸 우 고 있어 서 그들 사이 에는 어떠한 말 도 통 하지 않 을 것 이다.그래서 아버 지 는 어떤 아가씨 가 이미 데 이 트 를 했 는 지 모른다.따라서 다음 데이트 상 대 는 이미 데 이 트 를 했 을 가능성 이 높다.만약 장 군 이 모든 아가 씨 를 한 번 데 이 트 를 하려 고 한다 면, 평균 몇 명의 아가 씨 를 데 이 트 를 해 야 합 니까?
사고: 이것 은 확률 문제 입 니 다. 주로 수학 기 초 를 검사 하고 공식 을 내 놓 은 후에 몇 줄 의 코드 를 내 놓 으 면 해결 할 수 있 습 니 다.확률론 에서 '초대권 수집 문제' 를 잘 알 고 있다 면 이 문 제 는 쉽게 풀 릴 것 이다.
4. 567917. 기대치 계산: T 가 모든 N 명의 여자 와 데 이 트 를 마 친 횟수 라 고 가정 하면 ti 는 i - 1 번 여자 와 데 이 트 를 한 후에 i 번 째 (예전 에 데 이 트 를 하지 않 았 던) 로 데 이 트 를 한다.아가씨 가 쓰 는 횟수, 그러면 T 와 ti 는 모두 무 작위 변수 입 니 다. i - 1 명의 아가 씨 를 데 이 트 를 한 후에 새로운 아가 씨 를 데 이 트 를 할 확률 pi = n - i + 1n 이기 때문에 ti 는 기하학 적 분포 이 고 기대 치 1pi 가 있 습 니 다. 기대 치 의 선형 성에 따라:
E(T)=====E(t1)+E(t2)+⋯+E(tn)1p1+1p2+⋯+1pnnn+nn−1+⋯+n1n(11+12+⋯+1n)nHn
그 중에서 Hn 은 조화 수 이 고 그 근사치 에 따라 E (T) = nHn = nlnn + 로 변 할 수 있다.γn + 12 + o (1), as n → ∞, 그 중γ≈ 0.5772156649 는 오 라 마 히 로 상수 이다.
C + + 코드 는 다음 과 같 습 니 다.
#include 
#include 
#include 
#include 
#include 

using namespace std;


/*         ,         */
/*  ,                ,           ^-^ */
/******************************     ******************************/
double date(int N) {
    double H = 0;
    for (int i = 1; i <= N; i++)
    {
        H += 1.0 / i;
    }

    return N * H;
}
/******************************     ******************************/


int main() {
    double res;
    int N;
    cin >> N;

    res = date(N);
    printf("%.4f", res);

    return 0;

}

좋은 웹페이지 즐겨찾기