4 Functions - Bo2SS

Course Content#

Basic Knowledge of Functions#

Function Encapsulation
- Readability, Aesthetics, ⭐Debugging (debug by function module)
Three Components of Function Declaration (must)
- Return Value
  - Write void for no return value
- Function Name
- Parameter Declaration List
  - Parameter Type + Parameter Name
Function Definition
- Content inside the curly braces

Recursive Functions#

A type of programming technique (for loops, if statements, recursion), not an algorithm (recursion)
A function calls itself
Components
- Semantic Information: Designed according to requirements
- Boundary Conditions: Design recursive exit, can have multiple
- Recursion Formula: Targeting the problem!
- Result Return: Not just through return
  - Two ways: return value, output parameters (pointers)
How to prove that a recursive function is correct?
- Simple Recursion: Expand the intermediate process
  - Downward recursion + upward backtracking
- Complex Recursion: Mathematical Induction
  - For example, factorial
    - fac(1) holds
    - Assume fac(k) is correct
    - Prove fac(k+1) is correct

Function Pointers and Applications#

Pass the function name as a pointer to a function, and use the function directly in the function
- Return Value (*Function Name)(Parameter Type List)
Applications
- Implement piecewise functions, as shown in the image
- Euler Problem Set: EP-45
- Find the number 40755, which is simultaneously a triangular number, pentagonal number, and hexagonal number
  - That is, find the next triangular number that also satisfies the conditions of pentagonal and hexagonal numbers
- Binary Search
  - Monotonic sequence: The above number sequences are all ordered
  - Time Efficiency: O(logn)
- Code

⭐EP-45 has many highlights, mainly pay attention to 6 key points#

The binary search does not have to be an array, any monotonic sequence with a mapping relationship will do
2. Adjusted the interval head and tail according to the characteristics of the sequence
Dual Logic reduces indentation and increases readability
Triangular numbers include hexagonal numbers: The 2n-1th triangular number = the nth hexagonal number
If using int type (4 bytes), it will fall into an infinite loop
1. The int type is insufficient to cover the next required number
2. Use long long int type (8 bytes), control character: %lld
Fixing hexagonal numbers has a larger span and faster speed, and according to point 4, it is definitely a triangular number

Others
- It should be possible to use a right boundary smaller than temp or a left boundary larger than 1
  - However, since it is O(logn), the effect of shrinking will not be very significant
- Here, function pointers are used; if not, how many similar binary_search functions would need to be written?
  - However, macros can also be used to switch functions
- The red cross in the image is a typo, Hexagonal should be changed to Triangle

Euclidean Algorithm#

Also known as the method of successive divisions

Quickly calculate the greatest common divisor
- If gcd(a, b) = gcd(b, a % b) = c, it will reduce the scale
- Proof

① Let c be the greatest common divisor of a and b, prove that b and a % b also have a common divisor c

Let positive integers k1, k2, k3
a = k1 * c
b = k2 * c
a % b = a - k3 * b // The essence of modulus
So a % b = k1 * c - k3 * k2 * c = (k1 - k3 * k2) * c
That is, a % b is a multiple of c, and b is a multiple of c
Therefore, c is a common divisor of both

② Prove that c is the largest common divisor

Prove that the other two divisors k2 and k1 - k3 * k2 of b and a % b are coprime
Let gcd(k2, k1 - k3 * k2) = d (positive integer), then prove d = 1
Let positive integers m, n, we can let
k2 = m * d
k1 - k3 * k2 = n * d
Then
k1 = n * d + k3 * k2 = (n + k3 * m) * d
We can get
gcd(k1, k2) >= d
And since
gcd(a, b) = c
a = k1 * c
b = k2 * c
That is
gcd(k1, k2) = 1
Therefore
d = 1

Code
Recursive function
- Can implement gcd function in one line
  - Replace if statements with ternary expressions
No need to swap the order based on a and b? No need
- If a ≥ b: gcd() function proceeds as normal
- If a < b: gcd() function will swap the two variables
Ctrl+D will repeat the last output instead of terminating?
- 【Returns 0 when the number of characters read is 0, which will terminate, such as inputting a non-int value】
- Because there is no judgment for EOF in the return value of scanf
- You can negate before scanf with "~" or do a -1 judgment afterwards

Extended Euclidean Algorithm#

Quickly solve a set of integer solutions for ax + by = 1
- When gcd(a, b) = C, what value of C allows for a set of integer solutions
  - C can be either 1 or >1

a = nC
b = mC
nCx + mCy = 1
C(nx + my) = 1
nx + my must be ≥1
C can only be 1

When there is only 1 and 0 left in the last round of the successive division method, that is, when they are coprime, it indicates that there is an integer solution
Mathematical Induction
- Process
  - For f(0) holds → assume f(k) holds → if it can be shown that f(k+1) also holds → then k can hold for any value
  - Refer to the above image and the table below, downward recursion + upward backtracking

	a	b	x	y
Level k+1 (Derivation)	a	b	y	x - ky
	↓↓↓	↓↓↓	↑↑↑	↑↑↑
Level k (Assumption)	b	a % b	x	y
...	↓↓↓	↓↓↓	↑↑↑	↑↑↑
Level 0 (Holds)	1	0	1	0 (arbitrary)

Code

The address of the function input initially has no value, which is assigned only at the deepest point, then backtracked
The right side of the output equation is not necessarily 1
- In fact, the extended Euclidean algorithm can quickly solve integer solutions for ax + by = gcd(a, b)

Variable Argument Functions#

Learn through the above scenario:

The problem is not how to declare the function, but how to locate each parameter in the variable argument list
- Do not know the names of the variables in the variable argument list
- For example: The teacher wants to call the student behind Zhang San to answer a question but forgets the name, so they can directly call the student behind Zhang San to answer
Implement through the va family <stdarg.h>
- Variable: va_list type, to get the parameter list after a

