是否存在一个由1~9组成的9位数,每个数字只能出现一次,且这个9位数由高位到低位前i位能被i整除java实现
时间: 2024-02-16 20:05:04 浏览: 155
可以使用回溯算法来实现这个问题。具体步骤如下:
1. 定义一个长度为9的布尔数组used来记录数字是否已经被使用过;
2. 从高位到低位枚举每一个数字,判断当前数字是否已经被使用过,如果已经被使用过则跳过,否则尝试将当前数字放到当前位置上;
3. 判断当前数字是否能被当前位置加1整除,如果不能则回溯到上一步;
4. 如果当前位置是最后一位,且满足前i位能被i整除的要求,则找到了一个符合条件的9位数;
5. 如果当前位置不是最后一位,则递归到下一位继续尝试放置数字;
6. 在回溯时需要将当前位置的数字标记为未使用过。
下面是一个Java实现的示例代码:
```java
public class NineDigits {
private boolean[] used = new boolean[9];
private int[] digits = new int[9];
public void find(int pos) {
if (pos == 9) {
// 判断前i位能否被i整除
for (int i = 1; i <= 9; i++) {
if (Integer.parseInt(toString().substring(0, i)) % i != 0) {
return;
}
}
// 找到了一个符合条件的9位数
System.out.println(toString());
return;
}
for (int i = 1; i <= 9; i++) {
if (!used[i - 1]) {
digits[pos] = i;
used[i - 1] = true;
// 判断当前数字是否能被当前位置加1整除
if ((pos + 1) % i == 0) {
find(pos + 1);
}
used[i - 1] = false;
}
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int d : digits) {
sb.append(d);
}
return sb.toString();
}
public static void main(String[] args) {
NineDigits nineDigits = new NineDigits();
nineDigits.find(0);
}
}
```
该程序会输出所有符合条件的9位数。注意,由于题目要求从高位到低位前i位能被i整除,因此输出的数字是从高位到低位依次满足这个条件的。
阅读全文