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

某天上课讲到这样一个题:
丢失的牛
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的全排列。

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

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

巴特西

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

最新文章

热门文章