C 语言二分法

2025年3月17日 | 阅读 8 分钟

本节将讨论 C 语言中的二分法。二分法是一种简单且收敛的方法，用于求非线性方程的实根。二分法重复地将区间一分为二，并选择一个子区间，在该子区间中找到给定方程的根。

这意味着，如果函数 f(x) 在闭区间 [a, b] 中连续，并且 f(a) 和 f(b) 是两个符号相反的实数，则在 a 和 b 之间至少包含一个 f(x) = 0 的实根。此方法也称为 Bolzano 或半区间或二分搜索方法。

二分法算法

以下是 C 语言中二分法的算法。

启动程序。
输入两个初始猜测 x1 和 x2。'e' 是获得所需精度的绝对误差。
计算函数值：f1 = f(x1) 和 f2 = f(x2)
现在将 f1 和 f2 的乘积与 0 比较，如下所示

如果 (f1 * f2) > 0，则显示初始猜测错误并将控制权转移到步骤 11。

获取中间值：x = (x1 + x2) / 2
如果 ( [ (x1 - x2) / x] < e)，则打印值 x 并跳到 (11)。
否则，显示：f = f(x)
如果 (( f * f1) > 0)，则赋值 x1 = x 且 f1 = f。
否则，赋值 x2 = x 且 f2 = f。
跳到 5。循环以新值继续。
终止程序。

示例 1：使用二分法查找给定方程的根的程序

让我们考虑一个示例，使用 C 语言中的二分法和 for 循环来获取方程的近似根。

/* program to demonstrate the usage of the bisection method in C. */
#include <stdio.h>

// funciton definition 
void bisect (float *mid_pt, float int_st, float int_end, int *iter_cnt);
double get_fun (double res);


int main ()
{
	// declaration of the variables
	int iter_cnt, mx_iter_cnt;
	float mid_pt, int_st, int_end, err_all, root;
	
	printf (" \n Enter the first starting point: ");
	scanf (" %f", &int_st);
	printf (" \n Enter the second ending point: ");
	scanf (" %f", &int_end);
	
	// declare no. of iteration to be allowed
	printf (" \n Enter the maximum iteration to be allowed: ");
	scanf (" %d", &mx_iter_cnt);
	
	// allow no. of error point
	printf (" Input the no. of allowed error point: ");
	scanf (" %f", &err_all);
	
	// call bisect() function
	bisect (&mid_pt, int_st, int_end, &iter_cnt);
	
	// use for loop to print the max iteration
	for (iter_cnt = 0; iter_cnt < mx_iter_cnt; mid_pt = root)
	{
		
		// chcck initial num * mid_pt is less than 0
		if ( get_fun (int_st) * get_fun (mid_pt) < 0)
		{
			int_end = mid_pt; // assign the mid_pt to int_end
		}
		else
		{
			int_st = mid_pt; // else it assign the mid_pt to int_st
		}
		
		bisect ( &root, int_st, int_end, &iter_cnt); // get the address
		if ( fabs (root - mid_pt) < err_all)
		{
			printf (" \n The approximation root is: %f \n", root);
			return 0;
		}
	}
	
	// print insufficient
	printf (" The iterations are insufficient: ");
	return 0;
}

// function definition
void bisect (float *mid_pt, float int_st, float int_end, int *iter_cnt)
{
	*mid_pt = (int_st + int_end) / 2; // get the middle value
	++(*iter_cnt); // increment the iteration value
	printf ( " Iteration \t %d: \t %f \n", *iter_cnt, *mid_pt);
}

double get_fun (double res)
{
	return (res * res * res - 4 * res - 9);
}

输出

Enter the first starting point: 5
Enter the second ending point: 9
Enter the maximum iteration to be allowed: 8
Input the no. of allowed error point: 0.02
Iteration	1:	7.000000
Iteration	1: 	8.000000
Iteration	2: 	8.500000
Iteration	3: 	8.750000
Iteration	4: 	8.875000
Iteration	5: 	8.937500
Iteration	6: 	8.968750
Iteration	7: 	8.984375

The approximation root is: 8.984375

示例 2：使用二分法查找方程 (x³ + 3x - 5 = 0) 的实根的程序

让我们考虑一个示例，使用 C 语言中的二分法打印实根。

#include <stdio.h>
#include <conio.h>

// create a function
double bisect ( double num)
{
	// it returns the value of the function
	return ( pow (num, 3) + 3 * num - 5);
}

int main ()
{
	printf ( " \n Display the real roots of the given equation using the Bisection method: ");
	printf ( " \n x ^ 3 + 3 * x - 5 = 0 \n ");
	double x0, x1;
	
	printf ( " \n Enter the first approximation of the root: ");
	scanf (" %lf", &x0);
	
	
	printf ( " \n Enter the second approximation of the root: ");
	scanf (" %lf", &x1);
	
	int iterate;
	printf (" \n Input the number of iteration you want to perform: ");
	scanf (" %d", &iterate);
	
	
	int count = 1;
	double l1 = x0;
	double l2 = x1;
	double r, f1, f2, f3;
	
	// now check whether the initial approximation are the real root
	if (bisect (l1) == 0) // it is a root
	{
		r = l1;
	}
	else if ( bisect (l2) == 0)
	{
		r = l2;
	}
	
	// if the above two values are not the root of the given equation
	else
	{
		while (count <= iterate) // here count is initialized with 1
		{
			f1 = bisect (l1);
			r = (l1 + l2) / 2.0; // get the mid value of the interval l1 and l2
			f2 = bisect (r);
			f3 = bisect (l2);
			
			// check f2 is equal to 0
			if (f2 == 0)
			{
				r = f2;
				break; // break the execution from the while loop statement
			}
			
			printf (" \n The root after %d iterations is %lf. \n", count, r);
			
			// check multiplication of f1 * f2 not less than 0
			if ( f1 * f2 < 0)
			{
				l2 = r;
			}
			else if (f2 * f3 < 0)
			{
				l1 = r;
			}
			count++;
		}
	}	
	// return final value after mentioned the iteration
	printf (" \n The approximation of the root is: %lf \n ", r);	
	return 0;
}  

