關於”丟失的牛”這個題的教學反思

• 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的全排列。

通過這個案例，有以下幾點感懷：
首先，學生的創造性是無窮的，永遠要去鼓勵學生積極探索。
我們的學生都是一個個鮮活的個體，他們天生沒有束縛，有着無窮的探索欲。在這一點上，成年人由於接受的知識較多，也就形成了一些條條框框。老師不能以自己的年紀、身份、地位等等因素去打壓學生的探索欲，而是應該去鼓勵他們積極探索,當然這種探索應該是以理性思考為基礎，進行縝密的分析，層層推進。

其次,對於每節課，應該給學生一定的自由。
對於教學來說，最簡單最無腦的教法就是老師從頭講到尾，不給學生任何思考的機會。這樣的課看似老師很負責任，非常賣力的在講。但事實上學生接收了多少呢，就算有一定的接收，這種被動的接收，對他的心智的啟發又有多大呢？所以對於教學來說，之所以可稱之為一門藝術，很大的原因就在於，當面臨的學生個體不同，課堂的設計是完全不同的，教學情景如何設計、如何引出問題，引導學生進行分析並進行析疑等等都是非常有講究的。