是否存在一个由1~9组成的9位数,每个数字只能出现一次,且这个9位数由高位到低位前i位能被i整除java实现
时间: 2024-02-17 19:01:43 浏览: 82
C语言编写两个一百位数相加的程序
5星 · 资源好评率100%
是的,存在这样一个由1~9组成的9位数,每个数字只能出现一次,且这个9位数由高位到低位前i位能被i整除的数。这个数是"381654729"。
在Java中,可以使用回溯算法实现找到这个数。具体实现方式如下:
```java
public class Main {
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
boolean[] used = new boolean[9];
StringBuilder sb = new StringBuilder();
dfs(nums, used, sb);
}
private static void dfs(int[] nums, boolean[] used, StringBuilder sb) {
if (sb.length() == 9) {
if (check(sb.toString())) {
System.out.println(sb.toString());
}
return;
}
for (int i = 0; i < 9; i++) {
if (!used[i]) {
sb.append(nums[i]);
used[i] = true;
dfs(nums, used, sb);
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
}
private static boolean check(String s) {
for (int i = 1; i <= 9; i++) {
int num = Integer.parseInt(s.substring(0, i));
if (num % i != 0) {
return false;
}
}
return true;
}
}
```
在程序中,首先定义了一个数组nums,存储了1~9这9个数字。然后定义了一个boolean类型的数组used,用来标记已经使用过的数字。接着定义了一个StringBuilder类型的变量sb,用来存储当前正在构造的数字。最后调用dfs函数进行搜索。
在dfs函数中,首先判断当前正在构造的数字长度是否为9,如果是,则进行判断该数字是否符合要求,如果是,则输出该数字。然后返回上一层递归。如果当前正在构造的数字长度不为9,则遍历nums数组,对于每个没有使用过的数字,将其添加到sb末尾,标记为已使用,然后递归进入下一层。递归返回时,将sb末尾的数字删除,将该数字标记为未使用。
最后,定义了一个check函数,用来判断当前正在构造的数字是否符合要求。在check函数中,遍历1~9这9个数字,对于每个数字i,取出数字串的前i位,将其转换成整数,然后判断是否能够被i整除。如果不能被整除,则该数字串不符合要求,返回false。如果能够被整除,继续遍历下一个数字。如果所有数字都能被整除,则返回true。
阅读全文