C++/Python 实现沙漏形状符号打印：算法解析与代码示例

题目描述

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

*****
 ***
  *
 ***
*****

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

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

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

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

输入样例:

19 *

输出样例:

*****
 ***
  *
 ***
*****
2

算法

(模拟)

时间复杂度

C++ 代码

// C++ 代码示例
#include <iostream>
using namespace std;

int main() {
    int n, cnt = 0;
    char ch;
    cin >> n >> ch;
    // 计算沙漏最大高度
    int height = 1;
    while (height * (height + 1) <= n) {
        height += 2;
    }
    height -= 2;
    // 打印沙漏上半部分
    for (int i = height; i >= 1; i -= 2) {
        for (int j = 0; j < (height - i) / 2; j++) {
            cout << ' ';  // 打印空格
        }
        for (int j = 0; j < i; j++) {
            cout << ch;  // 打印符号
        }
        cout << endl;
        cnt += i;
    }
    // 打印沙漏下半部分
    for (int i = 3; i <= height; i += 2) {
        for (int j = 0; j < (height - i) / 2; j++) {
            cout << ' ';  // 打印空格
        }
        for (int j = 0; j < i; j++) {
            cout << ch;  // 打印符号
        }
        cout << endl;
        cnt += i;
    }
    // 输出剩余符号数
    cout << n - cnt << endl;
    return 0;
}

Python3 代码

# Python3 代码示例
N, symbol = map(str, input().split())
N = int(N)
height = 1
while height * (height + 1) <= N:
    height += 2
height -= 2
for i in range(height, 0, -2):
    print(' ' * ((height - i) // 2) + symbol * i)
for i in range(3, height + 1, 2):
    print(' ' * ((height - i) // 2) + symbol * i)
print(N - height * (height + 1) // 2)

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

// C++ 代码示例
#include <iostream>
using namespace std;

int main() {
    int n, cnt = 0;
    char ch;
    cin >> n >> ch;
    // 计算沙漏最大高度
    int height = 1;
    while (height * (height + 1) <= n) {
        height += 2;
    }
    height -= 2;
    // 打印沙漏上半部分
    for (int i = height; i >= 1; i -= 2) {
        for (int j = 0; j < (height - i) / 2; j++) {
            cout << ' ';  // 打印空格
        }
        for (int j = 0; j < i; j++) {
            cout << ch;  // 打印符号
        }
        cout << endl;
        cnt += i;
    }
    // 打印沙漏下半部分
    for (int i = 3; i <= height; i += 2) {
        for (int j = 0; j < (height - i) / 2; j++) {
            cout << ' ';  // 打印空格
        }
        for (int j = 0; j < i; j++) {
            cout << ch;  // 打印符号
        }
        cout << endl;
        cnt += i;
    }
    // 输出剩余符号数
    cout << n - cnt << endl;
    return 0;
}

Python3 代码

# Python3 代码示例
N, symbol = map(str, input().split())
N = int(N)
height = 1
while height * (height + 1) <= N:
    height += 2
height -= 2
for i in range(height, 0, -2):
    print(' ' * ((height - i) // 2) + symbol * i)
for i in range(3, height + 1, 2):
    print(' ' * ((height - i) // 2) + symbol * i)
print(N - height * (height + 1) // 2)