首页 > 分享 > 算法设计题解析

算法设计题解析

花匠小妙招
2024-12-18 15:43

绪论基本术语算法设计题 1.16试写一个算法，自大至小依次输出顺序读入的三个整数X,Y和Z的值。1.17已知k阶斐波拉切序列的定义为1.18假设有A,B,C,D,E五个高等院校对抗田径赛，各院校的单项成绩均以存入计算机，并构成一张表，表中每一行的形式为1.19试编写算法，计算!*2i(i=0,1,…,n-1)的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT,则当n>arrsize或对某个k(0<=k<=n-1)使k!*2k>MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。1.20试编写算法求一元多项式pn(x)=∑ni=0aixi的值pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题输入为ai(i=0,1,…,n),x0和n,输出为pn(x0).

绪论

基本术语

数据：是客观事物的符号表示
数据元素：数据的基本单位，一个数据元素可以有多个数据项
数据对象：是性质相同的数据元素的集合，是数据的一个子集
数据结构：是相互之间存在的一种或多种特定关系的数据元素的集合;
数据元素通常有四种：
+ 集合
+ 线性结构
+ 树形结构
+ 图状结构或网状结构

存储结构：顺序存储结构和链式存储结构

该书表达方式，c语法要求见
c语法归纳

算法设计题

1.16试写一个算法，自大至小依次输出顺序读入的三个整数X,Y和Z的值。

主要通过排序的方法解决的。

void Descending(){ //注意，要保证最少的移动和判断 //最终结果是a > b > c int a,b,c,max_num; scanf("%d %d %d",&a,&b,&c); //这里用了排序方法，将a,b,c从大到小排序 int temp = 0; if(a < b){ //temp拿到a的值，temp值为现在b的值 temp = a; a = b; b = temp; } if(b < c){ //先把c的值确定 temp = c; c = b; if(a > temp){ //temp值是原来c的值，这里判断c是最大值还是第二大值 b = temp; } else{ b = a; a = temp; } } printf("%d %d %d",a,b,c); }

1234567891011121314151617181920212223242526

刚开始感觉好复杂啊。

1.17已知k阶斐波拉切序列的定义为

f0 = 0 , f1 = 0 ,…, fk-2 = 0 , fk-1 = 1;
fn = fn-1 + fn-2 +…+ fn-k , n = k , k+1 ,…
试编写求k阶斐波拉切数列的第m项值的函数算法，k和m均以值调用形式在函数参数表中出现
递归写法

int Fab(int k, int m) { //k 是k阶的意思 //m 是第m项的值 if (m < k - 1) { return 0; } else if (m == k - 1) { return 1; } else { int count = 0; for (int i = m - 1; i >= m - k; i--) { count += Fab(k, i); } return count; } }

123456789101112131415161718192021

循环写法
目前只写出二阶

int fabdiao(int k,int m) { //k 是k阶的意思 //m 是第m项的值 int a = 0; int b = 1; int temp = 0; for(int i = 0;i < m;i++) { temp = b; b = a + b; a = temp; } return a; }123456789101112131415 1.18假设有A,B,C,D,E五个高等院校对抗田径赛，各院校的单项成绩均以存入计算机，并构成一张表，表中每一行的形式为

|项目名|性别|校名|成绩|得分|
|-|-|-|-|-|
编写一个算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。

#include <stdio.h> #include <stdlib.h> const int REPORT_SIZE = 10; const int EVENT_SIZE = 3; typedef enum {A,B,C,D,E}SchoolName; typedef enum{FEMALE,MALE}SexType; typedef struct { char event[EVENT_SIZE]; //一个项目由3个字符串组成 SexType sex; //性别 SchoolName school; //学校 int score; //成绩 }Component; typedef struct { int malessum;//男团总分 int femalesum;//女团总分 int totalsum;//团体总分 }Sum; Component report[REPORT_SIZE]; //代表记录条数 Sum result[5]; //代表5个学校 //男总分，女总分，团总分 void main() { for (int i = 0; i < REPORT_SIZE; i++) { switch (report[i].sex) { case FEMALE: result[report[i].school].femalesum = report[i].score; break; case MALE: result[report[i].school].malessum = report[i].score; break; default: break; } result[report[i].school].totalsum = report[i].score; } for (int i = 0; i < 5; i++) { printf("%d %d %d",result[i].femalesum, result[i].malessum,result[i].totalsum); } return; }

123456789101112131415161718192021222324252627282930313233343536373839404142 1.19试编写算法，计算!*2i(i=0,1,…,n-1)的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT,则当n>arrsize或对某个k(0<=k<=n-1)使k!*2k>MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。

#include <stdlib.h> #include <stdio.h> #define MAXINT INT_MAX #define TRUE 1 #define FALSE 0 typedef int Status; Status Function(int n,int* a); Status numToStr(int num, int* a); const int ARISE = 10; int a[ARISE] = {}; int main() { printf("%dn", INT_MAX); int sta = numToStr(655353, a); printf("%d ", sta); for (int i = 0; i < 11; i++) { if (!Function(i, a)) { printf("越界了！！！"); } for (int i = 0; i < ARISE; i++) { printf("%d", a[i]); a[i] = 0;//顺便清空数组 } printf("n"); } system("pause"); return 0; } //循环写法 Status Function(int n,int* a) { //n循环数，a为数组 //计算i的阶乘和乘以2的i次幂，i=0,...n-1 //分析，每次增加2i 1*1 1*2 1*2*2*2 1*2*3*2*2*2 long long int result = 1; for (int i = 1; i <= n; i++) { result = result * 2 * i; if (result > MAXINT) { return FALSE; } } //将数字转换到数组中 if (!numToStr(result, a)) { return FALSE; } return TRUE; } Status numToStr(int num,int* a){ int div = num; // 得到商 int floor = 0;//得到余数 int i = ARISE - 1;//记录位数，从后向前移动 while (div / 10) { floor = div % 10; div = div/10; a[i--] = floor; //得到每次的余数，位数向前移动一位 if (i < 0) //当i = 0时，不能继续循环，数组不够存了，0号为本应该给个位数的 { return FALSE; } } a[i] = div;//最后一次< 10的商为个位数 return TRUE; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 1.20试编写算法求一元多项式pn(x)=∑ni=0aixi的值pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题输入为ai(i=0,1,…,n),x0和n,输出为pn(x0).