奧賽精解(練習(xí)題)

1、一、棋盤類題目1.馬攔過河卒中學(xué)高級本（紫皮）中學(xué)高級本（紫皮）P2P2、《奧賽精解練習(xí)題奧賽精解練習(xí)題》P266》P266頁棋盤上A（00）點有一個過河卒，需要走到目標(biāo)B（n，m）點。卒街的規(guī)則：可以向下、或者向右。同時在棋盤上C點有一個對方的馬，該馬所在點及所有跳躍一步可達點稱為馬的控制點。因此稱之為“馬攔過河卒”。輸入：一行四個數(shù)據(jù)，表示B點和C點馬的坐標(biāo)，n、m均為不超過15的整數(shù)。輸出：一個數(shù)據(jù)，表示所有的路徑數(shù)?！痉治觥勘闅v

2、每個點的路徑，A點所在行及列上點的路徑均為1，馬的9個控制點的路徑均為0，其余每個點的路徑為a[xy]:=a[xy1]a[x1y]。2.設(shè)有一個nm方格的棋盤（1≤mn≤100）。求出該棋盤中包含多少個正方形、多少個長方形（不包括正方形）。(Noip971)(Noip971)例如：當(dāng)n=2，m=3時，正方形的個數(shù)有8個；即邊長為1的正方形有6個；邊長為2的正方形有2個。長方形的個數(shù)有10個；即21的長方形有4個；12的長方形有3個；31

3、的長方形有2個；32的長方形有1個。程序要求：輸入：n和m輸出：正方形的個數(shù)與長方形的個數(shù)如上例：輸入：23輸出：8，10【分析】二、貪心算法二、貪心算法中學(xué)高級本（紫皮）中學(xué)高級本（紫皮）P22P221.排隊接水有n個人在一個水龍頭前排隊接水，假如每個人接水的時間為Ti，請編程找出這n個人排隊的一種順序，使得n個人的平均等待時間最小。輸入：輸入文件共2行，第一行為n；第二行為每個人的接水等待時間輸出：文件為2行，第一行為排隊順序，第二

4、行為平均等待時間。如果一個n位正整數(shù)等于其各位數(shù)字的n次方之和則稱該數(shù)為阿姆斯特朗數(shù)。例如1^35^33^3=153當(dāng)n＝3時，又稱水仙花數(shù)，特指一種三位數(shù)，其各個數(shù)之立方和等于該數(shù)。水仙花數(shù)共有4個，分別為：153、370、371、407。題目：史密斯數(shù)。題目：史密斯數(shù)。輸出4—9999中的所有史密斯數(shù)。史密斯數(shù)是可以分解的整數(shù)，且所有數(shù)位上的數(shù)字和等于其全部素數(shù)因子的數(shù)字總和。例如：9975=3557199975=30355719=