用c语言回溯法写一个由1-9组成的九位数,每个数字只出现了一次,且这个九位数由高到低位前i位能被i整除
时间: 2023-06-10 11:08:20 浏览: 93
以下是一个基于回溯法的C语言程序,实现了由1-9组成的九位数,每个数字只出现了一次,且这个九位数由高到低位前i位能被i整除的功能。
```c
#include <stdio.h>
#define N 9
int visited[N + 1] = {0};
int number[N] = {0};
int check(int i) {
int sum = 0;
for (int j = i; j >= 1; j--) {
sum = sum * 10 + number[j - 1];
if (sum % j != 0)
return 0;
}
return 1;
}
void dfs(int i) {
if (i == N) {
for (int j = 0; j < N; j++)
printf("%d", number[j]);
printf("\n");
return;
}
for (int j = 1; j <= N; j++) {
if (visited[j] == 0) {
visited[j] = 1;
number[i] = j;
if (check(i + 1))
dfs(i + 1);
visited[j] = 0;
}
}
}
int main() {
dfs(0);
return 0;
}
```
在这个程序中,我们使用了一个visited数组来记录数字是否已经被访问过,使用一个number数组来存储当前已经确定的数字。然后使用一个check函数来判断当前的数字是否符合条件,如果符合条件,则进行下一步递归。
最后,在主函数中调用dfs函数,从第0位开始搜索所有可能的组合。程序输出的结果就是所有符合条件的九位数。