快速幂 java 扩底 降幂
时间: 2023-05-18 13:03:34 浏览: 32
可以使用以下代码实现快速幂:
public static long power(long x, long n) {
if (n == 0) {
return 1;
}
long half = power(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
其中,x 是底数,n 是指数。这个算法的时间复杂度是 O(log n)。
至于“扩底”和“降幂”,我不太清楚您具体指的是什么,如果您能提供更多的信息,我会尽力回答。
相关问题
C语言完成对链表的降幂输出
假设链表节点的数据类型为int,可以按照以下步骤完成链表的降幂输出:
1. 定义一个指针p指向链表头节点。
2. 定义一个数组arr,用于存储链表节点的值。
3. 遍历链表,将节点的值依次存入数组arr中。
4. 对数组arr进行降序排序。
5. 遍历数组arr,将每个元素输出。
下面是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
void insert(Node **head, int data) {
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->next = *head;
*head = new_node;
}
void print_list(Node *head) {
Node *p = head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
void print_list_desc(Node *head) {
Node *p = head;
int count = 0;
while (p != NULL) {
count++;
p = p->next;
}
int arr[count];
p = head;
int i = 0;
while (p != NULL) {
arr[i] = p->data;
p = p->next;
i++;
}
for (int j = 0; j < count; j++) {
for (int k = j + 1; k < count; k++) {
if (arr[j] < arr[k]) {
int temp = arr[j];
arr[j] = arr[k];
arr[k] = temp;
}
}
printf("%d ", arr[j]);
}
}
int main() {
Node *head = NULL;
insert(&head, 5);
insert(&head, 2);
insert(&head, 3);
insert(&head, 1);
insert(&head, 4);
printf("原始链表:");
print_list(head);
printf("\n降幂输出:");
print_list_desc(head);
printf("\n");
return 0;
}
```
输出结果为:
```
原始链表:4 1 3 2 5
降幂输出:5 4 3 2 1
```
C语言链表完成多项式的降幂输出
假设多项式的项的结构体如下所示:
```c
typedef struct Term {
int coef; // 系数
int expn; // 指数
struct Term *next;
} Term;
```
则可以按照以下步骤完成多项式的降幂输出:
1. 定义一个指针p指向多项式头节点。
2. 定义一个数组arr,用于存储多项式的每一项。
3. 遍历多项式,将每一项依次存入数组arr中。
4. 对数组arr进行降序排序。
5. 遍历数组arr,将每个元素输出。
下面是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Term {
int coef; // 系数
int expn; // 指数
struct Term *next;
} Term;
void insert(Term **head, int coef, int expn) {
Term *new_node = (Term*)malloc(sizeof(Term));
new_node->coef = coef;
new_node->expn = expn;
new_node->next = *head;
*head = new_node;
}
void print_poly(Term *head) {
Term *p = head;
while (p != NULL) {
if (p->coef > 0) {
printf("+");
}
printf("%dx^%d", p->coef, p->expn);
p = p->next;
}
}
void print_poly_desc(Term *head) {
Term *p = head;
int count = 0;
while (p != NULL) {
count++;
p = p->next;
}
Term *arr[count];
p = head;
int i = 0;
while (p != NULL) {
arr[i] = p;
p = p->next;
i++;
}
for (int j = 0; j < count; j++) {
for (int k = j + 1; k < count; k++) {
if (arr[j]->expn < arr[k]->expn) {
Term *temp = arr[j];
arr[j] = arr[k];
arr[k] = temp;
}
}
if (arr[j]->coef > 0) {
printf("+");
}
printf("%dx^%d", arr[j]->coef, arr[j]->expn);
}
}
int main() {
Term *poly = NULL;
insert(&poly, 3, 2);
insert(&poly, 4, 3);
insert(&poly, 5, 1);
insert(&poly, 2, 4);
printf("原始多项式:");
print_poly(poly);
printf("\n降幂输出:");
print_poly_desc(poly);
printf("\n");
return 0;
}
```
输出结果为:
```
原始多项式:+2x^4+5x^1+4x^3+3x^2
降幂输出:+2x^4+4x^3+3x^2+5x^1
```