IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 紫书第6章 数据结构基础 例题A~D -> 正文阅读

[数据结构与算法]紫书第6章 数据结构基础 例题A~D

A . Concurrency Simulator

Description
Programs executed concurrently on a uniprocessor system appear to be executed at the same time, but in reality the single CPU alternates between the programs, executing some number of instructions from each program before switching to the next. You are to simulate the concurrent execution of up to ten programs on such a system and determine the output that they will produce.

The program that is currently being executed is said to be running, while all programs awaiting execution are said to be ready. A program consists of a sequence of no more than 25 statements, one per line, followed by an end statement. The statements available are listed below.

A variable is any single lowercase alphabetic character and a constant is an unsigned decimal number less than 100. There are only 26 variables in the computer system, and they are shared among the programs. Thus assignments to a variable in one program affect the value that might be printed by a different program. All variables are initially set to zero.

Each statement requires an integral number of time units to execute. The running program is permitted to continue executing instructions for a period of time called its quantum. When a program’s time quantum expires, another ready program will be selected to run. Any instruction currently being executed when the time quantum expires will be allowed to complete.

Programs are queued first-in-first-out for execution in a ready queue. The initial order of the ready queue corresponds to the original order of the programs in the input file. This order can change, however, as a result of the execution of lock and unlock statements.

The lock and unlock statements are used whenever a program wishes to claim mutually exclusive access to the variables it is manipulating. These statements always occur in pairs, bracketing one or more other statements. A lock will always precede an unlock, and these statements will never be nested. Once a program successfully executes a lock statement, no other program may successfully execute a lock statement until the locking program runs and executes the corresponding unlock statement. Should a running program attempt to execute a lock while one is already in effect, this program will be placed at the end of the blocked queue. Programs blocked in this fashion lose any of their current time quantum remaining. When an unlock is executed, any program at the head of the blocked queue is moved to the head of the ready queue. The first statement this program will execute when it runs will be the lock statement that previously failed. Note that it is up to the programs involved to enforce the mutual exclusion protocol through correct usage of lock and unlock statements. (A renegade program with no lock/unlock pair could alter any variables it wished, despite the proper use of lock/unlock by the other programs.)

Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first line of the input file consists of seven integers separated by spaces. These integers specify (in order): the number of programs which follow, the unit execution times for each of the five statements (in the order given above), and the number of time units comprising the time quantum. The remainder of the input consists of the programs, which are correctly formed from statements according to the rules described above.

All program statements begin in the first column of a line. Blanks appearing in a statement should be ignored. Associated with each program is an identification number based upon its location in the input data (the first program has ID = 1, the second has ID = 2, etc.)

Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Your output will contain of the output generated by the print statements as they occur during the simulation. When a print statement is executed, your program should display the program ID, a colon, a space, and the value of the selected variable. Output from separate print statements should appear on separate lines.

Samples
Input 复制
3 1 1 1 1 1 1
a = 4
print a
lock
b = 9
print b
unlock
print b
end
a = 3
print a
lock
b = 8
print b
unlock
print b
end
b = 5
a = 17
print a
print b
lock
b = 21
print b
unlock
print b
end
Output
1: 3
2: 3
3: 17
3: 9
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21
题目大意
你的任务是模拟n个程序(按输入顺序编号为1~n)的并行执行。每个程序包含不超过 25条语句,格式一共有5种:var = constant(赋值);print var(打印);lock;unlock;end。 变量用单个小写字母表示,初始为0,为所有程序公有(因此在一个程序里对某个变量 赋值可能会影响另一个程序)。常数是小于100的非负整数。 每个时刻只能有一个程序处于运行态,其他程序均处于等待态。上述5种语句分别需 要t1、t2、t3、t4、t5单位时间。运行态的程序每次最多运行Q个单位时间(称为配额)。当 一个程序的配额用完之后,把当前语句(如果存在)执行完之后该程序会被插入一个等待队 列中,然后处理器从队首取出一个程序继续执行。初始等待队列包含按输入顺序排列的各个 程序,但由于lock/unlock语句的出现,这个顺序可能会改变。 lock的作用是申请对所有变量的独占访问。lock和unlock总是成对出现,并且不会嵌套。 lock总是在unlock的前面。当一个程序成功执行完lock指令之后,其他程序一旦试图执行lock 指令,就会马上被放到一个所谓的阻止队列的尾部(没有用完的配额就浪费了)。当unlock 执行完毕后,阻止队列的第一个程序进入等待队列的首部。
输入n, t1, t2, t3, t4, t5, Q以及n个程序,按照时间顺序输出所有print语句的程序编号和结 果

