递归 队列 优先队列笔记

 

递归

递归是解决问题时容易想出解决方案，但是递归会占用较大的内存，也容易超时，所以有时又要避免递归的解决方法。我感觉以下两个问题的比较能够较好的反映递归的优缺点。

问题

A - 蟠桃记

喜欢西游记的同学肯定都知道悟空偷吃蟠桃的故事，你们一定都觉得这猴子太闹腾了，其实你们是有所不知：悟空是在研究一个数学问题！ 
什么问题？他研究的问题是蟠桃一共有多少个！ 
不过，到最后，他还是没能解决这个难题，呵呵^-^ 
当时的情况是这样的： 
第一天悟空吃掉桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。聪明的你，请帮悟空算一下，他第一天开始吃的时候桃子一共有多少个呢？ 

Input

输入数据有多组，每组占一行，包含一个正整数n（1<n<30），表示只剩下一个桃子的时候是在第n天发生的。

Output

对于每组输入数据，输出第一天开始吃的时候桃子的总数，每个测试实例占一行。

Sample Input

2
4

Sample Output

4
22

我的思路：由题可知可以列出第n天前的蟠桃数的数列 {  }，，,由此可以列出数列的递归函数

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
const int maxn=1e3+10;
long long nb(int x)
{
	if(x==1) return 1;
	else return 2*(nb(x-1)+1);
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF&&n)
	{
		printf("%lld\n",nb(n));
	}
}

B - 一只小蜜蜂...

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。 
其中，蜂房的结构如下所示。 

Input

输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。 

Output

对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。 

Sample Input

2
1 2
3 6

Sample Output

1
3

我的思路：有题目可以知晓，若从1->4,可以把1->3的路线数加上1->2的路线数，即求得：3；由此观察出规律：从a->b的情况数是：    ,哈哈，这居然是斐波拉契数列

然后我们用以下递归代码来尝试解决，但是...

#include<iostream>
#include<stdio.h>
using namespace std;
long int f(int c)
{
	if(c==1) return 1;
	else if(c==2) return 2;
	     else return f(c-1)+f(c-2); 
	
}
int main() 
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%ld\n",f(b-a));
	}
}

OMG，上面这个代码会超时，之后就要避免用递归的方法了，然后用for循环提前把题目要求的数列前n项求出。

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	long long x[51];
	x[0]=1;
	x[1]=2;
	for(int i=2;i<50;i++)
    	x[i]=x[i-1]+x[i-2];
	scanf("%d",&n);
	while(n--)
	{

		int a,b;
		scanf("%d%d",&a,&b);
		printf("%lld\n",x[b-a-1]);
	}
}

队列与优先队列

许多内容来自此博客，同时在细节上有所改动https://www.cnblogs.com/xzxl/p/7266370.html

感觉这篇博客写得很好，让我学得更清楚明白了https://blog.csdn.net/c20182030/article/details/70757660

队列

• queue模板类的定义在<queue>头文件中。
• queue 模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。

队列的定义：

queue<int>q1;    //队列中为整数

queue<double>q2; //队列中为双精度浮点数

queue的基本操作：
入队：q.push(x); 将x 接到队列的末端。
出队：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素：q.front()，即最早被压入队列的元素。
访问队尾元素：q.back()，即最后被压入队列的元素。
判断队列空：q.empty()，当队列空时，返回true。
访问队列中的元素个数：q.size()

问题

C - 愚人节的礼物

四月一日快到了，Vayko想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko为了愚人，准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。 
用()表示一个盒子，B表示礼物，Vayko想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。 

Input

本题目包含多组测试，请处理到文件结束。 
每组测试包含一个长度不大于1000,只包含'(',')'和'B'三种字符的字符串，代表Vayko设计的礼物透视图。 
你可以假设，每个透视图画的都是合法的。 

Output

对于每组测试，请在一行里面输出愚人指数。

Sample Input

((((B)()))())
(B)

Sample Output

4
1

