Table of Contents
Engineering architecture:
initial version:
Algorithm principle:
Problem 1: The space alignment function is not applicable to the Yang Hui triangle with large order
Cause analysis: The appearance of two-digit and three-digit numbers makes the output results no longer aligned.
Solution: Calculate the total number of bytes of quadratic items in each row and divide by 2
Problem 2: The quadratic term data after the 13th order is wrong
Cause analysis: The data of the quadratic items after the 13th order is too large, int-type variables cannot store too large numbers, and overflow occurs.
Solutions and program evolution (the core of this article, the 170-order Yang Hui triangle!)
Program source code
Project structure
Reference link: Use Dev C++ to create a project file and call a c file under a different file_How does devc call another file-CSDN Blog
The method of establishing a project is shown in the reference blog link
The program is divided into three sub-files, and the project structure is as follows
Initial version
Algorithm principle:
In this file, I created two functions for main.c to call, namely the factorial calculation function and the space alignment function (optional)
Each row of output of Yang Hui’s triangle corresponds to the quadratic term of the classical concept. The classical concept combination formula: C(n,m)=n!(n-k)!*k!
Use two for loops to output the n-order Yang Hui triangle
Problem exists 1:
The space alignment function is not suitable for Yang Hui triangles with large orders. The effect is as follows
Cause analysis:
The appearance of two-digit and three-digit numbers causes the output results to no longer align
Solution:
Calculate the total number of bytes of quadratic items in each row and divide by 2
Problem 2:
The quadratic term data after the 12th order is wrong
Reason analysis:
The maximum length of int is 11 bits. The quadratic term data after the 12th order is too large. The int type variable cannot exceed a four-byte 2^32 number, and an overflow occurs, as shown in the figure below
Add an if statement to test the output size of the factorial result
Solution:
A. Modify variable data type
20th level Yang Hui triangle!
Change the int type to long long type (note that the function type must also be changed to long long), so that you can get the 20th order Yang Hui triangle
Level 33 Yang Hui Triangle!
Change the int type to double type. At this time, printf needs to print out the floating point type, and change %d to %f.
In order to improve the appearance, the result needs to be converted into int type and the floating point type 000000 should be removed. In this way, the Yang Hui triangle of order 33 can be obtained.
Level 170 Yang Hui Triangle!
After exceeding the 33rd level, the int type overflow problem of the result output appeared again. There is no way, don’t be beautiful, remove the forced conversion of int
This time, we got the 170-level Yang Hui Triangle! ! !
#INF00 will be output after level 170: This error indicates that the value has overflowed, or that the divisor is 0. We are obviously in the former situation here.
B. Allocate memory
Use the malloc() function to allocate memory to create an array to store data. For example, you can allocate two Int-sized variables.
The result of the attempt: No success, it feels the same as if it was divided or not.
Program source code
main.c
#include <stdio.h>
#include "../test/test.h"//Load test.h through the directory
extern double factorial (int num);//Access the declaration of external functions
extern int space(int num);
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main() {
int num,i,j,temp,e;
printf("Please enter the order of Yang Hui triangle to be created:");
scanf("%d", & amp;num);
temp=num;
for(j=0;j<=num;j + + ){//Output num lines
\t\t
space(temp);//Yang Hui triangle alignment
temp--;
for(i=0;i<=j;i + + ) //Output the quadratic coefficient of each row
{
if(j<=33){//Below order 33, it is integer data for aesthetic purposes. After order 33, it will overflow and be replaced with floating point type.
printf("%d ",(int)(factorial(j)/(factorial(j-i)*factorial(i))));//Classical summary combination formula: C(n,m)=n!(n-k) !*k!
}
else
{
printf("%f ",factorial(j)/(factorial(j-i)*factorial(i)));//Classical summary combination formula: C(n,m)=n!(n-k)!*k!
}
// if(j>12) //Test the overflow of factorial output
// {
// printf("(%d!=%d,%d!=%d,%d!=%d)",j,factorial(j),j-i,factorial(j-i),i,factorial(i)) ;
// }
}
printf("\
");
}
\t
return 0;
}
test.c
#include<stdio.h>
#include<stdlib.h>
#include"test.h"
//extern int factorial (int num);//It doesn’t matter whether you add it or not
double factorial (int num)//factorial function
{
int i;
double sum;
// sum=(double)malloc(sizeof(long long));
sum=1;
for(i=1;i<=num;i + + ){
sum=sum*i;
}
return sum;
}
int space(int num){//Yang Hui triangle alignment function, only applicable to low-order Yang Hui triangle
int k=num,j;
for(j=0;j<=num;j + + ){
printf(" ");
\t
}
}
test.h
#ifndef __TEST_H #define __TEST_H #endif