main.cpp

我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:递归,分治,动态规划,回溯法,AO算法等,除此之外还用到比较多的数学知识,我做了一部分,还有一些暂时还没做出来,大家也帮

/***************************************************************************
 25. (量水) 用存水为Ｍ，Ｎ升的两个罐子，量出Ａ升水。
 
   分析:显然  0=<A<=M+N
   由题意,我们可以假设量出的A升水为M,N升两个瓶子的水的总和;
   对于M和N整体来说,只有4种操作:
   1.用M升瓶子装水
   2.用M升瓶子倒水
   3.用N升瓶子装水
   4.用N升瓶子倒水
   由此得出表达式: M*x + N*y = A (其中x,y为整数)
   即求此方程的整数解;
   而此方程有整数解的充要条件为: M,N的最大公约数能整除A
   如何求出此整数方程的解成了问题的关键;
****************************************************************************/

#include <stdio.h> 

int get_max_common_divisor(int a, int b)
{
	int c;
	do
	{
		c = a%b;
		a=b;
		b=c;
	}while(c);

	return a;
}

void main()
{
	int x,y;
	int M,N,A;

	printf("请按顺序输入M,N,A:\n");
	scanf("%d%d%d", &M, &N, &A);
	if(A % get_max_common_divisor(M,N) !=0 )
	{
		printf("问题无解!\n");
		return;
	}
	for(x=0; (A-M*x)%N !=0; x++);
	y = (A-M*x)/N;
	printf("x=%d y=%d\n",x,y);
}