分析:”
因为有“等待队列”和“阻止队列”的字眼,本题看上去是队列的一个简单应用,但请注意 “阻止队列的第一个程序进入等待队列的首部”。这违反了队列的规则:新元素插入 了队列首部而非尾部。
本题是对STL中的“双端队列”deque的应用;

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, a[10];
string s, ans;
int i,j;
    cin >>n;
    for (i = 0; i < n; i ++) {
        for (j = 0; j < 7; j ++) scanf("%d", &a[j]);
        getchar(); // 吸收多余字符
        queue<string> q1[a[0]]; deque<int> qr; queue<int> qb; // 每个程序对应指令;ready;阻塞
        for (j = 0; j < a[0]; j ++) { // n个程序
            while (getline(cin, s) && s != "end") q1[j].push(s);
            qr.push_back(j);
        }
        if (i != 0) puts(""); // 连续输出的空行
        map<string, string> vmp; // 变量对应的值
        bool isLock = false; // 标记是否有锁
        while (!qr.empty()) { // 等待队列非空
            int t = 0, k = qr.front(); qr.pop_front(); // 耗费时间,当前程序编号
            bool isBlock = false; // 标记是否发生阻塞
            while (t < a[6] && !q1[k].empty()) { // 未超时
                s = q1[k].front(); // 取出第一条命令
                int j = s.find('=');
                if (j != string::npos) { // 赋值
                    vmp[s.substr(0,j-1)] = s.substr(j+2);
                    t += a[1]; // 计时
                }
                else {
                    j = s.find(' ');
                    if (j != string::npos) { // 打印输出
                        ans = "0"; // 初始化
                        if (vmp[s.substr(j+1)] != "") ans = vmp[s.substr(j+1)];  
                        printf("%d: %s\n", k+1, ans.c_str()); // print val
                        t += a[2];
                    }
                    else {
                        if (s[0] == 'l') { // lock
                            if (!isLock) { // 未有锁定
                                isLock = true;
                                t += a[3]; // 时间增加
                            }
                            else { // 已有锁定
                                qb.push(k); // 加入阻塞队列尾部
                                isBlock = true;
                                break; // 直接退出,忽略其它剩余时间
                            }
                        }
                        else if (s[0] == 'u') { // unlock
                            isLock = false; // 标记未锁定
                            if (!qb.empty()) { // 阻塞非空
                                qr.push_front(qb.front()); // 阻塞头部加入ready头部
                                qb.pop();
                            }
                            t += a[4];
                        }
                    }
                }
                q1[k].pop(); // 确保阻塞时lock命令不会被删除
            }
            if (!q1[k].empty() && !isBlock) qr.push_back(k); // 非空再次加入等待队列尾部
        }
    }
    return 0;
}

B . Rails

Description
There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.
The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N≤1000 coaches numbered in increasing order 1,2,…,N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1,a2,…,aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.
Input
The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1,2,…,N. The last line of the block contains just 0.
The last block consists of just one line containing 0.
Output
The output contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last ``null’’ block of the input.

Samples
Input 复制
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0
Output
Yes
No

Yes

题目大意:
为了重组车厢,你可以借助中转站C。这是一个可以停放任意多节车厢的车站,但由于 末端封顶,驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢,一旦从A移入C,就不 能再回到A了;一旦从C移入B,就不能回到C了。换句话说,在任意时刻,只有两种选择: A→C和C→B。
有n节车厢从A方向驶入车站,按进站顺 序编号为1~n。你的任务是判断是否能让它们按照某种特定的顺序进入B方向的铁轨并驶出 车站。例如,出栈顺序(5 4 1 2 3)是不可能的,但(5 4 3 2 1)是可能的。
为了重组车厢,你可以借助中转站C。这是一个可以停放任意多节车厢的车站,但由于 末端封顶,驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢,一旦从A移入C,就不 能再回到A了;一旦从C移入B,就不能回到C了。换句话说,在任意时刻,只有两种选择: A→C和C→B。