va_list arg;

- Functions
- - va_start: Locate the position of the first parameter in the variable argument list

va_start(arg, n); // n is the variable before the variable argument list

- - va_arg: Returns the next type-matching expression

va_arg(arg, int);

- - va_end: Ends the traversal of variable function actual parameters, clears the va_list space

va_end(arg);

Code
Details are in the comments, including header files, va_arg type matching, maximum traversal times, va_end clearing, int minimum value
When unsure of which header file a method is in, using gcc to compile may prompt for the required header file

However, on my local Xshell, even using -Wall did not show, the teacher used a Mac

In-Class Exercises#

Code

Did not consider negative input, but that is not the focus~

Code Demonstration#

Implementation of a Simplified printf Function#

Implement the function to print characters (one step from 0 to 1)
1. putchar('x') function: Outputs a character 'x' to standard output
Output string functionality: "hello world", and return the number of successfully printed characters

The system will automatically add '\0' to the end of the string, which corresponds to the decimal value of 0; eg. 'a'→97
The const modifier is to prevent the string literal from being modified; it cannot be modified
- If not added, there will be no warning in C, but there will be a warning in C++, as shown below:
- Also: char *const frm
  - Cannot modify the frm pointer (like char *p; frm = p;), but can modify the content pointed to by that pointer
  - Refer to the difference between const char *, char const *, char *const-CSDN, the first two are the same
The character pointer can access the value of the string at the i-th position in two ways
- frm[i]
- *(frm + i)

Make the %d control character effective to output integers
1. Output '%' to the screen

- Use switch structure
- The break before cannot be a comma; it needs to be a semicolon
1. Output positive integer 123 to the screen
- Through two while loops, reverse the number and then output it
  - Without reversing, it can only traverse and output from the low bit
- Add '0' (which is 48) to the number to convert it to a character for output
- ❌ Cannot output integer 0
1. Output positive integer 0 to the screen
The difference between do...while and while
❌ For positive integer 1000, the output is 1
1. Output positive integer 1000 to the screen
Record the number of digits, consider the value of 0, change to do...while
The second reversal can use do...while(--digit)
- But to avoid falling into an infinite loop when digit is 0, use while(digit--) to check the digit count first
- Although it is almost impossible for digit to be 0
❌ Error example
When digit--, outputting the number 1000 will add an extra digit
- --digit may fall into an infinite loop, continuously outputting 0
  - Because when the input is 0, the recorded digit count is 0 (see below), --digit becomes -1
The first while loop calculates the digit count of 0 as 0, which is incorrect!
❌ For negative integers, the output is incorrect!
1. Output negative integer -123 to the screen
Just add a negative number check
❌ For INT32_MAX, INT32_MIN, the output is incorrect!
1. Output INT32_MAX(2^31 - 1), INT32_MIN(-2^31) to the screen
INT32_MAX after reversal cannot be represented by int type → chunk reversal
- Split into two parts of 5 digits each → reverse each part → output each part
- 24174 / 83647 →47142 / 74638 →24174 83647
- Code
  - rev_num must pass the address of temp1 to modify its value
  - The return digit operation of output_num can be directly obtained through digit1, 2
  - Remember to correct the actual digit count of the high 5 digits and low 5 digits
  - The rev_num and output_num functions are as follows:
    - * PUTC in output_num does not take effect; consider that its order is before the definition of PUTC during compilation
  - ❌ For INT32_MIN, the output is still incorrect!
At this point, the output for INT32_MIN is still incorrect because
Taking the negative of INT32_MIN is still itself; the positive number cannot be represented
- The absolute value of a negative number is one greater than the positive number
- INT32_MIN: 1000...000
  - →⭐To find the opposite number: take the complement +1 → 0111...111 + 1
  - →1000...000 (itself)
- Code
  - Use unsigned integer uint32_t to store it!

Make the %s control character effective to output strings

Very simple, just add a case
- Note that literals should be used with const char *

Check the return value functionality

Additional Knowledge Points#

K&R style function definition
- The declaration of parameters in the parameter list is placed at the end
- An ancient style of writing, just for understanding, not recommended for use
Using %g control character can output numbers in a more user-friendly way
Arrays: Expanded functions; Functions: Compressed arrays
The difference between int and long-Jianshu
- Different sizes in different bit systems
- long -> 32 bits: 4 bytes; 64 bits: 8 bytes
- But int is always 4 bytes, long long is always 8 bytes
What is an algorithm? A smart person's way of doing things
⭐while(~scanf("%d\n", &a))
- while(scanf("%d\n", &a) != EOF) can be replaced with while(~scanf("%d\n", &a))
- ~ is bitwise NOT, EOF is -1, bitwise NOT gives 0
When undefining a macro, just add the macro name, no need for parameters, like:

#define PUTC(a) putchar(a)
#undef PUTC

⭐Finding the opposite number in binary: Take the complement +1
- Whether positive or negative, it is reversible; applying this operation twice returns to itself
- It is the same as taking the complement with -1

Points to Consider#

💡How does va_arg handle type mismatches?
- There are two issues with the output:
  - In the first line, when the first int value cannot be obtained, it outputs 0.000000, but the second time it is nan?
  - In the third line, all inputs are of int type, but the second number obtained is 3.000000, experimental evidence shows that this number is related to the second line's 3.000000; is it because va_list was not cleaned properly?
- ❓What type causes it to move forward by the length of the address to get the value
  - For example, double, it moves forward to get 8 bytes corresponding to the variable
- 💡But for the issue of covering or not cleaning, I can't explain it~
- It would be great if we could print the address of va_list~

Tips#

Brush up on OJ
Refer to the reference book Chapter 7