湖南大学计算机与通信学院2007年保研能力测试(机试题目+部分解题报告)

stephenmjm

游客，如果您要查看本帖隐藏内容请回复

stephenmjm

游客，如果您要查看本帖隐藏内容请回复

stephenmjm

游客，如果您要查看本帖隐藏内容请回复

xnby

这都被你找出来了哈哈...
今年计通院可能还会继续搞吧...去年我成了最大的受益者，今年不知道还有谁
题目都是比较简单，去年那个数论的没搞出来，数学太挫，反正切也没做出来。

reason

还要回复啊

lulu_tj_tl

你好
我想看一下答案
谢谢

tangxixiaowu

不错 顶起

xnby

又一年保研...此贴能火一阵吧...

crc1987

呵呵，真好

doudou

好帖呀！找了好久了。想看看网络传输的答案

gltangjin

顶！！！

xnby

引用第21楼doudou于2008-09-14 11:57发表的:
好帖呀！找了好久了。想看看网络传输的答案

第一个程序是没用c++写的，后面那个程序是测试时候写的。
算法很简单的，像FloodFill吧，也就是广搜下
#include <stdio.h>
#define MAX 200
int map[MAX][MAX],n,st,ttl,total,t=1,lab[MAX],isv[MAX];
int bfs(int cc,int tt)
{
int i,j,k,rec[10000]={0},pt,pb,pe,vx;
pb=0;pe=0;pt=pe;rec[0]=cc;
for(i=0;i<tt;i++)
{
pt=pe;
for(j=pb;j<=pt;j++)
{
vx=rec[j];
isv[vx]=1;
for(k=1;k<=t;k++)
{
if(!isv[k] && map[vx][k])
{
isv[k]=1;
rec[++pe]=k;
}
}
}
pb=pt+1;
}
return t-pe-2;
}
int main()
{
int i,j,k,a,b;
scanf("%d",&n);
memset(lab,0,sizeof(lab));
memset(map,0,sizeof(map));
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
if(!lab[a]) lab[a]=t++;
if(!lab) lab=t++;
map[lab[a]][lab]=1;
map[lab][lab[a]]=1;
}
while(scanf("%d%d",&st,&ttl),st+ttl)
{
total=0;
memset(isv,0,sizeof(isv));
printf("%d\n",bfs(lab[st],ttl));
}
return 0;
}

#include <iostream>
#include <string.h>
#include <map>

using namespace std;
#define MAX 100

int g[MAX][MAX];
int used[MAX];

int n;
map <int ,int > dic;

void floodfill(int pos,int ttl)
{
int i;
used[pos] = 1;
if (ttl==0) return ;
for(i=0;i<n;i++)
{
if(!used && g[pos]==1)
{
floodfill(i,ttl-1);
}
}
}

int main()
{
int i,j,fr,to,ans;
int cnt=1;
scanf("%d",&n);
memset(g,0,sizeof(g));
for(i=0;i<n;i++)
{
scanf("%d%d",&fr,&to);

if(dic[fr]==0)
{
dic[fr] = cnt++;
}
if(dic[to]==0)
{
dic[to] = cnt++;
}
g[dic[fr]-1][dic[to]-1] = 1;
g[dic[to]-1][dic[fr]-1] = 1;
}
n = cnt -1 ;
// for(i=0;i<n;i++){for(j=0;j<n;j++) printf("%d ",g[j]);printf("\n");}

int s,t;
while(scanf("%d%d",&s,&t),s+t)
{
memset(used,0,sizeof(used));
floodfill(dic-1,t);
for(ans=0,i=0;i<n;i++) if(!used) ans ++;
printf("%d\n",ans);
}
return 0;
}