【经典算法学习-排序篇】顺序查找 - 作业讲解

目录

一、通观题目，找准考察方向 

二、题目讲评

1.有一门课不及格的学生

2.不定方程求解

3.子串变换

三、总结规律，探索发现

1.程序的多样性

2.思维的提升

---

一、通观题目，找准考察方向 

有一门课不及格的学生 - 洛谷

不定方程求解 - 洛谷

[NOIP2002 提高组] 字串变换 - 洛谷（较难）

 很明显，在读完题后，我们都有一种明显的感觉：这考察的不就是顺序查找吗？

顺序查找，也就是线性查找，指逐个查找。记住这句话后，我们来看是看题吧。

二、题目讲评

1.有一门课不及格的学生

这道题目可以堪称为顺序查找的模板题了。

这道题要求判断学生的不及格科目的总数，所以我们可以定义一个变量sum来求。如何判断是否不及格？判断的依据就是如果没有到60分就是不及格，这也正是我们的if语句了。

#include 
 
using namespace std;
 
int main()
{
    //定义语文、数学、英语三个变量并输入
    int chinese, math, english;
    cin >> chinese >> math >> english;
 
    //用来求有多少科目不及格
    int sum = 0;
 
    //判断有多少门科目不及格
    if (chinese < 60)
        sum++;
    if (math < 60)
        sum++;
    if (english < 60)
        sum++;
 
    //判断是否为1门科目不及格
    if (sum == 1)
        cout << "1" << endl;
    else
        cout << "0" << endl;
    return 0;
}

这道题不同于我们例题中的顺序查找，没有用到循环。所以，我们对于线性查找又多了一层认知：线性查找不必非要使用循环来解决，只要按照一条线的进行查找就可以算是线性查找。

2.不定方程求解

这道题其实就是一道让我们解方程的题。解方程的题还不简单？直接奉上我们的暴力枚举不就可以AC了吗？

那么，让我们思考一下如何枚举。首先，我们要枚举的一定是x和y的值，这点是毋庸置疑的。那么，枚举的边界条件是什么？一定是  和  了。有了这些思路，我们的代码也就能轻而易举的写出来了。

#include 
 
using namespace std;
 
int main()
{
    //按照题意输入
    int a, b, c;
    cin >> a >> b >> c;
 
    //用来记录一共有多少种情况
    int sum = 0;
 
    //开始暴力枚举
    for (int x = 0; x <= c; x++)
    {
        for (int y = 0; y <= c; y++)
        {
            if (a * x + b * y == c)
            {
                sum++;
            }
        }
    }
 
    //输出有多少种情况
    cout << sum << endl;
    return 0;
}

这道题让我们明白了什么？首先，就是要大胆的去写。不管会不会超时，一定要先尝试像这样搜索一下。其次，顺序查找是可以多重循环的。

这也变相说明了暴力枚举的本质就是线性查找。

3.子串变换

这道题相较于前两道题而言，那么就相当于是世界难题了。这是一道NOIP提高组的试题，足以见得它的难度。这道题是对于线性查找的一个扩展，使用了BFS来解决问题。

这道题如果对于新手的话，可能会不太友好，所以这道题就不会讲解了。如何想要掌握这道题的，那么可以阅读以下代码，摸索出答案。

#include 
#include 
#include 
#include 
#include 
#include 
 
using namespace std;
 
map int> zt;
queue  que;
string st, ed, x[1001], y[1001];
int tot = 1, ans;
 
bool eq(string s, int be, int to)
{
    string &tmp = x[to];
    if (s.size() - be + 1 < x[to].size())
        return false;
    for (int i = be; i - be < tmp.size(); i++)
    {
        if (s[i] != tmp[i - be])
            return false;
    }
    return true;
}
string change(string s, int be, int to)
{
    if (eq(s, be, to))
    {
        string neww = s.substr(0, be) + y[to] + s.substr(x[to].size() + be, s.size());
        return neww;
    }
    else
        return "";
}
int bfs()
{
    que.push(st);
    zt[st] = 0;
    while (!que.empty())
    {
        string now = que.front();
        que.pop();
        for (int i = 0; i < now.size(); i++)
        {
            for (int j = 1; j <= tot; j++)
            {
                string neww = change(now, i, j);
                if (neww == "")
                    continue;
                if (zt.count(neww))
                    continue;
                if (zt[now] + 1 > 10)
                    continue;
                que.push(neww), zt[neww] = zt[now] + 1;
                if (neww == ed)
                    return zt[now] + 1;
            }
        }
    }
    return 0;
}
int main()
{
    cin >> st >> ed;
    while (cin >> x[tot] >> y[tot])
    {
        tot++;
    }
    tot--;
    ans = bfs();
    if (!ans)
        printf("NO ANSWER!");
    else
        printf("%d", ans);
    return 0;
}

咋样，我没骗你吧！这道题是不是难了很多！

三、总结规律，探索发现

从上述的三道题中，我们发现了什么规律？

1.程序的多样性

使用一种思想来做题，程序可能会迥然不同 。在顺序查找中，可能程序中没有循环，也可能一下子出现五个循环嵌套。这也是为什么我们顺序查找的题目没有模板的原因。

2.思维的提升

通过这三道题，我们的思维提升了，我们又学会了换一种方法思考问题。思考问题的方式多种多样，如果一道题目不会的话，不妨换一种方式来思考，你或许会获得新的收获。