2012程序设计竞赛基础实训9

2012程序设计竞赛基础实训9

46 素数和序列

把前8个正整数排成一个序列，如果序列中所有相邻的两项之和都是一个素数，该序列称为一个8项素数和序列。

构造并输出所有不同的8项素数和序列(约定序列左瑞小于右瑞)。 (1) 设计要点

为避免重复，约定首项小于尾项。

环中的每一项为一个数字，相连的8项构成一个8位数。因而设置a循环,在12345678——87654321中枚举。注意到所有1——8没有重复数字的8位数的数字和为9的倍数，该数也为9的倍数，为此，枚举循环步长可取9，以精简枚举次数。

为操作与判断方便，设置3个数组： f数组统计8位数a中各个数字的频数。如f[3]=2，即a中有2个数字“3”。 g数组表示8位数a中每位数的数字。如g[4]=6，即a的从高位开始第4位数为数字“6”。

b数组标记整数x是否为素数。如b[13]=1，标识“1”表示13为素数，标识“0”为非素数。

枚举实施：

1） 注意到8项中每相邻两项之和不超过15,对15以内的5个素数用b数组标注“1”,其余均为“0”。

2） 在8位数的a 循环中，对a实施8次求余分离出各个数字x，应用f[x]++统计数字x的频数，应用g[9-k]=x记录a的各位数字。

3） 设置k(1——8)判断循环：

若f[k]!=1 ，表明数字k出现重复或遗漏，返回。 若 b[g[k]+g[k+1]]!=1，表明相邻的第k项与第k+1项之和不是素数，返回。 (2) 程序设计

// 8项素数序列枚举求解 #include #include void main()

{ int t,k,s,x,g[10],f[10],b[18];long a,y; for(k=1;k<=15;k++) b[k]=0; s=0;

b[3]=b[5]=b[7]=b[11]=b[13]=1; // 5个奇素数标记 printf(\项素数序列：\\n\

for(a=12345678;a<=78654321;a+=9) // 步长为9枚举8位数 {t=0;y=a;

for(k=0;k<=9;k++) f[k]=0; for(k=1;k<=8;k++)

{x=y;f[x]++; // 分离a的8数字,用f数组统计x的个数 y=y/10;g[9-k]=x; // 用g数组记录a的第k位数字 }

for(k=1;k<=7;k++)

if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1; if(f[8]!=1 || t==1 || g[1]>g[8]) continue;

// 有相同数字或相邻和非素或左大于右，返回

s++;

printf(\输出8项素数和环 for(k=2;k<=8;k++) printf(\ printf(\ } }

(3) 程序运行示例 8项素数序列： 1: 1,2,3,4,7,6,5,8 2: 1,2,3,8,5,6,7,4 ??

30: 7,6,5,2,1,4,3,8

(4) 拓广到8项素数和环

把前8个正整数摆成一个环，如果环中所有相邻的两个数之和都是一个素数，该环称为一个8项素数和环。

构造并输出所有不同的8项素数和环。 1) 设计要点

为简化输出，环序列简化为一般序列输出，为避免重复，约定首项为“1”。 环中的每一项为一个数字，相连的8项构成一个8位数。因而设置a循环在没有重复数字数字且以“1”开头的8位数12345678——18765432中枚举。注意到所有1——8没有重复数字的8位数的数字和为9的倍数，该数也为9的倍数，为此，枚举循环步长可取9，以精简枚举次数。

若 b[g[k]+g[k+1]]!=1，表明相邻的第k项与第k+1项之和不是素数，返回。顺便说明，为判断方便，首项“1”先行赋值给g[9]，以与g[8]相邻，在k循环中一道进行判别。

通过以上判断筛选的a，其各个数字即为所求的8项素数环的各项，打印输出。

2) 枚举实现8项素数和环 // 8项素数和环枚举求解 #include #include void main()

{ int t,k,s,x,g[10],f[10],b[18];long a,y; for(k=1;k<=15;k++) b[k]=0; g[9]=1;s=0;

b[3]=b[5]=b[7]=b[11]=b[13]=1; // 5个奇素数标记 printf(\项素数和环：\\n\

for(a=12345678;a<=18765432;a+=9) // 步长为9枚举8位数 {t=0;y=a;

for(k=0;k<=9;k++) f[k]=0; for(k=1;k<=8;k++)

{x=y;f[x]++; // 分离a的8个数字,用f数组统计x的个数 g[9-k]=x; // 用g数组记录a的第k位数字

y=y/10;

}

for(k=1;k<=8;k++)

if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1;

if(t==1) continue; // 有相同数字或相邻和非素，返回 s++;

printf(\// 输出8项素数和环 for(k=2;k<=8;k++) printf(\ printf(\ } }

3) 程序运行示例 8项素数和环： 1: 1,2,3,8,5,6,7,4 2: 1,2,5,8,3,4,7,6 3: 1,4,7,6,5,8,3,2 4: 1,6,7,4,3,8,5,2

容易验证，所得素数和环中每相邻两项（包括首尾两项）之和均为素数。 如果求解素数和序列，只要把环中的首尾相接的条件“b[a[n]+1]==1”去除即可。

(5) 探索首项为1的10项素数序列 // 10项素数序列枚举求解 #include #include void main()

{ int t,k,s,x,g[11],f[11],b[20];double a,y; for(k=1;k<=18;k++) b[k]=0; s=0;

b[3]=b[5]=b[7]=b[11]=b[13]=b[17]=b[19]=1; // 7个奇素数标记 printf(\项素数序列：\\n\

for(a=1023456789;a<=1987654320;a=a+9) // 步长为9枚举10位数 {t=0;y=a;

for(k=0;k<=10;k++) f[k]=0;

for(k=1;k<=10;k++)

{ x=(int)fmod(y,10); if(x==0) x=10; f[x]++; // 分离a的10个数字,用f数组统计x的个数 y=floor(y/10.0);g[11-k]=x; // 用g数组记录a的第k位数字 }

for(k=1;k<=9;k++)

if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1; if(f[10]!=1 || t==1) continue;

// 有相同数字或相邻和非素或左大于右，返回 s++;

printf(\输出10项素数和环 for(k=2;k<=10;k++) printf(\ printf(\ } }

10项素数序列：

1: 1,10,3,2,5,6,7,4,9,8 2: 1,10,3,2,5,8,9,4,7,6 3: 1,10,3,2,9,4,7,6,5,8 ??

128: 1,6,7,4,9,8,5,2,3,10

47 6 顺数

定义排列数：整数m的排列数为m的各位数字的不同排列产生的整数。例如123的排列数有132，213，231，312，321等。

定义6顺数：一个w(5

输入w,输出所有w位6顺数。 测试数据： （1） w=6 （2） w=7

// 搜索w位6顺数 #include void main()

{ int b,c,j,k,w,f[10],h[10]; long m,n,d,t; printf(\请输入位数: \t=1;

for(k=1;k<=w-1;k++) t=t*10; // 计算最小的w位整数t