分析:
在中转站C中,车厢符合后进先出的原则,因此是一个栈。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,int>mp;
int main(){
      int n;
	  int i,j,k;
	  int a[1005],c[1005],b[1005];
	  int v;
	  while(cin>>n){
	  	if(n==0)
	  	return 0;
	  	v=0;
	  	for(i=1;i<=n;i++)
	  	a[i]=i;
	  	while(cin>>b[1]){
	  		v=0;
	  	if(b[1]==0){
	  		
	  		break;
		  }
	  	else if(b[1]){
	  		for(i=2;i<=n;i++)
	  		cin>>b[i];
	  		for(i=1,j=1;i<=n;){
	  			if(a[i]==b[j]){
	  				i++;
	  				j++;
				  }
				   else{
				  	c[++v]=a[i];
				  	i++;
				  }
				  while(b[j]==c[v]&&j<=n){
				  	j++;v--;
				  }
				 
			  }
			  if(v==0)
			  cout<<"Yes"<<endl;
			  else
			  cout<<"No"<<endl;
		  }
		  }
		  cout<<endl;
	  } 
	return 0;
}

C . Matrix Chain Multiplication

Description
Suppose you have to evaluate an expression like A?B?C?D?E where A,B,C,D and E are matrices.
Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose.
For example, let A be a 5010 matrix, B a 1020 matrix and C a 20*5 matrix.
There are two different strategies to compute A?B?C, namely (A?B)?C and A?(B?C).
The first one takes 15000 elementary multiplications, but the second one only 3500.
Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.

Input
Input consists of two parts: a list of matrices and a list of expressions.
The first line of the input file contains one integer n (1≤n≤26), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix.
The second part of the input file strictly adheres to the following syntax (given in EBNF):

SecondPart = Line { Line }
Line = Expression
Expression = Matrix | “(” Expression Expression “)”
Matrix = “A” | “B” | “C” | … | “X” | “Y” | “Z”

Output
For each expression found in the second part of the input file, print one line containing the word “error” if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.

Samples
Input 复制
9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))
Output
0
0
0
error
10000
error
3500
15000
40500
47500
15125
题目大意:
输入n个矩阵的维度和一些矩阵链乘表达式,输出乘法的次数。如果乘法无法进行,输 出error。假定A是mn矩阵,B是np矩阵,那么AB是mp矩阵,乘法次数为mnp。如果A的 列数不等于B的行数,则乘法无法进行。 例如,A是5010的,B是1020的,C是205的,则(A(BC))的乘法次数为10205(BC的 乘法次数)+ 50105((A(BC))的乘法次数)= 3500。
分析:
本题的关键是解析表达式。可以用一个栈来完成:遇到字母时 入栈,遇到右括号时出栈并计算,然后结果入栈。因为输入保证合法,括号无须入栈。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<char,int>ma;
map<char,int>mb;
int main(){
     int a[50],b[50],flag=0,aa,bb;
     int i,j,k;
     int n,sum=0,v=0,u=0;
     string s;
     char w;
     cin>>n;
     for(i=1;i<=n;i++){
     	cin>>w>>aa>>bb;
     	ma[w]=aa;
     	mb[w]=bb;
	 }
	 while(cin>>s){
	 	v=0;flag=1;sum=0;
	 	for(i=0;s[i];i++){
	 		if(s[i]=='(')
	 	continue;
	 	else if(s[i]==')'){
	 		if(a[v]==b[v-1]){
	 		sum+=a[v-1]*b[v]*a[v];
	 			b[v-1]=b[v];
	 			v--;
			}
			 else{
			 	flag=0;
			 	break;
			 }
		 }
		 else{
		 	v++;
		 	a[v]=ma[s[i]];
		 	b[v]=mb[s[i]];
		 }
		 }
		 if(flag)
		 cout<<sum<<endl;
		 else
		 cout<<"error"<<endl;
	 }
	return 0;
}

