noip2010提高组初赛试题求解3．#include<iostream>usingnamespacestd;constintNUM=5;intr(intn){inti;if(n<=NUM)return0;for(i=1;i<=NUM;i++)if(r(n-i)<0)returni;return-1;}intmain(){intn;cin>>n;cout

Question

noip2010提高组初赛试题求解3． #include<iostream> using namespace std; const int NUM=5; int r(int n) { int i; if(n<=NUM) return 0; for(i=1;i<=NUM;i++) if( r(n-i)<0) return i; return -1; } int main() { int n; cin>>n; cout<<r(n)<<endl; return 0; } 输入： 16 输出：10______________ 4． #include<iostream> #include<cstring> using namespace std; const int SIZE=100; int n,m,r[SIZE]; bool map[SIZE][SIZE],found; bool successful() { int i; for(i=1;i<=n;i++) if(!map[r[i]][r[i%n+1]]) return false; return true; } void swap(int *a,int *b) { int t; t=*a; *a=*b; *b=t; } void perm(int left,int right) { int i; if(found) return ; if(left>right) { if(successful()) { for(i=1;i<=n;i++) cout<<r[i]<<' '; found=true; } return ; } for(i=left;i<=right;i++) { swap(r+left,r+i); perm(left+1,right); swap(r+left,r+i); } } int main() { int x,y,i; cin>>n>>m; memset(map,false,sizeof(map)); for(i=1;i<=m;i++) { cin>>x>>y; map[x][y]=true; map[y][x]=true; } for(i=1;i<=n;i++) r[i]=i; found=false; perm(1,n); if(!found) cout<<"Nosolution!"<<endl; return 0; } 输入： 9 12 1 2 2 3 3 4 4 5 5 6 6 1 1 7 2 7 3 8 4 8 5 9 6 9 输出：_________ 请问这两段程序分别为了实现什么

Answer 1

求r(n)的值 要很好地解决这道题，首先我们要明确一个定理：r(n)无论在什么时候调用，其值不变。这样我们就可以反复调用我们之前算过的r(n)的结果。 注意到程序有一个判断n