题目:输入正整数n,把整数1,2,3,…,n组成一个环。
使得相邻两个整数之和均为素数。
输出时从整数1檫始逆时针排列。
同一个环应该恰好输出一次。
C语言描述:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn =1000; int vis[maxn]; int A[maxn]; int isp[maxn]; int n; int ans=0; int is_prime(int x){ for( int i=2; i*i<=x; i++ ){ if(x%i==0) return 0; } return 1; } void dfs(int cur){ if(cur==n&&isp[A[0]+A[n-1]]){ ans++; for( int i=0; i<n; i++ ) cout<<A[i]<<" "; cout<<endl; } else{ for(int i=2; i<=n; i++ ){ if(!vis[i]&&isp[i+A[cur-1]]){ /*i这个数没被用过,并且符合前后两个数相加为素数的要求*/ A[cur]=i;/*采用这个数*/ vis[i]=1;/*设置使用标志*/ dfs(cur+1); vis[i]=0;/*消除标志*//*回溯的本质*/ } } } } int main(int argc, char const *argv[]) { cin>>n; memset(vis,0,sizeof(vis)); for( int i=2; i<=n*2; i++ ) isp[i]=is_prime(i); A[0]=1;/*题目中规定从1开始*/ dfs(1); cout<<ans<<endl; return 0; }
汇编语言:
INCLUDE Irvine32.inc .data maxn dd 1000 vis dd 4000 dup(0) A dd 4000 dup(0) isp dd 4000 dup(?) n dd 10 ans dd 0 .code main PROC mov eax,10 ;输入的整数 mov n,eax call initial mov edx,offset A mov eax,1 mov [edx],eax mov eax,1 push eax call dfs mov eax,ans call writedec exit main ENDP dfs PROC push ebp mov ebp,esp pushad mov ecx,[ebp+8] ;ecx:cur cmp ecx,n jne else_0 mov edx,offset A ;edx:A mov eax,[edx] ;eax:A[0] mov ebx,n ;ebx:n add eax,[edx+ebx*4-4];eax:A[0]+A[n-1] mov edx,offset isp ;edx:isp mov ebx,[edx+eax*4] cmp ebx,1 jne else_0 push n call output else_0: mov esi,2 ;esi:i for_1: cmp esi,n jg final mov edx,offset vis ;edx:vis mov eax,[edx+esi*4] ;eax:vis[i] cmp eax,0 jne for_1_end mov edx,offset A ;edx:A mov eax,[edx+ecx*4-4] ;eax:A[cur-1] mov edx,offset isp add eax,esi mov eax,[edx+eax*4] cmp eax,1 jne for_1_end mov edx,offset A ;edx:A mov [edx+ecx*4],esi mov edx,offset vis mov eax,1 mov [edx+esi*4],eax mov eax,ecx inc eax push eax call dfs mov edx,offset vis mov eax,0 mov [edx+esi*4],eax for_1_end: inc esi jmp for_1 final: popad pop ebp ret 4 dfs ENDP is_prime PROC push ebp mov ebp,esp sub esp,4 pushad mov ebx,[ebp+8] ;ebx:x mov esi,2 ;esi:i for_0: mov eax,esi mul esi cmp eax,ebx ;eax:i^2 jg val1 mov eax,ebx ;eax:x mov edx,0 div esi cmp edx,0 jne for_0_end mov eax,0 mov [ebp-4],eax jmp final for_0_end: inc esi jmp for_0 val1: mov eax,1 mov [ebp-4],eax final: popad mov eax,[ebp-4] add esp,4 pop ebp ret 4 is_prime ENDP initial PROC push ebp mov ebp,esp pushad mov esi,2 ;esi:2 mov edi,n mov eax,n mul edi mov edi,eax ;edi:n^2 again: cmp esi,edi jg final mov edx, offset isp push esi call is_prime mov [edx+esi*4],eax inc esi jmp again final: popad pop ebp ret initial ENDP output PROC push ebp mov ebp,esp pushad mov edx, offset A ;edx:A mov edi,[ebp+8] ;edi:n mov esi,0 ;esi:i again: cmp esi,edi jge final mov eax,[edx+esi*4] call writedec inc esi jmp again final: call crlf popad pop ebp ret 4 output ENDP END main
运行结果: