关于”丢失的牛”这个题的教学反思

  • 2021 年 11 月 29 日
  • 笔记

某天上课讲到这样一个题:
丢失的牛
1~n,乱序排列,告诉从第二个位置到最后一个位置, 每个位置的前面的数字中比它小的数的个数,求每个位置的数字是多少
N<=8000

Format
Input
第一行给出数字N 接下来N-1,每行给出一个数字

Output
一行输出一个数字。共输出N行。

样例输入
5
1
2
1
0

样例输出
2
4
5
3
1

拿到这个题,我先尝试正面求解,发现有些困难,拿样例来说。
对于输入的第1个数字1,说明求解出来的数列中第2个位置,在它的前面有1个数字比它小。
则对于数对(1,2),(1,3),(1,4),(1,5),(2,3),(2,4)….均是满足条件的,仔细算下的c(n,2)个数对满足条件。
如果以这个为最初状态来进行后面的推演是非常困难的。
正难则反,于是我们倒过来做。
设输入数列为Ai,结果数列为ansi,ansi的数值其实就是在全排列1–N之间找第ai+1小的数字。
每求出一个ansi来后,要将其从全排列1–N之中删除掉。以样例来说
对于输入的倒数第1个数字0,代表要在全排列1–N之间找第1小的数字,明显为1。我们记下这个值并将其从全排列中删除掉。
对于输入的倒数第2个数字1,代表要在全排列2–N之间找第2小的数字,明显为3。我们记下这个值并将其从全排列中删除掉。
对于输入的倒数第3个数字2,代表在数列(2,4,5)中第3小的数字,明显为5.
对于输入的倒数第4个数字1,代表在数列(2,4)中第2小的数字,明显为4.
最后还剩下数字2,易知其为结果数列的第1个数字。于是最终找出来的数列为(2,4,5,3,1),而这个题就本质而言就是一个动态求第K数字的问题,而且数据范围也不大,可以暴力来进行实现。
代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[8010],f[8010],ans[8010];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=n;i>=1;i--)
    {
        int sum=0;
        for(int j=1;j<=n;j++)
        {
            if(!f[j])sum++;
            if(sum==a[i]+1)
            {
                ans[i]=j;
                f[j]=1;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

  

接下来,我就安排学生们来自行书写程序了,但有个学生一直在纸上写写画画,我问他:有什么疑问吗?他说:老师,我觉得这个题正过来做,也是可以的。我有些不耐烦的说:这个题,我研究得很深入了,正着做是不太可能的。但学生仍倔强的说:老师,你再让我试试吧。过了大概15分钟,那个学生说:老师,这个题,我正着做,做过去了,我是这样做的。
我们对于结果数列,不妨设第1个位置为1,然后于输入的1来说,其代表有一个数字比它小,所以可设之为2
于是结果数列为1 2
然后于输入的2来说,其代表有2个数字比它小,所以可设之为3
于是结果数列为1 2 3
然后于输入的1来说,其代表有1个数字比它小,所以可设之为2
于是对前面的1 2 3进行调整,将所有>=2的数字加1
于是结果数列变成1 3 4 2
然后于输入的0来说,其代表有0个数字比它小,所以可设之为1
于是对前面的1 3 4 2进行调整,将所有>=1的数字加1
于是结果数列变成2 4 5 3 1。
代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,a[8000],b[8000],t;
int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>a[i];
    }
    b[1]=1;
    for(int i=2;i<=n;i++)
    {
        b[i]=a[i]+1;
        //对于第i个位置来说,在它前面有a[i]个数字比它小,于是可以不考虑其它因素
        //这个位置上应该是a[i]+1.
        for(int j=1;j<=i-1;j++)
        //对于在其左边的数字,如果其权值大于b[i],则对其进行调整
            if(b[j]>=b[i])
                b[j]++;
    }
    for(int i=1;i<=n;i++){
        cout<<b[i]<<endl;
    }
    return 0;
}

  

仔细思考下这个学生的求解过程 ,他比我最开始那个想法更进一步的,在于以下两点
1:对于数列的第1个位置上的数来说,它的左边是没有别的数字的,自然也就没有数字比它小。
2:本题是求某个N的全排列,也就是说当N=1时,这个全排列是唯一的,就是数列1。如果N=2,则样例输入就只需要给出1个数字,我们求解出来的,自然也就是一个2的全排列。
于是他的整个求解就有一个扎实的“初状态”,即可以设结果数列的第1个位置就是数字1.
然后根据数据的输入,先去找一个第ai+1小的数字,再对数列进行适当的调整,保证其始终是一个满足题意的N的全排列。

通过这个案例,有以下几点感怀:
首先,学生的创造性是无穷的,永远要去鼓励学生积极探索。
我们的学生都是一个个鲜活的个体,他们天生没有束缚,有着无穷的探索欲。在这一点上,成年人由于接受的知识较多,也就形成了一些条条框框。老师不能以自己的年纪、身份、地位等等因素去打压学生的探索欲,而是应该去鼓励他们积极探索,当然这种探索应该是以理性思考为基础,进行缜密的分析,层层推进。

其次,对于每节课,应该给学生一定的自由。
对于教学来说,最简单最无脑的教法就是老师从头讲到尾,不给学生任何思考的机会。这样的课看似老师很负责任,非常卖力的在讲。但事实上学生接收了多少呢,就算有一定的接收,这种被动的接收,对他的心智的启发又有多大呢?所以对于教学来说,之所以可称之为一门艺术,很大的原因就在于,当面临的学生个体不同,课堂的设计是完全不同的,教学情景如何设计、如何引出问题,引导学生进行分析并进行析疑等等都是非常有讲究的。