c语言什么是穷举、递归、迭代算法

Python015

c语言什么是穷举、递归、迭代算法,第1张

穷举法也叫枚举法或列举法。通常对于一些要求得到精确结果而所求结果又不大的时候可用此法,具体的做法就是将所有可能的情况一一举出。程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法，即一次性解决问题。

设公鸡、母鸡、小鸡分别为x、y、z 只，由题意得：x＋y＋z ＝100……①5x＋3y＋(1/3)z ＝100……②有两个方程，三个未知量，称为不定方程组，有多种解。令②×3－①得：7x＋4y＝100；即：y ＝(100－7x)/4＝25－(7/4)x由于y 表示母鸡的只数，它一定是自然数，而4 与7 互质，因此x 必须是4 的倍数。我们把它写成：x=4k（k 是自然数），于是y=25-7k，代入原方程组，可得：z=75+3k。把它们写在一起有：x ＝4ky ＝25 - 7kz ＝75+ 3k一般情况下，当k 取不同数值时，可得到x、y、z 的许多组值。但针对本题的具体问题，由于x、y、z 都是100 以内的自然数，故k 只能取1、2、3 三个值，这样方程组只有以下三组解：一、 x ＝4；y ＝18；z ＝78 二、 x ＝8；y ＝11；z ＝81三、 x ＝12；y ＝4；z ＝84

一、穷举算法:

穷举每天杀猪数，若最后9天杀不完或提早杀完则证明无解。

利用递归完成：

#include <stdio.h>

//PIG头猪，分DAY天杀完，每天杀单数头

const int DAY=9

const int PIG=36

bool DFS(int day,int remain) //第day天剩下remain只猪，若最后能杀完则返回1，否则返回0

{

if(day>DAY) //如果DAY天已过，剩余0只返回1，即能杀完，否则返回0

return remain==0

int i

for(i=1i<=remaini+=2) //穷举第day天杀猪的头数i(i为奇数)

if(DFS(day+1,remain-i))//当第day+1天剩下remain-i头猪，而最后能杀完所有猪时，返回1

return 1

return 0 //若各种情况都不能则返回0

}

int main()

{

if(DFS(1,PIG)) //第一天剩下PIG头猪能否杀完

puts("有解")

else

puts("无解")

getchar()

return 0

}

二、推出数学关系式求解

设第i天杀ki头猪

则DAY天中共杀 k1+k2+k3+...+kDAY头猪

假设DAY天能杀完PIG头猪

则有 k1+k2+k3+...+kDAY==PIG (1)

因为每天杀奇数头猪,不妨设ki=2*pi+1 (pi>=0) (2)

则由(1)(2)得 PIG==2*(p1+p2+p3+...+pDAY)+DAY

显然如果等式成立，则PIG与DAY奇偶性相同

即

PIG%2==DAY%2

#include <stdio.h>

const int DAY=9

const int PIG=36

int main()

{

if(PIG%2==DAY%2)

puts("有解")

else

puts("无解")

getchar()

return 0

}