当前位置:网站首页>Implementing Yang Hui triangle with cyclic queue C language
Implementing Yang Hui triangle with cyclic queue C language
2022-07-05 12:20:00 【A finger leaf next to the giant】
Abstract :
In a data structure experiment class , The teacher proposed the topic of using queues to realize Yang Hui triangle , But the Yang Hui triangle we came into contact with at that time has always been implemented in the form of two-dimensional arrays , Similar to the queue of one-dimensional array to realize Yang Hui triangle , This is something I have never thought of , Until I saw the following article , The author gives the algorithm diagram of realizing Yang Hui triangle with queue , This algorithm makes me suddenly enlightened , I think this algorithm is in the implementation of Yang Hui triangle , Is a very good algorithm . But the author did not write the implementation steps in the article , I'll take c Language loop queue to implement this algorithm .
Algorithm reference source : https://zhuanlan.zhihu.com/p/89667145
1. Algorithm analysis :
Program analysis : Print Yanghui triangle , Use the circular queue to realize the transformation of each line of Yang Hui triangle .
Algorithm analysis : By operation , Use the circular queue to realize the transition from the previous row to this row .
Intermediate number operation :
Int Variable 1(outOne) Record team leader ( Team head ) data , Then the head of the team moves one digit to the right , And use variable two (outTwo) Record this location data , The sum of the two variables enters the end of the team ., At last, the tail pointer advances by one
Finally, make up at the end of the team 1;
use n Record the number of lines to print ,i Record the number of lines to print .
When i by 1 when , No intermediate operation , Just make up at the end of the team 1, Then print a single line
When i by 2 when , No intermediate operation , Just make up at the end of the team 1, Then print a single line .
When i by 3 when , The intermediate operation is performed once , Make up at the end of the team 1, Then print a single line .
When i by 5 when , The middle number operation is performed three times , Make up at the end of the team 1, Then print a single line .
When i by i when , Intermediate number operation execution j=i-2 Time , Make up at the end of the team 1, Then print a single line ( for(int j=1;j<i-1;j++){}; )
2. Detailed code :
// Use queue to realize Yang Hui triangle
//what is Yang hui triangle ? A triangular figure composed of regular numbers arranged in a triangle . The implementation instance has marble probability
//, Like the arrangement of Yang Hui's triangle numbers , The probability of marbles entering the middle hole is higher than that of the edge
// Application sequence queue implementation , Analyze the relationship and transformation rules between rows
#include <stdio.h>
#define MAXSIZE 13 /* Set the maximum number of print lines */
typedef struct {
int data[MAXSIZE];
int front; /* The head pointer */
int rear; /* Tail pointer , If the queue is not empty , Just want the queue to be the next location of the element */
}SqQueue;
/* Initialize a queue to store a value Q*/
int InitQueue(SqQueue *Q ) {
/* Circular queue */
Q->front=0;
Q->rear=0;
return 1;
}
int printOut(SqQueue *Q ,int n){
int outOne=0;
int outTwo=0;
// Print from the first line
for(int i=1;i<=n;i++){
// Carry out operations , Do not execute when the first line , The second line is not executed
// The third line is executed once , The fourth line executes twice , The fifth line is executed three times , From 1331 To 14641
for(int j=2;j<i;j++){
outOne=Q->data[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
outTwo=Q->data[Q->front];
Q->data[Q->rear]=outOne+outTwo;
Q->rear=(Q->rear+1)%MAXSIZE;
}
// After execution , Join the team at the end 1
Q->data[Q->rear]=1;
Q->rear=(Q->rear+1)%MAXSIZE;
// Print space :
for(int u=1;u<=n-i;u++){
printf(" ");
}
// Traverse
int single=Q->front;
while(single!=Q->rear){
printf("\2 %4d",Q->data[single]);
single=(single+1)%MAXSIZE;
}
printf("\n");
}
return 1;
}
int main(){
SqQueue Q;
int n=0;
while(n<=0||n>=13){
/* Control the number of printed lines not to be too large , The display is not standard */
printf(" Please enter the number of lines to print :");
scanf("%d",&n);
}
InitQueue(&Q);
printOut(&Q,n);
return 1;
}
3. Print the results :
边栏推荐
- Handwriting blocking queue: condition + lock
- MySQL regular expression
- Learn garbage collection 01 of JVM -- garbage collection for the first time and life and death judgment
- Understand redis persistence mechanism in one article
- ABAP table lookup program
- Solution to order timeout unpaid
- Codeforces Round #804 (Div. 2)
- 你做自动化测试为什么总是失败?
- SENT协议译码的深入探讨
- Sentinel sentinel mechanism of master automatic election in redis master-slave
猜你喜欢
Get all stock data of big a
Intern position selection and simplified career development planning in Internet companies
Flutter2 heavy release supports web and desktop applications
Select drop-down box realizes three-level linkage of provinces and cities in China
[untitled]
Troubleshooting of high memory usage of redis in a production environment
Course design of compilation principle --- formula calculator (a simple calculator with interface developed based on QT)
Solve the problem of cache and database double write data consistency
报错ModuleNotFoundError: No module named ‘cv2.aruco‘
Why learn harmonyos and how to get started quickly?
随机推荐
Redis highly available sentinel mechanism
Design of music box based on assembly language
MySQL basic operation -dql
Simple production of wechat applet cloud development authorization login
MySQL installation, Windows version
Linux Installation and deployment lamp (apache+mysql+php)
投资理财适合女生吗?女生可以买哪些理财产品?
Swift - add navigation bar
MySQL splits strings for conditional queries
About cache exceptions: solutions for cache avalanche, breakdown, and penetration
What is the difference between canvas and SVG?
1. Laravel creation project of PHP
Learn garbage collection 01 of JVM -- garbage collection for the first time and life and death judgment
Deep discussion on the decoding of sent protocol
struct MySQL
Reading notes of growth hacker
Conversion du format de données GPS [facile à comprendre]
mmclassification 训练自定义数据
A new WiFi option for smart home -- the application of simplewifi in wireless smart home
强化学习-学习笔记3 | 策略学习