1-4 消息传递接口【Csp认证真题】

老师给了 T 份 MPI 的样例代码，每份代码都实现了 n 个进程通信。这些进程标号从 0 到 n − 1，每个进程会顺序执行自己的收发指令，如：“S x”，“R x”。“S x”表示向x 号进程发送数据，“R x”表示从 x 号进程接收数据。每一对收发命令必须匹配执行才能生效，否则会“死锁”。 举个例子，x 号进程先执行发送命令“S y”，y 号进程必. 须. 执行接送命令“R x”，这一对命令才执行成功。否则 x 号进程会一直等待 y 号进程执行对应的接收命令。反之，若 y 号进程先执行接收命令“R x”，则会一直等待 x 号进程执行发送命令“S y”，若 x号进程一直未执行发送命令“S y”，则 y 号进程会一直等待 x 号进程执行对应的发送命令。上述这样发送接收命令不匹配的情况都会造成整个程序出现“死锁”。另外，x 号进程不会执行“S x”或“R x”，即不会从自己的进程收发消息。.现在老师请你判断每份样例代码是否会出现“死锁”的情况。每个进程的指令最少有 1 条，最多有 8 条，这些指令按顺序执行，即第一条执行完毕，才能执行第二条，依次到最后一条。

输入格式:

从标准输入读入数据。 输入第一行两个正整数 T, n，表示有 T 份样例代码，实现了 n 个进程通信。 接下来有 T × n 行，每行有若干个（1 − 8 个）字符串，相邻之间有一个空格隔开，表示相应进程的收发指令。不存在非法指令。对于第 2 + i, 0 ≤ i ≤ (T × n − 1) 行，表示第 i ÷ n（商）份代码的 i KQ/ n（余数）号进程的收发指令。 （比如，“S1”表示向 1 号进程发送消息，“R1”表示从 1 号进程接收消息。细节请参考样例。）

输出格式:

输出到标准输出。 输出共 T 行，每行一个数字，表示对应样例代码是否出现“死锁”的情况。1 表示死锁，0 表示不死锁。

输入样例:

3 2
R1 S1
S0 R0
R1 S1
R0 S0
R1 R1 R1 R1 S1 S1 S1 S1
S0 S0 S0 S0 R0 R0 R0 R0

输出样例:

0
1
0

这里对于自己找来的答案做思路分析，对其中所用到的技巧做总结。

          

                   {

 大致思路：

题目给T份MPI数据，而每一份都有n个进程，编号为0-（n-1），每个进程给指令。在接收好数据后。idx【i】表示第i个进程执行到第几个指令。要进行指令间的匹配，第i个进程的指令（R/S）对象为x，则寻找x号进程当前的是否为（S/R），对应匹配的话，对应索引后移--idx[i]++ idx[x]++  例如：  

而从0-n-1进程都执行为一次循环，但很有可能一次下来所有进程都可以完成，可能只是完成个别进程的匹配（尤其当数据进程多的话），所有需要不断循环执行这样从0-n-1进程的匹配判断。而这样循环结果有两种，1-进程完成，2-死锁，而死锁的表现就是在某一次的循环中，没有进程的指令被执行，idx[i]都没有+1；这用bool flag记录，每一次匹配循环进行时，flag=false//认为死锁，当在后续的匹配判断中，发现有进程匹配成功时，就flag=true；说明存在有效匹配。而一次0-n-1的匹配循环后，都进行判断flag==false;是则说明死锁了，则直接输出1，并break，进行下一份MPI数据进程的判断。                                                                                                                   

而对于不死锁，通过bool judge来记录，while写条件是true，这意味是死循环，只有通过break出循环。而死锁解决，但当顺利匹配完成后，并没有东西可以标志顺利结束，所以通过judge来标志。每次循环前，judge=true//认为匹配完成，当当前进程i还有指令时，judge=false；说明还有进程指令，但也可能是最后一个，对此将会在下次匹配循环中时，没有进程需要匹配而一直保持true，进行判断后出循环。

 细节                                                                                                              

 1.对于stringstream的使用                                                                                                         

通过stringstream将接收了一行进程指令数据的line中的诸多指令分开储存。

2.vector> precess（n）;                                                                                   

实现二维动态数组，同时precess(n)，直接开创n行，是我没用过的方法。

3.获得字符串字串  substr(起始位置=0，长度=起始位置之后所有)   

4.string（数字）转换成int类型： stoi(string to int)--stoi(string,起始位置，进制=10)   后2参数不写，默认将string转化为int类型。 

后续在网上查资料发现很多关于string转换的方法，借鉴一下。

    #include
    #include
    using namespace std;
    int main(){
    stringstream stream;  //声明一个之后所需的流对象。
    //第一块知识,string转换成int。
   cout<<"string转int"<>n;
  	cout <<"stringstream string转int:    "<< n << endl;  
  	
  	stream.clear（）；
    //同一个流对象两次使用时应该用clear函数清除流标志，
    否则下一块就不起作用，这应该是一个程序员的基本素养。
  	
  	//第二块知识，int转为string
  	cout<<"int转string"<>str1;
  	cout << "stringstream int转string:    " << str1 << endl;
}

stringstream stream;
string str="asfdd"
char ch[];
stream<>ch;
cout <<"stringstream string转char:    "<< ch<< endl;  

通过 stringstream stream可以实现string，int以及string，char【】间的互换。                     

值得注意的是：之前自己尝试过通过循环将string s-> char ch[](s[i]=ch[i])。但这样对于ch的输出不能直接通过cout>>ch;因为没有''作为结束符。（应该是这样吧、、、）