我的思路：题意主要是至少拆开的盒子数是多少，如：(()(B)),至少需要拆开两层盒子就能够得到礼物，所以愚人指数是2；这道题用队列或者栈就会使问题变得简单许多了。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
using namespace std;
const int maxn=1e3+10;
int main()
{
	char str[maxn];
	while(scanf("%s",str)!=EOF)
	{
	    queue<char>fr;
	    int t1=0;
		for(int i=0;str[i]=='B'||str[i]==')'||str[i]=='(';i++)
		{
			switch(str[i])
			{
				case'(':
				    fr.push('(');
				    break;
				case')':
				    fr.push(')');
				    break;
				case'B':
				    fr.push('B');
				    break;
		    }
	    }
        for(;fr.front()!='B';)
        {
            if(fr.front()=='(')
                t1++;
            else if(fr.front()==')')
                    t1--;
            fr.pop();
        }
        printf("%d\n",t1);
    }
}

优先队列

头文件：#include <queue>

优先队列的定义：

//普通方法
priority_queue<int> q;   　　　　　　　　　　　　  //通过操作，按照元素从大到小的顺序出队
priority_queue<int,vector<int>, greater<int> > q;  　　//通过操作，按照元素从小到大的顺序出队


//优先级定义
struct cmp 
{     
　　operator bool ()(int x, int y)     
　　{        
　　　　 return　x > y;　　 // x小的优先级高       //也可以写成其他方式，如： return p[x] > p[y];表示p[i]小的优先级高
　　}
};
priority_queue<int, vector<int>, cmp> q;    //定义方法
//其中，第二个参数为容器类型。第三个参数为比较函数。


//结构体声明的方式
struct node 
{     
　　int x, y;     
　　friend bool operator < (node a, node b)  //通过自定义operator<操作符来比较元素中的优先级。   
　　{         
　　　　return a.x > b.x;    //结构体中，x小的优先级高     
　　}
};
priority_queue<node>q;   //定义方法
//在该结构中，y为值, x为优先
//在重载”<”时，最好不要重载”>”，可能会发生编译错误

类似队列，priority_queue的基本操作：

empty() 　　   如果队列为空，则返回真

pop()　　　　删除对顶元素，删除第一个元素

push() 　　     加入一个元素

size() 　　　  返回优先队列中拥有的元素个数

top() 　　　　返回优先队列对顶元素，返回优先队列中有最高优先级的元素

注意优先队列里面没有black( )操作！！！

在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。

阅读代码来理解最直接了：

/*优先队列的基本使用    2017/8/1    xzxl*/ 
#include<stdio.h> 
#include<functional> 
#include<queue> 
#include<vector> 
using namespace std; 
//定义结构，使用运算符重载,自定义优先级1 
struct cmp1{ 
    bool operator ()(int &a,int &b){ 
        return a>b;//最小值优先 
    } 
}; 
struct cmp2{ 
    bool operator ()(int &a,int &b){ 
        return a<b;//最大值优先 
    } 
}; 
//定义结构，使用运算符重载,自定义优先级2 
struct number1{ 
    int x; 
    bool operator < (const number1 &a) const { 
        return x>a.x;//最小值优先 
    } 
}; 
struct number2{ 
    int x; 
    bool operator < (const number2 &a) const { 
        return x<a.x;//最大值优先 
    } 
}; 
int a[]={14,10,56,7,83,22,36,91,3,47,72,0}; 
number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0}; 
number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0}; 
   
