第五章练习题

第五章练习题

实践出真知，在实践中不断进步。

The Blocks Problem , Uva 101

第一次错误，指令处理出现问题。

/**
 * @author Miubai
 * The Blocks Problem , Uva 101
 * 第一次敲
 */
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>

using namespace std;

const int  MAX = 30;
int n;
vector<int> pile[MAX];

//找出块a所在的位置,a代表要查找的数，p代表堆，h代表块a所在的高度
void find_block(int a,int &p,int &h){
    for(p = 0; p < n;p++){
        for(h = 0;h < pile[p].size();h++)
            if(pile[p][h] == a)//找到a则结束查找，因以引用的形式，所以p,h值已被修改。
                return;
    }
}

//归位操作,将p堆上a块以上的块全部归位，h代表a块在p上的位置
void clean_block(int p, int h){
    for(int i = h+1; i < pile[p].size(); i++){
        int b = pile[p][i];
        pile[b].push_back(b); //将b块归位
    }
    pile[p].resize(h+1); //将该堆高度调整到与a等高
}

//插入操做，将p堆a以上的所有木块放到p2堆上
void pill_onto(int p,int p2,int h){
    for(int i = h; i < pile[p].size(); i++){
        int b = pile[p][i];
        pile[p2].push_back(b);//将p堆a及其以上一堆插入到p2堆上面
        
    }
    pile[p].resize(h);//将p堆高度降低到与a等高
}

//输出最后的结果

