LP算法算法题.docx
《LP算法算法题.docx》由会员分享，可在线阅读，更多相关《LP算法算法题.docx（24页珍藏版）》请在冰点文库上搜索。
LP算法算法题
实验七分治与递归专项
（1）
1.汉诺塔
古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。
有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。
在移动过程中可以利用B座，要求打印移动的步骤。
你的输入盘子个数请小于等于15，（否则程序执行时间会很长）。
#include
voidhano（intn,chara,charb,charc）
{
if（n>0）
{
hano（n-1,a,c,b）;
printf（"Movediskform%cto%c\n",a,c）;
hano（n-1,c,b,a）;
}
}
voidmain（）
{
intn;
chara,b,c;
a='A';b='B';c='C';
scanf（"%d",&n）;
hano（n,a,b,c）;//通过B杆将A上的盘子移动到C杆上
}
2.求N个数的和,用分治方法求N个数中的和
#include
intadd（intm,intn）
{
intresult1,result2;
if（m==n）
returnn;
result1=add（m,（m+n）/2）;
result2=add（（m+n）/2+1,n）;
returnresult1+result2;
}
voidmain（）
{
intn,result;
scanf（"%d",&n）;
result=add（1,n）;
printf（"1加到n的和为%d\n",result）;
}
3．组合从n个数中选r个数
#include
inta[100];
intn,r;
voidzuhe（intm,intk）
{
inti,j;
for（i=m;i>=k;i--）{
a[k]=i;
if（k>1）
zuhe（i-1,k-1）;
else
{
for（j=r;j>0;j--）
printf（"%d",a[j]）;
printf（"\n"）;
}
}
}
voidmain（）
{
scanf（"%d%d",&n,&r）;
if（n>=r）
zuhe（n,r）;
}
实验十贪心专项
（2）
1.课本4-18
键盘上输入一个高精度的正整数n，去掉任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。
编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。
#include
voidmain（）
{
intdata[20];
inti,j,n,s,k,tag;
scanf（"%d%d",&n,&s）;
i=0;
while（i{
scanf（"%d",&data[i]）;
i++;
}
data[n]=0;
for（i=0;ifor（j=0;j<=n-i;j++）
{
if（data[j]>data[j+1]）
{
for（k=j;k<=n-i;k++）
data[k]=data[k+1];
break;
}
}
tag=0;
for（i=0;i{
if（data[i]==0）{
tag++;
continue;
}
printf（"%d",data[i]）;
}
if（tag==n-s）
printf（"0\n"）;
}
2.埃及分数和（课本4-20）
设计一个算法，把一个真分数表示为最少埃及分数之和的形式，所谓埃及分数，是指分子为1的分数。
如7/8=1/2+1/3+1/24。
#include
voidmain（）
{
intm,n;
inti,d;
scanf（"%d/%d",&m,&n）;//mfor（i=1;;i++）
{
d=n/m;
if（n%m==0）
{
printf（"1/%d",n/m）;
break;
}
else
{
printf（"1/%d",d+1）;
}
m=m*（d+1）-n;
n=n*（d+1）;
printf（"+"）;
}
printf（"\n"）;
}
实验十一动态规划专项
（1）
1.数塔
随机输入一个N行的点数值三角形，即三角形的每一个点都是一个正整数，寻找从顶点开始每一步可沿左下走或者右下走至底的路径，使该路径所经过的点的数值和最大。
#include
max（inta,intb）
{
if（a>b）
returna;
else
returnb;
}
voidmain（）
{
intN;
intdata[50][50];
inti,j;
scanf（"%d",&N）;
for（i=1;i<=N;i++）
for（j=1;j<=i;j++）
scanf（"%d",&data[i][j]）;
for（i=N;i>1;i--）
for（j=1;j{
data[i-1][j]=data[i-1][j]+max（data[i][j],data[i][j+1]）;
}
printf（"%d\n",data[1][1]）;
}
2.采药（背包）
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。
医师为了判断他的资质，给他出了一个难题。
医师把他带到个到处都是草药的山洞里对他说：
“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。
如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。
”
如果你是辰辰，你能完成这个任务吗？
Input
输入的第一行有两个整数T（1≤T≤1000）和M（1≤M≤100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
Output
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
SampleInput
703
71100
691
12
SampleOutput
3
#include
intmax（intx,inty）
{
returnx>y?
x:
y;
}
intmain（）
{
inttm,m,i,j;
intt[100],v[100];
intf[100][1000];
scanf（"%d%d",&tm,&m）;
for（i=1;i<=m;i++）
scanf（"%d%d",&t[i],&v[i]）;
for（i=0;i<=tm;i++）
f[0][i]=0;
for（i=1;i<=m;i++）
for（j=0;j<=tm;j++）
{
if（t[i]>j）
f[i][j]=f[i-1][j];
else
{
f[i][j]=max（f[i-1][j],f[i-1][j-t[i]]+v[i]）;
}
}
printf（"%d\n",f[m][tm]）;
return0;
}
3.最大子段和
用动态规划方法解决N个数的最大子段和问题。
返回最大子段和在数组中的起始和终止位序。
#include
intmain（）
{
inti,j,n,sum=0,x,y,max;
inta[100],b[101][101];
for（i=0;i<=100;i++）
for（j=0;j<=100;j++）
b[i][j]=0;
scanf（"%d",&n）;
for（i=1;i<=n;i++）
{
scanf（"%d",&a[i]）;
sum+=a[i];
}
b[0][1]=sum;
for（i=1;i<=n;i++）
{
b[i][1]=b[i-1][1]-b[i-1][n-i+2];
for（j=2;j<=n-i+1;j++）
{
b[i][j]=b[i][j-1]-a[j-1];
}
}
for（i=0;i<=n;i++）
{
for（j=0;j<=n-i+1;j++）
printf（"%d",b[i][j]）;
printf（"\n"）;
}
max=b[0][0];
for（i=1;i<=n;i++）
for（j=1;j<=n-i+1;j++）
{
if（max{
max=b[i][j];
x=i;
y=j;
}
}
printf（"%d%d->%d\n",max,y,n-x+1）;
}
实验十二动态规划专项
（2）
1.资源分配问题
设有资源（n），分配给m个项目，gi（x）为第i个项目分得资源x（x为整数）所得到的利润。
求总利润最大的资源分配方案。
例如，有n=7个资源，投资到A，B，C三个项目，如下表。
最大利润为0.52。
1
2
3
4
5
6
7
A
0.11
0.13
0.15
0.21
0.24
0.30
0.35
B
0.12
0.16
0.21
0.23
0.25
0.24
0.34
C
0.08
0.12
0.20
0.24
0.26
0.30
0.35
2.青蛙过河问题
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。
在桥上有一些石子，青蛙很讨厌踩在这些石子上。
由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：
0，1，……，L（其中L是桥的长度）。
坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。
青蛙从桥的起点开始，不停的向终点方向跳跃。
一次跳跃的距离是S到T之间的任意正整数（包括S,T）。
当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。
你的任务是确定青蛙要想过河，最少需要踩到的石子数。
输入：
第一行有一个正整数L（1<=L<=109），表示独木桥的长度。
第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1<=S<=T<=10，1<=M<=100。
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。
所有相邻的整数之间用一个空格隔开。
输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。
样例输入：
10
235
23567
样例输出：
2
实验十三搜索专项
（1）
1.走迷宫问题（课本5-3），用深度优先搜索实现。
////////////////广度优先搜索
#include
#include
intmaze[9][9]={
{1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0},{1,0,1,1,1,1,0,1,0},{1,0,0,0,0,1,0,1,0},{1,0,1,0,0,0,0,1,0},
{1,0,1,0,1,1,0,1,0},{1,0,1,0,0,0,0,1,1},{1,0,1,0,0,1,0,0,0},{1,0,1,1,1,1,1,1,0}
};
intfx[5]={0,1,-1,0,0};
intfy[5]={0,0,0,-1,1};
structSQ{
intx,y,pre;
};
SQsq[100];//以队列的形式实现
intqh,qe,i,j;
intcheck（intm,intn）
{
intflag=1;
if（（m<1||m>8）||（n<1||n>8））
flag=0;
if（maze[m][n]==1||maze[m][n]==-1）
flag=0;
returnflag;
}
voidout（）
{
printf（"（%d,",sq[qe].x）;
printf（"%d）",sq[qe].y）;
while（sq[qe].pre!
=0）
{
qe=sq[qe].pre;
printf（"<--（%d,",sq[qe].x）;
printf（"%d）",sq[qe].y）;
}
}
voidsearch（）
{
intk;
qh=0;qe=1;
maze[1][1]=-1;
sq[1].pre=0;
sq[1].x=1;
sq[1].y=1;
while（qe!
=qh）
{
qh++;
for（k=1;k<=4;k++）
{
i=sq[qh].x+fx[k];//检查四个方向是否被搜索过
j=sq[qh].y+fy[k];
if（check（i,j）==1）
{
qe++;
sq[qe].x=i;
sq[qe].y=j;
sq[qe].pre=qh;//前驱
maze[i][j]=-1;//
if（sq[qe].x==8&&sq[qe].y==8）
{
out（）;
exit（0）;
}
}
}
}
printf（"No~\n"）;
}
voidmain（）
{
search（）;
printf（"\n"）;
}
2.已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少（课本5-1），用广度优先搜索实现。
#include
#include
#defineN20
intqu[40],head,rear;
intpre[N];
intn;
intnotempty（）
{
if（head==rear）
return0;
return1;
}
voidinitqueue（）
{
head=0;
rear=0;
}
voidenqueue（intk）
{
qu[rear]=k;
rear++;
}
intdelqueue（）
{
inttemp;
temp=qu[head];
head++;
returntemp;
}
voidoutput（）
{
intk;
k=n;
while（k!
=0）
{
printf（"%d",k）;
k=pre[k];
}
printf（"\n"）;
}
intmain（）
{
inti,j,k,t;
intadj[N][N];
intvisit[N];
scanf（"%d",&n）;
for（i=1;i<=n;i++）
for（j=1;j<=n;j++）
scanf（"%d",&adj[i][j]）;
memset（visit,0,sizeof（visit））;
initqueue（）;
enqueue
（1）;
visit[1]=1;
pre[1]=0;
while（notempty（））
{
t=delqueue（）;
for（k=1;k<=n;k++）
if（visit[k]==0&&adj[t][k]==1）
{
if（k==n）
{
pre[n]=t;
output（）;
return0;
}
else
{
pre[k]=t;
visit[k]=1;
enqueue（k）;
}
}
}
}
实验十四搜索专项
（2）
1.素数环问题
#include
#include
#include
#include
#defineN1000
inta[N];
intvisit[N];
intn;
intisprime（inti）
{intk;
for（k=2;k<=sqrt（i）;k++）
if（i%k==0）
return0;
return1;
}
intcheck（intt,intk）
{
if（t==n）
{if（isprime（k+1）&&isprime（k+a[t-1]））
return1;
}
else
if（isprime（k+a[t-1]））
return1;
return0;
}
voidbacktrack（inti）
{intk;
if（i>n）
{
for（k=1;k<=n;k++）
printf（"%d",a[k]）;
printf（"\n"）;
}
else
{
for（k=2;k<=n;k++）
{
if（visit[k]）
continue;
if（check（i,k））
{
visit[k]=1;
a[i]=k;
backtrack（i+1）;
visit[k]=0;
}
}
}
}
intmain（）
{
scanf（"%d",&n）;
a[1]=1;
memset（visit,0,sizeof（visit））;
backtrack
（2）;
return0;
}
2.背包问题（子集树）
#include
#include
#defineN100
intw[N],v[N],a[N];
intn,c;
intmax,weight,value;
voidbacktrack（inti）
{intk;
if（i>n）
{
if（value>max）
max=value;
}
else
{
a[i]=0;
backtrack（i+1）;
a[i]=1;
weight+=w[i];
value+=v[i];
if（weight<=c）
backtrack（i+1）;
weight-=w[i];//恢复现场
value-=v[i];//恢复现场
}
}
intmain（）
{inti,j;
scanf（"%d%d",&n,&c）;//N是物品个数，c是包重
for（i=1;i<=n;i++）
scanf（"%d%d",&w[i],&v[i]）;//W是物品重，V是价值
max=0;weight=0;value=0;
backtrack
（1）;
printf（"%d\n",max）;
return0;
}
3.按排列树搜索解决八皇后问题（课本5-12）
#include
#include
#include
#defineN1000
inta[N];
intn;
intcheck（intt）
{
introw,col,j,i;
intflag=0;
row=t/n;col=t%n;
for（j=0;jif（a[row*n+j]==1）
flag=1;
for（i=0;iif（a[i*n+col]==1）
flag=1;
for（i=0;ifor（j=0;jif（（a[i*n+j]==1）&&abs（row-i）==abs（col-j））
flag=1;
if（flag==0）
return1;
else
return0;
}
voidbacktrack（inti）
{intk,count;
if（i>=n*n）
{count=0;
for（k=0;kif（a[k]==1）
count++;
if（count==n）
{for（k=0;k{printf（"%d",a[k]）;
if（（k+1）%n==0）
printf（"\n"）;
}
printf（"\n"）;
exit
（1）;
}
}
else
{
a[i]=0;
backtrack（i+1）;
a[i]=1;
if（check（i））
backtrack（i+1）;
}
}
intmain（）
{
scanf（"%d",&n）;
backtrack（0）;
return0;
}
升级会员 