Bo2SS

Course Content#

Basic Knowledge of Functions#

• Function Encapsulation
  • Readability, Aesthetics, ⭐Debuggability (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 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 based on requirements
  • Boundary Conditions: Design recursive exit, can have multiple
  • Recursion Formula: For the problem!
  • Result Return: Not just through return
    • Two methods: return return, 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 that fac(k+1) is correct

Function Pointers and Applications#

• 

• Pass the function name as a pointer to the 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#

1. The binary search does not have to be an array; any monotonic sequence with a mapping relationship will suffice
   2. Adjusted the interval head and tail based on the sequence characteristics
2. Dual Logic reduces indentation and increases readability
3. Triangular numbers include hexagonal numbers: The 2n-1th triangular number = the nth hexagonal number
4. 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
5. Fixing hexagonal numbers has a larger span, faster speed, and based on point 4, it is certainly 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 large
  • 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 division

• 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 because
gcd(a, b) = c
a = k1 * c
b = k2 * c
That is
gcd(k1, k2) = 1
So
d = 1

• Code

• 

• Recursive function

  • The gcd function can be implemented in one line
    • Replace the if statement with a ternary expression

• Is it necessary to swap the order based on a and b? No need

  • If a ≥ b: the gcd() function proceeds as normal
  • If a < b: the gcd() function will swap the two variables

• Does Ctrl+D repeat the last output instead of terminating?

  • 【It will terminate when the number of characters read is 0, for example, when a non-int value is input】
  • Because there is no judgment for the return value of scanf being EOF
  • You can negate before scanf with "~" or do a -1 check afterward

Extended Euclidean Algorithm#

• Quickly solve a set of integer solutions for ax + by = 1
  • When gcd(a, b) = C, for what value of C can a set of integer solutions be found
    • 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 f(k+1) can also hold → then k can hold for any value

    • 

    • Refer to the above image and the table below, downward recursion + upward backtracking

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 the integer solution for ax + by = gcd(a, b)

Variadic Functions#

Learn through the above scenario:

• The problem is not how to declare the function, but how to locate each parameter in the variadic list
  • The names of the variables in the variadic list are unknown
  • 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
• Implemented 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 variadic list

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

• • • va_arg: Returns the next type-matching expression

​ va_arg(arg, int);

• • • va_end: Ends the traversal of the actual parameters of the variadic function, 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 belongs to, using gcc for compilation may prompt for the required header file

• 

​ However, on my machine's Xshell, even using -Wall did not display, 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#

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

• 
• The system automatically adds '\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 passed in from being modified, and it cannot be modified

  • If not added, there will be no warning in C, but in C++ there will be a warning, as follows:

  • 

  • Also: char *const frm

    • Cannot modify the frm pointer (e.g., char *p; frm = p;), but can modify the content pointed to by that pointer
    • Refer to the difference between const char *, char const *, and 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)

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

• 

  • Use switch structure

  • A semicolon must precede break, not a comma

  2. Output the 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
  • Adding '0' (which is 48) to the number can convert the number to a character for output
  • ❌ Cannot output integer 0
  3. Output the positive integer 0 to the screen
• 

• The difference between do...while and while

• ❌ For the positive integer 1000, the output is 1

  4. Output the 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, it is safer to 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!

  5. Output the negative integer -123 to the screen
• 

• Just add a negative number check

• ❌ For INT32_MAX and INT32_MIN, the output is incorrect!

  6. Output INT32_MAX(2^31 - 1) and INT32_MIN(-2^31) to the screen
• 

• INT32_MAX reversed cannot be represented by int type → block 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 from digit1 and digit2
    • 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:
      • * The PUTC in output_num does not take effect; consider that its order in compilation is before the definition of PUTC
    • ❌ 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: invert + 1 → 0111...111 + 1
    • →1000...000 (itself)

  • Code

    • 

    • Use the unsigned integer type uint32_t to store it!

4. Make the %s control character effective to output strings

• Very simple, just add a case
  • 
  • Note that literals should use const char *

5. Verify 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 the effective digits of numbers in a more user-friendly way

• 

• Arrays: Expanded functions; Functions: Compressed arrays

• The difference between int and long-Jianshu

  • Different sizes under 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? The method of doing things by smart people

• ⭐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

• To undef a macro definition, just add the macro name, no parameters needed, such as:

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

• ⭐To find the opposite in binary: invert + 1
  • Regardless of positive or negative, it is the inverse, applying this operation twice returns to itself
  • It is the same as taking -1 and then inverting

Points for Thought#

• 💡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 is nan?
    • In the third line, all inputs are int types, 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?

  • ❓For what type does it move forward by the length of the address to obtain the value

    • For example, double, it moves forward to get the variable corresponding to 8 bytes

  • 💡But regarding the issue of overwriting or not cleaning, I cannot explain it~

  • It would be better if we could print the address of va_list~

Tips#

• Brush OJ
• Refer to the reference book Chapter 7