PAT乙级.1027. 打印沙漏(20)

1027. 打印沙漏(20)

---

题目：

本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个“*”，要求按下列格式打印

所谓“沙漏形状”，是指每行输出奇数个符号；各行符号中心对齐；相邻两行符号数差2；符号数先从大到小顺序递减到1，再从小到大顺序递增；首尾符号数相等。

给定任意N个符号，不一定能正好组成一个沙漏。要求打印出的沙漏能用掉尽可能多的符号。

输入格式：

输入在一行给出1个正整数N（<=1000）和一个符号，中间以空格分隔。

输出格式：

首先打印出由给定符号组成的最大的沙漏形状，最后在一行中输出剩下没用掉的符号数。

输入样例：

19 *

输出样例：

2

PAT链接

---

思路：

1.首先要得到不同数字所能对应的底边图案数，方法是1+3+5+……不断累加，直到数字比n大跳出 2.依次打印上三角和下三角 3.每次打印字符时，cnt++

//得到底边的符号数 int getCol(int n) { int upper = 0; int sum = 0; int i = 1; for (i; i<=n; i++) { upper += (i * 2 - 1); sum = 2 * upper - 1; if (sum > n) break; } return 2*i-3; } //测试点2为n=1的情况

2.根据底边图案数分别打印上半部分和下半部分

---

代码：

version1.0

/** * @tag PAT_B_1027 * @authors R11happy (xushuai100@126.com) * @date 2016-8-14 5:26-6:10 * @version 1.0 * @Language C++ * @Ranking 290/2389 * @function null */ #include <cstdio> #include <cstdlib> #include <cstring> /* //得到底边的符号数 int getCol(int n) { int upper = 0; int sum = 0; int i; for (i = 0; i<n; i++) { upper += (i * 2 + 1); sum = 2 * upper - 1; if (sum > n) return 2 * i - 1; if (sum == n) return 2*i + 1; //考虑测试点2：n=1的情况 } return -1; }*/ //得到底边的符号数 int getCol(int n) { int upper = 0; int sum = 0; int i = 1; for (i; i<=n; i++) { upper += (i * 2 - 1); sum = 2 * upper - 1; if (sum > n) break; } return 2*i-3; } //测试点2为n=1的情况 int main(int argc, char const *argv[]) { int i, N; char ch; int col; int cnt = 0; scanf("%d %c", &N, &ch); col = getCol(N); if (N) { //打印上半部分(包括中间的) for (i = col; i >= 1; i -= 2) { for (int k = 0; k<(col - i) / 2; k++) { printf(" "); } for (int j = 0; j<i; j++) { printf("%c", ch); cnt++; } printf("\n"); } //打印下半部分 for (i += 4; i <= col; i += 2) { for (int k = 0; k<(col - i) / 2; k++) { printf(" "); } for (int j = 0; j<i; j++) { printf("%c", ch); cnt++; } printf("\n"); } } //打印剩余符号 printf("%d\n", N - cnt); return 0; }

version2.0（参考晴神代码）

/** * @tag PAT_B_1027 * @authors R11happy (xushuai100@126.com) * @date 2016-8-14 5:26-6:10 * @version 1.0 * @Language C++ * @Ranking 290/2389 * @function null */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> int main(int argc, char const *argv[]) { int n; char ch; scanf("%d %c", &n, &ch); int bottom = floor(sqrt(2*(n+1))) - 1; //得到底边的字符数 if(bottom % 2 == 0) bottom--; //偶数修正，得到奇数 int used = (bottom+1)*(bottom+1)/2 - 1; //打印上半部分(包括中间的) for (int i = bottom; i >= 1; i -= 2) { for (int k = 0; k<(bottom - i) / 2; k++) { printf(" "); } for (int j = 0; j<i; j++) { printf("%c", ch); } printf("\n"); } //打印下半部分 for (int i = 3; i <= bottom; i += 2) { for (int k = 0; k<(bottom - i) / 2; k++) { printf(" "); } for (int j = 0; j<i; j++) { printf("%c", ch); } printf("\n"); } printf("%d\n", n - used ); return 0; }

---

收获：

1.用数学推导解决问题：

int bottom = floor(sqrt(2*(n+1))) - 1; //得到底边的字符数 if(bottom % 2 == 0) bottom--; //偶数修正，得到奇数 int used = (bottom+1)*(bottom+1)/2 - 1; //总输出的非空格字符数

2.等差数列求和公式 3.先求底边字符数，进而求每行空格字符数