数据结构第五周 ：（进制转换问题 + 迷宫自动行走问题 + 杨辉三角形 + 队列元素逆置 + 银行排队 + 整数划分问题 + 卡特兰数）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
进制转换问题
【问题描述】根据课堂讲授请用“顺序栈”解决进制转换问题不采用顺序栈不给分。
【输入形式】十进制数据和待转换的进制
【输出形式】转换后的数据
【样例输入】1348 8
【样例输出】2504
【样例输入】2608 16
【样例输出】A30
#include<stdio.h>
#define Stack_Size 50
typedef struct{
int elem[Stack_Size];
int top;
}SeqStack;
void InitStack(SeqStack * L){ //栈的初始化
L->top = -1;
}
int PushStack(SeqStack * L,int e){ //进栈
if(L->top == Stack_Size - 1){
return 0;
}
else{
L->top++;
L->elem[L->top] = e;
return 0;
}
return 0;
}
int PopStack(SeqStack * L,int * e){
if(L->top == -1){
return 0;
}
else{
*e = L->elem[L->top];
L->top--;
return 0;
}
return 0;
}
void Metric(SeqStack * L,int oper,int base){
while(oper != 0){
PushStack(L,oper%base);
oper = oper/base;
}
while(L->top != -1){
int temp;
PopStack(L,&temp);
if(base <= 10){
printf("%d",temp);
}
else{
if(temp < 10){
printf("%d",temp);
}
else{
char a ='A'+(temp - 10);
printf("%c",a);
}
}
}
}
int main(){
SeqStack L;
InitStack(&L);
int oper,base;
scanf("%d %d",&oper,&base);
Metric(&L,oper,base);
return 0;
}
迷宫自动行走问题
【问题描述】有一个 10 x 10 的迷宫起点是‘S’终点是‘E’墙是‘#’道路是空格。一个机器人从起点走到终点。当机器人走到一个通道块前面已经没有路可走时它会按照右下左上的顺序在四个方向选择从而继续走。如果机器人能够过则留下足迹‘*’如果走不通则留下标记‘!’。
#include<iostream>
#include<stdio.h>
using namespace std;
const int N = 150;
typedef struct position{//定义坐标位置类型
int r, c;
}PosType;
typedef struct{// 定义堆栈元素的类型
int ord; // 通道块在路径上的序号
PosType seat; //通道块在迷宫中的坐标位置
int di; //此通道块走向下一通道块的方向
}SElemType;
typedef struct{// 定义迷宫类型
char arr[10][11];
}MazeType;
typedef struct{//定义顺序栈
SElemType elem[N];
int top;
}SqStack;
void InitStack(SqStack * S){// 初始化栈
S->top = -1;
}
void Fillmaze(MazeType &maze){//输入初始地图
int i;
for(i = 0; i < 10; i++){
gets(maze.arr[i]); //可读入空格回车表结束
}
}
void DisplayMaze(MazeType &maze){ //输出地图
int i;
for(i = 0; i < 10; i++){
cout<<maze.arr[i];
cout<<endl;
}
}
void Push(SqStack * S,SElemType e){ //进栈操作
S->elem[++S->top] = e;
}
bool IsEmpty(SqStack * S){ //判空
if(S->top == -1) return true;
else return false;
}
void Pop(SqStack * S, SElemType &e){ //出栈
if(IsEmpty(S))return ;
else{
e = S->elem[S->top--];
}
}
bool Pass(MazeType &maze, PosType curpos){//判断能否通行
if(maze.arr[curpos.r][curpos.c] == ' ' || maze.arr[curpos.r][curpos.c] == 'S' || maze.arr[curpos.r][curpos.c] == 'E')
return true;
else
return false;
}
void FootPrint(MazeType &maze, PosType curpos){ //标记已走过的路
maze.arr[curpos.r][curpos.c] = '*';
}
position NextPos(PosType curpos, int num){
switch(num){
case 1:curpos.c += 1;break;
case 2:curpos.r += 1;break;
case 3:curpos.c -= 1;break;
case 4:curpos.r -= 1;break;
}
return curpos;
}
void MarkPrint(MazeType &maze, PosType seat){ //标记死路
maze.arr[seat.r][seat.c] = '!';
}
void MazePath(MazeType &maze, PosType start, PosType end){ //迷宫路径
SqStack S; //存放路径
PosType curpos; //当前位置
int curstep; //当前步数
SElemType e; //栈元素
InitStack(&S);
curpos = start;
curstep = 1;
do{
if(Pass(maze,curpos)){
FootPrint(maze,curpos);
e.di = 1;
e.ord = curstep;
e.seat = curpos;
Push(&S,e);
if(curpos.r == end.r && curpos.c == end.c) return ;
curpos = NextPos(curpos,1);
curstep++;
}
else{
if(!IsEmpty(&S)){
Pop(&S,e);
while(e.di == 4 && !IsEmpty(&S)){
MarkPrint(maze,e.seat);
Pop(&S,e);
}
if(e.di < 4){
e.di++;
Push(&S,e);
curpos = NextPos(e.seat,e.di);
}
}
}
}while(!IsEmpty(&S));
return ;
}
int main(){
MazeType maze;
PosType start;
PosType end;
Fillmaze(maze); //传递的是maze 的地址
for(int i = 0; i < 10; i ++)
for(int j = 0; j < 10; j ++)
{
if(maze.arr[i][j] == 'S')
{
start.c = i, start.r = j;
}
if(maze.arr[i][j] == 'E')
{
end.c = i, end.r = j;
}
}
MazePath(maze,start,end);
DisplayMaze(maze);
return 0;
}
杨辉三角形
【问题描述】杨辉三角形的打印请用循环队列实现。不采用“循环队列”不给分。
【样例输入】
4
【样例输出】
1
1 1
1 2 1
1 3 3 1
#include<stdio.h>
#define Queue_Size 50
typedef struct{
int elem[Queue_Size];
int front;
int rear;
}SeqQueue;
void InitQue(SeqQueue * L){ //队列的初始化
L->front = 0;
L->rear = 0;
}
int EnterQue(SeqQueue * L,int e){ //进队列
if((L->rear + 1) % Queue_Size == L->front){
return 0;
}
else{
L->elem[L->rear] = e;
L->rear = (L->rear + 1) % Queue_Size;
return 0;
}
return 0;
}
int DeleteQue(SeqQueue * L,int * e){ //出队列
if(L->front == L->rear){
return 0;
}
else{
*e = L->elem[L->front];
L->front = (L->front + 1) % Queue_Size;
return 0;
}
return 0;
}
int GetHead(SeqQueue * L,int * e){
if(L->front == L->rear){
return 0;
}
else{
*e = L->elem[L->front];
return 0;
}
return 0;
}
int IsEmpty(SeqQueue * L){
if(L->rear == L->front){
return 1;
}
else{
return 0;
}
}
void DisplayYh(SeqQueue * L,int r){ //实现杨辉三角的打印
EnterQue(L,1);
int i;
for(i = 2; i <= r; i++){
EnterQue(L,1);
int j;
int temp = 0;
int head = 0;
for(j = 1; j <= i - 2; j++){
DeleteQue(L,&temp);
printf("%d ",temp);
GetHead(L,&head);
EnterQue(L,temp + head);
}
DeleteQue(L,&temp);
printf("%d ", temp);
printf("\n");
EnterQue(L,1);
}
while(!IsEmpty(L)){
int temp = 0;
DeleteQue(L,&temp);
printf("%d ",temp);
}
}
int main(){
SeqQueue L;
InitQue(&L);
int r;
scanf("%d",&r);
DisplayYh(&L,r);
return 0;
}
队列元素逆置
【问题描述】已知Q是一个非空队列S是一个空栈。仅使用少量工作变量以及对队列和栈的基本操作编写一个算法将队列Q中的所有元素逆置。需采用链式队列与栈顺序或链式否则不能得分。
【输入形式】输入的第一行为队列元素个数第二行为队列从首至尾的元素
【输出形式】输出队列的逆置
【样例输入】
3
1 2 3
【样例输出】
3 2 1
#include<stdio.h>
#include<stdlib.h>
typedef struct SNode{
int data;
struct SNode * next;
}LinkStackNode; //链式栈的节点
typedef LinkStackNode* LinkStack;
typedef struct QNode{
int data;
struct QNode * next;
}LinkQueueNode; //链式队列节点
typedef struct{
LinkQueueNode * front;
LinkQueueNode * rear;
}LinkQueue;
void InitStack(LinkStack * S){//链栈的初始化
*S = (LinkStack)malloc(sizeof(LinkStackNode));
(*S)->next = NULL;
}
int PushStack(LinkStack top,int e){//链栈的进栈操作
LinkStackNode * temp;
temp = (LinkStack)malloc(sizeof(LinkStackNode));
if(temp == NULL){
return 0;
}
else{
temp->data = e;
temp->next = top->next;
top->next = temp;
return 0;
}
return 0;
}
int PopStack(LinkStack top,int * e){
if(top->next == NULL){
return 0;
}
else{
LinkStackNode * temp;
temp = top->next;
top->next = temp->next;
*e = temp->data;
free(temp);
return 0;
}
return 0;
}
void InitQueue(LinkQueue * Q){ //链队列的初始化
Q->front = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
if(Q->front != NULL){
Q->rear = Q->front;
Q->front->next = NULL;
}
}
int EnterQueue(LinkQueue * Q,int e){ //链队列的进队列操作
LinkQueueNode * temp;
temp = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
if(temp != NULL){
temp->data = e;
temp->next = NULL;
Q->rear->next = temp;
Q->rear = temp;
return 0;
}
return 0;
}
int DeleteQueue(LinkQueue * Q,int * e){//链队列的出队列操作
LinkQueueNode * temp;
if(Q->rear != Q->front){
temp = Q->front->next;
*e = temp->data;
Q->front->next = temp->next;
free(temp);
}
return 0;
}
int main(){
LinkStack top = NULL;
InitStack(&top);
LinkQueue Q;
InitQueue(&Q);
int QueLen;
scanf("%d",&QueLen);
int flag;
flag = QueLen;
while(flag--){
int QueData;
scanf("%d",&QueData);
EnterQueue(&Q,QueData);
}
flag = QueLen;
while(flag--){
int temp;
DeleteQueue(&Q,&temp);
PushStack(top,temp);
}
flag = QueLen;
while(flag--){
int temp = 0;
PopStack(top,&temp);
EnterQueue(&Q,temp);
printf("%d ",temp);
}
return 0;
}
银行排队——队列
【问题描述】
我们大多都有在银行排队的经历唉那坑爹的排队啊现在就让我们来算算我们这些客户平均需要等多久吧。
每天刚开始时银行会开m个窗口来为我们total个客户办理业务当有客户需要办理业务时先选择可以办理业务的窗口如果有多个窗口可以办理业务就选择空闲时间最长的窗口如果有多个窗口空闲的时间一样长则选择序号小的窗口办理业务。假设我们每个人来到的时间和办理业务所需要的时间为了简化问题采用整数表示时间都知道了。现在请你算算我们平均需要等待多久呢请用顺序队列或链式队列来完成本题。
【输入形式】
有多组测试数据每组数据开始有两个正整数m(<20)和total(<200)后面有total对整数对应客户先后到来的时间以及办理业务所需的时间。
【输出形式】
平均等待的时间保留两位小数。
【样例输入】
2 6 1 3 4 1 5 3 9 2 13 4 13 3
3 14 0 3 2 2 2 4 5 4 7 2 11 3 12 3 12 4 12 1 13 3 15 4 19 1 22 3 23 2
2 5 0 6 0 5 0 6 7 1 7 2
【样例输出】
0.00
0.29
1.20
【提示】
题目中选择办理的窗口有三个状态实际上从序号自小到大查找可以最早办理业务的窗口就已经满足上述三个状态了。若客户的到来时间相同现实中并不知道该用户需要多久处理完任务所以遵循先来的先服务原则。
【要求】
请用顺序队列或链式队列来完成否则不得分。
#include<bits/stdc++.h>
using namespace std;
int m,tot,a,b;
template<class T> class Pque{
protected:
struct node{
T data;
node* next;
node():next(NULL){}
};
node* head;
int Size;
public:
Pque():Size(0){
head=new node;
}
~Pque(){
head=head->next;
while(head) {
node* t=head;
head=head->next;
delete t;
}
}
void push(T t){
node* p=head;
for(;p->next&&p->next->data<t;p=p->next);
node* n=new node;
n->data=t;n->next=p->next;p->next=n;
++Size;
}
T pop(){
node* p=head->next;
head->next=p->next;
T t=p->data;
delete p;--Size;
return t;
}
T front(){return head->next->data;}
int size(){return Size;}
};
int main(){
while(cin>>m){
Pque<int> win;cin>>tot;
double wt=0;
for(int i=0;i<tot;++i){
cin>>a>>b;
while(win.size()&&win.front()<=a)win.pop();
if(win.size()<m) win.push(a+b);
else{
int k=win.front();
wt+=k-a;
win.pop();
win.push(k+b);
}
}
cout<<fixed<<setprecision(2)<<wt/tot<<endl;
}
return 0;
}
整数划分问题
【问题描述】根据课堂讲授编程实现某整数的划分的输出
【样例输入】
6
【样例输出】
6
5+1
4+2
4+1+1
3+3
3+2+1
3+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 110;
int res[N];
int n;
void dfs(int rest, int pre, int cnt)
{
if(rest == 0)
{
for(int i = 0; i < cnt - 1; i ++)
{
cout<< res[i] << '+';
}
cout << res[cnt - 1] << endl;
return;
}
for(int i = pre; i >= 1; i --)
{
if(i > rest) continue;
res[cnt] = i;
dfs(rest - i, i, cnt + 1);
}
}
int main()
{
int n;
cin >> n;
dfs(n, n, 0);
return 0;
}
买票问题——卡特兰数
【问题描述】
m个人只有50元钱n个人只有100元整钱票价50元/人。现在售票厅没钱只有50元钱的人可以不用找钱顺利买票而拿着100元整钱的人只有在前面有50元的情况下才能买票因为只有这样才能找零50元。所有的人能否买票和排队的方式有一定关系问使得所有的人能够顺利买票的排队方式有多少种
【输入形式】
m和n当输入0 0则结束输入
【输出形式】
先输出Test #i期中i代表第几组测试数据再输出排队方式的种数
【样例输入】
3 0
3 1
3 3
0 0
【样例输出】
Test #1:
6
Test #2:
18
Test #3:
180
#include<iostream>
using namespace std;
long long zh(int m, int n){
int i;
long long r1 = 1;
long long r2 = 1;
for(i = m; i > 0; i--){
r1 *= n;
n--;
r2 *= i;
}
return r1/r2;
}
long long jc(int m){
int i;
long long r = 1;
for(i = m; i > 0; i--){
r *= i;
}
return r;
}
long long fun(int m, int n){
if(n == 0){
return jc(m);
}
long long r1 = zh(m, m + n) * jc(m) * jc(n);
long long r2 = zh(m + 1, m + n) * jc(m) * jc(n);
return r1 - r2;
}
int main(){
int flag = 0;
while(1){
flag++;
int m,n;
cin>>m>>n;
if(m == 0 && n == 0){
break;
}
else{
long long res;
res = fun(m,n);
cout<<"Test #"<<flag<<':'<<endl;
cout<<res<<endl;
}
}
return 0;
}
小兔的棋盘——卡特兰数
【问题描述】
小兔的叔叔从外面旅游回来给她带来了一个礼物小兔高兴地跑回自己的房间拆开一看是一个棋盘小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(00)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)这样的路径数有多少?小兔想了很长时间都没想出来现在想请你帮助小兔解决这个问题对于你来说应该不难吧!
【输入形式】
每次输入一个数n(1<=n<=35)当n等于－1时结束输入。
【输出形式】
对于每个输入数据输出路径数具体格式看Sample。
【样例输入】
1
3
12
-1
【样例输出
1 1 2
2 3 10
3 12 416024
#include<stdio.h>
#include<iostream>
using namespace std;
int LC(int num,int cent){
int i;
long long r1 = 1;
long long r2 = 1;
for(i = cent; i > 0; i--){
r1 *= num;
num--;
r2 *= i;
}
return r1/r2;
}
int main(){
int flag = 0;
while(1){
flag++;
int n;
scanf("%d",&n);
if(n == -1) break;
long long r1 = LC(2 * n,n);
long long r2 = LC(2 * n,n - 1);
long long res = 2 * (r1 - r2);
cout<<flag<<" "<<n<<" "<<res<<endl;
}
return 0;
}