D . Broken Keyboard

Description
You’re typing a long text with a broken keyboard. Well it’s not so badly broken. The only problem with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed (internally).

You’re not aware of this issue, since you’re focusing on the text and did not even turn on the monitor! After you finished typing, you can see a text on the screen (if you turn on the monitor).

In Chinese, we can call it Beiju. Your task is to find the Beiju text.

Input
There are several test cases. Each test case is a single line containing at least one and at most 100,000 letters, underscores and two special characters ‘[’ and ‘]’. ‘[’ means the “Home” key is pressed internally, and ‘]’ means the “End” key is pressed internally. The input is terminated by end-of-file (EOF).

Output
For each case, print the Beiju text on the screen.

Samples
Input 复制
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University
Output
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University
题目大意:
你有一个破损的键盘。键盘上的所有键都可以正常工作,但有时Home键或者End键会自 动按下。你并不知道键盘存在这一问题,而是专心地打稿子,甚至连显示器都没打开。当你 打开显示器之后,展现在你面前的是一段悲剧的文本。你的任务是在打开显示器之前计算出 这段悲剧文本。 输入包含多组数据。每组数据占一行,包含不超过100000个字母、下划线、字符“[”或 者“]”。其中字符“[”表示Home键,“]”表示End键。输入结束标志为文件结束符(EOF)。输 入文件不超过5MB。对于每组数据,输出一行,即屏幕上的悲剧文本。
分析:
解决方案是采用链表(list)。每输入一个字符就把它存起来,设输入字符串是 s[1~n],则可以用next[i]表示在当前显示屏中s[i]右边的字符编号(即在s中的下标。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool lock;
deque<int>qr;//双端队列 
queue<int>qw;
vector<string> sta[1000];
int var[26],p[1000],t[1000];
int Q;
void run(int i)
{
    int rt=Q,v;
    string cur;
    while(rt>0){
        cur=sta[i][p[i]];
        if(cur[2]=='='){
            rt-=t[0];
            v=cur[4]-'0';
            if(cur.size()==6)v=v*10+cur[5]-'0';
            var[cur[0]-'a']=v;
        }
        else if(cur[2]=='i'){
            rt-=t[1];
            printf("%d: %d\n",i,var[cur[6]-'a']);
        }
        else if(cur[2]=='c'){
            rt-=t[2];
            if(lock){
                qw.push(i);
                return;
            }
            else lock=true;
        }
        else if(cur[2]=='l'){
            lock=false;
            rt-=t[3];
            if(!qw.empty()){
                v=qw.front();
                qw.pop();
                qr.push_front(v);//在头部添加一个元素v 
            }
        }
        else return;
        ++p[i];//在尾部添加一个元素i
    }
    qr.push_back(i);
}
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<5;i++)
            scanf("%d",&t[i]);
        scanf("%d",&Q);
        string s;
        for(int i=1;i<=n;i++){
            sta[i].clear();//初始化 
            while(getline(cin,s)){
                if(s=="")continue;
                sta[i].push_back(s);
                if(sta[i].back()=="end")break;//当vector最后一个元素是end,结束; 
            }
            qr.push_back(i);
        }
        memset(p,0,sizeof(p));
        memset(var,0,sizeof(var));
        while(!qr.empty()){//判断是否为空 
            int cur=qr.front();
            qr.pop_front();
            run(cur);//运行当前第cur个进程 
        }
        if(cas) printf("\n"); 
    }
    return 0;
}
 
  数据结构与算法 最新文章
二叉树lc题集
关于单链表及其常用操作的简单实现
二叉排序树(二叉搜索树)的算法实现
leetcode-python3-1759. 统计同构子字符串的
4.寻找两个正序数组的中位数
【leetcode】Nim 游戏c++
算法基础之贪心
LeetCode 2021-07-14
C++使用cuBLAS加速矩阵乘法运算
剑指offer - 调整数组顺序使奇数位于偶数前
上一篇文章      下一篇文章      查看所有文章
加:2021-07-25 16:16:15  更:2021-07-25 16:16:24 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年9日历 -2021/9/27 2:56:12-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码