잘못된 배열 문 제 를 대충 분석 하 다.

정의: n 개의 질서 있 는 요 소 는 n 이 있어 야 합 니 다!서로 다른 배열 을 하 다.만약 하나의 배열 이 모든 요 소 를 원래 의 위치 에 두 지 않 게 한다 면, 이 배열 을 잘못된 배열 이 라 고 부른다.n 을 주 고 1, 2, 3 을 구하 세 요.n 의 잘못된 배열 개수 D 가 얼마 인지, 그리고 모든 잘못된 배열 방안 을 제시 합 니 다.
추리:
첫 번 째 단 계 는 n 번 째 요 소 를 한 위치 에 놓 습 니 다. 예 를 들 어 위치 k 는 모두 n - 1 가지 방법 이 있 습 니 다.
두 번 째 단 계 는 번호 가 k 인 요 소 를 넣 을 때 두 가지 상황 이 있다. (1) 이 를 위치 n 에 두 면 나머지 n - 1 개의 요소 에 대해 두 번 째 요 소 는 위치 n 에 두 었 기 때문에 나머지 n - 2 개의 요 소 는 D (n - 2) 방법 이 있다.(2) 두 번 째 k 요 소 는 이 를 위치 n 에 두 지 않 는 다. 이때 이 n - 1 요소 에 대해 D (n - 1) 방법 이 있다.
so:
D(n)=(n-1)*[D(n-1)+D(n-2)];
D(1)=0,D(2)=1
e.g
Oh, my God!
시간 제한:
1000 ms  |  메모리 제한:
65535 KB
난이도:
2
묘사 하 다.
In order to happy everyone, organizer HRW held an open up partythere have specific requirements for this activity is this:
First of all, all person in the party will have to write a note to his name into the box;Then, after all the note added is completed, each taking a note from the box;Finally, if made note of your name, then "Congratulations, won the party!"
Oh, my God!
Now to the question, you can calculate the probability of this happening?Don't count? Don't you want said by others as a  DouBi?!  AC it!
입력
Input file contains several test cases. Each test case consists of a integer numbers n on a line(one≤n≤ten ).The last test case is followed by a line that contains one zeroes. This line must not be processed.
출력
print the the probability
See the following example.
샘플 입력
2
3
0

샘플 출력
Case [1]: 50.00%.
Case [2]: 33.33%.

제시 하 다.
잘못된 배열 공식 을 사용 하여 모든 사람 이 자신의 이름 을 뽑 을 확률 을 계산 해 야 한다.
근원
오리지널
업로드 자
ACM_하 영 위
제목 번역: 우선 파티 에 참석 한 모든 사람들 은 자신의 이름 이 적 힌 쪽 지 를 추첨 함 에 넣는다.
그리고 모든 쪽지 가 들 어가 면 상자 에서 쪽 지 를 하나씩 가 져 옵 니 다.
마지막 으로 받 은 쪽지 에 자신의 이름 이 적 혀 있다 면 "축하합니다. 당 첨 되 었 습 니 다!"
이런 상황 이 발생 할 확률 을 계산 해 주 시 겠 습 니까?
사고방식: 사실 잘못된 배열 공식의 운용
p=D(n)/n!;
#include<stdio.h>
int main()
{
    double a[55];
    double b[55];
    a[0]=1;
    for(int i=1;i<=22;i++)
        a[i]=a[i-1]*i;
    b[1]=0;
    b[2]=1;
    b[3]=2;
    for(int i=4;i<=22;i++)
        b[i]=(i-1)*(b[i-1]+b[i-2]);
        int n,d=1;
    while(~scanf("%d",&n),n)
    {
        printf("Case [%d]: ",d++);
        if(n==1)
            printf("100.00%%.
"); else { printf("%.2lf%%.
",100*b[n]/a[n]); } } }

좋은 웹페이지 즐겨찾기