int main() 
{   priority_queue<int>que;//采用默认优先级构造队列 
   
    priority_queue<int,vector<int>,cmp1>que1;//最小值优先 
    priority_queue<int,vector<int>,cmp2>que2;//最大值优先 
   
    priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误， 
                                                      //这是右移运算符，所以这里用空格号隔开 
    priority_queue<int,vector<int>,less<int> >que4;////最大值优先 
   
    priority_queue<number1>que5; 
    priority_queue<number2>que6; 
   
    int i; 
    for(i=0;a[i];i++)
    { 
        que.push(a[i]); 
        que1.push(a[i]); 
        que2.push(a[i]); 
        que3.push(a[i]); 
        que4.push(a[i]); 
    } 
    for(i=0;num1[i].x;i++) 
        que5.push(num1[i]); 
    for(i=0;num2[i].x;i++) 
        que6.push(num2[i]); 
   
    printf("采用默认优先关系:\n(priority_queue<int>que;)\n"); 
    printf("Queue 0:\n"); 
    while(!que.empty()){ 
        printf("%3d",que.top()); 
        que.pop(); 
    } 
    puts(""); 
    puts(""); 
   
    printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n"); 
    printf("Queue 1:\n"); 
    while(!que1.empty()){ 
        printf("%3d",que1.top()); 
        que1.pop(); 
    } 
    puts(""); 
    printf("Queue 2:\n"); 
    while(!que2.empty()){ 
        printf("%3d",que2.top()); 
        que2.pop(); 
    } 
    puts(""); 
    puts(""); 
    printf("采用头文件\"functional\"内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n"); 
    printf("Queue 3:\n"); 
    while(!que3.empty()){ 
        printf("%3d",que3.top()); 
        que3.pop(); 
    } 
    puts(""); 
    printf("Queue 4:\n"); 
    while(!que4.empty()){ 
        printf("%3d",que4.top()); 
        que4.pop(); 
    } 
    puts(""); 
    puts(""); 
    printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n"); 
    printf("Queue 5:\n"); 
    while(!que5.empty()){ 
        printf("%3d",que5.top()); 
        que5.pop(); 
    } 
    puts(""); 
    printf("Queue 6:\n"); 
    while(!que6.empty()){ 
        printf("%3d",que6.top()); 
        que6.pop(); 
    } 
    puts(""); 
    return 0; 
} 
/*
运行结果 ：
采用默认优先关系:
(priority_queue<int>que;)
Queue 0:
91 83 72 56 47 36 22 14 10  7  3
  
采用结构体自定义优先级方式一:
(priority_queue<int,vector<int>,cmp>que;)
Queue 1:
 7 10 14 22 36 47 56 72 83 91
Queue 2:
91 83 72 56 47 36 22 14 10  7  3
  
采用头文件"functional"内定义优先级:
(priority_queue<int,vector<int>,greater<int>/less<int> >que;)
Queue 3:
 7 10 14 22 36 47 56 72 83 91
Queue 4:
91 83 72 56 47 36 22 14 10  7  3
  
采用结构体自定义优先级方式二:
(priority_queue<number>que)
Queue 5:
 7 10 14 22 36 47 56 72 83 91
Queue 6:
91 83 72 56 47 36 22 14 10  7  3
*/ 

问题

F - 看病要排队

看病要排队这个是地球人都知道的常识。 
不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高，级别为1的优先权最低。医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人。 
现在就请你帮助医院模拟这个看病过程。

Input

输入数据包含多组测试，请处理到文件结束。 
每组数据第一行有一个正整数N(0<N<2000)表示发生事件的数目。 
接下来有N行分别表示发生的事件。 
一共有两种事件： 
1:"IN A B",表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10) 
2:"OUT A",表示医生A进行了一次诊治，诊治完毕后，病人出院。(0<A<=3)

Output

对于每个"OUT A"事件，请在一行里面输出被诊治人的编号ID。如果该事件时无病人需要诊治，则输出"EMPTY"。 
诊治人的编号ID的定义为：在一组测试中，"IN A B"事件发生第K次时，进来的病人ID即为K。从1开始编号。 

Sample Input

7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1

Sample Output

2
EMPTY
3
1
1

我的思路：用三个队列分别存储三个医生的病人队伍，我尝试用priority_queue<patient>d[3];然后可以这么用。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<queue>
using namespace std;
const int maxn=1e3+10;
struct patient
{
    int p,ID;
    bool operator < (const patient &a) const
    {
        if(p!=a.p)
            return a.p>p;
        else
            return a.ID<ID;
    }
};
int main()
{
    int n;
    patient doctor[3];
    while(scanf("%d",&n)!=EOF)
    {
        priority_queue<patient> d[3];  
        int i=1;
        while(n--)
        {
            char op[4];
            int j;
            scanf("%s",op);
            if(op[0]=='I')
            {
                scanf("%d",&j);
                scanf("%d",&doctor[j-1].p);
                doctor[j-1].ID=i;
                d[j-1].push(doctor[j-1]);
                i++;
            }
            else if(op[0]=='O')
            {
                scanf("%d",&j);
                if(!d[j-1].empty())
                {
                    printf("%d\n",(d[j-1].top()).ID);
                    d[j-1].pop();
                }
                else
                    printf("EMPTY\n");
            }
        }
    }
    return 0;
}