<Advanced Loops and Detailed Examples>From beginner to expert, from Hello World to ACMAll content is practical, no textbooks required!
Excellent loop design = Correct termination conditions + Efficient loop control + Appropriate algorithm selection.
<Lecture>
1. Designing Loop Termination Conditions
1.1 Counting Control vs. Condition Control
In loop program design, the design of termination conditions is crucial as it determines when the loop ends. There are mainly two control methods:
Counting Control Loop: The number of iterations is known before starting
// Example: Calculate the sum from 1 to 100
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum += i;
}
Condition Control Loop: The number of iterations is unknown and depends on specific conditions
// Example: Read numbers until encountering 0
int num, sum = 0;
do {
scanf("%d", &num);
sum += num;
} while (num != 0);
1.2 Common Patterns for Designing Termination Conditions
Pattern 1: Control with Flag Variable
#include <stdio.h>
int main() {
int score, sum = 0, count = 0;
int continue_flag = 1; // Flag variable
while (continue_flag) {
printf("Please enter the score (input -1 to end):");
scanf("%d", &score);
if (score == -1) {
continue_flag = 0; // Change flag to terminate loop
} else {
sum += score;
count++;
}
}
if (count > 0) {
printf("Average score: %.2f\n", (double)sum / count);
}
return 0;
}
Pattern 2: User Interaction Control
#include <stdio.h>
int main() {
char choice;
int a, b;
do {
printf("Please enter two integers:");
scanf("%d %d", &a, &b);
printf("%d + %d = %d\n", a, b, a + b);
printf("Continue? (y/n):");
scanf(" %c", &choice); // Note the space to avoid reading the previous newline
} while (choice == 'y' || choice == 'Y');
return 0;
}
Common Mistakes Reminder
Boundary Condition Errors: One of the most common types of errors
// Error example: Off by one error
for (int i = 1; i < 10; i++) {
// Actually loops 9 times, not 10!
}
// Correct version
for (int i = 1; i <= 10; i++) {
// Loops 10 times
}
2. Loop Count Control and Optimization
2.1 Loop Optimization Techniques
Technique 1: Reduce the amount of computation inside the loop
// Before optimization: Calculate square root every iteration
for (int i = 0; i < n; i++) {
if (sqrt(i) == (int)sqrt(i)) {
printf("%d is a perfect square\n", i);
}
}// After optimization: Pre-calculate or extract invariant calculations
for (int i = 0; i < n; i++) {
int root = (int)sqrt(i); // Extract invariant calculation
if (root * root == i) {
printf("%d is a perfect square\n", i);
}
}Technique 2: Use more efficient loop structures
// Use for loop for known iteration counts
int array[100];
for (int i = 0; i < 100; i++) {
array[i] = i * i;
}
// Use while for condition-controlled loops
int num;
while (scanf("%d", &num) != EOF && num != 0) {
// Process input
}
2.2 Best Practices for Loop Control
Practice 1: Avoid redundant calculations
// Bad practice: Repeatedly calculate in loop condition
int i = 0;
while (i < strlen(str)) { // Calculate strlen every iteration
// Process character
i++;
}
// Good practice: Pre-calculate
int len = strlen(str);
int i = 0;
while (i < len) {
// Process character
i++;
}
Practice 2: Use appropriate loop control variables
#include <stdio.h>
int main() {
// Forward loop
for (int i = 1; i <= 10; i++) {
printf("%d ", i);
}
printf("\n");
// Backward loop
for (int i = 10; i >= 1; i--) {
printf("%d ", i);
}
printf("\n");
// Loop with step not equal to 1
for (int i = 0; i <= 100; i += 5) {
printf("%d ", i);
}
printf("\n");
return 0;
}
3. Analysis of Typical Loop Problems
3.1 Prime Number Judgment Problem
Problem Description: Determine if a number is prime
Algorithm Idea: A prime number is a natural number greater than 1 that can only be divided by 1 and itself
#include <stdio.h>
#include <math.h>
int main() {
int num, is_prime = 1; // Assume it is prime
printf("Please enter a positive integer:");
scanf("%d", &num);
if (num <= 1) {
is_prime = 0;
} else {
// Optimization: Only check up to sqrt(num)
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
is_prime = 0;
break; // Found a factor, exit loop immediately
}
}
}
if (is_prime) {
printf("%d is prime\n", num);
} else {
printf("%d is not prime\n", num);
}
return 0;
}
3.2 Fibonacci Sequence Problem
Problem Description: Generate the first n terms of the Fibonacci sequence
Algorithm Idea: Each number is the sum of the previous two numbers
#include <stdio.h>
int main() {
int n;
printf("Please enter the number of terms to generate:");
scanf("%d", &n);
if (n >= 1) {
long long a = 0, b = 1, c;
printf("The first %d terms of the Fibonacci sequence:\n", n);
for (int i = 1; i <= n; i++) {
if (i == 1) {
printf("%lld ", a);
} else if (i == 2) {
printf("%lld ", b);
} else {
c = a + b;
printf("%lld ", c);
a = b;
b = c;
}
}
printf("\n");
}
return 0;
}
3.3 Greatest Common Divisor Problem (Euclidean Algorithm)
Problem Description: Find the greatest common divisor of two numbers
Algorithm Idea: Use the Euclidean algorithm
#include <stdio.h>
int main() {
int a, b, temp;
printf("Please enter two positive integers:");
scanf("%d %d", &a, &b);
// Ensure a >= b
if (a < b) {
temp = a;
a = b;
b = temp;
}
// Use while loop to implement the Euclidean algorithm
int original_a = a, original_b = b;
while (b != 0) {
temp = a % b;
a = b;
b = temp;
}
printf("The greatest common divisor of %d and %d is: %d\n", original_a, original_b, a);
return 0;
}
In-Class Practical Exercises
Exercise 1: Luogu P5735 Distance Function
Problem Description: Given the coordinates of three points in a plane, calculate the perimeter of the triangle.
Input Format: 6 real numbers representing the x and y coordinates of the three points
Output Format: Perimeter, rounded to two decimal places
Input:0.0 0.0 3.0 0.0 0.0 4.0Output:12.00Code Implementation:
#include <stdio.h>
#include <math.h>
double distance(double x1, double y1, double x2, double y2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
int main() {
double x1, y1, x2, y2, x3, y3;
scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
double d1 = distance(x1, y1, x2, y2);
double d2 = distance(x2, y2, x3, y3);
double d3 = distance(x3, y3, x1, y1);
printf("%.2f\n", d1 + d2 + d3);
return 0;
}
Exercise 2: HDOJ 1108 Least Common Multiple
Problem Description: Given two positive integers, calculate their least common multiple
Input Format: Multiple sets of data, each line contains two positive integers
Output Format: The least common multiple for each set of data
Input:
Input:10 206 8Output:2024Code Implementation:
#include <stdio.h>// Use the Euclidean algorithm to find the greatest common divisor
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int a, b;
while (scanf("%d %d", &a, &b) != EOF) {
int g = gcd(a, b);
printf("%d\n", a / g * b); // Least common multiple = a*b/greatest common divisor
}
return 0;
}
Exercise 3: POJ 1503 Large Number Summation
Problem Description: Calculate the sum of multiple large integers
Input Format: Multiple large integers, ending with 0
Output Format: The sum of all numbers
Input:
Input:1234567890123456789012345678901234567890123456789012345678900Output:246913578024691357802469135780Code Implementation Idea:
#include <stdio.h>
#include <string.h>
#define MAX_LEN 1000
void addBigNumbers(char result[], char num1[], char num2[]) {
int len1 = strlen(num1);
int len2 = strlen(num2);
int max_len = (len1 > len2) ? len1 : len2;
int carry = 0, sum, i;
// Add from the least significant digit
for (i = 0; i < max_len; i++) {
int digit1 = (i < len1) ? (num1[len1 - 1 - i] - '0') : 0;
int digit2 = (i < len2) ? (num2[len2 - 1 - i] - '0') : 0;
sum = digit1 + digit2 + carry;
result[max_len - i] = (sum % 10) + '0';
carry = sum / 10;
}
if (carry > 0) {
result[0] = carry + '0';
result[max_len + 1] = '\0';
} else {
// Shift result forward by one position
for (i = 0; i < max_len; i++) {
result[i] = result[i + 1];
}
result[max_len] = '\0';
}
}
int main() {
char sum[MAX_LEN] = "0";
char num[MAX_LEN];
while (scanf("%s", num) != EOF) {
if (strcmp(num, "0") == 0) {
break;
}
char temp[MAX_LEN];
strcpy(temp, sum);
addBigNumbers(sum, temp, num);
}
printf("%s\n", sum);
return 0;
}
Common Questions and Answers
Q: When to use break and continue?
A: break is used to completely exit the loop, while continue is used to skip the current iteration and continue to the next iteration. break is suitable for immediate exit when a result is found or an error occurs, while continue is suitable for skipping certain special cases.
Q: How to avoid infinite loops?
A: Ensure that the loop condition will eventually become false, and that there are statements in the loop body that change the loop condition. Avoid using expressions that may not change in the loop condition.
Q: When should nested loops be used?
A: Use nested loops when dealing with two-dimensional data (such as matrices), combinatorial problems, or when multiple layers of iteration are needed. However, be careful not to exceed three layers of nesting.
Debugging Techniques
Use debug output to trace loop execution
#include <stdio.h>
int main() {
int n = 5;
for (int i = 0; i < n; i++) {
printf("Debug info: i = %d\n", i); // Trace loop variable
for (int j = 0; j < n; j++) {
printf(" Inner loop: j = %d\n", j); // Trace inner loop
if (some condition) {
printf(" Condition met, perform some operation\n");
}
}
}
return 0;
}
<Exercise Class>
1. Detailed explanation and analysis of typical example problems
Example Problem 1: Luogu P5735 - Distance Function (Design of Loop Termination Conditions)
Problem Description: Given the coordinates of three points in a plane, calculate the perimeter of the triangle.
Input Format: 6 real numbers representing the x and y coordinates of the three points
Output Format: Perimeter, rounded to two decimal places
Input: 0.0 0.0 3.0 0.0 0.0 4.0
Output: 12.00
Code Implementation and Explanation:
#include <stdio.h>
#include <math.h>
// Function to calculate the distance between two points
double distance(double x1, double y1, double x2, double y2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
int main() {
double x1, y1, x2, y2, x3, y3;
// Read the coordinates of three points
scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
// Calculate the lengths of the three sides
double d1 = distance(x1, y1, x2, y2);
double d2 = distance(x2, y2, x3, y3);
double d3 = distance(x3, y3, x1, y1);
// Calculate the perimeter and output, rounded to two decimal places
printf("%.2f\n", d1 + d2 + d3);
return 0;
}
Knowledge Point Application: This problem focuses on the correct design of loop termination conditions. Although the problem itself does not explicitly involve loops, the distance calculation involves square and square root operations, requiring attention to the precision of floating-point comparisons.
Example Problem 2: HDOJ 1108 - Least Common Multiple (Optimization of Loop Count Control)
Problem Description: Given two positive integers, calculate their least common multiple.
Input Format: Multiple sets of data, each line contains two positive integers
Output Format: The least common multiple for each set of data
Input: 10 206 8
Output: 2024
Code Implementation and Explanation:
#include <stdio.h>// Use the Euclidean algorithm to find the greatest common divisor
int gcd(int a, int b) {
// Use while loop to implement the Euclidean algorithm
while (b != 0) {
int temp = b;
b = a % b; // Remainder as the next divisor
a = temp; // Current divisor as the next dividend
}
return a;
}
int main() {
int a, b;
// Process multiple sets of input data
while (scanf("%d %d", &a, &b) != EOF) {
// Calculate the greatest common divisor
int g = gcd(a, b);
// Least common multiple = product of two numbers / greatest common divisor
// To avoid integer overflow, divide first then multiply
printf("%d\n", a / g * b);
}
return 0;
}
Knowledge Point Application: This problem demonstrates the importance of optimizing loop count control. The Euclidean algorithm converges quickly through remainder operations, optimizing significantly compared to simple iteration.
Example Problem 3: Prime Number Judgment Problem (Analysis of Typical Loop Problems)
Problem Description: Determine if a number is prime
Input Format: A positive integer n
Output Format: If it is prime, output "is prime", otherwise output "is not prime"
Input: 17
Output: is prime
Input: 100
Output: is not prime
Optimized Code Implementation:
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
bool is_prime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
// Optimization: Only check up to sqrt(n), and only check odd numbers
for (int i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
int main() {
int n;
printf("Please enter a positive integer:");
scanf("%d", &n);
if (is_prime(n)) {
printf("%d is prime\n", n);
} else {
printf("%d is not prime\n", n);
}
return 0;
}
Algorithm Optimization Analysis:
Exclude obvious non-primes: n ≤ 1 is definitely not prime, 2 is prime
Exclude even numbers: All even numbers except 2 are not prime
Reduce the check range: Only check up to √n
Step length optimization: Increment by 2, only check odd numbers
2. Summary and Solutions of Loop Problem Types
2.1 Counting Loop Problems
Characteristics: The number of iterations is known, usually using for loops
Solution Template:
for (int i = 0; i < known iterations; i++) {
// Operations to repeat
}
2.2 Condition-Controlled Loop Problems
Characteristics: The number of iterations is unknown, controlled by specific conditions, usually using while or do-while loops
Solution Template:
while (condition holds) {
// Loop body
// Must include statements that change the condition
}
2.3 Iterative Approximation Problems
Characteristics: Gradually approach the final result through multiple iterations
Solution Template:
double precision requirement = 0.0001;
double current value = initial value;
double previous value;
do {
previous value = current value;
current value = iterative formula(current value);
} while (fabs(current value - previous value) > precision requirement);
3. Common Errors and Debugging Techniques
3.1 Infinite Loop Problems
Error Example:
int i = 0;
while (i < 10) {
printf("%d\n", i);
// Forgot to write i++, leading to an infinite loop
}
Debugging Method: Add debug output in the loop body
int i = 0;
while (i < 10) {
printf("Debug info: i = %d\n", i); // Track variable changes
printf("%d\n", i);
i++; // Ensure loop variable updates
}
3.2 Boundary Condition Errors
Error Example:
// Incorrect boundary condition: should use <= instead of <
for (int i = 1; i < 10; i++) {
// Actually loops 9 times, not 10 times!
}
Correct Version:
for (int i = 1; i <= 10; i++) {
// Loops 10 times
}
3.3 Floating Point Comparison Errors
Error Example:
double x = 0.1 + 0.2;
if (x == 0.3) { // Floating point precision issue, may not be equal
// This may not execute
}
Correct Version:
double x = 0.1 + 0.2;
if (fabs(x - 0.3) < 0.0001) { // Use precision comparison
// Correctly executes
}
4. Homework Assignments
Basic Problems (Must Do)
Luogu P5719 - Classification Average
Problem Description: Given n and k, classify numbers from 1 to n into Class A (multiples of k) and Class B (non-multiples of k), and find the average of both classes.
Input Format: Two integers n, k
Output Format: Two floating-point numbers, representing the averages of Class A and Class B, rounded to 1 decimal place
HDOJ 1092 - Sum Until 0
Problem Description: Multiple sets of test data, each set ends with 0, find the sum of each set of data.
Input Format: Multiple sets of data, each set ends with 0
Output Format: The sum of each set of data
Luogu P1420 - Longest Consecutive Sequence
Problem Description: Input n positive integers, find the length of the longest consecutive increasing sequence.
Input Format: The first line n, the second line n integers
Output Format: The length of the longest consecutive increasing sequence
Advanced Problems (Optional)
POJ 1503 - Large Number Summation
Problem Description: Calculate the sum of multiple large integers
Input Format: Multiple large integers, ending with 0
Output Format: The sum of all numbers
Luogu P1217 - Palindromic Prime
Problem Description: Find all palindromic primes within a specified range
Input Format: Two integers a, b representing the range
Output Format: All palindromic primes, one per line
5. Homework Answers
1. Luogu P5719 - Classification Average
#include <stdio.h>
int main() {
int n, k;
scanf("%d %d", &n, &k);
int sumA = 0, countA = 0; // Class A: multiples of k
int sumB = 0, countB = 0; // Class B: non-multiples of k
for (int i = 1; i <= n; i++) {
if (i % k == 0) {
sumA += i;
countA++;
} else {
sumB += i;
countB++;
}
}
double avgA = (countA > 0) ? (double)sumA / countA : 0;
double avgB = (countB > 0) ? (double)sumB / countB : 0;
printf("%.1f %.1f\n", avgA, avgB);
return 0;
}
2. HDOJ 1092 - Sum Until 0
#include <stdio.h>
int main() {
int num, sum;
while (1) {
sum = 0;
scanf("%d", &num);
if (num == 0) break; // End program on a standalone 0
// Process one set of data
do {
sum += num;
scanf("%d", &num);
} while (num != 0); // End current set on 0
printf("%d\n", sum);
}
return 0;
}
3. Luogu P1420 - Longest Consecutive Sequence
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
if (n <= 0) {
printf("0\n");
return 0;
}
int prev, current;
int maxLen = 1, currentLen = 1;
scanf("%d", &prev);
for (int i = 1; i < n; i++) {
scanf("%d", ¤t);
if (current == prev + 1) {
currentLen++;
if (currentLen > maxLen) {
maxLen = currentLen;
}
} else {
currentLen = 1;
}
prev = current;
}
printf("%d\n", maxLen);
return 0;
}
4. POJ 1503 - Large Number Summation (Advanced Problem Idea)
#include <stdio.h>
#include <string.h>
#define MAX_LEN 1000
// Function to add large numbers
void addBigNumbers(char result[], char num1[], char num2[]) {
int len1 = strlen(num1);
int len2 = strlen(num2);
int max_len = len1 > len2 ? len1 : len2;
int carry = 0, sum;
result[max_len] = '\0';
for (int i = 0; i < max_len; i++) {
int digit1 = i < len1 ? num1[len1 - 1 - i] - '0' : 0;
int digit2 = i < len2 ? num2[len2 - 1 - i] - '0' : 0;
sum = digit1 + digit2 + carry;
result[max_len - 1 - i] = (sum % 10) + '0';
carry = sum / 10;
}
if (carry > 0) {
// Handle carry for the highest digit
memmove(result + 1, result, max_len + 1);
result[0] = carry + '0';
}
}
5. Luogu P1217 - Palindromic Prime (Advanced Problem Idea)
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
bool is_prime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0) return false;
}
return true;
}
bool is_palindrome(int n) {
int reversed = 0, original = n;
while (n > 0) {
reversed = reversed * 10 + n % 10;
n /= 10;
}
return reversed == original;
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
// Optimization: Palindromic numbers at even positions can be divisible by 11, except for 11 itself, are not prime
for (int i = a; i <= b; i++) {
if (is_palindrome(i) && is_prime(i)) {
printf("%d\n", i);
}
}
return 0;
}
Next class we will learn:
Nested loops and state changes
If you have questions, feel free to comment!
Follow YunJie Algorithm, no textbooks needed, just a finger tap to systematically learn programming!