资源描述:
《基础算法(一)枚举法.pdf》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、基础算法(一)枚举(穷举)法无论什么类型的试题,只要能归纳出数学模型,我们尽量用解析方法求解,因为一个好的数学模型建立了客观事物间准确的运算关系。在一时找不出解决问题的更好途径时,可以根据问题中的约束条件,将所有可能的解全部列举出来,然后逐一验证是否符合整个问题的求解要求。一、枚举法的基本思想:从可能的解集合中一一穷举各元素,用题目给定的检验条件判定哪些是有用的,哪些是无用的,能使命题成立的,即为其解。这种思维方法主要是基于计算机运算速度快的特点。二、枚举法解题思路:1、对命题建立正确的数学模型;2、根据命题确定数学模型中各变
2、量的变化范围(即可能解的范围);3、利用循环语句、条件判断语句逐步求解或证明。三、枚举法的特点:算法简单,但运算量大。对于可能确定解的范围,又一时找不到更好的算法时,可以采用枚举法。1、求满足表达式A+B=C的所有整数解,其中A、B、C为1~3之间的整数。2、鸡兔同笼问题(在同一个笼子里有鸡和兔子若干只,从上面看,能看到20个头,从下面看,能看到60只脚,问鸡兔各有多少只?)3、百钱百鸡问题(一百块钱要买一百只鸡,这一百只鸡必须包含母鸡、公鸡和小鸡,其中,公鸡5元一只,母鸡3元一只,小鸡1元三只,问有哪些购买方案?)3334、
3、水仙花数问题(ABC=A+B+C,列出所有的整数ABC)5、一根29厘米长的尺子,只允许在上面刻7个刻度,要能用它量出1~29厘米的各种长度,试问刻度应该怎样选择?6、猴子选大王:有M个猴子围成一圈,每个有一个编号,编号从1到M。打算从中选出一个大王。经过协商,决定选大王的规则如下:从第一个开始,每隔N个,数到的猴子出圈,最后剩下来的就是大王。要求:从键盘输入M,N,编程计算哪一个编号的猴子成为大王。参考程序:programtt;constn1=100;vara:array[1..n1]ofinteger;m,n,i,j,k:
4、integer;beginwrite('inputm,n:');readln(m,n);fori:=1tomdoa[i]:=i;i:=1;k:=0;whileimthenbegink:=1;whilea[k]=0dok:=k+1;end;end;a[k]:=0;i:=i+1;end;i:=1;whilea[i]=0doi:=i+1;writeln('Thekingis',i);end.7、变形猴子选大王:有M个人围成一圈,每人有一个
5、编号,从编号为1的人开始,每隔N个出圈,按出圈次序排成一列,其编号刚好按顺序从1到M。要求:从键盘输入M,N,编程计算并输出这M个人原来在圈中的位置。8、求数串的原始排列:前N个自然数排成一串:X1,X2,X3.....Xn,先取出x1,将x2,x3移到数串尾,再取出x4,将x4,x6移到数串尾,.......类推直至取完.取出的序列恰好是:1,2,3......n.要求输入N,求原来的数串的排列方式.vara:array[1..1000]ofword;n,i,j,dep:word;beginwrite('N(1-1000)=
6、');readln(n);if(n=0)or(n>1000)thenbeginwriteln('Inputerror.');readln;halt;end;fillchar(a,sizeof(a),0);a[1]:=1;dep:=1;fori:=2tondobeginj:=3;while(j>0)dobegindep:=depmodn+1;ifa[dep]=0thendec(j);end;a[dep]:=i;end;fori:=1tondowrite(a[i]:5);writeln;readln;end.9、狐狸捉兔子问题:围
7、绕着山顶有10个洞,狐狸要吃兔子,兔子说:“可以,但必须找到我,?我就藏身于这十个洞中,你从10号洞出发,先到1号洞找,第二次隔1个洞找,第三次隔2个洞找,以后如此类推,次数不限。”但狐狸从早到晚进进出出了1000次,仍没有找到兔子。问兔子究竟藏在哪个洞里?【答案】2,4,7,9【参考程序1】constholenumber=10;varhole:array[0..holenumber]of0..1;step,i,number:longint;beginfori:=0to9dohole[i]:=0;number:=0;forst
8、ep:=1to1000dobeginnumber:=number+step;{循环地数}i:=numbermodholenumber;{第几个洞}hole[i]:=1;end;fori:=0toholenumber-1doifhole[i]=0thenwrite(i:3);r