第1次實驗——NPC問題(回溯算法、聚類分析)

（1）八皇後及N皇後問題

    八皇後問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。計算機發明後，有多種方法可以解決此問題。

    請程式設計實作八皇後問題，并把92種解的前三種解輸出到螢幕（8*8的二維矩陣，Q代表皇後，X代表空）。并把此問題的求解過程延伸到N皇後問題。

（2）學生聚類分析思考(PPT,PDF)

    為了實作因材施教的目标，現教務處計劃對學生進行摸底并分類，假如使用K均值聚類算法，并且認為學生大概可以分為四類，分别為“積極主動型”、“學霸型”、“遊戲人生型”、“迷茫無目标型”。現在你是該項目的負責人，（1）請設計一個較為完整的項目實施方案；（2）你是否認可對學生進行分類？（3）按照你給定的實施方案與需要測量的要素（如天學習時間），請嘗試按照自身情況對其進行回答，以及對自身的評價與定位和努力目标。

問題1的解答：

package IText;

public class NQueenQuestion {  
   
    private int[] column;  //同欄是否有皇後，1表示有  
    private int []rup;   //右上至左下是否有皇後  
    private int[] lup;  //左上至右下是否有皇後  
    private int[] queen;  //解答    
    private int num; 	//解答編号  
    
    public NQueenQuestion(){  
        column=new int[8+1];  
        rup=new int[2*8+1];  
        lup=new int[2*8+1];  
        for(int i=1;i<=8;i++){  
            column[i]=1;  
        }  
        for(int i=1;i<=2*8;i++){  
            rup[i]=lup[i]=1;  
            queen=new int[8+1];  
        }  
    }  
    public void backtrack(int i){  
        if(i>8){  
            showAnswer();  
        }  
        else{  
            for(int j=1;j<=8;j++){  
                if(column[j]==1&&rup[i+j]==1&&lup[i-j+8]==1){  
                    queen[i]=j;//設定為占用  
                    column[j]=rup[i+j]=lup[i-j+8]=0;  
                    backtrack(i+1);  
                    column[j]=rup[i+j]=lup[i-j+8]=1;  
                }  
            }  
        }  
    }  
  
    protected void showAnswer(){  //列印矩陣
        num++;  
        if(num<=3){
        System.out.println("\n解答"+num);  
        for(int y=1;y<=8;y++){  
            for(int x=1;x<=8;x++){  
                if(queen[y]==x){  
                    System.out.print(" Q ");  
                }  
                else{  
                    System.out.print(" X ");  
                }  
            }  
        System.out.println();  
        }  
        }
    }  
    public static void main(String[] args) {  
        NQueenQuestion queen=new NQueenQuestion();  
        queen.backtrack(1);  
    }  
}  
           

問題2解答：

（1）方案：

a、定義一些衡量變量：閱讀時間、閱讀量、學習時間、睡眠時間、玩遊戲時間、參加社團活動時間、是否有目标、參與比賽次數 

b、設定變量範圍屬于哪個範疇，判定在哪個類型

c、确定使用的算法，寫出思路

d、設計算法，對輸入資料進行比較分類，輸出結果

（2）不認可這種分類，應該多分幾類。

（3）我不屬于這“積極主動型”、“學霸型”、“遊戲人生型”、“迷茫無目标型”中的任何一種。