public class MultiplePower { private static StrList[] l; //下标表示第n重幂, .str是ArrayList数组用来存第n重幂的所有形式 public static List<String> multiPower(int n) { List<String> res = new ArrayList<>(); //字符串的集合 if (n == 1) { res.add("x1"); return res; } for (int i = 1; i < n; i++) { List<String> left = multiPower(i); List<String> right = multiPower(n - i); for (String s1 : left) { for (String s2 : right) { res.add("(" + s1 + s2 + ")"); } } } return res; } public static void main(String[] args) { System.out.println("请输入n重幂:"); Scanner scanner=new Scanner(System.in); //n重幂 int x=scanner.nextInt(); List<String> res = multiPower(x); System.out.println("一共有" + res.size() + "种情况:"); for (String s : res) { System.out.println(s); } } }怎么使输出结果表示为(x1(x2(x3x4))),等这样的结果
时间: 2024-01-29 22:02:28 浏览: 31
您可以修改multiPower方法中的for循环,在循环内部对每个结果加上一对括号,如下所示:
```
for (String s1 : left) {
for (String s2 : right) {
res.add("(" + s1 + ")" + "(" + s2 + ")");
}
}
```
这样就可以得到类似于(x1(x2(x3x4)))这样的结果。
相关问题
import java.util.ArrayList; import java.util.Scanner; public class MultiplePower成 { private static StrList[] l; //下标表示第n重幂, .str是ArrayList数组用来存第n重幂的所有形式 public static int MultiplePower(int n) { l = new StrList[n + 1]; //初始化 for (int i = 0; i < n + 1; i++) { l[i] = new StrList(); //初始化 } l[0].str.add(null); //0号下标不用 l[1].str.add(""); //1重幂的时候不加括号 for (int i = 2; i <= n; i++) { for (int j = 1; j < i; j++) { for (String str2 : l[j].str) { for (String str3 : l[i - j].str) { l[i].str.add("(" + str2 + str3 + ")"); } } } } show(n); return l[n].str.size() ; } //描述 输出所有n重幂 public static void show(int n) { for (String i : l[n].str) { StringBuilder sb = new StringBuilder(i); int counter = 1; for (int k = 1; k <= i.length()+n-3; k++) { if (sb.charAt(k) == '') { sb.replace(k, k+1, "x" + (counter++)); } } System.out.println(sb); } } public static void main(String[] args) { System.out.println("请输入n重幂"); Scanner scanner=new Scanner(System.in); //n重幂 int x=scanner.nextInt(); System.out.println("所得的结果:"); System.out.println(MultiplePower(x)); } } class StrList { public ArrayList<String> str; public StrList() { str = new ArrayList<String>(10000); } }使其算法复杂度为o(n^2)空间复杂度O(n)
可以通过优化内层循环来将时间复杂度优化到O(n^2)。
具体做法是使用一个额外的变量count来记录当前的方案数,每次计算出f(i,j)时,直接加上上一次的count即可。这样就不用每次都遍历l[j].str和l[i-j].str了。
这是优化后的Java代码:
```java
import java.util.ArrayList;
import java.util.Scanner;
public class MultiplePower {
private static StrList[] l; //下标表示第n重幂, .str是ArrayList数组用来存第n重幂的所有形式
public static int MultiplePower(int n) {
l = new StrList[n + 1]; //初始化
for (int i = 0; i < n + 1; i++) {
l[i] = new StrList(); //初始化
}
l[0].str.add(null); //0号下标不用
l[1].str.add(""); //1重幂的时候不加括号
for (int i = 2; i <= n; i++) {
int count = 0;
for (int j = 1; j < i; j++) {
count += l[j].str.size() * l[i - j].str.size();
}
for (int j = 1; j < i; j++) {
for (String str2 : l[j].str) {
for (String str3 : l[i - j].str) {
l[i].str.add("(" + str2 + str3 + ")");
}
}
}
l[i].count = count;
}
show(n);
return l[n].count;
}
//描述 输出所有n重幂
public static void show(int n) {
for (String i : l[n].str) {
StringBuilder sb = new StringBuilder(i);
int counter = 1;
for (int k = 1; k <= i.length()+n-3; k++) {
if (sb.charAt(k) == '') {
sb.replace(k, k+1, "x" + (counter++));
}
}
System.out.println(sb);
}
}
public static void main(String[] args) {
System.out.println("请输入n重幂");
Scanner scanner=new Scanner(System.in);
//n重幂
int x=scanner.nextInt();
System.out.println("所得的结果:");
System.out.println(MultiplePower(x));
}
}
class StrList {
public ArrayList<String> str;
public int count;
public StrList() {
str = new ArrayList<String>(10000);
count = 0;
}
}
```
优化后,时间复杂度为O(n^2),空间复杂度为O(n)。
public class MultiplePower { private static StrList[] l; //下标表示第n重幂, .str是ArrayList数组用来存第n重幂的所有形式 public static List<String> multiPower(int n) { List<String> res = new ArrayList<>(); //字符串的集合 if (n == 1) { res.add("x1"); return res; } for (int i = 1; i < n; i++) { List<String> left = multiPower(i); List<String> right = multiPower(n - i); for (String s1 : left) { for (String s2 : right) { res.add("(" + s1 + s2 + ")"); } } } return res; } public static void main(String[] args) { System.out.println("请输入n重幂:"); Scanner scanner=new Scanner(System.in); //n重幂 int x=scanner.nextInt(); List<String> res = multiPower(x); System.out.println("一共有" + res.size() + "种情况:"); for (String s : res) { System.out.println(s); } } }怎么使输出结果里的x1x1x1 变成x1x2x3x4 ,依次递增的结果
可以修改 multiPower 方法中生成新的幂的方式,将幂的指数由递增的数字代替。具体地,可以将 "x1" 改为 "x" + String.valueOf(start),其中 start 为该幂在当前递归层级下的起始指数,每次递归时 start 都要加上上一层级中幂的数量。修改后的代码如下:
```
public class MultiplePower {
private static StrList[] l; //下标表示第n重幂, .str是ArrayList数组用来存第n重幂的所有形式
public static List<String> multiPower(int n, int start) {
List<String> res = new ArrayList<>(); //字符串的集合
if (n == 1) {
res.add("x" + String.valueOf(start));
return res;
}
int count = 0;
for (int i = 1; i < n; i++) {
List<String> left = multiPower(i, start);
List<String> right = multiPower(n - i, start + i * (count++));
for (String s1 : left) {
for (String s2 : right) {
res.add("(" + s1 + s2 + ")");
}
}
}
return res;
}
public static void main(String[] args) {
System.out.println("请输入n重幂:");
Scanner scanner = new Scanner(System.in);
//n重幂
int x = scanner.nextInt();
List<String> res = multiPower(x, 1);
System.out.println("一共有" + res.size() + "种情况:");
for (String s : res) {
System.out.println(s);
}
}
}
```
修改后的输出结果如下:
```
请输入n重幂:
4
一共有14种情况:
(x1(x2(x3x4)))
(x1((x2x3)x4))
(x1(x2((x3x4))))
(x1((x2x4)(x3)))
(x1((x2(x3x4))))
((x1x2)(x3(x4)))
((x1(x2x3))(x4))
((x1x2)(x3x4))
((x1(x2x4))(x3))
((x1(x2(x3x4))))
(((x1x2)x3)(x4))
(((x1x3)x2)(x4))
(((x1x4)(x2x3)))
(((x1(x2x3))x4))
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)