赵天泽

本来是在数据结构一书中看到了一种高效率求高次幂的算法，便想来这找找有没有类似的算法题，结果找到了这个题，让我思考了一整天。
  
  ```c
int mi(int x, int n)
{
	if (n > 1)
	{
		if (n % 2 == 0)
			return mi(x, n / 2) * mi(x, n / 2);
		else
			return mi(x, (n - 1) / 2) * mi(x, (n - 1) / 2) * x;
	}
	else if (n == 1)
		return x;
	else if (n == 0)
		return 1;
	else
		return 0;
}
```
这是一个高效求x的n次方的值的函数，因为其不断对分，所以时间复杂度为O(logN)，不用担心在求高次方时出现时间超限（其实尝试这个函数才是我做这个题的本意，没想到反而这里思考的时间最少）

接下来便是将数值中最大的2的n次方找出来
```c
	for (i = 0; i < 100; i++)
		if (n < mi(2, i+1) && n>=mi(2, i)）//查找最大的2的n次方
			a = i;//将指数保存
```
然后接下来要利用递归实现两大步：
1.将去除这最大的2的n次方后的数进行递归
2.若最大的2的n次方的这个n大于2，要对其进行递归

我思考的时间最多的便是这第2步，因为我对递归还不太熟练，走上了岔路，总想着将n递归后再变成字符串，再将其作为返回值返回到上一层函数，最终自然是花了很多时间，也没有想明白该怎么做。好在最后还是顿悟，既然是字符串，只要调整一下顺序，直接输出不就好了。
```c
printf("2");
	if (a > 2)
	{
		printf("(");
		fen(a);//若指数大于2，将其递归
		printf(")");
	}
	else if(a!=1)//因为只能有2和0，所以指数为1时不能输出
		printf("(%d)", a);//输出括号和指数
	
	if (n - mi(2, a) != 0)//检查是否有剩余部分，有的话再输出一个加号，并将剩余部分递归
	{
		printf("+");
		fen(n - mi(2, a));
	}
```
最后放出来全部的代码：
```c
#include<stdio.h>
int mi(int x, int n)
{
	if (n > 1)
	{
		if (n % 2 == 0)
			return mi(x, n / 2) * mi(x, n / 2);
		else
			return mi(x, (n - 1) / 2) * mi(x, (n - 1) / 2) * x;
	}
	else if (n == 1)
		return x;
	else if (n == 0)
		return 1;
	else
		return 0;
}
void fen(int n)
{
	int i = 0;
	int a;
	for (i = 0; i < 100; i++)
		if (n < mi(2, i+1) && n>=mi(2, i))
		{
			a = i;
		}
	printf("2");
	if (a > 2)
	{
		printf("(");
		fen(a);
		printf(")");
	}
	else if(a!=1)
		printf("(%d)", a);
	
	if (n - mi(2, a) != 0)
	{
		printf("+");
		fen(n - mi(2, a));
	}
}
int main()
{
	int n;
	scanf_s("%d", &n);
	fen(n);
	return 0;
}
```

0.0分

3 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

赵天泽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

不需要数组和指针的做法！！！

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

蓝桥杯算法训练VIP-幂方分解-题解（C语言）

评论区

精彩推荐

简单的a+b （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【绝对值排序】（C++代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

字符串的输入输出处理（C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

赵天泽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

不需要数组和指针的做法！！！

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

蓝桥杯算法训练VIP-幂方分解-题解（C语言）

评论区

精彩推荐

简单的a+b （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【绝对值排序】 （C++代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

字符串的输入输出处理 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

【绝对值排序】（C++代码）

字符串的输入输出处理（C语言代码）