输出

Display the real roots of the given equation using the Bisection method:
X ^ 3 + 3 * x - 5 = 0
Enter the first approximation of the root: 1
Enter the second approximation of the root: 5
Input the number of iteration you want to perform: 7
The root after 1 iterations is 3.000000
The root after 2 iterations is 2.000000.
The root after 3 iterations is 1.500000.
The root after 4 iterations is 1.250000.
The root after 5 iterations is 1.125000.
The root after 6 iterations is 1.187500.
The root after 7 iterations is 1.156250.
The approximation root is 1.156250

示例 3：使用二分法查找非代数函数的近似根的程序

让我们创建一个简单的程序，使用 C 语言中的二分法和 do while 循环计算近似根。

/* program to get the roots of the given equation using the do while loop in C. */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
// define function whose root to be determined
double f (double a)
{
	return 3 * a + sin (a) - exp (a); 
}

int main ()
{
	// declare double data type variable
	double x, y, z, eps;
	int count; // integer data type
	
	x:printf (" \n Input the initial approximation for x: \n ");
	scanf (" %lf", &x);
	
	printf (" Input the initial approximation for y: \n ");
	scanf (" %lf", &y);
	
	printf (" Define the input accuracy: \n ");
	scanf (" %lf", &eps);
	
	printf (" Input the maximum number of iteration: \n ");
	scanf (" %d", &count);
	
	// use if statement to check the product of f(a) and f(b) is not less than 0
	if (f(x) * f(y) <= 0)
	{
		int iter = 1; // initialize iter to 1
		// execution of the bisection method starts here
		
		printf (" Iteration \t x \t \ty \t\tz \t\tf(z) \t |x - y| \n ");
		
		// use do while loop
		do {
			z = (x + y) / 2; // get the mid value for z
			printf (" %d \t %lf \t %lf \t %lf \t %lf \t %lf \n", iter, x, y, z, f(z), fabs(x - y));
			if (f(x) * f(z) > 0)
			{
				x = z; // assign the value of z to x
			}
			else if (f(x) * f(z) < 0)
			{
				y = z; // assign the value of z to y
			}
			iter++; // increment counter by 1
		}
		while (fabs (x - y) >= eps && iter <= count);
		printf (" \nThe root of the given equation is: %lf", z);
	}
	else
	{
		printf (" \n The root doesn't exist in the given interval. ");
		goto x;
	}
		
}

输出

 Input the initial approximation for x: 
 1
 Input the initial approximation for y: 
 3
 Define the input accuracy: 
 .002
 Input the maximum number of iteration: 
 10
 Iteration 	 x 	 	y 		z 		f(z) 	 |x - y| 
  1 	 1.000000 	 3.000000 	 2.000000 	 -0.479759 	 2.000000 
 2 	 1.000000 	 2.000000 	 1.500000 	 1.015806 	 1.000000 
 3 	 1.500000 	 2.000000 	 1.750000 	 0.479383 	 0.500000 
 4 	 1.750000 	 2.000000 	 1.875000 	 0.058267 	 0.250000 
 5 	 1.875000 	 2.000000 	 1.937500 	 -0.195362 	 0.125000 
 6 	 1.875000 	 1.937500 	 1.906250 	 -0.064801 	 0.062500 
 7 	 1.875000 	 1.906250 	 1.890625 	 -0.002343 	 0.031250 
 8 	 1.875000 	 1.890625 	 1.882812 	 0.028192 	 0.015625 
 9 	 1.882812 	 1.890625 	 1.886719 	 0.012982 	 0.007812 
 10 	 1.886719 	 1.890625 	 1.888672 	 0.005334 	 0.003906 
 
The root of the given equation is: 1.888672

二分法的优点

二分法保证了实根的收敛。
它减少了非线性方程中出错的机会。
它在每次迭代中评估一个函数。
它通常以线性方式收敛。
我们可以通过增加迭代次数来控制误差，这在二分法中返回更准确的根。
它不涉及复杂的计算来获取根。
在多根的情况下，二分法更快。

二分法的缺点

与其他迭代方法相比，二分法的收敛速度非常慢。
二分法中收敛的近似率为 0.5。
它是线性收敛速度。
它无法获取复根。
如果猜测区间中出现任何不连续性，则无法应用。
它无法为某些方程找到根。例如，f(x) = x²，因为没有括号或二分值。
当函数取相同符号值时，不能在一个区间内使用它。

下一主题C 语言中的 snprintf() 函数

C 语言二分法

二分法算法

二分法的优点

二分法的缺点

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言二分法

二分法算法

二分法的优点

二分法的缺点

相关帖子

C 语言平方根

给定范围内奇偶数的数量

C 语言交换数字的首位和末位

C 语言 isprint() 函数

C 语言数字图案程序

C 语言字符串数组

十六进制转十进制

C 语言 Strrrchr() 函数

C 语言逻辑非 (!) 运算符

C 语言 restrict 关键字

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器