1021.從前有座山，1021從前有座山

1021.從前有座山，1021從前有座山

Description

從前有座山，山的俯視圖是一個n×n的矩形，(1,1)位置海拔最低為1，然後海拔沿環形依次升高。

給定n的值，輸出這座山的海拔高度圖。

Input Format

輸入僅有一行，為一個正整數n。

Output Format

輸出為這座山的海拔高度圖。

Sample Input

4

Sample Output

     1     2     3     4
    12    13    14     5
    11    16    15     6
    10     9     8     7

題目來源是上海交大acm題庫，地址http://acm.sjtu.edu.cn/OnlineJudge/problem/1021

google了一下，網上現有的做法似乎都沒有我的好，所以把我的做法貼出來^_^。

基本的思路是開辟一個n * n的矩陣，填上表示高度的數字，再輸出這個矩陣。

問題在於如何填上正確的數字。

以 n = 5 為例子，觀察最外圈的數字，將其分為4個部分，如圖

顯然，每個部分都可以用一個循環來填充數字。不失一般的，填充一整圈的偽代碼為：

for i = 1 .. N-1
    map[1][i] = i
    map[i][N] = N - 1 + i
    map[N][N - i] = 2 * (N - 1) + i
    map[N - i][1]= 3 * (N - 1) + i

對於非最外圈而言，記錄下起始填充位置的偏移量（包括x軸偏移，y軸偏移，填充數字偏移）即可。

最後，對於奇數邊長矩陣，需要在矩陣的中心點填上高度的最大值，也就是邊長的平方。

#include <iostream>
#include <iomanip>
#include <string.h>

using namespace std;

int main(){

	int i, j;
	int n;
	int *map;

	cin >> n;
	map = new int[n * n];
	memset(map, 0, sizeof(map));

	int h_offset = 1;
	int x_offset = 0;
	int y_offset = 0;

	for (int len = n - 1; len > 0; len-= 2){	//a loop fills a circle, from outer to inner

		for (i = 0; i < len; ++i){
			
			map[x_offset * n + (y_offset + i)] = h_offset + i;
			map[(x_offset + i) * n +  (n - 1 - y_offset)] = h_offset + len + i;
			map[(n - 1 - x_offset) * n + (n - 1 - y_offset - i)] = h_offset + 2 * len + i;
			map[(n - 1 - x_offset - i) * n + (y_offset)] = h_offset + 3 * len + i;

		}

		h_offset += 4 * len;
		x_offset ++;
		y_offset ++;

	}

	if(n % 2 == 1)
		map[n * n / 2] = n * n;

	for (i = 0; i < n; ++i){
		for (j = 0; j < n; ++j){
			cout << setw(6) << map[i * n + j];
		}
		cout << endl;
	}

	delete []map;
	return 0;
}

小學六年級數學海澱小狀元猴子分桃

1/3+1/5+1/6=7/10
21/7*10=30（個）
30*1/3=10；30*1/5=6；30*1/6=5（個）
老大老二老三分別得10,6,5個。
（如果不理解可算為：1/3：1/5：1/6=10:6:5，再得答案（比例關系））