您的当前位置:首页正文

【C语言程序设计】穷举法典例------韩信点兵问题

2024-11-29 来源:个人技术集锦

【例】. 韩信有一队兵,他想知道有多少人,他让士兵排队报数,按从1到5报数,最末一个士兵报的数为1;按从1到6报数,最末一个士兵报的数为5;按从1到7报数,最末一个士兵报的数为4;最后再从1到11报数,最末一个士兵报的数为10.请编程计算韩信至少有多少兵。

【问题求解方法分析】设兵数为x,则按题意应满足以下关系式:

#include<stdio.h>
int main()
{
	int x;
	for(x=0;x<3000;x++)
	{
		if(x%5==1 && x%6==5 && x%7==4 && x%11==10)
		{
			printf("x = %d\n",x);
		}
		
	}
	return 0;
} 

运行结果:

 这里我们是假设韩信有3000兵,属于“瞎猫碰到死耗子”,如果真正的解不在这个范围内,那么程序运行之后将一无所有。如果没有x<3000的限制条件,那么又是怎样的结果呢?显然一定会找到正解,而且不止一个正解,更严重的是程序将进入一个死循环。所以这个时候我们就可以用break语句程序如下:

#include<stdio.h>
int main()
{
	int x;
	for(x=0;;x++)
	{
		if(x%5==1 && x%6==5 && x%7==4 && x%11==10)
		{
			printf("x = %d\n",x);
			break;
		}
		
	}
	return 0;
} 

由于本例中,程序退出循环以后什么事情也不做,直接结束程序的运行,因此还可以调用函数exit()来直接结束程序的运行。程序如下:

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int x;
	for(x=0;;x++)
	{
		if(x%5==1 && x%6==5 && x%7==4 && x%11==10)
		{
			printf("x = %d\n",x);
			exit(0);
		}
		
	}
	return 0;
} 

可读性更好的方法是使用标志变量,即定义一个标志变量find,标志是否找到了解,先置find为假,表示“未找到”一旦找到了满足给定条件的解,就将find置为真,表示“找到了”。相应的,循环控制表达式取为“find的逻辑非”的值,当find值为0时,即!find为真,表示没找到,继续循环,否则表示已找到,退出循环,程序如下:

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int x;
	int find=0;
	for(x=1;!find;x++)
	{
		if(x%5==1 && x%6==5 && x%7==4 && x%11==10)
		{
			printf("x = %d\n",x);
			find = 1;
		}
		
	}
	return 0;
} 

显示全文