素数链

素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。

【算法分析】

非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同(判重)；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。

【算法流程】

1、数据初始化；   2、递归填数：判断第J种可能是否合法；

A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；

B、如果不合法：选择下一种可能；

【参考程序】

program ex5_1;框架[一]
var  a:array[0..20]of integer;
        b:array[0..20]of boolean;  
        total:longint;
function pd(x,y:integer):boolean;    //判断素数
var   k,i:integer;
begin
   k:=2; 
   i:=x+y; 
   pd:=false;
   while (k<=trunc(sqrt(i)))and(i mod k<>0) do inc(k);
   if k>trunc(sqrt(i)) then pd:=true;
end;
procedure print;                                        //输出方案
var j:integer;
begin
   inc(total);
   write('<',total,'>:');
   for j:=1 to 20 do write(a[j],' ');
   writeln;
end;
procedure Search(t:integer);                  //回溯过程
var i:integer;
begin
   for i:=1 to 20 do                                    //有20个数可选
    if pd(a[t-1],i)and b[i] then                    //判断与前一个数是否构成素数及该数是否可用
      begin
        a[t]:=i;   b[i]:=false;
        if t=20 then begin if pd(a[20],a[1]) then print;end
          else Search(t+1);
        b[i]:=true;
     end;
end;
BEGIN
  fillchar(b,sizeof(b),#1);                         //b数组赋初值为True
  total:=0;
  Search(1);write('total:',total);               //输出总方案数
END.


框架二：
var  a:array[0..20]of integer;    b:array[0..20]of boolean;    total:longint;   s:set of 1..40;
procedure print;                                        //输出方案
var j:integer;
begin
   inc(total);   write('<',total,'>:');
   for j:=1 to 20 do write(a[j],' ');   writeln;
end;
procedure Search(t:integer);                  //回溯过程
var i:integer;
begin
  if t>20 then begin                          //如果20个数选用完则回溯
    if (a[20]+a[1])in s then print;           //如果满足条件，则输出
    exit;
  end;
   for i:=1 to 20 do                                    //有20个数可选
    if ((a[t-1]+i) in s) and b[i] then              //判断与前一个数是否构成素数及该数是否可用
      begin
        a[t]:=i;   b[i]:=false;
        Search(t+1);
        b[i]:=true;
     end;
end;
BEGIN
  fillchar(b,sizeof(b),#1);                         //b数组赋初值为True
  total:=0;  s:=[1,2,3,5,7,11,13,17,19,23,29,31,37];
  Search(1);write('total:',total);               //输出总方案数
END.

素数链

设计程序将1...n（20）排成一排，使任意两个相邻的数的和为素数。第1个和最后一个的和也为素数.

输出:第一个数为1.

如：

样例输入：

6

样例输出：

1 4 3 2 5 6

主程序
b[1..maxn]:记录结果序列。
Visited[1..maxn]: 标记是否已用过
fillchar(visited,sizeof(visited),0);
      b[1]:=1;
      visited[1]:=1;
      dfs(1,1);
搜索过程
procedure dfs(i,k:integer); //已找到第k个数是i，找第k+1个
  var j:integer;
    begin
      if (n=k)and(check(b[1]+b[k])) then print(1);
      for j:=1 to n do
        if (visited[j]=0) and (check(i+j)) then
          begin
            visited[j]:=1;
            b[k+1]:=j;
            dfs(j,k+1);
            visited[j]:=0;
          end;
    end;
判读素数
function check(i:integer):boolean;
    var j:integer;
    begin
        for j:=2 to i-1 do
           if  i mod j=0 then   exit(false);
        exit(true);
    end;
优化：建立素数表
maxn
Prime[3..2*maxn-1]: boolean
素数：true；非素数：false
筛选法建立素数表
筛选法求素数
for i:=1 to n do prime[i]:=true;
    prime[1]:=false;
    for i:=2 to trunc(sqrt(n)) do
       if prime[i] then
          begin
              j:=2*i;
              while j<=n do
                  begin  prime[j]:=false; j:=j+i; end;
          end;