void print_pile(){
    for(int i = 0; i < n; i++){
        printf("%d:",i);
        for(int j = 0; j < pile[i].size();j++){
            printf(" %d",pile[i][j]);
        }
        printf("
");
    }
}

int main(){
    int a,b,p,h;
    cin >> n;
    //初始化各堆
    for(int i = 0; i < n ; i++){
        pile[i].push_back(i);
    }

    string s1,s2;
    
    //第一次出现问题点：在于while作用域，功能模糊
    cin >> s1 >> a >> s2 >> b;//自动匹配，
    while(s1 != "quit"){

        if(s2 == "onto"){
            find_block(b,p,h);//找到b的具体位置
           clean_block(p,h);//将b上面的块全部归位
        }

        //找到a的位置，并将a上方的块全部归位
        if(s1 == "move"){
            find_block(a,p,h);
            clean_block(p,h);
        }
        pill_onto(p,b,h);

        cin >> s1 >> a >> s2 >> b;
    }
    print_pile();
    return 0;

}

第二次错误

/**
 * @author Miubai
 * The Blocks Problem , Uva 101
 *
 */
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>

using namespace std;

const int  MAX = 30;
int n;
vector<int> pile[MAX];

//找出块a所在的位置,a代表要查找的数，p代表堆，h代表块a所在的高度
void find_block(int a,int &p,int &h){
    for(p = 0; p < n;p++){
        for(h = 0;h < pile[p].size();h++)
            if(pile[p][h] == a)//找到a则结束查找，因以引用的形式，所以p,h值已被修改。
                return;
    }
}

//归位操作,将p堆上a块以上的块全部归位，h代表a块在p上的位置
void clean_block(int p, int h){
    for(int i = h+1; i < pile[p].size(); i++){
        int b = pile[p][i];
        pile[b].push_back(b); //将b块归位
    }
    pile[p].resize(h+1); //将该堆高度调整到与a等高
}

//插入操做，将p堆a以上的所有木块放到p2堆上
void pill_onto(int p,int p2,int h){
    for(int i = h; i < pile[p].size(); i++){
        int b = pile[p][i];
        pile[p2].push_back(b);//将p堆a及其以上一堆插入到p2堆上面
    }
    pile[p].resize(h);//将p堆高度降低到与a等高
}

//输出最后的结果

void print_pile(){
    for(int i = 0; i < n; i++){
        printf("%d:",i);
        for(int j = 0; j < pile[i].size();j++){
            printf(" %d",pile[i][j]);
        }
        printf("
");
    }
}

int main(){
    int a,b;
    cin >> n;
    //初始化各堆
    for(int i = 0; i < n ; i++){
        pile[i].push_back(i);
    }

    string s1,s2;

    while(cin >> s1 >> a >> s2 >> b){
        int pa,pb,ha,hb;
        find_block(a,pa,ha);//找到a所在堆的具体位置
        find_block(b,pb,hb);//找到b所在的具体位置

        //如果在同一堆则跳过
        if(pa == pb)
            continue;
        if(s2 == "onto")
            clean_block(pb,hb);
        if(s1 == "move")
            clean_block(pa,ha);
        pill_onto(pa,pb,hb); //第二次出错地方，这里应该是ha，将以上的块放到b堆上

        print_pile();
    }

    return 0;

}

第三次样例过了

/**
 * @author Miubai
 * The Blocks Problem , Uva 101
 *
 */
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>

using namespace std;

const int  MAX = 30;
int n;
vector<int> pile[MAX];

//找出块a所在的位置,a代表要查找的数，p代表堆，h代表块a所在的高度
void find_block(int a,int &p,int &h){
    for(p = 0; p < n;p++){
        for(h = 0;h < pile[p].size();h++)
            if(pile[p][h] == a)//找到a则结束查找，因以引用的形式，所以p,h值已被修改。
                return;
    }
}

//归位操作,将p堆上a块以上的块全部归位，h代表a块在p上的位置
void clean_block(int p, int h){
    for(int i = h+1; i < pile[p].size(); i++){
        int b = pile[p][i];
        pile[b].push_back(b); //将b块归位
    }
    pile[p].resize(h+1); //将该堆高度调整到与a等高
}

//插入操做，将p堆a以上的所有木块放到p2堆上
void pill_onto(int p,int p2,int h){
    for(int i = h; i < pile[p].size(); i++){
        int b = pile[p][i];
        pile[p2].push_back(b);//将p堆a及其以上一堆插入到p2堆上面
    }
    pile[p].resize(h);//将p堆高度降低到与a等高
}

//输出最后的结果

void print_pile(){
    for(int i = 0; i < n; i++){
        printf("%d:",i);
        for(int j = 0; j < pile[i].size();j++){
            printf(" %d",pile[i][j]);
        }
        printf("
");
    }
}

int main(){
    int a,b;
    cin >> n;
    //初始化各堆
    for(int i = 0; i < n ; i++){
        pile[i].push_back(i);
    }

    string s1,s2;

    while(cin >> s1 >> a >> s2 >> b){
        int pa,pb,ha,hb;
        find_block(a,pa,ha);//找到a所在堆的具体位置
        find_block(b,pb,hb);//找到b所在的具体位置

        //如果在同一堆则跳过
        if(pa == pb)
            continue;
        if(s2 == "onto")
            clean_block(pb,hb);
        if(s1 == "move")
            clean_block(pa,ha);
        pill_onto(pa,pb,ha);


    }
    print_pile();
    return 0;

}

本题总结：对于本题，

1. 主要首先是练习对于vector的运用，pile[p].resize()可用于改变数组的长度；pile[p].size()可用于获取数组的长度；pile[b].push_back(a) 可将数a插入到二维数组pile[b]的尾部，编写相应的函数可用来实现题目“摞在上面”的操做。

2. 本题是在看完书上代码后进行的编写。不得不惊叹作者编写代码的精简老练。结合文本内容，最让我感到惊异有以下几点

   1. 对于文本的分析，找到各个指令节点之间的共同特点，从而简化编程，使得代码是很精简。同时也启示我，做题之前应该先分析题目，透彻的分析题目。以后的编写中，我将吸取教训。
   2. while(cin >> s1 >> a >> s2 >> b)这一块的代码，同样也让我收获良多，第一次我考虑的是利用if语句判断是否终止。但作者的程序打破了我传统认知，
   3. 就这一道编程题让我深刻的认识到了我对于一些基础的东西掌握的不牢固，不够精细，在以后的学习中应当注意这种粗略式的学习。

---

本周只做了两个练习题，但就这一道题而言，可学习的地方太多，当然也有自己太贪玩的原因，我也会继续努力克服的。