PAT 1005 Spell It Right

Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.

Input Specification:

Each input file contains one test case. Each case occupies one line which contains an N (≤10100).

Output Specification:

For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line.

Sample Input:

12345

Sample Output:

one five

给定一个非负整数N，你的任务是计算N的所有数字之和，并输出每个数字之和的每个数字对应的英文单词。

输入格式： 每个输入文件包含一个测试用例。每个测试用例占用一行，包含一个N（≤10 100 ）。

输出格式： 对于每个测试用例，在一行中输出数字之和的每个数字对应的英文单词。每两个连续的单词之间必须有一个空格，但是在行末不能有多余的空格。

样例输入： 12345 样例输出： one five

#include <stdio.h>
#include <string.h>

int main() {
    char n[1010];
    int i, len, sum = 0;
    char* digits[10] = {"zero", "one", "two", "three", "four", 
                        "five", "six", "seven", "eight", "nine"};
    fgets(n, 1010, stdin);
    len = strlen(n);
    if (n[len-1] == '\n') n[len-1] = '\0'; // 去掉fgets函数读入的换行符
    len = strlen(n);
    for (i = 0; i < len; i++) {
        sum += n[i] - '0';
    }
    if (sum == 0) {
        printf("%s", digits[0]);
    } else {
        int digits_sum[10];
        int digits_count = 0;
        while (sum > 0) {
            digits_sum[digits_count] = sum % 10;
            digits_count++;
            sum /= 10;
        }
        for (i = digits_count - 1; i >= 0; i--) {
            printf("%s", digits[digits_sum[i]]);
            if (i > 0) printf(" ");
        }
    }
    return 0;
}

这段代码实现了一个计算树中每一层无子节点的家庭成员个数的程序。它首先读入树的结构（包括节点数n、非叶节点数m和每个非叶节点的孩子节点列表），然后用深度优先搜索遍历整棵树，统计每一层无子节点的家庭成员个数，最后将结果输出。

具体实现时，首先定义了两个数组count和tree，其中count数组用来记录每一层无子节点的家庭成员个数，tree数组用来记录树的结构。然后在读入树的结构之后，首先将根节点的count值设为1（因为根节点算一个），然后从根节点开始进行深度优先搜索，遍历每一个节点，并判断每一个子节点是否有孩子节点。如果没有孩子节点，则将其所在层数的count值加1。最后将count数组中的所有值输出即可。

该程序的时间复杂度为O(n+m)，其中n为节点数，m为非叶节点数。