当前位置:网站首页>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 :
边栏推荐
- Want to ask, how to choose a securities firm? Is it safe to open an account online?
- [superhard core] is the core technology of redis
- Learn the garbage collector of JVM -- a brief introduction to Shenandoah collector
- MySQL data table operation DDL & data type
- Course design of compilation principle --- formula calculator (a simple calculator with interface developed based on QT)
- Redis highly available slice cluster
- Troubleshooting of high memory usage of redis in a production environment
- MySQL log module of InnoDB engine
- 【ijkplayer】when i compile file “compile-ffmpeg.sh“ ,it show error “No such file or directory“.
- Matlab superpixels function (2D super pixel over segmentation of image)
猜你喜欢
Master the new features of fluent 2.10
Matlab superpixels function (2D super pixel over segmentation of image)
Error modulenotfounderror: no module named 'cv2 aruco‘
Course design of compilation principle --- formula calculator (a simple calculator with interface developed based on QT)
Mmclassification training custom data
Get data from the database when using JMeter for database assertion
Understand kotlin from the perspective of an architect
Reading notes of growth hacker
Redirection of redis cluster
Redis highly available sentinel mechanism
随机推荐
How does MySQL execute an SQL statement?
ABAP table lookup program
Simple production of wechat applet cloud development authorization login
Take you hand in hand to develop a service monitoring component
MySQL splits strings for conditional queries
A guide to threaded and asynchronous UI development in the "quick start fluent Development Series tutorials"
Principle and performance analysis of lepton lossless compression
Principle of redis cluster mode
A new WiFi option for smart home -- the application of simplewifi in wireless smart home
[cloud native | kubernetes] actual battle of ingress case (13)
Image hyperspectral experiment: srcnn/fsrcnn
信息服务器怎么恢复,服务器数据恢复怎么弄[通俗易懂]
Learn JVM garbage collection 05 - root node enumeration, security points, and security zones (hotspot)
Recyclerview paging slide
MySQL data table operation DDL & data type
Learn garbage collection 01 of JVM -- garbage collection for the first time and life and death judgment
Matlab imoverlay function (burn binary mask into two-dimensional image)
Select drop-down box realizes three-level linkage of provinces and cities in China
GPS數據格式轉換[通俗易懂]
Four operations and derivative operations of MATLAB polynomials