阅读以下说明和流程图,填补流程图中的空缺(1)~(5),将解答填入答题纸的对应栏内。
【说明】以下流程图用于检查数组A[1:n]中的元素是否为自然数1~n的一个排列(含有1~n各数)。若是,则输出OK,否则输出所缺的自然数及其个数m。为检查A[1:n]中是否含有k,只要判断P(k)=(A(1)-k)*(A(2)-k)*…*(A(n)-k)是否等于0即可。【流程图】
参考答案:
(1)0
(2)1
(3)P*(A(i)-k)
(4) P=0
(5)m+1
解析:
本题考查算法设计和描述的基本能力。 从流程图看出,首先需要对m赋初值,然后对k=1,2,…,n循环,检查数组A中是否含k。为此,在该循环中,需要嵌套内循环来计算P(k)。然后判断计算结果P的值是否等于0,来决定数组A中是否含k,并采取相应的动作。 为了对i循环计算累乘的P(k),需要先在P中送初值1。因此(2)处应填1,并在(3)处填写P*(A(i)-k)进行累乘。 内循环结束后,(4)处应判断P=0是否成立。P=0表示数组A中含k,否则表示数组A中缺k。因此,(4)处应填写P=0。如果数组A中缺k,则缺数计数m应增1。因此,(5)处应填m+1,而m的初值应送0,从而(1)处应填0。 k循环结束后,应根据m的值决定输出结果。m=0表示数组A中包含全部自然数1至n,即数组A的元素就是1~n的一个排列;m不等于0表示数组A中短缺其中m个自然数。 本题的算法可应用于判断标准数独的答案是否正确。例如,9阶 (9*9)标准数独解 答所得的结果应在每行、每列、每个3*3宫内都包含1~9,并不重复,即都是1~9的一个排列。靠人工检查稍有麻烦,尤其是1 6阶标准数独解答结果的人工检查更令人烦恼,这个算法则提供了一种处理思路。