（3）是否存在一个由1~9组成的9位数，每个数字只能出现一次，且这个9位数由高位到低位前i位能被i整除？ 算法思路及c代码

可以使用回溯算法来解决这个问题，依次枚举每个位置填入的数字，检查是否符合要求。具体实现如下：

#include <stdio.h>
#include <stdbool.h>

bool used[10]; // 记录每个数字是否被使用过
int num[10]; // 记录当前填入的数字

// 检查前i位是否符合要求
bool check(int i) {
    int n = 0;
    for (int j = 1; j <= i; ++j) {
        n = n * 10 + num[j];
        if (n % j != 0) {
            return false;
        }
    }
    return true;
}

// 回溯函数
bool backtrack(int i) {
    if (i > 9) {
        return true; // 已经填完了所有的数字
    }
    for (int j = 1; j <= 9; ++j) {
        if (!used[j]) { // 如果数字j还没有被使用过
            used[j] = true; // 标记数字j已经被使用过
            num[i] = j; // 填入数字j
            if (check(i)) { // 检查前i位是否符合要求
                if (backtrack(i + 1)) { // 递归填下一个位置
                    return true; // 如果填完所有位置能够满足要求，返回true
                }
            }
            used[j] = false; // 回溯，取消数字j的使用状态
        }
    }
    return false;
}

int main() {
    if (backtrack(1)) {
        for (int i = 1; i <= 9; ++i) {
            printf("%d", num[i]);
        }
    } else {
        printf("No solution!");
    }
    return 0;
}

该算法的时间复杂度为 $O(9!)$，因为一共有 $9!$ 种不同的数字排列方式。但是实际运行时间可能比较短，因为该算法采用了剪枝，能够尽早排除一些不符合要求的数字排列方式。