集训队作业猜数解题报告

1、猜数解题市复旦附中问题描述 见 2006 年冬令营试题第一题算法分析对于猜数问题，自然想到了筛法：一开始，所有的数都未被筛去。对于每一步，总是猜最小的未被筛去的数 A，得到 P 与 Q，并将该数与其它未被筛去的数进行比较，设与 B 比较时，得到 P1 与 Q1。显然，当 P1P 且 Q1Q 时，B 并不满足条件，将其筛去。一直重复这样的过程，直到 P 与 Q 均为 L。但是，这种朴素的想法在实现上遇到了两个问题：1.在待猜数长度较大时，朴素的筛使猜每个数的平均次数比最有此数大许多。2.由于待猜数最多可能有 10！=3628800 个，不恰当的枚举方法和程序超时。结构可能会使对于第一个问题，可以

2、利用在启发式搜索上得到广泛应用的估价函数，对每一个未被筛去的数 A，设它与未被筛去的数中的 Sp,q 个数比较得到 p 与 q，经过试验，了一个效果较好的估价函数：S=(Sp,q)2只要取所有数中使到 S 最小的数，就可以减少猜测的次数。得到，问题又接踵而至，在使用估价函数的过程中，每次猜测时间复杂度由 O(n)扩大到了 O(n2)，使问题二变得更加严重了。但经过一些思考后发现，由于未被筛去的数的规模在几次猜测后便会急剧缩小就可以加快运行速度。只需在规模不大于 1000 个数时再使用估价函数，对于第二个问题，由于 L 是确定的，可以在预处理时用数组 rec下满足条件的所有数，并在每次猜测后用另

3、一个数组 rec2下未被筛去的数，由于 rec 可以反复利用而rec2 可以使每次猜测的复杂度大大降低。通过这两个优化，完全可以在时间范围内出解。总结猜数问题是一道多次出现在各种竞赛上的题，虽说这次待猜数的长度扩大到 10，但猜数问题的精髓筛法依然是解决这道题的关键。在无需任何优化的情况下，筛法就可以得到 70 分以上的高分。所以在遇到这类扩大范围的经典题目时， 首先要借鉴原题的经典方法，然后尽自己所能进行优化，这样才能得到一个满意的成绩。参考程序uses guesslib_p; varcould:array0.3628801 ofrec:array0.3628801,0.9 of;short

4、;rec2:array0.2000001,0.9 of short;l,p1,q1,all,i,j,k,now,rest,num,num2,tr,min,now2,t,d,st:long;p,q:eger;a,b:tnumber; used,used2,have:array0.9 oftypenum:array0.10,0.10 of long;over,ov2:procedure grid; var;j1:longbegin;p1:=0; q1:=0;for j1:=0 to l-1 do if aj1=bj1 then p1:=p1+1;if p1p then begin couldi:=

5、false; exit;end; fillchar(have,sizeof(have),false); if l=9 thenbeginfor j1:=0 to l-1 do haveaj1:=true; for j1:=0 to l-1 do if havebj1 thenq1:=q1+1;end else q1:=q;if (p1p) or (q1q) then couldi:=false;end;procedure solve; begin trynumber(a,p,q);if (p=l) and (q=l) then beginnext; ov2:=true; exit;end; f

6、illchar(could,sizeof(could),true); for i:=1 to num dobeginfor j:=0 to l-1 do bj:=rec2i,j; grid;end;num2:=0;for i:=1 to num do if couldi then beginnum2:=num2+1;for j:=0 to l-1 do rec2num2,j:=rec2i,jend; num:=num2; end;begin l:=len;all:=1;for i:=10 downto 11-len all:=all*i;for i:=0 to l-1 do beginbi:=

7、i;rec1,i:=i; usedi:=true; end;for i:=2 to all do beginnow:=l-1; over:=false; usedbnow:=false; while not over do beginbnow:=bnow+1; over:=true;if bnow9 then begin over:=false;now:=now-1;dousedbnow:=false; end;if (over) and (usedbnow) then over:=false;end; usedbnow:=true; rest:=0;for j:=now+1 to l-1 d

8、o beginwhile usedrest do rest:=rest+1;bj:=rest; usedrest:=true; end;for j:=0 to l-1 do reci,j:=bj;end;while true do begin ov2:=false;fillchar(used,sizeof(used),false);p1:=0; q1:=0; i:=0; j:=0; k:=0; now:=0; rest:=0; num:=0; num2:=0;tr:=0; min:=0; now2:=0; t:=0; d:=0; st:=0; p:=0; q:=0; over:=false;

9、for i:=0 to l-1 doai:=i; trynumber(a,p,q);if (p=l) and (q=l) then beginnext; continue; end;fillchar(could,sizeof(could),true); for i:=1 to all dobeginfor j:=0 to 9 do bj:=reci,j; grid;if couldi then begin num:=num+1;for j:=0 to l-1 do rec2num,j:=bj;end; end; d:=1;while num=1000 do beginif d9 then a0

10、:=a0-10; fillchar(used2,sizeof(used2),false);used2a0:=true;for k:=1 to l-1 do beginak:=ak-1+d;while (used2ak) or (ak9) beginif ak9 then ak:=ak-10else ak:=ak+1;end; used2ak:=true; end;end elsefor k:=0 to l-1 do ak:=rec21,k;solve;if ov2 then break; end;if ov2 then continue; while true dobegindomin:=ma

11、xlongtr:=0;for i:=1 to num do beginfillchar(typenum,sizeof(typenum),0); for k:=0 to l-1 doak:=reci,k; for j:=1 to num do beginfor k:=0 to l-1 do bk:=recj,k; p1:=0; q1:=0;for k:=0 to l-1 do if ak=bk then p1:=p1+1;fillchar(have,sizeof(have),false); for k:=0 to l-1 do haveak:=true;for k:=0 to l-1 do if

12、 havebk then q1:=q1+1;typenump1,q1:=typenump1,q1+1; end;now2:=0;for j:=0 to l do for k:=0 to l donow2:=now2+typenumj,k*typenumj,k; if now2mhenbegin min:=now2; tr:=i; end;end;for i:=0 to l-1 do ai:=rec2tr,i; trynumber(a,p,q);if (p=l) and (q=l) then beginnext; break; end;fillchar(could,sizeof(could),true); fo