Simple Algorithms for Counting, Summation, and Factorial
These types of problems require the use of loops. It is important to determine the initial value, terminal value, or termination condition of the loop based on the problem. Additionally, pay attention to the initial values of the variables used to represent counting, summation, and factorial.
Example: Use a random function to generate 100 random integers in the range of [0, 99], count the occurrences of the digits 1, 2, 3, 4, 5, 6, 7, 8, 9, and 0 in the unit place, and print the results.
This problem can be handled using arrays. Use array a[100] to store the generated 100 random integers, and array x[10] to store the counts of the digits 1, 2, 3, 4, 5, 6, 7, 8, 9, and 0. For example, the count of numbers with the unit digit 1 is stored in x[1], the count of numbers with the unit digit 2 is stored in x[2], and so on. The count of numbers with the unit digit 0 is stored in x[10].
void main() { int a[101], x[11], i, p; for(i = 0; i <= 11; i++) x[i] = 0; for(i = 1; i <= 100; i++) { a[i] = rand() % 100; printf("%4d", a[i]); if(i % 10 == 0) printf("\n"); } for(i = 1; i <= 100; i++) { p = a[i] % 10; if(p == 0) p = 10; x[p] = x[p] + 1; } for(i = 1; i <= 10; i++) { p = i; if(i == 10) p = 0; printf("%d, %d\n", p, x[i]); } printf("\n"); } 
Finding the Greatest Common Divisor and Least Common Multiple of Two Integers
Analysis: The algorithm for finding the greatest common divisor (GCD) is as follows: (Least Common Multiple (LCM) = product of the two integers / GCD)
(1) Given two numbers m and n, where m > n;
(2) The remainder r is obtained by dividing m by n;
(3) If r = 0, then n is the GCD, and the algorithm ends; otherwise, go to (4);
(4) Set m <- n, n <- r, and repeat (2).
For example: Find the GCD of m = 14 and n = 6. m n r
14 6 2
6 2 0
void main() { int n, r, n, m, t; printf("please input two numbers:\n"); scanf("%d,%d", &m, &n); nm = n * m; if (m < n) { t = n; n = m; m = t; } r = m % n; while (r != 0) { m = n; n = r; r = m % n; } printf("GCD: %d\n", n); printf("LCM: %d\n", nm / n); }
Checking for Prime Numbers
A number that can only be divided by 1 or itself is called a prime number. The basic idea is to take m as the dividend and use integers from 2 to INT( ) as divisors. If none divide evenly, m is a prime number; otherwise, it is not. (This can be implemented with the following code segment)
void main() { int m, i, k; printf("please input a number:\n"); scanf("%d", &m); k = sqrt(m); for(i = 2; i <= k; i++) { if(m % i == 0) break; } if(i >= k) printf("The number is prime"); else printf("The number is not prime"); } // Convert to a function, return 1 if prime, return 0 if not int prime(int m) { int i, k; k = sqrt(m); for(i = 2; i <= k; i++) { if(m % i == 0) return 0; } return 1; }
Verifying Goldbach’s ConjectureBasic Idea: Any even number n greater than or equal to 6 can be decomposed into two numbers n1 and n2. Check if both n1 and n2 are prime. If both are, it is a solution. If n1 is not prime, there is no need to check n2. Start with n1 = 3 and check if n1 and n2 (where n2 = n – n1) are prime. Then increment n1 by 2 and repeat until n1 = n/2.
Using the above prime function, the code to verify Goldbach’s Conjecture is as follows:
#include "math.h" int prime(int m) { int i, k; k = sqrt(m); for(i = 2; i <= k; i++) { if(m % i == 0) break; } if(i >= k) return 1; else return 0; } main() { int x, i; printf("please input an even number (>=6):\n"); scanf("%d", &x); if (x < 6 || x % 2 != 0) printf("data error!\n"); else for(i = 2; i <= x / 2; i++) if (prime(i) && prime(x - i)) { printf("%d + %d\n", i, x - i); printf("Verification successful!"); break; } }
1. Selection Sort (Ascending)
Basic Idea:
1) For a sequence with n numbers (stored in array a(n)), select the smallest number and swap it with the first number;
2) From the remaining n-1 numbers, select the smallest number and swap it with the second number;
3) Repeat this process, and after n-1 selections, the sequence will be sorted in ascending order.
The code is as follows:
void main() { int i, j, imin, s, a[10]; printf("\n input 10 numbers:\n"); for(i = 0; i < 10; i++) scanf("%d", &a[i]); for(i = 0; i < 9; i++) { imin = i; for(j = i + 1; j < 10; j++) if(a[imin] > a[j]) imin = j; if(i != imin) { s = a[i]; a[i] = a[imin]; a[imin] = s; } printf("%d\n", a[i]); } }2. Bubble Sort (Ascending)
Basic Idea: (Compare adjacent numbers, move the smaller one to the front)
1) For n numbers (stored in array a(n)), in the first pass, compare each pair of adjacent numbers and move the smaller one to the front. After n-1 passes, the largest number will have “sunk” to the last position, while the smaller numbers will have “floated” up;
2) In the second pass, compare the remaining n-1 numbers (the largest has already sunk) using the same method, leading to the second largest number;
3) Repeat this process, with n-1 passes in total, and in the j-th pass, n-j comparisons will be made.
The code segment is as follows:
void main() { int a[10]; int i, j, t; printf("input 10 numbers\n"); for(i = 0; i < 10; i++) scanf("%d", &a[i]); printf("\n"); for(j = 0; j <= 8; j++) for(i = 0; i < 9 - j; i++) if(a[i] > a[i + 1]) { t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; } printf("the sorted numbers:\n"); for(i = 0; i < 10; i++) printf("%d\n", a[i]); }3. Merge Sort (Merging Two Sorted Arrays A and B into Another Sorted Array C, Ascending)
Basic Idea:
1) First, take the first element from arrays A and B for comparison, placing the smaller element into array C;
2) Compare the next element from the array that had the smaller element with the previously larger one, repeating this comparison until one of the arrays is exhausted;
3) Copy the remaining elements from the other array into C, completing the merge sort.
The code segment is as follows:
void main() { int a[10], b[10], c[20], i, ia, ib, ic; printf("please input the first array:\n"); for(i = 0; i < 10; i++) scanf("%d", &a[i]); for(i = 0; i < 10; i++) scanf("%d", &b[i]); printf("\n"); ia = 0; ib = 0; ic = 0; while(ia < 10 && ib < 10) { if(a[ia] <= b[ib]) { c[ic] = a[ia]; ia++; } else { c[ic] = b[ib]; ib++; } ic++; } while(ia <= 9) { c[ic] = a[ia]; ia++; ic++; } while(ib <= 9) { c[ic] = b[ib]; ib++; ic++; } for(i = 0; i < 20; i++) printf("%d\n", c[i]); }
Searching Algorithms
1. Sequential Search (Searching for a Number x in a List)
Basic Idea: A list of numbers is stored in array a[1]—a[n], and the number to be searched is stored in x. Compare x with each element in the array from start to end. Use variable p to represent the index of elements in array a, starting with p = 1. Compare x with a[p]; if x is not equal to a[p], increment p by 1 and repeat this process. Once x equals a[p], exit the loop. Additionally, if p exceeds the length of the array, the loop should also stop. (This process can be implemented with the following statement)
void main() { int a[10], p, x, i; printf("please input the array:\n"); for(i = 0; i < 10; i++) scanf("%d", &a[i]); printf("please input the number you want to find:\n"); scanf("%d", &x); printf("\n"); p = 0; while(x != a[p] && p < 10) p++; if(p >= 10) printf("the number is not found!\n"); else printf("the number is found at index %d!\n", p); }Consider: Rewrite the above program into a search function Find that returns the index if found, or returns -1 if not found.
2. Basic Idea: A list of numbers is stored in array a[1]—a[n], and the key value to be searched is stored in key. Compare the key with each element in the array from start to end. If they are the same, the search is successful; if not found, the search fails. (The search sub-process is as follows. index: stores the index of the found element.)
void main() { int a[10], index, x, i; printf("please input the array:\n"); for(i = 0; i < 10; i++) scanf("%d", &a[i]); printf("please input the number you want to find:\n"); scanf("%d", &x); printf("\n"); index = -1; for(i = 0; i < 10; i++) if(x == a[i]) { index = i; break; } if(index == -1) printf("the number is not found!\n"); else printf("the number is found at index %d!\n", index); }
In an array, if a value is known, we want to determine its index position, for example, array: A[5] = {1, 2, 6, 7, 9}; if I know the value is 6, then its index position is 3.
int Dichotomy(int *ucData, int long, int num) { int iDataLow = 0; int iDataHigh = num - 1; int iDataMIDDLE; while (iDataLow <= iDataHigh) { iDataMIDDLE = (iDataHigh + iDataLow) / 2; if (ucData[iDataMIDDLE] > long) { iDataHigh = iDataMIDDLE - 1; } else if (ucData[iDataMIDDLE] < long) { iDataLow = iDataMIDDLE + 1; } else { return iDataMIDDLE; } } }
Clipping Filter MethodFor random interference, the clipping filter is an effective method;
Basic Method: Compare the two sampling values y(n) and y(n-1) at adjacent times n and n-1, and determine the maximum allowable deviation based on experience. If the difference between the two sampling values exceeds the maximum allowable deviation, it is considered random interference, and the later sampling value y(n) is deemed invalid and should be discarded. After deleting y(n), y(n-1) can replace y(n); if the maximum allowable deviation is not exceeded, the sampling value is considered valid.
The clipping filter program is as follows: (A value can be adjusted based on actual conditions, value is the valid value, new_value is the current sampling value that the filter program returns as the valid actual value)
#define A 10 char value; char filter() { char new_value; new_value = get_ad(); if ((new_value - value > A) || (value - new_value > A)) return value; return new_value; }
Median Filter MethodThe median filter method can effectively overcome fluctuations caused by random factors or pulse interference caused by unstable sampling;
This method can achieve good filtering results for slowly changing measured parameters such as temperature and liquid level, but it is generally not suitable for rapidly changing parameters such as flow and pressure.
Basic Method: Continuously sample a measured parameter n times (generally n is an odd number), then arrange the sampled values in order of size and take the middle value as the sampled value.
The median filter program is as follows:
#define N 11 char filter() { char value_buf[N], count, i, j, temp; for (count = 0; count < N; count++) { value_buf[count] = get_ad(); delay(); } for (j = 0; j < N; j++) { for (i = 0; i < N - 1; i++) { if (value_buf[i] > value_buf[i + 1]) { temp = value_buf[i]; value_buf[i] = value_buf[i + 1]; value_buf[i + 1] = temp; } } } return value_buf[(N - 1) / 2]; }
Arithmetic Mean Filter Method
The arithmetic mean filter method is suitable for filtering signals with random interference. The characteristic of such signals is that they fluctuate around a certain value, such as measuring flow or liquid level;
Basic Method: For the N sampled data inputs, find a Y such that the square of the deviation from each sampled value is minimized.
When writing the arithmetic mean filter program, pay strict attention to:
1. To speed up data measurement, you can first measure data and store it in memory. After measuring N points, calculate the average of the N data;
2. Choose an appropriate data format, i.e., whether to use fixed-point or floating-point numbers. The program is as follows:
#define N 12 char filter() { int sum = 0, count; for (count = 0; count < N; count++) { sum += get_ad(); delay(); } return (char)(sum / N); }
Recursive Average Filter Method
Basic Method: Use a queue as a storage medium for measurement data. Set the length of the queue to N. For each measurement, place the result at the tail of the queue and discard the original head data. Thus, the queue will always contain N “latest” data. When calculating the average, simply perform an arithmetic average of the N data in the queue to obtain a new arithmetic mean value. This way, with each measurement, a new arithmetic mean value can be obtained.
#define N 12 char value_buf[N], i = 0; char filter() { char count; int sum = 0; value_buf[i++] = get_ad(); if (i == N) i = 0; for (count = 0; count < N; count++) sum += value_buf[count]; return (char)(sum / N); }
First-Order Lag Filter Method
Advantages: Good suppression of periodic interference, suitable for situations with high frequency fluctuations;
Disadvantages: Phase lag, low sensitivity. The degree of lag depends on the value of a. Cannot eliminate interference signals with frequencies higher than half the sampling frequency. The program is as follows:
#define a 50 char value; char filter() { char new_value; new_value = get_ad(); return (100 - a) * value + a * new_value; }
PID Control Algorithm
In process control, the PID controller (also known as the PID regulator) controls based on the proportional (P), integral (I), and derivative (D) of the deviation. It is one of the most widely used automatic controllers;
For typical process control objects—”first-order lag + pure lag” and “second-order lag + pure lag”, the PID controller is an optimal control;
The PID tuning method is an effective way to calibrate the dynamic quality of continuous systems, with simple parameter tuning and flexible structural changes (PI, PD, …).
1. Analog PID Controller
The functions of each correction link of the PID controller:
Proportional Link: Reacts proportionally to the deviation signal e(t) of the control system. Once a deviation occurs, the regulator immediately generates a control effect to reduce the deviation;
Integral Link: Mainly used to eliminate static error and improve the system’s accuracy. The integral time constant TI determines the strength of the integral effect; the larger the TI, the weaker the effect, and vice versa;
Derivative Link:Reflects the trend (rate of change) of the deviation signal and introduces an effective early correction signal into the system before the deviation signal becomes too large, thus speeding up the system’s response and reducing the adjustment time.
The PID controller is a linear regulator that combines the proportional (P), integral (I), and derivative (D) of the deviation between the setpoint r(t) and the actual output c(t) to control the controlled object.
The code snippet is as follows:
#include <stdio.h> #include <stdlib.h> typedef struct PID { double SetPoint; // Desired value double Proportion; // Proportional constant double Integral; // Integral constant double Derivative; // Derivative constant double LastError; // Error[-1] double PrevError; // Error[-2] double SumError; // Sums of Errors } PID;</stdlib.h></stdio.h>Main Program:
double sensor(void) { return 100.0; } void actuator(double rDelta) {} void main(void) { PID sPID; double rOut; double rIn; PIDInit(&sPID); sPID.Proportion = 0.5; sPID.Derivative = 0.0; sPID.SetPoint = 100.0; for (;;) { rIn = sensor(); rOut = PIDCalc(&sPID, rIn); actuator(rOut); } }
Square Root Algorithm
Fast Algorithm for Square Root Calculation on Microcontrollers
Due to work requirements, we need to perform square root operations on microcontrollers. Most current methods for calculating square roots use Newton’s iteration method. After researching, I found a method that is faster than Newton’s method. I dare not keep it to myself, so I share it with everyone, hoping it will be helpful.
1. Principle
Due to formatting reasons, pow(X,Y) represents X raised to the power of Y, and B[0], B[1], …, B[m-1] represents a sequence, where [x] is the index.
Assume:
B[x], b[x] are both binary sequences, taking values of 0 or 1.
M = B[m-1]*pow(2,m-1) + B[m-2]*pow(2,m-2) + … + B[1]*pow(2,1) + B[0]*pow(2,0)
N = b[n-1]*pow(2,n-1) + b[n-2]*pow(2,n-2) + … + b[1]*pow(2,1) + b[0]*pow(2,0)
pow(N,2) = M
(1) The highest bit of N, b[n-1], can be directly determined from the highest bit of M, B[m-1].
Let m be known. Because pow(2, m-1) <= M <= pow(2, m), it follows that pow(2, (m-1)/2) <= N <= pow(2, m/2).
If m is odd, let m=2*k+1,
then pow(2,k) <= N < pow(2, 1/2+k) < pow(2, k+1),
n-1=k, n=k+1=(m+1)/2
If m is even, let m=2k,
then pow(2,k) > N >= pow(2, k-1/2) > pow(2, k-1),
therefore b[n-1] is completely determined by B[m-1].
The remainder M[1] = M – b[n-1]*pow(2, 2*n-2)
(2) The next highest bit b[n-2] can be determined using a trial method.
Assuming b[n-2]=1, then pow(b[n-1]*pow(2,n-1) + b[n-2]*pow(2,n-2), 2) = b[n-1]*pow(2,2*n-2) + (b[n-1]*pow(2,2*n-2) + b[n-2]*pow(2,2*n-4)),
Then compare if the remainder M[1] is greater than or equal to (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4). This comparison can be made based on B[m-1], B[m-2], …, B[2*n-4], without comparing lower bits.
If M[1] >= (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), then the assumption is valid, b[n-2] = 1;
The remainder M[2] = M[1] – pow(pow(2,n-1)*b[n-1] + pow(2,n-2)*b[n-2], 2) = M[1] – (pow(2,2)+1)*pow(2,2*n-4);
If M[1] < (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), then the assumption is invalid, b[n-2] = 0; the remainder M[2] = M[1].
(3) Similarly, the bits of N can be calculated from high to low.
When using this algorithm to calculate the square root of a 32-bit number, at most only 16 comparisons are needed, and during each comparison, there is no need to compare all bits of M, especially in the beginning, when the number of bits compared is very small, so the time consumption is far less than that of Newton’s iteration method.
3. Implementation Code
Here is the implementation code in C for calculating the square root of a 32-bit unsigned integer to obtain a 16-bit unsigned integer.
/****************************************//* Function: Square Root Processing *//* Entry Parameter: Number to be squared, long type *//* Exit Parameter: Square Root Result, int type *//****************************************/ unsigned int sqrt_16(unsigned long M) { unsigned int N, i; unsigned long tmp, ttp; // Result, loop count if (M == 0) // If the number to be squared is 0, the square root result is also 0 return 0; N = 0; tmp = (M >>> 30); // Get the highest bit: B[m-1] M <<<= 2; if (tmp > 1) // If the highest bit is 1 { N++; // Set the current bit of the result to 1, otherwise it's default 0 tmp -= N; } for (i = 15; i > 0; i--) // Calculate the remaining 15 bits { N <<<= 1; // Shift left tmp <<<= 2; tmp += (M >>> 30); // Assume ttp = N; ttp = (ttp <<< 1) + 1; M <<<= 2; if (tmp >= ttp) // If the assumption holds { tmp -= ttp; N++; } } return N; }From beginner to advanced, 30 selected C language e-books
How to obtain: Reply [728] in the background
1
“Must Read! An Expert Summarized the Essential Knowledge Points of Embedded C Language in 10,000 Words…”
2
“There is a huge talent gap in embedded systems! But why is the salary level not very high?”
3
“Which expert compiled this 17,000-word summary of basic knowledge in embedded systems? It’s so comprehensive!”
This Week’s Live Broadcast | Click to View👇
Monday | What is Deep Learning in Artificial Intelligence?
1. What is deep learning?
2. How much do you know about artificial neural networks?
3. Do you understand the mechanisms behind perceptrons?
Tuesday | Do You Really Understand What Compilers Do?
1. CPU that doesn’t recognize any language?
2. Unfamiliar with the development of programming languages?
3. Unclear how compilers work?
Tuesday | What is the Relationship Between Pointers and Arrays?
1. What can pointers be used for?
2. What are arrays?
3. Do you understand the relationship between pointers and arrays?
