|
|
# tzd
|
|
|
C.3 个 C.T(n)= T(n/2)+1，T(1)=1 C.问题规模不同，问题性质相同
|
|
|
D.以上皆可行。但不同方法，算法复杂度上界可能不同 D.深度优先 D.14
|
|
|
D. if(x==a[low]) return low; return –1;
|
|
|
C.回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
|
|
|
A.确定解空间的时间 B.剪枝函数 A.广度优先 B.大根堆
|
|
|
D.队列式（FIFO）分枝限界法与优先队列式分枝限界法 A.分支界限法
|
|
|
C.结点的优先级 C.贪心选择性质 B.n 皇后问题 D.O(nlog2n)
|
|
|
D.对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做 0/1 背包问题 B.108 B.动态规划法 D.动态规划法 D.子问题重叠性质C.最优子结构性质 D.深度优先遍历
|
|
|
斐波那契数列
|
|
|
#include <stdio.h>
|
|
|
int Fibon1(int n)
|
|
|
{
|
|
|
if (n == 1 || n == 2)
|
|
|
{
|
|
|
return 1;
|
|
|
}
|
|
|
else
|
|
|
{ return Fibon1(n - 1) + Fibon1(n - 2);} }
|
|
|
int main()
|
|
|
{
|
|
|
int n = 0;
|
|
|
int ret = 0;
|
|
|
scanf("%d", &n);
|
|
|
ret = Fibon1(n);
|
|
|
printf("ret=%d", ret);
|
|
|
return 0;
|
|
|
}
|
|
|
众数
|
|
|
#include<stdio.h>
|
|
|
#include<string.h>
|
|
|
int n;
|
|
|
int main(){
|
|
|
int max;
|
|
|
int position;
|
|
|
scanf("%d",&n);
|
|
|
int data[n],
|
|
|
num[n];
|
|
|
memset(&data , 0 , sizeof(data));
|
|
|
memset(&num , 0 , sizeof(num));
|
|
|
for(int i=0 ; i<n ; i++)
|
|
|
{
|
|
|
scanf("%d",&data[i]);
|
|
|
}
|
|
|
|
|
|
printf("\n");
|
|
|
for(int i=0 ; i<n ; i++){
|
|
|
for (int j = i; j < n; j++)
|
|
|
{
|
|
|
if(data[i]==data[j]) num[i]++;
|
|
|
}
|
|
|
}
|
|
|
max=num[0];
|
|
|
for (int i = 0; i < n; i++)
|
|
|
{
|
|
|
if(max<=num[i]){
|
|
|
max=num[i];
|
|
|
position = i;
|
|
|
}
|
|
|
}
|
|
|
for(int i = 0; i < n; i++)
|
|
|
{
|
|
|
if(max==num[i])
|
|
|
printf("%d\n",data[i]);
|
|
|
}
|
|
|
printf("%d\n",max); return 0;
|
|
|
}
|
|
|
0-1背包问题
|
|
|
#include <iostream>
|
|
|
using namespace std;
|
|
|
const int N=1010;
|
|
|
int v[N],w[N],f[N];
|
|
|
int n,m;
|
|
|
int main()
|
|
|
{ scanf("%d%d",&n,&m);
|
|
|
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
|
|
|
for(int i=1;i<=n;i++)
|
|
|
for(int j=m;j>=v[i];j--)
|
|
|
{ f[j]=max(f[j],f[j-v[i]]+w[i]); }
|
|
|
printf("%d",f[m]);
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
正确答案:
|
|
|
设该年级的人数为x，租船数为y。因为每只船坐10人正好多出2个座位，则
|
|
|
x=10*y-2;因为每只船多坐2人即12人时可少租1只船(没有说恰好全部座位占满)，有x+z=12*(y1)，z表示此时空出的座位，显然z<12。让 y从1到100(实际上y取更大范围的结果是相同的)、z从 0到 11 枚举，求出最大的 x即可。对应的程序如下:#include <stdio.h> int solve(){
|
|
|
int xy; z;
|
|
|
for(y=1;y<=100;y++) for(z=0;z<12;z++)
|
|
|
if(10*y-2-12*(y-1)-z) x=10*y-2; return x;}
|
|
|
void main(){
|
|
|
print£(“求解结果\n”);
|
|
|
printf(”最多人数:%d\n",solve())
|
|
|
|
|
|
正确答案:
|
|
|
设fstr，n)返回含n个字符的字符串str是否为回文，其递归模型如下:
|
|
|
fstr，n)=true 当n=0或者n=1时
|
|
|
fstr，n)=flase 当 str[0]≠str[n-1]时
|
|
|
f(str，n)=fstr+1，n-2) 其他情况对应的递归算法如下:#include <stdio.h>#include <string.h>
|
|
|
bool isPal(char *str,int n)//str回文判断算法{
|
|
|
if(n-0|| n=1)
|
|
|
return true;
|
|
|
if(str[0]!=str[n-1]) return false;
|
|
|
return isPal(str+1,n-2):}
|
|
|
void disp(char *str)
|
|
|
int n=strlen(str); if(isPal(str,n))
|
|
|
printf(”%s是回文\n”,str); else
|
|
|
printf(”%s不是回文\n”，str);}
|
|
|
void main(){
|
|
|
printf(“求解结果\n”): disp("abcba”); disp("a”): disp("abc”):
|
|
|
|
|
|
|
|
|
对应的程序如下:#include <stdio.h>#include <set>
|
|
|
using namespace std:
|
|
|
woid solve(set<int) s1,set<int) s2,set<int) &s3)//求交集s3
|
|
|
|
|
|
set<int)::iterator it1,it2;
|
|
|
it1=s1.begin();it2=s2.begin();
|
|
|
while(it1!=s1.end() &&it2!=s2.end())
|
|
|
|
|
|
if(*it1-*it2)
|
|
|
s3.insert(*it1);++it1; ++it2:
|
|
|
|
|
|
else if (*it1<*it2)++it1: else++it2;
|
|
|
|
|
|
void dispset(set<int> s)//输出集合的元素{
|
|
|
set<int)::iterator it;
|
|
|
for(it=s.begin();it!=s.end();++it) printf("%d ",*it): printf("\n”);
|
|
|
void main()
|
|
|
int a[]={3,2,4,8};
|
|
|
int n=sizeof(a)/sizeof(a[0]); set<int) s1(a,atn); int b[]={1,2,4,5,3};
|
|
|
int m=sizeof(b)/sizeof(b[0]); set<int) s2(b,b+m); set<int) s3;
|
|
|
solve(s1,s2,s3);
|
|
|
printf(“求解结果\n”):
|
|
|
print£(”s1:“);dispset(s1); print£(”s2:");dispset(s2): printf(”s3:“);dispset(s3);
|
|
|
|
|
|
|
|
|
【问题描述】 求解自行车慢速比赛问题
|
|
|
一个美丽的小岛上有许多景点,景点之间有一条或者多条道路。现在进行自行车慢速比赛(最慢的选手获得冠军)，工作人员在道路上标出自行车的单向行驶方向，所有比赛线路不会出现环,选手不能在中途的任何地方停下来,否则犯规，退出比赛。首先给定一行两个整数N和M,N为岛上的景点数(景点编号为0~N-1,N≤100),接下来的M行，每行为a、b、l,表示景点a和景点b之间的单向路径长度为L(L为整数)。最后一行为s和t，表示比赛的起点s和终点t。所有选手水平高超，都能够以自行车的最低速度行驶，并且所有自行车的最低速度相同。问冠军所走的路径长度是多少?假设只有一组测试数据。
|
|
|
#include <stdio.h>
|
|
|
#define INF 0x3f3f3f3f //定义∞
|
|
|
#define MAXV 101
|
|
|
int A[MAXV][MAXV]; //邻接矩阵
|
|
|
int n,m;
|
|
|
int s,t;
|
|
|
int dist[MAXV];
|
|
|
void BellmanFord(int v) //贝尔曼-福特算法
|
|
|
{ int i,k,u;
|
|
|
for (i=0;i<n;i++)
|
|
|
dist[i]=A[v][i]; //对dist0[i]初始化
|
|
|
for (k=1;k<n;k++) //从dist0[u]递推出dist2[u], …,distn-1[u]循环n-2次
|
|
|
{ for (u=0;u<n; u++) //修改所有非顶点v的dist[]值
|
|
|
{ if (u!=v)
|
|
|
{ for (i=0;i<n;i++)
|
|
|
{ if (A[i][u]<INF && dist[u]>dist[i]+A[i][u])
|
|
|
dist[u]=dist[i]+A[i][u];
|
|
|
}
|
|
|
} } }
|
|
|
}
|
|
|
int main()
|
|
|
{ int i,j;
|
|
|
int a,b,l;
|
|
|
scanf("%d%d",&n,&m); //输入n、m
|
|
|
for (i=0;i<n;i++) //初始化邻接矩阵
|
|
|
for (j=0;j<n;j++)
|
|
|
if (i==j)
|
|
|
A[i][j]=0;
|
|
|
else
|
|
|
A[i][j]=INF;
|
|
|
for (i=0;i<m;i++) //输入边
|
|
|
{ scanf("%d%d%d",&a,&b,&l);
|
|
|
A[a][b]=-l;
|
|
|
}
|
|
|
scanf("%d%d",&s,&t); //输入s和t
|
|
|
BellmanFord(s); //采用BellmanFord算法求s出发的最短路径
|
|
|
printf("%d\n",-dist[t]); //输出结果
|
|
|
return 1;
|
|
|
}
|
|
|
|
|
|
【问题描述】假设二叉树中所有结点值为int类型，采用二叉链存储。设计递归算法求二叉树bt中从根结点到叶子结点路径和最大的一条路径。编写完整的实验程序，并采用相应数据进行测试
|
|
|
1、引导学生回顾二叉树的基本运算算法：定义结点类型，选择存储结构，建立二叉链表，用括号表示法输出二叉树，释放二叉树等。
|
|
|
相应代码如下 ：
|
|
|
#include <vector>
|
|
|
#include <string>
|
|
|
using namespace std;
|
|
|
typedef int ElemType;
|
|
|
typedef struct node
|
|
|
{ ElemType data; //数据元素
|
|
|
truct node *lchild; //指向左孩子结点
|
|
|
struct node *rchild; //指向右孩子结点
|
|
|
} BTNode; //二叉链结点类型
|
|
|
BTNode *CreateBTree(ElemType a[],ElemType b[],int n) //对应例2.8的算法由先序序列a[0..n-1]和中序序列b[0..n-1]建立二叉链
|
|
|
{
|
|
|
int k;
|
|
|
if (n<=0) return NULL;
|
|
|
ElemType root=a[0]; //根结点值
|
|
|
BTNode *bt=(BTNode *)malloc(sizeof(BTNode));
|
|
|
bt->data=root;
|
|
|
for (k=0;k<n;k++) //在b中查找b[k]=root的根结点
|
|
|
if (b[k]==root)
|
|
|
break;
|
|
|
bt->lchild=CreateBTree(a+1,b,k); //递归创建左子树
|
|
|
bt->rchild=CreateBTree(a+k+1,b+k+1,n-k-1); //递归创建右子树
|
|
|
return bt;
|
|
|
}
|
|
|
void DispBTree(BTNode *bt) //采用括号表示输出二叉链bt
|
|
|
{
|
|
|
if (bt!=NULL)
|
|
|
{ printf("%d",bt->data);
|
|
|
if (bt->lchild!=NULL || bt->rchild!=NULL)
|
|
|
{ printf("("); //有孩子结点时才输出(
|
|
|
DispBTree(bt->lchild); //递归处理左子树
|
|
|
if (bt->rchild!=NULL) printf(","); //有右孩子结点时才输出,
|
|
|
DispBTree(bt->rchild); //递归处理右子树
|
|
|
printf(")"); //有孩子结点时才输出)
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
void DestroyBTree(BTNode *&bt) //对应例2.9的算法
|
|
|
//释放以bt为根结点的二叉树
|
|
|
{ if (bt!=NULL)
|
|
|
{ DestroyBTree(bt->lchild);
|
|
|
DestroyBTree(bt->rchild);
|
|
|
free(bt);
|
|
|
}
|
|
|
} |
