- 一、将三个整数按升序重新排列
- 二、求一元多项式的值
- 三、求k阶裴波那契序列的第m项的值
- 四、计算i!×2^i的值
- 五、由一维数组构建一个序列
- 六、构建一个值为x的结点
- 七、构建长度为2且两个结点的值依次为x和y的链表
- 八、构建长度为2的升序链表
一、将三个整数按升序重新排列
【题目】试写一算法，如果三个整数a，b和c的值不是依次非递增的，则通过交换，令其为非递增。
要求实现下列函数：
void Descend(int &a, int &b, int &c);
/* 通过交换，令 a >= b >= c */
#include "allinclude.h" //DO NOT edit this line
void Descend(int &a, int &b, int &c) { // 通过交换，令 a >= b >= c
// Add your code here
int t,max;
//先找出abc中的最大值
max = (((a>=b)?a:b)>=c)?((a>=b)?a:b):c;
if(max==a){
if(b<c){
t = b;
b = c;
c = t;
}
}
if(max==b){
if(a>=c){
t = a;
a = b;
b = t;
}else{
t = b;
b = c;
c = a;
a = t;
}
}
if(max==c){
if(b>=a){
t = a;
a = c;
c = t;
}else{
t = c;
c = b;
b = a;
a = t;
}
}
}
二、求一元多项式的值
【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。
要求实现下列函数：
float Polynomial(int n, int a[], float x0);
/* 求一元多项式的值P(x0)。 /
/ 数组a的元素a[i]为i次项的系数，i=0,1,...,n */
#include "allinclude.h" //DO NOT edit this line
float Polynomial(int n, int a[], float x0){
// Add your code here
float p = 0;
float t = x0;
if(n)
for(int i = 1;i<=n;i++){
p += a[i]*t;
t = t*x0;
}
return a[0]+p;
}
三、求k阶裴波那契序列的第m项的值
【题目】已知k阶裴波那契序列的定义为f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1; f(n)=f(n-1)+f(n-2)+...+f(n-k), n=k,k+1,... 试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。
要求实现下列函数：
Status Fibonacci(int k, int m, int &f);
/* 如果能求得k阶斐波那契序列的第m项的值f，则返回OK；/
/ 否则（比如，参数k和m不合理）返回ERROR */
#include "allinclude.h" //DO NOT edit this line
Status Fibonacci(int k, int m, int &f) {
// Add your code here
int a[100],sum;
//异常处理
if(k < 2||m < 0) return ERROR;
if(m < k-1) f = 0;
else{
if(m == k-1) f = 1;
else{
//前k-1项都为0
for(int i = 0;i < k-1;i++) a[i] = 0;
//第k-1项为1
a[k-1] = 1;
//前k项和为下一项
for(int j = k;j <= m;j++){
sum = 0;
for(int i = j-k;i < j;i++) sum += a[i];
a[j] = sum;
}
f = a[m];
}
}
return OK;
}
四、计算i!×2^i的值
【题目】试编写算法，计算i!×2^i的值并存入数组a[0..n-1]的第i-1个分量中 (i=1,2,…,n)。假设计算机中允许的整数最大值为MAXINT，则当对某个k(1≤k≤n)使k!×2^k>MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。
要求实现下列函数：
Status Series(int a[], int n);
/* 求i!*2^i序列的值并依次存入长度为n的数组a；若所有 /
/ 值均不超过MAXINT，则返回OK，否则返回EOVERFLOW */
#include "allinclude.h" //DO NOT edit this line
Status Series(int a[], int n) {
// Add your code here
if(n <= 0) return ERROR;
int l,m;
l = 1;
m = 2;
for(int i = 1;i <= n;i++){
l *= i;
a[i-1] = l*m;
m *= 2;
if(l > MAXINT||m > MAXINT||l*m > MAXINT) return EOVERFLOW;
}
return OK;
}
五、由一维数组构建一个序列
【题目】试写一算法，由长度为n的一维数组a构建一个序列S。
要求实现下列函数：
Status CreateSequence(Sequence &S, int n, ElemType a);
/ 由长度为n的一维数组a构建一个序列S，并返回OK。 /
/ 若构建失败，则返回ERROR */
序列的定义为：
typedef struct {
ElemType *elem;
int length;
} Sequence;
#include "allinclude.h" //DO NOT edit this line
Status CreateSequence(Sequence &S, int n, ElemType *a) {
S.elem = a;
if(NULL == S.elem||n <= 0) return ERROR;
S.length = n;
return OK;
}
六、构建一个值为x的结点
【题目】链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
试写一函数，构建一个值为x的结点。
要求实现下列函数：
LinkList MakeNode(ElemType x);
/* 构建一个值为x的结点，并返回其指针。 /
/ 若构建失败，则返回NULL。 */
#include "allinclude.h" //DO NOT edit this line
LinkList MakeNode(ElemType x) {
// Add your code here
LinkList p;
p = (LinkList)malloc(sizeof(LNode));//sizeof里面最好不要写LinkList
If(! p) return NULL;
p->data = x;
return p;
}
七、构建长度为2且两个结点的值依次为x和y的链表
【题目】链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
试写一函数，构建长度为2且两个结点的值依次为x和y的链表。
要求实现下列函数：
LinkList CreateLinkList(ElemType x, ElemType y);
/* 构建其两个结点的值依次为x和y的链表。/
/ 若构建失败，则返回NULL。 */
#include "allinclude.h" //DO NOT edit this line
LinkList CreateLinkList(ElemType x, ElemType y) {
// Add your code here
LNode *p1;
LNode *p2;
p1 = (LNode *)malloc(sizeof(LNode));
p2 = (LNode *)malloc(sizeof(LNode));
if(!p1||!p2) return NULL;
p1->data = x;
p1->next = p2;
p2->data = y;
p2->next = NULL;
return p1;
}
八、构建长度为2的升序链表
【题目】链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
试写一函数，构建长度为2的升序链表，两个结点的值
分别为x和y，但应小的在前，大的在后。
要求实现下列函数：
LinkList CreateOrdLList(ElemType x, ElemType y);
/* 构建长度为2的升序链表。 /
/ 若构建失败，则返回NULL。 */
#include "allinclude.h" //DO NOT edit this line
LinkList CreateOrdLList(ElemType x, ElemType y) {
// Add your code here
LNode *p1,*p2;
p1 = (LNode *)malloc(sizeof(LNode));
p2 = (LNode *)malloc(sizeof(LNode));
If(!p1||!p2) return NULL;
ElemType t;
if(x > y){
t = x;
x = y;
y = t;
}
p1->data = x;
p1->next = p2;
p2->data = y;
p2->next = NULL;
return p1;
}