(검지 Offer) 면접 문제 43:n 주사위 점수
제목:
n개의 주사위를 바닥에 놓고 모든 주사위가 위쪽으로 향하는 점수의 합은 s이다.n을 입력하여 s의 모든 가능한 값이 나타날 확률을 출력합니다.
생각:
s가 나타날 수 있는 값의 범위는 n--6*n
1. 전체 배열
거슬러 올라가는 방법은 n개의 주사위(6면)의 전체 배열을 열한 다음에 매번 모든 값을 배열하는 합을 계산하고 이 합이 나타나는 횟수를 통계한다. 6^n(전 배열의 모든 가능성), 즉 확률로 나눈다.코드 목록이 없습니다
2. 귀속 사상
귀속적인 사상을 통해 n개의 주사위의 포인트를 누적하다.
n개의 주사위의 포인트와 n개의 주사위의 포인트를 요구하면 먼저 전 n-1개의 주사위의 포인트와 n개의 주사위의 포인트를 더한다.
귀속 종료 조건: n=1, 이때 어떤 점과 나타나는 횟수+1;
3. 동적 기획 사상
가령 f(m, n)는 m번째 주사위를 던질 때 점수의 합과 n이 나타나는 횟수를 나타내고 m번째 주사위를 던질 때의 점수의 합은 m-1번째 주사위를 던질 때만 관련이 있다.
귀속방정식: f(m, n)=f(m-1, n-1)+f(m-1, n-2)+f(m-1, n-3)+f(m-1, n-5)+f(m-1, n-5)+f(m-1, n-6)는 이번 라운드의 점수와 n의 출현 횟수가 지난 라운드의 점수와 n-1, n-2, n-3, n-4, n-5, n-6의 출현 횟수의 합을 나타낸다.
초기 조건: 1라운드의 f(1), f(2), f(3), f(4), f(5), f(6)는 모두 1이다.
코드:
1. 귀속 방법
#include
#include
using namespace std;
int g_maxValue=6;
void Probability(int original,int index,int curSum,int* pProbability){
if(index==0){
pProbability[curSum-original]+=1;
return;
}
for(int i=1;i<=6;i++)
Probability(original,index-1,curSum+i,pProbability);
}
void PrintProbability(int n){
if(n<1)
return;
int maxSum=n*g_maxValue;
int* pProbability=new int[maxSum-n+1];
for(int i=n;i<=maxSum;i++)
pProbability[i-n]=0;
int curSum=0;
Probability(n,n,curSum,pProbability);
int total=pow((double)g_maxValue,n);
double prob=0;
for(int i=n;i<=maxSum;i++){
double ratio=(double)pProbability[i-n]/total;
prob+=ratio;
cout< 2. 동적 계획
#include
#include
using namespace std;
int g_maxValue=6;
void PrintProbability(int n){
if(n<1)
return;
int* pProbability[2];
pProbability[0]=new int[g_maxValue*n+1];
pProbability[1]=new int[g_maxValue*n+1];
for(int i=0;i<=g_maxValue*n;i++){
pProbability[0][i]=0;
pProbability[1][i]=0;
}
int flag=0;
for(int i=1;i<=g_maxValue;i++)
pProbability[flag][i]=1;
for(int k=2;k<=n;k++){
for(int i=0;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
