运动员最佳配对问题(习题514)

运动员最佳配对问题(习题5—14)

羽毛球队有男女运动员各n人.给定两个n×n得矩阵P和Q.

P[i][j]是男运动员i和女运动员j配对组成混合双打的运动员竞赛优势. Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势.

由于技术配合和心理状态等各种因素影响,P[i][j]不一定等于Q[i][j].

男运动员i女运动员j配合组成混合双打的男女双方竞赛优势为P[i][j]×Q[j][i]. 设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大. 此题目的解空间显然是一棵排列树,可以套用搜索排列树的回溯法框架: void backtrack(int t) {

if(t>n)compute(); else

for(int j=i;j<=n;j++) {

swap(r,t,j); backtrack(i+1); swap(r,t,j); } }

void compute() {

int temp=0;

for(int i=1;i<=n;i++)

temp+=p[i][r[i]]*q[r[i]][i];

if(temp>best) {

best=temp;

for(int i=1;i<=n;i++) bestr[i]=r[i]; } }

无和集问题(习题5—16)

设S是正整数集合。S 是一个无和集当且仅当x,y属于S, 蕴含x+y不属于S 。 对于任意正整数k ，如果可将{1,2... k} 划分为n个无和子集S1,S2...Sn，称正整 数k是n可分的。记F(n) =max{ k | k 是n可分的}。 试设计一个算法，对任意给定的n，计算F(n) 的值。

该题是子集选取问题,解空间显然是一棵子集树,同样可以套用搜索子集树的回溯法框架. 但是由于搜索的空间很大,用搜索时间控制搜索深度: Bool search(int dep) {

t1=clock();

elapsed+=(t1-t2)/()double)clock_per_sec); t0=t1;

If(elapsed>15.0)return false; If(dep>k){out();return true;} for(int i=1;i<=n;i++){ If(sum[i][dep]==0){ t[dep]=I;s[i][dep]=true;

for(int j=1;j

for(j=1;j

Return false; }

整数变换问题(习题5—18)

关于整数i的变换f和g。f=3i,g=（i/2）向下取整。 对于给定的两个整数m，n.要求从n变换为m。 如15,4 4=ggfg(15)

首先分析: 永远可以。g操作就是对一个数字的二进制表示向右移动一位。 首先，任何数字都可以通过若干次连续的g操作成为1. 然后通过若干次f操作成为3^k,

如果存在k,使得3^k的前面若干位2进制数正好是n的二进制表示，那么我们就通过若干次右移(g操作）将3^k变成n.

所以我们只要能够证明得出：

对于任何一个w进制表示的数字n (s位数）,我们能够找到一个整数k,使得 3^k的w进制表示的前面s位正好是n。 就可以了。

为了找最短路径,用逐步加深的回溯法搜索:

具体算法: Void compute() {

K=1;

While(! Search(1,n){ K++;

If(k>maxdep)break; Init(); }

If(found)output();

Else cout<<”No solution!”<

Bool search(int dep, int n) {

if(dep>k) return false; For(int i=0;i<2;i++){

Int n1=f(n,i);t[dep]=I;

If (n1==n)||search(dep+1,n1){found=true;out();return true;} }

Return false; }

无优先级运算(习题5—27)

#include #include \int n; //给定数字的个数 int a[999];//给定的数字

int m;//利用给定的数字 运算求出的数字m int num[999]; int oper[999]; int flag[999]; int k;

found() {

int x=num[0]; for(int i=0;i

switch(oper[i]) {

case 0: x+=num[i+1];break; case 1: x-=num[i+1];break; case 2: x*=num[i+1];break; case 3: x/=num[i+1];break; } }

return(x==m); }

search(int dep) {

if(dep>k) {

if(found()) return true; else

return false; }

for(int i=0;i

num[dep]=a[i]; flag[i]=1;

for(int j=0;j<4;j++) {

oper[dep]=j; if(search(dep+1)) return true; } flag[i]=0; } return false; } main() {

cout<<\输入给定的数字个数 \\n\ cin>>n;

for (int p=0;p

cout<<\输入第\个数字 \\n\ cin>>a[p]; flag[p]=0; }

cout<<\输入要求的数字 \\n\ cin>>m;

for(k=0;k

cout<

cout<<\} 运行:

本文来源：https://www.bwwdw.com/article/ifp2.html