양 휘 삼각형 - 대열 의 응용

양 휘 삼각형 은 다음 과 같다.   1 1   2   1 1   3   3   1 1   4   6   4   1 의 삼각형 은 실질 적 으로 이항식 (a + b) 의 n 차방 이 펼 쳐 진 후 각 항의 계수 가 배 열 된 삼각형 이다. 그 특징 은 좌우 양쪽 이 모두 1 이 고 두 번 째 줄 부터 중간의 모든 수 는 이전 줄 에서 서로 인접 한 두 수의 합 이다.
의 사상 을 사용 하여 양 휘 삼각형 의 절 차 를 실현 한다.
1 > 우선, 하나의 대기 열 을 초기 화해 야 합 니 다. 즉, 머리 = 꼬리 = 0 입 니 다.
2 > 첫 번 째 줄 의 요 소 를 1 로 줄 에 넣 고 두 번 째 줄 을 조작 합 니 다 (1, 2 줄 은 요구 와 조작 이 필요 없 이 요 소 를 직접 줄 에 넣 으 면 됩 니 다).
3 > 세 번 째 줄 부터 현재 의 대 두 는 N - 1 줄 을 가리 키 며 각 줄 의 고정 요 소 를 1 줄 로 정렬 한 다음 에 순환 작업 구 와 과정 을 반복 합 니 다.
팀 의 첫 번 째 요 소 를 팀 에서 내 고 값 temp 을 저장 합 니 다.
현재 팀 의 첫 번 째 요소 x 를 가 져 오고 temp = temp + x 를 진행 하 며 temp 을 파티 에 가입 합 니 다.
4 > 순환 이 끝 난 후, 팀 의 첫 번 째 는 N - 1 줄 의 마지막 요소 에 있 습 니 다. 현재 팀 에서 나 온 다음, 각 줄 의 마지막 고정 요소 1 을 팀 에 넣 습 니 다.
5 > 3, 4 단 계 를 순환 하면 양 휘 삼각형 을 출력 할 수 있다. 
주의: 양 휘 삼각형 의 특징 은 N 줄 의 중간 값 이 N - 1 줄 의 두 값 과 같 고 대열 은 단 진 단 출 을 사용 하 는 것 입 니 다. 

//          
#include "stdafx.h"
#include<stdio.h>

#define MAXSIZE 50
#define FALSE 0 
#define TRUE 1
typedef int QueueElemType;

typedef struct
{
	QueueElemType element[MAXSIZE];
	int front;//  
	int rear;//  
}SeqQueue;

void InitQueue(SeqQueue *Q)//   
{
	Q->front = Q->rear = 0;
}

int EnterQueue(SeqQueue *Q, QueueElemType x)//  
{
	if ((Q->rear + 1) % MAXSIZE == Q->front)///      
		return FALSE;
	Q->element[Q->rear] = x;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return TRUE;
}

int DelQueue(SeqQueue *Q, QueueElemType *x)//  
{
	if (Q->front == Q->rear)
		return FALSE;
	*x = Q->element[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;

	return TRUE;
}
int GetHead(SeqQueue *Q, QueueElemType *x)//     
{
	if (Q->front == Q->rear)
		return FALSE;
	*x = Q->element[Q->front];
	return TRUE;

}
int IsEmpty(SeqQueue *Q)
{
	if (Q->rear == Q->front)
		return TRUE;
	else
		return FALSE;
}
//      ，N        
void YangHuiTriangle(int N)
{
	int n, i, x, temp;
	SeqQueue Q;
	InitQueue(&Q);
	EnterQueue(&Q, 1);//       
	for (n = 2; n <= N; n++)
	{
		EnterQueue(&Q, 1);//  
		for (i = 1; i <= n - 2; i++)
		{
			DelQueue(&Q, &temp);//      temp
			printf("%d ", temp);
			GetHead(&Q, &x);
			temp = temp + x;
			EnterQueue(&Q, temp);
		}
		DelQueue(&Q, &x);//  
		printf("%d ", x);
		EnterQueue(&Q, 1);
		printf("
");
	}
	while (!IsEmpty(&Q))
	{
		DelQueue(&Q, &x);
		printf("%d ", x);

	}
}
void main()
{
	int N;
	printf("please input the N:");
	scanf("%d", &N);
	YangHuiTriangle(N);
	printf("
");
}

다음은 인터넷 에서 찾 은 사고 이 고 참고 할 수 있 습 니 다.
대기 열 을 사용 하여 이 문 제 를 해결 하 는 데 는 작은 기술 이 있 습 니 다. 두 개의 1 의 양쪽 에 0 을 두 개 추가 하고 0 을 통 해 이 층 의 끝 을 표시 합 니 다.즉: 0 1  0 (양 휘 삼각형 의 첫 줄, 우 리 는 첫 줄 에서 시작) 0 1  0
1   1   
1  2  1   1   3   3   1   1   4   6   4   1
프로그램 은 다음 과 같 습 니 다:

//         
void printQueue(Queue *q)
{
for(int i = 0; i < Qlength(q);++i)
printf("%d ",q->data[(q->front+i+q->Qsize)%q->Qsize]);
printf("
");
}
 
//        n    
void YangHuiTriangle(int n)
{
int level = n;
//printf("   ");
Queue myQueue;
initQueue(&myQueue,level);
//      :  0         
enQueue(&myQueue,0);
enQueue(&myQueue,1);
enQueue(&myQueue,1);
enQueue(&myQueue,0);
int x,y;
for(int m = 1;m < level;++m)
{
do{
//               ，       
deQueue(&myQueue,&x);
getHead(&myQueue,&y);
enQueue(&myQueue,x+y);
}while(y!=0);
//      
enQueue(&myQueue,0);
}
printQueue(&myQueue);
 
}
 

이 방법 은 매우 교묘 하 다. 먼저 요 소 를 팀 에서 내 보 낸 다음 에 뒤의 요 소 를 얻 은 다음 에 두 사람 을 더 한 후에 팀 에 들 어가 이 일 을 0 을 만 날 때 까지 반복 한다.이 0 은 이전 대기 열 이 끝 난 0 이자 이 대기 열 이 시작 한 0 이다.
。
마지막 으로 C + + 양 휘 삼각형 을 실현 하 는 코드 를 동봉 합 니 다.

//     C++  
#include "stdafx.h"
#include <iostream>
using namespace std;

int main()
{
	int i,j,t;
	int a[11][11];
	//      1
	for(i=1;i<11;i++)
	{
		a[i][1]=1;
		a[i][i]=1;
	}
	for(i=1;i<11;i++)
	{
		if(i>=3)
		{
			for(t=2;t<i;t++)
			{
				a[i][t]=a[i-1][t-1]+a[i-1][t];
			}
		}
	}
	for(i=1;i<11;i++)
	{
		for(j=1;j<=i;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);"> </span>