3.12打卡

金字塔

考虑在下面被显示的数字金字塔（第n行有n列）。写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每前进一步可以走到它的正下方或者右下方（往下一行、往右一列）的位置。

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30

个人总结：

1、因为每一步只能走到正下方或右下方，最大路径需要全局最优动态规划；

2、从最后一行往上加，将本行的数字替换为从改点往下可以经过的最大数字和；

#include<stdio.h> #include<stdlib.h> int main(){ int n; scanf("%d",&n); int **t=(int**)malloc(n*sizeof(int*)); for(int i=0;i<n;i++){ t[i]=(int*)malloc(n*sizeof(int)); for(int j=0;j<=i;j++){ scanf("%d",&t[i][j]); } } for(int i = n-2; i >= 0; i--) { for(int j = 0; j <= i; j++) { int left = t[i+1][j]; int right = t[i+1][j+1]; t[i][j] += (left > right ? left : right); } } printf("%d\n", t[0][0]); free(t); return 0; }

魔方阵

题目：

在一次数学课上，明明的老师讲了一种非常有趣的方阵，称之为三阶魔方阵。

它是一个三行三列，由1、2、3、……8、9，九个数字共同构成，且它每行、每列、两对角线之和均相等，于是一个合法的三阶魔方阵就形成了以下的方阵：

8 1 6

3 5 7

4 9 2

富有钻研精神的明明回家后，马上就对三阶魔方阵进行研究。

他总结出了5条n阶魔方阵的规律(n为奇数)，如下：

（1） 将“1”放在第一行（最上面一行）中间一列；

（2） 从“2”开始直到n*n为止各数依次按下列规则存放：每一个数存放的行的行数比前一个数的行数减1，每一个数存放的列的列数比前一个数的列数加1，即前一个数的右上方。

（3） 如果上一数的行数为1，则下一个数的行数为n（指最下面一行）；

（4） 当上一个数的列数为n时，下一个数的列数应为1（指最左一列）；

（5） 如果按上面规则确定的位置上已有数，或上一个数是第一行第n列时，则把下一个数放在上一个数的下面。

有了以上的方法，明明就可以轻易地构造出任意的n阶魔方阵。

个人总结：

1、看着情况很多，主要根据1.2.5三点就可以，3.4可以通过对n取余转化为情况2；

2、因为要判断这个位置有没有数字，最好初始化t[i][j]=0，方便条件判断；

3、起始i=1，放在循环外进行初始化；2~n*n放在循环里。

#include<stdio.h> #include<stdlib.h> int main(){ int n; while(scanf("%d",&n)==1){ //int t[20][20]={0}; int **t=(int**)malloc(n*sizeof(int*)); for(int i=0;i<n;i++){ t[i]=(int*)malloc(n*sizeof(int)); for(int j=0;j<n;j++) { t[i][j]=0; } } int x,y; x=0; y=n/2; t[x][y]=1; for(int i=2;i<=n*n;i++){ int x1=(x-1+n)%n; int y1=(y+1)%n; if(t[x1][y1]!=0){ x1=(x+1)%n; y1=y; } t[x1][y1]=i; x=x1; y=y1; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(j!=0) printf(" "); printf("%d",t[i][j]); } printf("\n"); } printf("\n"); for(int i=0;i<n;i++){ free(t[i]); } free(t); } return 0; }

单词